Search Continuous Nearest Neighbor on Air

Publication Type

Conference Proceeding Article

Publication Date

8-2004

Abstract

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.

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

Proc. The First International Conference on Mobile and Ubiquitous Systems: Networking and Services (MobiQuitous '04)

First Page

236

Last Page

245

ISBN

9780769522081

Identifier

10.1109/MOBIQ.2004.1331730

Publisher

IEEE

Additional URL

http://dx.doi.org/10.1109/MOBIQ.2004.1331730

Link to Full Text

Share

COinS