A Continuous Query System for Dynamic Route Planning
In this paper, we address the problem of answering continuous route planning queries over a road network, in the presence of updates to the delay (cost) estimates of links. A simple approach to this problem would be to recompute the best path for all queries on arrival of every delay update. How...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
International Conference on Data Engineering
2011
|
| Online Access: | http://hdl.handle.net/1721.1/62815 https://orcid.org/0000-0002-7470-3265 |
| _version_ | 1811094479533244416 |
|---|---|
| author | Malviya, Nirmesh Madden, Samuel R. Bhattacharyya, Arnab |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Malviya, Nirmesh Madden, Samuel R. Bhattacharyya, Arnab |
| author_sort | Malviya, Nirmesh |
| collection | MIT |
| description | In this paper, we address the problem of answering
continuous route planning queries over a road network, in the
presence of updates to the delay (cost) estimates of links. A simple
approach to this problem would be to recompute the best path
for all queries on arrival of every delay update. However, such
a naive approach scales poorly when there are many users who
have requested routes in the system.
Instead, we propose two new classes of approximate techniques
– K-paths and proximity measures to substantially speed up
processing of the set of designated routes specified by continuous
route planning queries in the face of incoming traffic delay
updates. Our techniques work through a combination of precomputation
of likely good paths and by avoiding complete
recalculations on every delay update, instead only sending the
user new routes when delays change significantly. Based on an
experimental evaluation with 7,000 drives from real taxi cabs,
we found that the routes delivered by our techniques are within
5% of the best shortest path and have run times an order of
magnitude or less compared to a naive approach. |
| first_indexed | 2024-09-23T16:00:39Z |
| format | Article |
| id | mit-1721.1/62815 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:00:39Z |
| publishDate | 2011 |
| publisher | International Conference on Data Engineering |
| record_format | dspace |
| spelling | mit-1721.1/628152022-09-29T17:38:41Z A Continuous Query System for Dynamic Route Planning Malviya, Nirmesh Madden, Samuel R. Bhattacharyya, Arnab Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Madden, Samuel R. Malviya, Nirmesh Madden, Samuel R. In this paper, we address the problem of answering continuous route planning queries over a road network, in the presence of updates to the delay (cost) estimates of links. A simple approach to this problem would be to recompute the best path for all queries on arrival of every delay update. However, such a naive approach scales poorly when there are many users who have requested routes in the system. Instead, we propose two new classes of approximate techniques – K-paths and proximity measures to substantially speed up processing of the set of designated routes specified by continuous route planning queries in the face of incoming traffic delay updates. Our techniques work through a combination of precomputation of likely good paths and by avoiding complete recalculations on every delay update, instead only sending the user new routes when delays change significantly. Based on an experimental evaluation with 7,000 drives from real taxi cabs, we found that the routes delivered by our techniques are within 5% of the best shortest path and have run times an order of magnitude or less compared to a naive approach. 2011-05-11T18:00:10Z 2011-05-11T18:00:10Z 2011-04 Article http://purl.org/eprint/type/ConferencePaper http://hdl.handle.net/1721.1/62815 Malviya, Nirmesh, Samuel Madden, and Arnab Bhattacharya. "A Continuous Query System for Dynamic Route Planning" in Proceedings of the International Conference on Data Engineering, ICDE 2011, April 11-16, Hannover, Germany. https://orcid.org/0000-0002-7470-3265 en_US http://www.icde2011.org/node/94 International Conference on Data Engineering (ICDE 2011) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf International Conference on Data Engineering MIT web domain |
| spellingShingle | Malviya, Nirmesh Madden, Samuel R. Bhattacharyya, Arnab A Continuous Query System for Dynamic Route Planning |
| title | A Continuous Query System for Dynamic Route Planning |
| title_full | A Continuous Query System for Dynamic Route Planning |
| title_fullStr | A Continuous Query System for Dynamic Route Planning |
| title_full_unstemmed | A Continuous Query System for Dynamic Route Planning |
| title_short | A Continuous Query System for Dynamic Route Planning |
| title_sort | continuous query system for dynamic route planning |
| url | http://hdl.handle.net/1721.1/62815 https://orcid.org/0000-0002-7470-3265 |
| work_keys_str_mv | AT malviyanirmesh acontinuousquerysystemfordynamicrouteplanning AT maddensamuelr acontinuousquerysystemfordynamicrouteplanning AT bhattacharyyaarnab acontinuousquerysystemfordynamicrouteplanning AT malviyanirmesh continuousquerysystemfordynamicrouteplanning AT maddensamuelr continuousquerysystemfordynamicrouteplanning AT bhattacharyyaarnab continuousquerysystemfordynamicrouteplanning |