Efficient query processing on spatial networks

ABSTRACT

A framework for determining the shortest path and the distance between every pair of vertices on a spatial network is presented. The framework, termed SILC, uses path coherence between the shortest path and the spatial positions of vertices on the spatial network, thereby, resulting in an encoding that is compact in representation and fast in path and distance retrievals. Using this framework, a wide variety of spatial queries such as incremental nearest neighbor searches and spatial distance joins can be shown to work on datasets of locations residing on a spatial network of sufficiently large size. The suggested framework is suitable for both main memory and disk-resident datasets.

REFERENCES

• 1: P. A. Burrough and R. A. McDonnell. Principles of Geographical Information Systems. Oxford University Press, New York, NY, USA, Apr. 1998.
• 2: E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.
• 3: G. G. Filho and H. Samet. A linear iterative approach for hierarchical shortest path finding. Computer Science Department CS-TR-4417, University of Maryland, College Park, MD, Nov. 2002.
• 4: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 5: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 6: Herbert Freeman, Computer Processing of Line-Drawing Images, ACM Computing Surveys (CSUR), v.6 n.1, p.57-97, March 1974 [doi>10.1145/356625.356627]
• 7: Irene Gargantini, An effective way to represent quadtrees, Communications of the ACM, v.25 n.12, p.905-910, Dec 1982 [doi>10.1145/358728.358741]
• 8: Andrew V. Goldberg , Chris Harrelson, Computing the shortest path: A search meets graph theory, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 9: A. V. Goldberg and R. F. Werneck. Computing point-to-point shortest paths from external memory. In ALENEX '05: Proceedings of the 7th Workshop on Algorithm Engineering and Experiments, Vancouver, BC, Canada, Jan. 2005.
• 10: Sandeep Gupta , Swastik Kopparty , Chinya Ravishankar, Roads, codes, and spatiotemporal queries, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055576]
• 11: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 12: Monika R. Henzinger , Philip Klein , Satish Rao , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Journal of Computer and System Sciences, v.55 n.1, p.3-23, Aug. 1997 [doi>10.1006/jcss.1997.1493]
• 13: Gisli R. Hjaltason , Hanan Samet, Ranking in Spatial Databases, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.83-95, August 06-09, 1995
• 14: Gísli R. Hjaltason , Hanan Samet, Incremental distance join algorithms for spatial databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.237-248, June 01-04, 1998, Seattle, Washington, United States
• 15: Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999 [doi>10.1145/320248.320255]
• 16: David Hutchinson , Anil Maheshwari , Norbert Zeh, An external memory data structure for shortest path queries, Discrete Applied Mathematics, v.126 n.1, p.55-82, March 2003 [doi>10.1016/S0166-218X(02)00217-2]
• 17: Ning Jing , Yun-Wu Huang , Elke A. Rundensteiner, Hierarchical Encoded Path Views for Path Query Processing: An Optimal Model and Its Performance Evaluation, IEEE Transactions on Knowledge and Data Engineering, v.10 n.3, p.409-432, May 1998 [doi>10.1109/69.687976]
• 18: M. R. Kolahdouzan and C. Shahabi. Voronoi-based k nearest neighbor search for spatial network databases. In VLDB'04: Proceedings of the 30th International Conference on Very Large Data Bases, pages 840--851, Toronto, Canada, Sept. 2004.
• 19: P. Micikevicius. General parallel computation on commodity graphics hardware: case study with the all-pairs shortest paths problem. In PDPTA '04: Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, pages 1359--1365, Las Vegas, NV, USA, June 2004.
• 20: Joseph S. B. Mitchell , David M. Mount , Christos H. Papadimitriou, The discrete geodesic problem, SIAM Journal on Computing, v.16 n.4, p.647-668, Aug. 1987 [doi>10.1137/0216045]
• 21: Randal C. Nelson , Hanan Samet, A consistent hierarchical representation for vector data, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.197-206, Aug. 1986
• 22: D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao. Query processing in spatial network databases. In VLDB'03: Proceedings of the 29th International Conference on Very Large Databases, pages 802--813, Berlin, Germany, Sept. 2003.
• 23: Indexing of Moving Objects for Location-Based Services, Proceedings of the 18th International Conference on Data Engineering, p.463, February 26-March 01, 2002
• 24: Hanan Samet, A quadtree medial axis transform, Communications of the ACM, v.26 n.9, p.680-693, Sept. 1983 [doi>10.1145/358172.358409]
• 25: Hanan Samet, Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 26: Hanan Samet , Houman Alborzi , František Brabec , Claudio Esperança , Gísli R. Hjaltason , Frank Morgan , Egemen Tanin, Use of the SAND spatial browser for digital government applications, Communications of the ACM, v.46 n.1, January 2003 [doi>10.1145/602421.602453]
• 27: Ralph E. Schofer , Franklin F. Goodyear, Electronic computer applications in urban transportation planning, Proceedings of the 1967 22nd national conference, p.247-253, January 1967, Washington, D.C., United States [doi>10.1145/800196.805994]
• 28: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 29: Cyrus Shahabi , Mohammad R. Kolahdouzan , Mehdi Sharifzadeh, A Road Network Embedding Technique for K-Nearest Neighbor Search in Moving Object Databases, Geoinformatica, v.7 n.3, p.255-273, September 2003 [doi>10.1023/A:1025153016110]
• 30: Shashi Shekhar , Toneluh Andrew Yang, Motion in a Geographical Database System, Proceedings of the Second International Symposium on Advances in Spatial Databases, p.339-358, August 28-30, 1991
• 31: Shashi Shekhar , Jin Soung Yoo, Processing in-route nearest neighbor queries: a comparison of alternative approaches, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.9-16, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956676.956678]
• 32: Vitaly Surazhsky , Tatiana Surazhsky , Danil Kirsanov , Steven J. Gortler , Hugues Hoppe, Fast exact and approximate geodesics on meshes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 33: Mikkel Thorup, Undirected single-source shortest paths with positive integer weights in linear time, Journal of the ACM (JACM), v.46 n.3, p.362-394, May 1999 [doi>10.1145/316542.316548]
• 34: U.S. Census Bureau. TIGER/Line Files, Census 2000. U.S. Census Bureau, Washington, DC, USA, Oct. 2001. http://www.census.gov/geo/www/tiger/tiger2k/tiger2000.html.
• 35: U.S. Geological Survey. Major Roads of the United States. U.S. Geological Survey, Reston, VA, USA, 199911. http://nationalatlas.gov/atlasftp.html.
• 36: D. Wagner and T. Willhalm. Geometric speed-up techniques for finding shortest paths in large sparse graphs. In ESA '03: Proceedings of the 11th Annual European Symposium on Algorithms, pages 776--787. 2003.
• 37: D. Wagner and T. Willhalm. Drawing graphs to speed up shortest-path computations. In ALENEX '05: Proceedings of the 7th Workshop on Algorithm Engineering and Experiments, Vancouver, BC, Canada, Jan. 2005.
• 38: Ouri Wolfson , Prasad Sistla , Bo Xu , Jutai Zhou , Sam Chamberlain, DOMINO: databases fOr MovINg Objects tracking, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.547-549, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 39: F. Benjamin Zhan , Charles E. Noon, Shortest Path Algorithms: An Evaluation Using Real Road Networks, Transportation Science, v.32 n.1, p.65-73, January 1998 [doi>10.1287/trsc.32.1.65]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Linked representations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Performance

Keywords:
SILC framework, location-based services, path coherence, query processing, spatial databases, spatial networks