|
Published Articles >> Table of Contents >> Abstract
First Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services (MobiQuitous'04)
pp. 236-245
Search Continuous Nearest Neighbors on the Air
Baihua Zheng, Singapore Management University
Wang-Chien Lee, Penn State University
Dik Lun Lee, Hong Kong University of Science and Technology
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/MOBIQ.2004.1331730
Send link to a friend
| 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.
|
 Additional Information
|
Citation:
Baihua Zheng, Wang-Chien Lee, Dik Lun Lee,
"Search Continuous Nearest Neighbors on the Air,"
mobiquitous,
pp. 236-245,
First Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services (MobiQuitous'04),
2004
|
|
