Energy Efficient Exact kNN Search in Wireless Broadcast Environments

Introduction

In the recent years, there has been significant amount of work in the area of wireless broadcasts. The mobile devices in use today, are not powerful devices and drain their batteries fairly quickly. Also, it is more expensive (in terms of power) for such devices to transmit data as compared to receiving it. Therefore, the idea is to do more data communication in the cheaper direction by broadcasting the data required by various wireless devices. Also, the broadcast has a special index which contains information to let the devices know when the data interesting to them will come and till then, the devices can be switched to the low-power (sleep) mode. Ofcourse, there is a trade-off between power and latency in this scenario.

Such an environment combined with the recent growth of GPS, acts as a fertile ground for a wide variety of mobile services. Now, mobile devices can query the broadcast environment depending upon their physical location (spatial queries). For example, a car can query for the restaurants in a five square mile area or the closest gas station. One of these class of queries is the k nearest neighbor queries (kNN), in which querying device seeks k nearest objects to it. All the literature in this regard either gave approximate answers or limited the value of k to 1 (only nearest neighbor queries). Also, some used new data structures like those based on voronoi diagrams as the structure for the broadcast, whereas typically for a general class of queries, it is always some form of an R-tree.

In this project, we deviced mechanisms to answer exact kNN queries for such wireless broadcast enviroments. In addition, we built our design using the R-tree index structure and utilize small histograms to reduce enery consumption for mobile devices. We also come up with bounds on tune-in time (the time devices had to listen to the broadcast) and the queue size (of buffered packets) at the devices. We discuss various data organization strategies and also evaluate for a mix of spatial and non-spatial queries.

People

Bugra Gedik
Aameek Singh
Ling Liu

Publications

Bugra Gedik, Aameek Singh, Ling Liu, "Energy Efficient Exact kNN Search in Wireless Broadcast Environments", in Proceedings of the 12th International Symposium of ACM GIS, November 2004. |Slides|

Contacts

Bugra Gedik <bgedik[AT]cc.gatech.edu>
Aameek Singh <aameek[AT]aameeksingh.com>

Acknowledgements

This work is partially supported by the National Science Foundation under a CNS Grant, an ITR grant, a Research Infrastructure grant, and a DoE SciDAC grant, an IBM SUR grant, an IBM faculty award, and an HP equipment grant. Any opinions, findings, and conclusions or recommend ations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation or DoE.