Search Continuous Nearest Neighbor on Air
Conference Proceeding Article
A continuous nearest neighbor (CNN) search retrieves the nearest neighbors corresponding to every point in a given query line segment. It is important for location-based services such as vehicular navigation tools and tourist guides. It is infeasible to answer a CNN search by issuing a traditional nearest neighbor query at every point of the line segment due to the large number of queries generated and the large overhead on bandwidth. Algorithms have been proposed recently to support CNN search in the traditional client-server service model. In this paper, we conduct a pioneering study on CNN search in wireless data broadcast environments. We propose two air indexing techniques, namely, R-tree air index and Hilbert curve air index, and develop algorithms based on these two techniques to search CNNs on the air. A simulation is conducted to compare the proposed air indexing techniques with a naive broadcast approach. The result shows that both of the proposed methods outperform the naive approach significantly. The Hilbert Curve air index is superior for uniform data distributions, while the R-tree air index is a better choice for skewed data distributions.
Databases and Information Systems | Numerical Analysis and Scientific Computing
Data Management and Analytics
Proc. The First International Conference on Mobile and Ubiquitous Systems: Networking and Services (MobiQuitous '04)
ZHENG, Baihua; LEE, Wang-chien; and LEE, Dik Lun.
Search Continuous Nearest Neighbor on Air. (2004). Proc. The First International Conference on Mobile and Ubiquitous Systems: Networking and Services (MobiQuitous '04). 236-245. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/520