Show simple item record

dc.contributor.authorGedik, Bugra
dc.contributor.authorSingh, Aameek
dc.contributor.authorLiu, Ling
dc.date.accessioned2004-08-11T19:26:19Z
dc.date.available2004-08-11T19:26:19Z
dc.date.issued2004-05-24
dc.identifier.urihttp://hdl.handle.net/1853/103
dc.description.abstractThe advances in wireless communication and decreasing costs of mobile devices have enabled users to access desired information at any time. Coupled with positioning technologies like GPS, this opens up an exciting domain of location based services, allowing a mobile user to query for objects based on its current position. Main bottlenecks in such infrastructures are the draining of power of the mobile devices and the limited network bandwidth available. To alleviate these problems, broadcasting spatial information about relevant objects has been widely accepted as an efficient mechanism. An important class of queries for such an infrastructure is the k-nearest neighbor (kNN) queries, in which users are interested in k closest objects to their position. Most of the research in kNN queries, use unconventional broadcast indexes and provide only approximate kNN search. In this paper, we describe mechanisms to perform exact kNN search on conventional sequential-access R-trees, and optimize established kNN search algorithms. We also propose a novel use of histograms for guiding the search and derive analytical results on maximum queue size and node access count. In addition, we discuss the effects of different broadcast organizations on search performance and challenge the traditional use of Depth-First (dfs) organization. We also extend our mechanisms to support kNN search with non-spatial constraints. While we demonstrate our ideas using a broadcast index, they are equally applicable to any kind of sequential access medium like tertiary tape storage. We validate our mechanims through an extensive experimental analysis and present our findings.en
dc.format.extent194739 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technology
dc.relation.ispartofseriesCERCS;GIT-CERCS-04-18
dc.subjectkNN
dc.subjectk-Nearest neighbor queries
dc.subjectBandwidth
dc.subjectGPS
dc.subjectHistograms
dc.subjectLocation-based services
dc.subjectMobile devices
dc.subjectMobile networks
dc.subjectPositioning technologies
dc.titleEnergy Efficient Exact kNN Search in Wireless Broadcast Environmentsen
dc.typeTechnical Report


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record