skip to main content
10.1145/1055558.1055576acmconferencesArticle/Chapter ViewAbstractPublication PagespodsConference Proceedingsconference-collections
Article

Roads, codes, and spatiotemporal queries

Published: 14 June 2004 Publication History

Abstract

We present a novel coding-based technique for answering spatial and spatiotemporal queries on objects moving along a system of curves on the plane such as many road networks. We handle join, range, intercept, and other spatial and spatiotemporal queries under these assumptions, with distances being measured along the trajectories. Most work to date has studied the significantly simpler case of objects moving in straight lines on the plane. Our work is an advance toward solving the problem in its more general form.Central to our approach is an efficient coding technique, based on hypercube embedding, for assigning labels to nodes in the network. The Hamming distance between codes corresponds to the physical distance between nodes, so that we can determine shortest distances in the network extremely quickly. The coding method also efficiently captures many properties of the network relevant to spatial and spatiotemporal queries. Our approach also yields a very effective spatial hashing method for this domain. Our analytical results demonstrate that our methods are space- and time-efficient.We have studied the performance of our method for large planar graphs designed to represent road networks. Experiments show that our methods are efficient and practical.

References

[1]
P. K. Agarwal, L. Arge, and J. Erickson. Indexing moving points. In Proc. of the 19th ACM Symp. on Principles of Database Systems (PODS), pages 175--186, 2000.
[2]
Bondy and Murthy. Graph theory with applications. 1976.
[3]
V. Chepoi and M. Deza. Clin d'oeil on l1-embeddable planar graphs. In Discrete Appl. Math. 80, pages 3--19, 1997.
[4]
Cormen, Lieserson, and Rivest. Introduction to algorithms. 1990.
[5]
G. N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. In SIAM J. Computing 16(6), pages 1004--1022, 1987.
[6]
C. Gavoille, D. Peleg, S. Perennes, and R. Raz. Distance labeling in graphs. In Symposium on Discrete Algorithms, pages 210--219, 2001.
[7]
R. Guting, M. Bohlen, M. Erwig, C. Jensen, N. Lorentzos, M. Schneider, and M. Vazirgiannis. A Foundation for Representing and Querying Moving Objects. In ACM TODS, Vol. 25, No 1, pages 1--42, 2000.
[8]
G. Kollios, D. Gunopulos, and V. Tsotras. On Indexing Mobile Objects. In Proc. of the 18th ACM Symp. on Principles of Database Systems (PODS), pages 261--272, June 1999.
[9]
N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215--245, 1995.
[10]
K. Mehlhorn, S. Naher, and C. Uhrig. The LEDA platform of combinatorial and geometric computing. In Automata, Languages and Programming, pages 7--16, 1997.
[11]
D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao. Query processing in spatial network databases, 2003.
[12]
S. Saltenis, C. Jensen, S. Leutenegger, and M. A. Lopez. Indexing the Positions of Continuously Moving Objects. In Proceedings of the ACM SIGMOD, pages 331--342, May 2000.
[13]
C. Shahabi and M. R. K. M. Sharifzadeh. A road network embedding technique for k-nearest neighbor search in moving object databases. In In the 10th ACM International Symposium on Advances in Geographic Information Systems (ACM-GIS'02), McLean, VA, 2002.
[14]
Y. Tao, D. Papadias, and J. Sun. The tpr*-tree: An optimized spatio-temporal access method for predictive queries. In Proc. of the VLDB, 2003.
[15]
US Census Bureau. TIGER. http://tiger.census.gov/.
[16]
M. Vazigiannis and O. Wolfson. A spatiotemporal model and language for moving objects on road networks. In Advances in Spatial and Temporal Databases, 2001.

Cited By

View all
  • (2024)Efficient and Privacy-Preserving Aggregate Query Over Public Property GraphsIEEE Transactions on Big Data10.1109/TBDATA.2023.334262310:2(146-157)Online publication date: Apr-2024
  • (2022)Efficient and Privacy-Preserving Ride Matching Using Exact Road Distance in Online Ride Hailing ServicesIEEE Transactions on Services Computing10.1109/TSC.2020.302287515:4(1841-1854)Online publication date: 1-Jul-2022
  • (2022)EPGQ: Efficient and Private Feature-Based Group Nearest Neighbor Query Over Road NetworksIEEE Internet of Things Journal10.1109/JIOT.2022.31774749:20(20492-20502)Online publication date: 15-Oct-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODS '04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
June 2004
350 pages
ISBN:158113858X
DOI:10.1145/1055558
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2004

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

SIGMOD/PODS04

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 31 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Efficient and Privacy-Preserving Aggregate Query Over Public Property GraphsIEEE Transactions on Big Data10.1109/TBDATA.2023.334262310:2(146-157)Online publication date: Apr-2024
  • (2022)Efficient and Privacy-Preserving Ride Matching Using Exact Road Distance in Online Ride Hailing ServicesIEEE Transactions on Services Computing10.1109/TSC.2020.302287515:4(1841-1854)Online publication date: 1-Jul-2022
  • (2022)EPGQ: Efficient and Private Feature-Based Group Nearest Neighbor Query Over Road NetworksIEEE Internet of Things Journal10.1109/JIOT.2022.31774749:20(20492-20502)Online publication date: 15-Oct-2022
  • (2017)Spatiotemporal Queries on Road Networks, Coding Based MethodsEncyclopedia of GIS10.1007/978-3-319-17885-1_1330(2168-2173)Online publication date: 12-May-2017
  • (2016)Proxies for Shortest Path and Distance QueriesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2016.253166728:7(1835-1850)Online publication date: 1-Jul-2016
  • (2016)Spatio-temporal Queries on Road Networks, Coding Based MethodsEncyclopedia of GIS10.1007/978-3-319-23519-6_1330-2(1-5)Online publication date: 31-May-2016
  • (2014)Shortest-path queries in static networksACM Computing Surveys10.1145/253053146:4(1-31)Online publication date: 1-Mar-2014
  • (2013)Shortest path and distance queries on road networksProceedings of the 2013 ACM SIGMOD International Conference on Management of Data10.1145/2463676.2465277(857-868)Online publication date: 22-Jun-2013
  • (2013)Multi-Point Shortest Path in the Complex Road Network Based on Floyd AlgorithmInformation Computing and Applications10.1007/978-3-642-53703-5_38(364-372)Online publication date: 2013
  • (2012)Shortest path and distance queries on road networksProceedings of the VLDB Endowment10.14778/2140436.21404385:5(406-417)Online publication date: 1-Jan-2012
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media