Turbo-GTS: Scaling Mobile Crowdsourcing via Workload-Balancing Bisection Trees

TL;DR

Turbo-GTS is a high-performance framework designed to solve the "last-mile" coordination problem in mobile crowdsourcing. By replacing standard spatial trees with a Workload-balancing Bisection Tree (WBT), the system dynamically redistributes workers to areas of high task density. Tested on massive real-world datasets from NYC and Tokyo, it significantly increases the total number of tasks completed while reducing computation time to nearly real-time levels.

Problem & Motivation: The Scalability Wall

In mobile crowdsourcing, the goal is simple but computationally brutal: maximize the total number of tasks completed by a group of workers, each constrained by their location, task deadlines (expiration), and the time it takes to actually perform the work.

Traditional approaches like BLALS-T create a worker-taskflow network, but they break down when the number of tasks explodes. They often assume workers are "trapped" in small neighborhoods or can only handle a few tasks. Previous spatial partitioning methods using PR Quadtrees (like QT-NNH) improved speed but lacked a mechanism to balance the actual difficulty of the tasks across the map—leading to "idle workers" in some zones and "overwhelmed workers" in others.

Methodology: The Logic of WBT

The core innovation is the Workload-balancing Bisection Tree (WBT). Unlike a Quadtree that splits space into four equal quadrants regardless of what's inside, the WBT focuses on the Task-Worker-Density (TWD).

1. The TWD Metric

The system calculates TWD for every node using the following logic:

• Numerator: The sum of work "demand" (reciprocal of execution durations).
• Denominator: The total available "time-distance" capacity of workers in that region, adjusted by the Random Point Distance (RPD)—the mathematical expected distance between two points in a rectangle.

2. Recursive Balancing

When a region is bisected, the system doesn't just split the map; it reassigns workers across the boundary. If region A has too many tasks and region B has too many workers, the WBT logic moves the virtual "responsibility" of workers to ensure both leaf nodes have similar TWD scores.

Figure: The WBT process showing worker reassignment (red arrows) to balance task demands.

Experiments & Results: Real-World Superiority

The authors validated the system using Foursquare check-in data from New York City (42k tasks) and Tokyo (67k tasks).

Scaling with Tasks and Workers

• Throughput: Both WBT-NNH and WBT-NUD consistently outperformed prior SOTA. In one case, WBT assigned nearly 500 more successful tasks than the Quadtree approach within the same timeframe.
• Efficiency: Despite the added complexity of balancing, the WBT algorithms maintain a "flat" CPU cost curve, making them suitable for real-time mobile applications.

Figure: WBT-based methods (solid lines) achieving higher task completion without an exponential increase in CPU cost.

Critical Analysis & Conclusion

Takeaway

Turbo-GTS proves that Workload-Awareness is the key to scaling spatial systems. By treating workers as a flexible resource that can be "pushed" to high-demand areas through intelligent partitioning, the system avoids the local optima that plague static quadrant-based methods.

Limitations & Future Work

While Turbo-GTS is highly efficient, its current TWD calculation assumes a uniform distribution of tasks within a node once split. Future iterations might incorporate real-time traffic data or worker-specific preferences (e.g., specific types of tasks) to further refine the density metric.

Demonstration Use Cases

The system is not just a theoretical model; it includes a full front-end that allows users to:

1. Compare algorithm results visually (e.g., seeing where WBT captures tasks that QT misses).
2. Generate an optimal sequence of waypoints for individual workers on a map.

Figure: The Turbo-GTS interface showing task assignment distributions.