Dual-heap kNN: k-nearest neighbor search for spatial data retrieval in embedded DBMS

ABSTRACT

In this paper, we present a kNN search method called the dual-heap kNN method, which is used in an embedded database management system (DBMS) for in-vehicle information systems. The dual-heap kNN method is based on two conventional kNN methods: (1) the RKV method and (2) the HS method. The RKV method and the HS method based on depth-first traversal and best-first traversal, respectively, shorten the search time. Our method not only shortens the search time but also reduces the capacity of the memory usage. Our simulation experiments suggest that our method results in the same number of disk accesses as that of the HS method, which is up to 12% smaller than the RKV method. Our method results in a memory usage capacity that is up to 24% larger than that of the RKV method and up to 68% smaller than that of the HS method. In addition, our prototype evaluation using actual data indicates that our method is applicable to in-vehicle information systems.

REFERENCES

• 1: Hitachi, Ltd., Entier Embedded Database, URL: http://www.hitachi.us/Apps/hitachicom/content.jsp?page=index.html&path=jsp/hitachi/forbus/entier/.
• 2: Oracle, Oracle Database Lite 10g, URL: http://www.oracle.com/technology/products/lite/index.html.
• 3: IBM, DB2 Everyplace, URL: http://www-306.ibm.com/software/data/db2/everyplace/.
• 4: 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
• 5: 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]
• 6: Haibo Hu , Dik Lun Lee, Range Nearest-Neighbor Query, IEEE Transactions on Knowledge and Data Engineering, v.18 n.1, p.78-91, January 2006 [doi>10.1109/TKDE.2006.15]
• 7: Norio Katayama , Shin'ichi Satoh, The SR-tree: an index structure for high-dimensional nearest neighbor queries, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.369-380, May 11-15, 1997, Tucson, Arizona, United States
• 8: 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
• 9: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 10: Zhexuan Song , Nick Roussopoulos, K-Nearest Neighbor Search for Moving Query Point, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.79-96, July 12-15, 2001
• 11: Yufei Tao , Dimitris Papadias , Qiongmao Shen, Continuous nearest neighbor search, Proceedings of the 28th international conference on Very Large Data Bases, p.287-298, August 20-23, 2002, Hong Kong, China
• 12: David A. White , Ramesh Jain, Similarity Indexing with the SS-tree, Proceedings of the Twelfth International Conference on Data Engineering, p.516-523, February 26-March 01, 1996

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
embedded database management, nearest neighbor