Energy-Conserving Air Indexes for Nearest Neighbor Search

Baihua Zheng, Jianliang Xu, Wang Chien Lee, Dik Lun Lee

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

23 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT 2004
Subtitle of host publication9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14-18, 2004
EditorsElisa Bertino, Stavros Christodoulakis, Dimitris Plexousakis, Vassilis Christophides, Manolis Koubarakis, Klemens Böhm, Elena Ferrari
PublisherSpringer Berlin Heidelberg
Number of pages19
ISBN (Electronic)9783540247418
ISBN (Print)9783540212003
Publication statusPublished - Mar 2004
Event 9th International Conference on Extending Database Technology, EDBT 2004 - Heraklion, Crete, Greece
Duration: 14 Mar 200418 Mar 2004 (Link to conference proceedings)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference 9th International Conference on Extending Database Technology, EDBT 2004
CityHeraklion, Crete
Internet address

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • mobile computing
  • location-based services
  • energy-conserving index
  • nearest-neighbor search
  • wireless broadcast


Dive into the research topics of 'Energy-Conserving Air Indexes for Nearest Neighbor Search'. Together they form a unique fingerprint.

Cite this