Spatial and Graphical Data Processing: Spatial Crowdsourcing and Quasi-Clique Enumeration

Abstract

<p>In this report, data processing in two realms, spatial and graphical, has been studied. In the first chapter of this work, we explain spatial crowdsourcing and how it incorporates the context of physical location and enables assignments of workers to tasks not only based on matching skills but also on the (relative) whereabouts in time. Most of the works in this field have assumed a kind of steadiness of the dynamic of the essential parameters that were used to generate the worker and task pairs. In this work, we address the problem of reassignment of workers and tasks pair due to a set of the abnormal situation which prevents worker(s) to accomplish their assigned tasks. We provide two solutions for this problem and observe the performance of each approach in terms of run time and achieving the objective goals. The results showed a trade-off between the accuracy and run time of the proposed solutions.</p> <p>In the second chapter of this report, we have work on graph data processing--Mining Largest Maximal Quasi-cliques. Quasi-cliques are dense incomplete subgraphs of a graph that generalize the notion of cliques. Quasi-clique enumeration is a robust method way to find the dense substructure of a graph. Since the quasi-clique enumeration is a challenging problem, we consider the enumeration of top-k degree-based quasi-clique in a graph. This chapter proves that this problem is NP-hard, and we provide a heuristic approach to count them. This chapter's experimental results indicate that our algorithm accurately enumerates quasi-cliques even faster than the state-of-the-art methods and can scale to large graphs than currently available methods.</p>