GIT-CERCS-04-18
Bugra Gedik, Aameek Singh, Ling Liu,
Energy Efficient Exact kNN Search in Wireless Broadcast Environments
The 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.