TY - GEN
T1 - Energy-conserving air indexes for nearest neighbor search
AU - Zheng, Baihua
AU - XU, Jianliang
AU - Lee, Wang Chien
AU - Lee, Dik Lun
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2004
Y1 - 2004
N2 - 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 energyconserving 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.
AB - 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 energyconserving 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.
KW - Energyconserving index
KW - Location-based services
KW - Mobile computing
KW - Nearest-neighbor search
KW - Wireless broadcast
UR - http://www.scopus.com/inward/record.url?scp=35048884103&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-24741-8_5
DO - 10.1007/978-3-540-24741-8_5
M3 - Conference contribution
AN - SCOPUS:35048884103
SN - 9783540212003
T3 - Lecture Notes in Computer Science
SP - 48
EP - 66
BT - Advances in Database Technology - EDBT 2004
A2 - Bertino, Elisa
A2 - Christodoulakis, Stavros
A2 - Koubarakis, Manolis
A2 - Plexousakis, Dimitris
A2 - Christophides, Vassilis
A2 - Bohm, Klemens
A2 - Ferrari, Elena
PB - Springer Berlin Heidelberg
T2 - 9th International Conference on Extending Database Technology EDBT 2004
Y2 - 14 March 2004 through 18 March 2004
ER -