Whom to Query? Spatially-Blind Participatory Crowdsensing under Budget Constraints

Abstract

The ubiquity of sensors has introduced a variety of new opportunities for data collection. In this paper, we attempt to answer the question: Given M workers in a spatial environment and N probing resources, where N < M, which N workers should be queried to answer a specific question? To solve this research question, we propose two querying algorithms: one that exploits worker feedback (DispNN) and one that does not rely on worker feedback (DispMax). We evaluate DispNN and DispMax algorithms on two different event distributions: clustered and complete spatial randomness. We then apply the algorithms to a dataset of actual street harassment events provided by Hollaback. The proposed algorithms outperform a random selection approach by up to 30%, a random selection approach with feedback by up to 35%, a greedy heuristic by up to 5x times, and cover up to a median of 96% of the incidents.