Degree Type

Creative Component

Semester of Graduation

Spring 2021

Department

Electrical and Computer Engineering

First Major Professor

Goce Trajcevski

Degree(s)

Master of Science (MS)

Major(s)

Computer Engineering

Abstract

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.

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.

Copyright Owner

Hashemi, Hooman

Creative Commons License

Creative Commons Attribution 4.0 International License
This work is licensed under a Creative Commons Attribution 4.0 International License.

File Format

PDF

Embargo Period (admin only)

11-30-2020

1

Share

COinS