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

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.