Approximate indexing in road network databases

ABSTRACT

In this paper, we address approximate indexing for efficient processing of k-nearest neighbor(k-NN) queries in road network databases. Previous methods suffer from either serious performance degradation in query processing or large storage overhead because they did not employ indexing mechanisms based on their network distances. To overcome these drawbacks, we propose a novel method that builds an index on those objects in a road network by approximating their network distances and processes k-NN queries efficiently by using that index. Also, we verify the superiority of the proposed method via extensive experiments using the real-life road network databases.

REFERENCES

• 1: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 2: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 3: E. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik, Vol. 1, pp. 269--271, 1959.
• 4: Ronald Fagin , Ravi Kumar , D. Sivakumar, Comparing top k lists, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 5: Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.163-174, May 22-25, 1995, San Jose, California, United States
• 6: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 7: 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]
• 8: Sang-Wook Kim , Sanghyun Park , Wesley W. Chu, An Index-Based Approach for Similarity Search Supporting Time Warping in Large Sequence Databases, Proceedings of the 17th International Conference on Data Engineering, p.607-614, April 02-06, 2001
• 9: 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
• 10: 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
• 11: The R-tree Portal, www.rtreeportal.org
• 12: Jason Tsong-Li Wang , Xiong Wang , King-Ip Lin , Dennis Shasha , Bruce A. Shapiro , Kaizhong Zhang, Evaluating a class of distance-mapping algorithms for data mining and clustering, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.307-311, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312264]
• 13: Kyu Young Whang , Sang Wook Kim , Gio Wiederhold, Dynamic maintenance of data distribution for selectivity estimation, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.1, p.29-51, January 1994 [doi>10.1007/BF01231357]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

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

General Terms:
Algorithms

Keywords:
k-nearest neighbor queries, approximate indexing, data structures, road network databases