Energy-Conserving Air Indexes for Nearest Neighbor Search

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

doi:10.1007/978-3-540-24741-8_5

Energy-Conserving Air Indexes for Nearest Neighbor Search

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

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

23 Citations (Scopus)

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.

Original language	English
Title of host publication	Advances in Database Technology - EDBT 2004
Subtitle of host publication	9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14-18, 2004
Editors	Elisa Bertino, Stavros Christodoulakis, Dimitris Plexousakis, Vassilis Christophides, Manolis Koubarakis, Klemens Böhm, Elena Ferrari
Publisher	Springer Berlin Heidelberg
Pages	48-66
Number of pages	19
Edition	1st
ISBN (Electronic)	9783540247418
ISBN (Print)	9783540212003
DOIs	https://doi.org/10.1007/978-3-540-24741-8_5
Publication status	Published - Mar 2004
Event	9th International Conference on Extending Database Technology, EDBT 2004 - Heraklion, Crete, Greece Duration: 14 Mar 2004 → 18 Mar 2004 https://link.springer.com/book/10.1007/b95855 (Link to conference proceedings)

Publication series

Name	Lecture Notes in Computer Science
Volume	2992
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Conference on Extending Database Technology, EDBT 2004
Country/Territory	Greece
City	Heraklion, Crete
Period	14/03/04 → 18/03/04
Internet address	https://link.springer.com/book/10.1007/b95855 (Link to conference proceedings)

Scopus Subject Areas

Theoretical Computer Science
General Computer Science

User-Defined Keywords

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

Access to Document

10.1007/978-3-540-24741-8_5

Cite this

Zheng, B., Xu, J., Lee, W. C., & Lee, D. L. (2004). Energy-Conserving Air Indexes for Nearest Neighbor Search. In E. Bertino, S. Christodoulakis, D. Plexousakis, V. Christophides, M. Koubarakis, K. Böhm, & E. Ferrari (Eds.), Advances in Database Technology - EDBT 2004: 9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14-18, 2004 (1st ed., pp. 48-66). (Lecture Notes in Computer Science; Vol. 2992). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-24741-8_5

Zheng, Baihua ; Xu, Jianliang ; Lee, Wang Chien et al. / Energy-Conserving Air Indexes for Nearest Neighbor Search. Advances in Database Technology - EDBT 2004: 9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14-18, 2004. editor / Elisa Bertino ; Stavros Christodoulakis ; Dimitris Plexousakis ; Vassilis Christophides ; Manolis Koubarakis ; Klemens Böhm ; Elena Ferrari. 1st. ed. Springer Berlin Heidelberg, 2004. pp. 48-66 (Lecture Notes in Computer Science).

@inproceedings{e6f62ed0104e44cba7502d15f39ac5f9,

title = "Energy-Conserving Air Indexes for Nearest Neighbor Search",

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.",

keywords = "mobile computing, location-based services, energy-conserving index, nearest-neighbor search, wireless broadcast",

author = "Baihua Zheng and Jianliang Xu and Lee, {Wang Chien} and Lee, {Dik Lun}",

note = "Funding information: Jianliang Xu{\textquoteright}s work was supported by the Hong Kong Baptist University under grant number FRG02-03II-34. Publisher copyright: {\textcopyright} 2004 Springer-Verlag Berlin Heidelberg; 9th International Conference on Extending Database Technology, EDBT 2004 ; Conference date: 14-03-2004 Through 18-03-2004",

year = "2004",

month = mar,

doi = "10.1007/978-3-540-24741-8_5",

language = "English",

isbn = "9783540212003",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "48--66",

editor = "Elisa Bertino and Stavros Christodoulakis and Dimitris Plexousakis and Vassilis Christophides and Manolis Koubarakis and Klemens B{\"o}hm and Elena Ferrari",

booktitle = "Advances in Database Technology - EDBT 2004",

edition = "1st",

url = "https://link.springer.com/book/10.1007/b95855",

}

Zheng, B, Xu, J, Lee, WC & Lee, DL 2004, Energy-Conserving Air Indexes for Nearest Neighbor Search. in E Bertino, S Christodoulakis, D Plexousakis, V Christophides, M Koubarakis, K Böhm & E Ferrari (eds), Advances in Database Technology - EDBT 2004: 9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14-18, 2004. 1st edn, Lecture Notes in Computer Science, vol. 2992, Springer Berlin Heidelberg, pp. 48-66, 9th International Conference on Extending Database Technology, EDBT 2004, Heraklion, Crete, Greece, 14/03/04. https://doi.org/10.1007/978-3-540-24741-8_5

Energy-Conserving Air Indexes for Nearest Neighbor Search. / Zheng, Baihua; Xu, Jianliang; Lee, Wang Chien et al.
Advances in Database Technology - EDBT 2004: 9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14-18, 2004. ed. / Elisa Bertino; Stavros Christodoulakis; Dimitris Plexousakis; Vassilis Christophides; Manolis Koubarakis; Klemens Böhm; Elena Ferrari. 1st. ed. Springer Berlin Heidelberg, 2004. p. 48-66 (Lecture Notes in Computer Science; Vol. 2992).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

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

PY - 2004/3

Y1 - 2004/3

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

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

KW - mobile computing

KW - location-based services

KW - energy-conserving index

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 proceeding

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 - Plexousakis, Dimitris

A2 - Christophides, Vassilis

A2 - Koubarakis, Manolis

A2 - Böhm, 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 -

Zheng B, Xu J, Lee WC, Lee DL. Energy-Conserving Air Indexes for Nearest Neighbor Search. In Bertino E, Christodoulakis S, Plexousakis D, Christophides V, Koubarakis M, Böhm K, Ferrari E, editors, Advances in Database Technology - EDBT 2004: 9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14-18, 2004. 1st ed. Springer Berlin Heidelberg. 2004. p. 48-66. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-24741-8_5

Energy-Conserving Air Indexes for Nearest Neighbor Search

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this