Energy-Conserving Air Indexes for Nearest Neighbor Search

A location-based service (LBS) provides information based on the location information specified in a query. Nearest-neighbor (NN) search is an important class of queries supported in LBSs. This paper studies energy-conserving air indexes for NN search in a wireless broadcast environment. Linear acce...

Full description

Saved in:
Bibliographic Details
Main Authors: ZHENG, Baihua, XU, Jianliang, 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/557
http://dx.doi.org/10.1007/b95855
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-1556
record_format dspace
spelling sg-smu-ink.sis_research-15562010-09-24T08:24:04Z Energy-Conserving Air Indexes for Nearest Neighbor Search ZHENG, Baihua XU, Jianliang LEE, Wang-chien LEE, Dik Lun A location-based service (LBS) provides information based on the location information specified in a query. Nearest-neighbor (NN) search is an important class of queries supported in LBSs. This paper studies energy-conserving air indexes for NN search in a wireless broadcast environment. Linear access requirement of wireless broadcast weakens the performance of existing search algorithms designed for traditional spatial database. In this paper, we propose a new energy-conserving index, called grid-partition index, which enables a single linear scan of the index for any NN queries. The idea is to partition the search space for NN queries into grid cells and index all the objects that are potential nearest neighbors of a query point in each grid cell. Three grid partition schemes are proposed for the grid-partition index. Performance of the proposed grid-partition indexes and two representative traditional indexes (enhanced for wireless broadcast) is evaluated using both synthetic and real data. The result shows that the grid-partition index substantially outperforms the traditional indexes. 2004-03-01T08:00:00Z text https://ink.library.smu.edu.sg/sis_research/557 info:doi/10.1007/b95855 http://dx.doi.org/10.1007/b95855 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
XU, Jianliang
LEE, Wang-chien
LEE, Dik Lun
Energy-Conserving Air Indexes for Nearest Neighbor Search
description A location-based service (LBS) provides information based on the location information specified in a query. Nearest-neighbor (NN) search is an important class of queries supported in LBSs. This paper studies energy-conserving air indexes for NN search in a wireless broadcast environment. Linear access requirement of wireless broadcast weakens the performance of existing search algorithms designed for traditional spatial database. In this paper, we propose a new energy-conserving index, called grid-partition index, which enables a single linear scan of the index for any NN queries. The idea is to partition the search space for NN queries into grid cells and index all the objects that are potential nearest neighbors of a query point in each grid cell. Three grid partition schemes are proposed for the grid-partition index. Performance of the proposed grid-partition indexes and two representative traditional indexes (enhanced for wireless broadcast) is evaluated using both synthetic and real data. The result shows that the grid-partition index substantially outperforms the traditional indexes.
format text
author ZHENG, Baihua
XU, Jianliang
LEE, Wang-chien
LEE, Dik Lun
author_facet ZHENG, Baihua
XU, Jianliang
LEE, Wang-chien
LEE, Dik Lun
author_sort ZHENG, Baihua
title Energy-Conserving Air Indexes for Nearest Neighbor Search
title_short Energy-Conserving Air Indexes for Nearest Neighbor Search
title_full Energy-Conserving Air Indexes for Nearest Neighbor Search
title_fullStr Energy-Conserving Air Indexes for Nearest Neighbor Search
title_full_unstemmed Energy-Conserving Air Indexes for Nearest Neighbor Search
title_sort energy-conserving air indexes for nearest neighbor search
publisher Institutional Knowledge at Singapore Management University
publishDate 2004
url https://ink.library.smu.edu.sg/sis_research/557
http://dx.doi.org/10.1007/b95855
_version_ 1770570478356791296