Scalable network distance browsing in spatial databases

ABSTRACT

An algorithm is presented for finding the k nearest neighbors in a spatial network in a best-first manner using network distance. The algorithm is based on precomputing the shortest paths between all possible vertices in the network and then making use of an encoding that takes advantage of the fact that the shortest paths from vertex u to all of the remaining vertices can be decomposed into subsets based on the first edges on the shortest paths to them from u. Thus, in the worst case, the amount of work depends on the number of objects that are examined and the number of links on the shortest paths to them from q, rather than depending on the number of vertices in the network. The amount of storage required to keep track of the subsets is reduced by taking advantage of their spatial coherence which is captured by the aid of a shortest path quadtree. In particular, experiments on a number of large road networks as well as a theoretical analysis have shown that the storage has been reduced from O(N³) to O(N^1.5) (i.e., by an order of magnitude equal to the square root). The precomputation of the shortest paths along the network essentially decouples the process of computing shortest paths along the network from that of finding the neighbors, and thereby also decouples the domain S of the query objects and that of the objects from which the neighbors are drawn from the domain V of the vertices of the spatial network. This means that as long as the spatial network is unchanged, the algorithm and underlying representation of the shortest paths in the spatial network can be used with different sets of objects.

REFERENCES

• 1: J. E. Bresenham. Algorithm for computer control of a digital plotter. IBM Systems Journal, 4(1):25--30, 1965.
• 2: Hyung-Ju Cho , Chin-Wan Chung, An efficient and scalable approach to CNN queries in a road network, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 3: Kenneth L. Clarkson, Fast algorithms for the all nearest neighbors problem, Proceedings of the 24th Annual Symposium on Foundations of Computer Science (sfcs 1983), p.226-232, November 07-09, 1983 [doi>10.1109/SFCS.1983.16]
• 4: E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.
• 5: Greg N. Frederickson, Planar graph decomposition and all pairs shortest paths, Journal of the ACM (JACM), v.38 n.1, p.162-204, Jan. 1991 [doi>10.1145/102782.102788]
• 6: K. Fukunage , P. M. Narendra, A Branch and Bound Algorithm for Computing k-Nearest Neighbors, IEEE Transactions on Computers, v.24 n.7, p.750-753, July 1975 [doi>10.1109/T-C.1975.224297]
• 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. Henrich. A distance-scan algorithm for spatial access structures. In ACM GIS'94, pp. 136--143, Gaithersburg, MD, Dec. 1994.
• 10: 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]
• 11: Erik G. Hoel , Hanan Samet, Efficient Processing of Spatial Queries in Line Segment Databases, Proceedings of the Second International Symposium on Advances in Spatial Databases, p.237-256, August 28-30, 1991
• 12: Haibo Hu , Dik Lun Lee , Victor C. S. Lee, Distance indexing on road networks, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 13: G. M. Hunter and K. Steiglitz. Operations on images using quad trees. PAMI, 1(2):145--153, Apr. 1979.
• 14: 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]
• 15: Mohammad Kolahdouzan , Cyrus Shahabi, Voronoi-based K nearest neighbor search for spatial network databases, Proceedings of the Thirtieth international conference on Very large data bases, p.840-851, August 31-September 03, 2004, Toronto, Canada
• 16: M. R. Kolahdouzan and C. Shahabi. Continuous k-nearest neighbor queries in spatial network databases. In STDBM'04, pp. 33--40, Toronto, Canada, Aug. 2004.
• 17: Michael Lindenbaum , Hanan Samet , Gisli R. Hjaltason, A Probabilistic Analysis of Trie-Based Sorting of Large Collections of Line Segments in Spatial Databases, SIAM Journal on Computing, v.35 n.1, p.22-58, 2005 [doi>10.1137/S0097539700368527]
• 18: G. M. Morton. A computer oriented geodetic data base and a new technique in file sequencing. Tech. report, IBM Ltd., Ottawa, Canada, 1966.
• 19: Randal C. Nelson , Hanan Samet, A population analysis for hierarchical data structures, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.270-277, May 27-29, 1987, San Francisco, California, United States
• 20: J. A. Orenstein. Multidimensional tries used for associative searching. Inf. Proc. Letters, 14(4):150--157, June 1982.
• 21: Dimitris Papadias , Jun Zhang , Nikos Mamoulis , Yufei Tao, Query processing in spatial network databases, Proceedings of the 29th international conference on Very large data bases, p.802-813, September 09-12, 2003, Berlin, Germany
• 22: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 23: H. Samet. Region representation: quadtrees from binary arrays. CGIP'80, 13(1):88--93, May 1980.
• 24: H. Samet. An algorithm for converting rasters to quadtrees. PAMI, 3(1):93--95, Jan. 1981.
• 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 , Robert E. Webber, Storing a collection of polygons using quadtrees, ACM Transactions on Graphics (TOG), v.4 n.3, p.182-222, July 1985 [doi>10.1145/282957.282966]
• 27: Jagan Sankaranarayanan , Houman Alborzi , Hanan Samet, Efficient query processing on spatial networks, Proceedings of the 13th annual ACM international workshop on Geographic information systems, November 04-05, 2005, Bremen, Germany [doi>10.1145/1097064.1097093]
• 28: Clifford A. Shaffer , Hanan Samet, Optimal quadtree construction algorithms, Computer Vision, Graphics, and Image Processing, v.37 n.3, p.402-419, March 1987 [doi>10.1016/0734-189X(87)90045-4]
• 29: C. A. Shaffer, H. Samet, and R. C. Nelson. QUILT: a geographic information system based on quadtrees. Int. Jour. of Geog. Inf. Sys., 4(2):103--131, Apr.-Jun. 1990.
• 30: 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]
• 31: D. Wagner and T. Willhalm. Geometric speed-up techniques for finding shortest paths in large sparse graphs. In ESA'03, LNCS 2832, pp. 776--787, Budapest, Hungary, Sep. 2003.
• 32: 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

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

General Terms:
Algorithms, Design, Performance

Keywords:
decoupling, nearest neighbor, scalability, shortest path quadtree, spatial networks