Crowdsourcing computing resources for shortest-path computation

Crowdsourcing road network data, i.e., involving users to collect data including the detection and assessment of changes to the road network graph, poses a challenge to shortest-path algorithms that rely on preprocessing. Hence, current research challenges lie with improving performance by adequately balancing preprocessing with respect to fast-changing road networks. In this work, we take the crowdsourcing approach further in that we solicit the help of users not only for data collection, but also to provide us their computing resources. A promising approach is parallelization, which splits the graph into chunks of data that may be processed separately. This work extends this approach in that small-enough chunks allow us to use browser-based computing to solve the pre-computation problem. Essentially, we aim for a Web-based navigation service that whenever users request a route, the service uses their browsers for partially preprocessing a large, but changing road network. The paper gives performance studies that highlight the potential of the browser as a computing platform and showcases a scalable approach, which almost eliminates the computing load on the server.