Search Continuous Nearest Neighbor on Air

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 n...

Full description

Saved in:
Bibliographic Details
Main Authors: ZHENG, Baihua, LEE, Wang-chien, LEE, Dik Lun
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2004
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/520
http://dx.doi.org/10.1109/MOBIQ.2004.1331730
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-1519
record_format dspace
spelling sg-smu-ink.sis_research-15192010-09-24T07:00:25Z Search Continuous Nearest Neighbor on Air ZHENG, Baihua LEE, Wang-chien LEE, Dik Lun 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. 2004-08-01T07:00:00Z text https://ink.library.smu.edu.sg/sis_research/520 info:doi/10.1109/MOBIQ.2004.1331730 http://dx.doi.org/10.1109/MOBIQ.2004.1331730 Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Databases and Information Systems Numerical Analysis and Scientific Computing
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Databases and Information Systems
Numerical Analysis and Scientific Computing
spellingShingle Databases and Information Systems
Numerical Analysis and Scientific Computing
ZHENG, Baihua
LEE, Wang-chien
LEE, Dik Lun
Search Continuous Nearest Neighbor on Air
description 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.
format text
author ZHENG, Baihua
LEE, Wang-chien
LEE, Dik Lun
author_facet ZHENG, Baihua
LEE, Wang-chien
LEE, Dik Lun
author_sort ZHENG, Baihua
title Search Continuous Nearest Neighbor on Air
title_short Search Continuous Nearest Neighbor on Air
title_full Search Continuous Nearest Neighbor on Air
title_fullStr Search Continuous Nearest Neighbor on Air
title_full_unstemmed Search Continuous Nearest Neighbor on Air
title_sort search continuous nearest neighbor on air
publisher Institutional Knowledge at Singapore Management University
publishDate 2004
url https://ink.library.smu.edu.sg/sis_research/520
http://dx.doi.org/10.1109/MOBIQ.2004.1331730
_version_ 1770570457886490624