Source-linked AI summary
Reliable Diversity-Based Spatial Crowdsourcing by Moving Workers
Peng Cheng, Xiang Lian, Zhao Chen, Rui Fu, Lei Chen, Jinsong Han, Jizhong Zhao
TL;DR
The paper addresses how to assign moving workers to time-constrained spatial tasks while ensuring reliable, spatially diverse, and temporally diverse answers. It formulates RDB-SC, develops approximation algorithms and a dynamic index because the problem is NP-hard, and reports efficient and effective performance on real and synthetic data.
Problem
RDB-SC addresses assigning moving workers to time-constrained tasks while maximizing completion reliability and spatial-temporal diversity, qualities not considered by earlier spatial-crowdsourcing work.
Method
The paper proposes greedy, sampling, and divide-and-conquer approximation algorithms plus a cost-model-based index for dynamically maintaining workers and tasks.
Results
Extensive experiments on both real and synthetic datasets confirm the efficiency and effectiveness of the proposed RDB-SC approaches.
Takeaways & Limitations
RDB-SC provides a framework for assigning moving workers to time-constrained tasks while pursuing reliable and diverse task answers.
Takeaways & Limitations
The paper leaves accuracy control for task answers as future work and notes that enumerating assignment strategies is infeasible because RDB-SC is NP-hard.
Abstract
from arXiv · showhide
With the rapid development of mobile devices and the crowdsourcig platforms, the spatial crowdsourcing has attracted much attention from the database community, specifically, spatial crowdsourcing refers to sending a location-based request to workers according to their positions. In this paper, we consider an important spatial crowdsourcing problem, namely reliable diversity-based spatial crowdsourcing (RDB-SC), in which spatial tasks (such as taking videos/photos of a landmark or firework shows, and checking whether or not parking spaces are available) are time-constrained, and workers are moving towards some directions. Our RDB-SC problem is to assign workers to spatial tasks such that the completion reliability and the spatial/temporal diversities of spatial tasks are maximized. We prove that the RDB-SC problem is NP-hard and intractable. Thus, we propose three effective approximation approaches, including greedy, sampling, and divide-and-conquer algorithms. In order to improve the efficiency, we also design an effective cost-model-based index, which can dynamically maintain moving workers and spatial tasks with low cost, and efficiently facilitate the retrieval of RDB-SC answers. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches over both real and synthetic data sets.
1. INTRODUCTION
The paper formulates reliable diversity-based spatial crowdsourcing for assigning moving workers to time-constrained tasks while maximizing answer reliability and spatial-temporal diversity. Because the problem is NP-hard, it develops approximation algorithms and an index for efficient dynamic assignment.
- Problem setting: Spatial crowdsourcing assigns nearby workers to location-based tasks that require physical movement, such as photographing landmarks.The paper motivates this setting with mobile sensing applications and a Statue of Liberty example.
- Motivation: Diverse worker directions and arrival times improve landmark reconstruction, virtual tours, and parking-space monitoring.Similar viewing angles can be uninformative, while different timestamps provide richer information for analysis and prediction.
- Research gap: Existing spatial-crowdsourcing work focused mainly on maximizing completed tasks rather than worker movement, task time constraints, or answer quality.The paper positions RDB-SC as addressing these constrained features and quality measures together.
- Problem formulation: RDB-SC assigns moving workers to time-constrained spatial tasks while maximizing reliability and spatial-temporal diversity.Reliability represents confidence that at least one assigned worker provides a high-quality answer.
- Evaluation: Extensive experiments on real and synthetic datasets evaluate the efficiency and effectiveness of the proposed approaches.The experiments are presented as evidence for the methods and the dynamic assignment system.
- Approach: The RDB-SC problem is NP-hard, so the paper proposes greedy, sampling, and divide-and-conquer approximation algorithms.The contributions also include a cost-model-based index for dynamically maintaining workers and time-constrained tasks.
2. PROBLEM DEFINITION
RDB-SC assigns dynamically moving workers to time-constrained spatial tasks while optimizing task reliability and expected spatial/temporal diversity. The formulation accounts for worker movement, confidence, possible completion worlds, and computational challenges that motivate approximation and indexing methods.
- Task and worker model: Time-constrained spatial tasks have fixed locations and valid periods, while workers move with registered directions and individual completion confidence.Workers and tasks may dynamically enter or leave the crowdsourcing system; workers may reject assignments that deviate substantially from their intended direction.
- Quality measures: Reliability is the probability that at least one assigned worker successfully completes a task.For worker confidence p_j, the probability that all assigned workers fail is multiplied across workers, so reliability is its complement.
- Quality measures: Spatial and temporal diversity measure whether task answers cover varied directions and arrival times rather than redundant viewpoints or timestamps.Spatial diversity uses angular separation, while temporal diversity uses entropy over intervals induced by worker arrival times.
- Optimization problem: RDB-SC maximizes the minimum task reliability and the summed expected spatial/temporal diversity subject to valid worker arrivals.Expected diversity is computed over possible worlds representing which assigned workers actually complete each task.
- Challenges and approach: The problem is difficult because assignment strategies and possible worlds are exponential, while moving workers and time-constrained tasks change dynamically.The paper proves NP-hardness and proposes greedy, sampling, and divide-and-conquer approximations, plus a grid index for dynamic updates and assignment retrieval.
3. PROBLEM REDUCTION
The paper reduces reliability and expected spatial/temporal diversity computation to tractable formulations, then proves that RDB-SC remains NP-hard and motivates approximation algorithms.
- Reliability: The reliability objective maximizes the smallest summed worker-confidence value across task partitions.Each worker contributes −ln(1−p_j) to the task subset receiving that worker.
- Hardness: Direct expected-diversity computation is impractical because it enumerates exponentially many possible worlds.The paper therefore seeks a polynomial-cost reduction.
- Diversity: The spatial diversity matrix can be computed in O(r^3) total time after each entry is computed in O(r) time.The matrix entries encode probability-weighted spatial-diversity terms.
- Diversity: The temporal diversity matrix similarly represents probability-weighted time-interval terms for j≤k.Entries are zero when j>k.
- Diversity: Expected spatial/temporal diversity combines expected spatial and temporal diversity through a weighted sum.The combination uses β for spatial diversity and 1−β for temporal diversity.
- Hardness: RDB-SC is NP-hard, so the paper proposes approximation algorithms for efficient suboptimal solutions.The hardness proof reduces the number partition problem to RDB-SC.
4. THE GREEDY APPROACH
The greedy approach exploits the fact that assigning workers does not decrease reliability or expected diversity, repeatedly selecting assignments with the strongest combined gains.
- Optimization properties: Adding a worker makes task reliability non-decreasing.The reliability increment is −ln(1−p_{r+1}), a positive contribution for a worker confidence in the stated range.
- Optimization properties: Adding a worker also makes expected spatial/temporal diversity non-decreasing.This property supports incremental assignment decisions.
- Greedy algorithm: RDB-SC Greedy repeatedly selects valid task-worker pairs that produce large reliability and diversity increases.Validity requires that the worker can reach the task under movement-direction and valid-period constraints.
- Greedy algorithm: Dominated candidate pairs are filtered, and remaining pairs are ranked by how many alternatives they dominate.The algorithm repeats this selection for n rounds and returns the resulting assignment strategy.
- Pruning: The method bounds diversity increases instead of computing exact diversity for every candidate pair.Lower and upper bounds are used to prune pairs that cannot outperform another candidate.
5. THE SAMPLING APPROACH
The sampling approach replaces exhaustive enumeration of exponentially many assignments with random assignments and selects a high-ranked sample, with sample size chosen for rank guarantees.
- Random sampling: All feasible task-worker assignments form an exponentially large population that cannot be enumerated efficiently.The population size is expressed as a product of worker degrees.
- Random sampling: Each random sample independently selects one feasible edge for every worker.The selected edges together form one task-worker assignment.
- Random sampling: After K samples are generated, the algorithm ranks them by reliability and diversity and returns the highest-scoring sample.If no sample dominates all others, it uses the ranking score based on domination count.
- Approximation scope: When K approaches the full population size, the sampled answer approaches the optimum, but the paper uses bounded-rank approximations because RDB-SC is NP-hard.This establishes a quality-efficiency trade-off for sampling.
- Sample-size determination: The required sample size targets an (ϵ,δ)-bounded rank for the best sampled assignment.The largest sample is intended to lie within the top ϵN population ranks with probability greater than δ.
- Sample-size determination: The sample-size calculation models the largest sampled rank as a random variable and derives its probability distribution.The probability terms account for selections before the largest sample, selecting it, and rejecting later values.
6. THE DIVIDE-AND-CONQUERAPPROACH
The divide-and-conquer approach recursively partitions the task-worker bipartite graph, solves smaller subproblems with existing approximations, and merges their assignments while resolving duplicated-worker conflicts.
- Framework: The framework recursively divides RDB-SC, solves the subproblems, and merges their answers.Subproblems can be solved with either the greedy or sampling approach.
- Partitioning: BG Partition heuristically creates two balanced subgraphs with few crossing edges.The underlying sparse balanced-cut problem is NP-hard.
- Partitioning: Tasks are split into two location-based subsets, while workers serving both subsets are duplicated in both subproblems.Workers serving only one subset are isolated in the corresponding subproblem.
- Partitioning: Duplicated workers remain assignable to at most one task in the final solution, and partitioning reduces each subproblem’s complexity.A threshold γ determines when a subproblem is small enough to solve directly.
- Merging: SA Merge resolves conflicts caused by duplicated workers when combining subproblem assignments.Independent conflicting workers can be deleted independently, whereas dependent conflicting workers require integral treatment.
- Merging: Deleting copies of conflicting workers preserves assignments of non-conflicting workers sharing tasks with deleted copies.This stability property supports the merging procedure.
7. COST-MODEL-BASED GRID INDEX
The cost-model-based grid index partitions the 2-dimensional space into cells storing task and worker information, then maintains reachability links to prune impossible assignments. Its operations support dynamic worker and task updates with stated insertion and removal costs.
- Index structure: RDB-SC-Grid partitions [0, 1]^2 into 1/η^2 square cells of side length η, with η selected using a cost model.The index is designed for a 2-dimensional data space.
- Index structure: Each cell stores task records with IDs, locations, and validity periods, alongside worker records containing locations, velocities, direction ranges, and reliability.Cells also maintain aggregate velocity, direction, and task-time bounds.
- Reachability pruning: The pruning strategy removes cells that workers are definitely unable to reach before task deadlines.For cells i and j, the index computes distance bounds and uses tmin = dmin/vmax(celli); if tmin exceeds the relevant latest deadline, cellj is pruned.
- Dynamic maintenance: Worker insertion locates its cell in O(1) time and updates that cell’s tcell list in O(costupdate) worst-case time; removal is similar.The worker’s cell is found directly, while maintaining reachability information incurs the update cost.
- Dynamic maintenance: Task insertion finds its cell in O(1) time but may check all workers, while task removal may likewise require O(n) worst-case checks.Insertion checks cells excluding the task’s cell that do not list it; removal checks cells whose tcell lists contain it.
8. EXPERIMENTAL STUDY
Experiments on real and synthetic data show that SAMPLING and D&C generally achieve reliability and diversity close to G-TRUTH, while trading higher effectiveness against computational cost. The RDB-SC-Grid index also substantially reduces worker-task retrieval time, and the real-platform showcase produces a plausible 3D model from diverse photos.
- Experimental Methodology: The experiments use China POI data, T-Drive taxi trajectories, and synthetic data with varied worker, task, velocity, and diversity parameters.The POI data contains over 6 million points, while T-Drive contains 10,357 Beijing taxi trajectories.
- Synthetic Data: SAMPLING and D&C maintain reliability and diversity similar to G-TRUTH, generally outperforming GREEDY in diversity.Their diversity remains close to G-TRUTH across several parameter settings, while GREEDY can suffer from startup effects.
- Synthetic Data: About 3% improvement in total STD is achieved by D&C over SAMPLING when merging solutions from smaller subproblems.Both methods remain very close to G-TRUTH in total STD.
- Efficiency: D&C trades efficiency for effectiveness, requiring higher CPU cost than SAMPLING while providing higher reliability and diversity.SAMPLING takes only several seconds because of its small sample size.
- Efficiency: Less than 0.7 sec construction time and up to 67% lower worker-task retrieval time are reported for the RDB-SC-Grid index.The comparison uses m = 10K and n varying from 5K to 30K on UNIFORM data.
- Real RDB-SC Platform: When tinterval increases, total STD decreases for all approaches, while SAMPLING and D&C remain better than GREEDY and close to G-TRUTH.On the real platform, minimum reliability remains high except for GREEDY, whose reliability becomes more sensitive.
- Real RDB-SC Platform: A real-platform showcase reconstructs a general garden shape from 23 photos assigned with good spatial diversity.The models are built from unordered photos using VisualSFM and compared with a ground-truth model.
9. RELATED WORK
Related work covers spatial crowdsourcing models for physically performed tasks, worker incentives, task-publication modes, assignment objectives, and privacy preservation. This paper differs by targeting reliability and spatial/temporal diversity for moving workers and time-constrained tasks.
- Spatial Crowdsourcing: Spatial crowdsourcing assigns workers to physically visit locations for sensing tasks, unlike prior crowdsourcing work where physical visits are unnecessary.Examples include monitoring scenes, local hotspots, and traffic conditions.
- Worker Motivation: Spatial crowdsourcing is classified by worker motivation into reward-based and self-incentivised settings; this paper studies self-incentivised crowdsourcing.Self-incentivised workers perform tasks voluntarily rather than for small rewards.
- Task Publication: Task-publication modes include worker selected tasks, where workers choose tasks, and server assigned tasks, where the server assigns workers.The paper’s setting concerns server-side assignment using worker location information.
- Assignment Objectives: Earlier assignment studies mainly maximize completed-task counts, whereas this work maximizes reliability and spatial/temporal diversity.The distinction separates the paper’s objective from static maximum assignment and single-worker task scheduling.
- Privacy Preservation: Privacy-preserving spatial crowdsourcing studies protect reported worker locations and trajectories, but privacy preservation is outside this paper’s scope.The paper focuses on assignment quality rather than location privacy.
10. CONCLUSION
The paper formulates RDB-SC for assigning time-constrained tasks to moving workers while maximizing reliability and spatial/temporal diversity. It proves NP-hardness, proposes three approximation algorithms, and introduces an index for efficient maintenance and retrieval.
- RDB-SC assigns time-constrained spatial tasks to dynamically moving workers while targeting high reliability and spatial/temporal diversity.
- The paper proves that RDB-SC is NP-hard and proposes greedy, sampling, and divide-and-conquer approximation algorithms.
- A cost-model-based index supports worker-task maintenance and RDB-SC answer retrieval.
- Experiments on real and synthetic data sets evaluate the efficiency and effectiveness of the proposed approaches.
Appendix
The appendix proves structural lemmas and NP-hardness for RDB-SC, deriving how reliability and spatial/temporal diversity change when workers are added or removed. It also establishes approximation-related probability bounds and reports how reliability and diversity vary with synthetic-data parameters.
- Hardness: The RDB-SC problem is shown NP-hard by reducing number partition to an instance with two tasks and workers that can reach either task.The constructed instance has zero total spatial/temporal diversity, while minimizing the larger subset sum corresponds to minimizing partition discrepancy.
- Reliability: Adding a worker increases reliability by −ln(1−p_r+1) under the lemma’s reliability formulation.The result follows by combining the reliability expressions for the original and expanded worker sets.
- Diversity: Adding a worker does not decrease expected spatial or temporal diversity, because each possible world’s diversity is shown to be nondecreasing.The proof handles spatial diversity through angle partitioning and applies the same argument to temporal diversity.
- Algorithmic lemmas: The appendix derives pruning conditions that discard worker-task pairs when another pair offers at least as much reliability and diversity improvement.The conditions compare the minimum-reliability increase and the diversity improvement of competing assignments.
- Sampling analysis: The sampling bound chooses K so that F(K) ≤ 1−δ, using monotonicity and binary search after relaxing harmonic-series terms.The derivation introduces a continuous Gamma-function form because factorials are not differentiable as a continuous function.
- Experiments: On synthetic data, minimum reliability is largely insensitive to task or worker counts, while diversity changes with these parameters and differs across algorithms.As tasks increase, SAMPLING and D&C diversity decreases while GREEDY diversity increases; as workers increase, all approaches’ diversities increase.