Energy-Conserving Air Indexes for Nearest Neighbor Search

Publication Type

Conference Proceeding Article

Publication Date

3-2004

Abstract

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.

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

Proc. the 9th International Conference on Extending Database Technology (EDBT'04)

First Page

645

Last Page

646

ISBN

9783540212003

Identifier

10.1007/b95855

Publisher

Springer Verlag

Additional URL

http://dx.doi.org/10.1007/b95855

Link to Full Text

Share

COinS