Energy efficient exact kNN search in wireless broadcast environments

ABSTRACT

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, <i>broadcasting</i> spatial information about relevant objects has been widely accepted as an efficient mechanism. An important class of queries for such an infrastructure is the <i>k</i>-nearest neighbor (<i>k</i>NN) queries, in which users are interested in <i>k</i> closest objects to their position. In this paper, we describe mechanisms to perform <i>exact</i> <i>k</i>NN search on conventional sequential-access R-trees, and optimize established <i>k</i>NN 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 (<i>dfs</i>) organization. We also extend our mechanisms to support <i>k</i>NN 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 mechanisms through an extensive experimental analysis and present our findings.

REFERENCES

• 1: City locations data set. http://www.rtreeportal.org/, October 2003.
• 2: Swarup Acharya , Rafael Alonso , Michael Franklin , Stanley Zdonik, Broadcast disks: data management for asymmetric communication environments, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.199-210, May 22-25, 1995, San Jose, California, United States
• 3: Swarup Acharya , Michael J. Franklin , Stanley B. Zdonik, Disseminating Updates on Broadcast Disks, Proceedings of the 22th International Conference on Very Large Data Bases, p.354-365, September 03-06, 1996
• 4: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 5: Ming-Syan Chen , Philip S. Yu , Kun-Lung Wu, Indexed Sequential Data Broadcasting in Wireless Mobile Computing, Proceedings of the 17th International Conference on Distributed Computing Systems (ICDCS '97), p.124, May 27-30, 1997
• 6: Keith Cheverst , Nigel Davies , Keith Mitchell , Adrian Friday, Experiences of developing and deploying a context-aware tourist guide: the GUIDE project, Proceedings of the 6th annual international conference on Mobile computing and networking, p.20-31, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345916]
• 7: Christos Faloutsos , Timos Sellis , Nick Roussopoulos, Analysis of object oriented spatial access methods, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.426-439, May 27-29, 1987, San Francisco, California, United States
• 8: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 9: Marios Hadjieleftheriou , George Kollios , Vassilis J. Tsotras, Performance evaluation of spatio-temporal selectivity estimation techniques, Proceedings of the 15th international conference on Scientific and statistical database management, p.202-211, July 09-11, 2003, Cambridge, MA [doi>10.1109/SSDM.2003.1214981]
• 10: Susanne E. Hambrusch , Chuan-Ming Liu , Walid G. Aref , Sunil Prabhakar, Query Processing in Broadcasted Spatial Index Trees, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.502-521, July 12-15, 2001
• 11: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 12: Qinglong Hu , Dik Lun Lee , Wang-Chien Lee, Performance evaluation of a wireless hierarchical data dissemination system, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.163-173, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313528]
• 13: T. Imielinski, S. Viswanathan, and B. Badrinath. Energy efficient indexing on air. In ICDE, 1994.
• 14: Yannis E. Ioannidis , Viswanath Poosala, Balancing histogram optimality and practicality for query result size estimation, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.233-244, May 22-25, 1995, San Jose, California, United States
• 15: Dik Lun Lee , Jianliang Xu , Baihua Zheng , Wang-Chien Lee, Data Management in Location-Dependent Information Services, IEEE Pervasive Computing, v.1 n.3, p.65-72, July 2002 [doi>10.1109/MPRV.2002.1037724]
• 16: M. L. Lee, W. Hsu, C. S. Jensen, B. Cui, and K. L. Teo. Supporting frequent updates in R-trees: A bottom-up approach. In VLDB, 2003.
• 17: M. Muralikrishna and D. DeWitt. Equi-depth histograms for estimating selectivity factors for multidimensional queries. In SIGMOD, 1988.
• 18: Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992
• 19: Dong-Joo Park , Hyoung-Joo Kim, An Enhanced Technique for k-Nearest Neighbor Queries with Non-Spatial Selection Predicates, Multimedia Tools and Applications, v.19 n.1, p.79-19, January 2003 [doi>10.1023/A:1021121030238]
• 20: Viswanath Poosala , Peter J. Haas , Yannis E. Ioannidis , Eugene J. Shekita, Improved histograms for selectivity estimation of range predicates, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.294-305, June 04-06, 1996, Montreal, Quebec, Canada
• 21: Qun Ren , Margaret H. Dunham, Using semantic caching to manage location dependent data in mobile computing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.210-221, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345948]
• 22: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 23: Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.331-342, May 15-18, 2000, Dallas, Texas, United States
• 24: Thomas Seidl , Hans-Peter Kriegel, Optimal multi-step k-nearest neighbor search, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.154-165, June 01-04, 1998, Seattle, Washington, United States
• 25: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 26: N. Shivakumar and S. Venkatasubramanian. Energy-efficient indexing for information dissemination in wireless systems. Journal of Mobile Networks and Nomadic Applications, December 1996.
• 27: Yannis Theodoridis , Emmanuel Stefanakis , Timos Sellis, Efficient Cost Models for Spatial Queries Using R-Trees, IEEE Transactions on Knowledge and Data Engineering, v.12 n.1, p.19-32, January 2000 [doi>10.1109/69.842247]
• 28: J. Xu, B. Zheng, W. Lee, and D. Lee. Energy efficient index for querying location-dependent data in mobile broadcast environments. In ICDE, 2003.
• 29: Ping Xuan , Subhabrata Sen , Oscar Gonzalez , Jesus Fernandez , Krithi Ramamritham, Broadcast on Demand: Efficient and Timely Dissemination of Data in Mobile Environments, Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS '97), p.38, June 09-11, 1997
• 30: Baihua Zheng , Wang-Chien Lee , Dik Lun Lee, Search K Nearest Neighbors on Air, Proceedings of the 4th International Conference on Mobile Data Management, p.181-195, January 21-24, 2003

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.m Miscellaneous

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Design, Performance

Keywords:
air indexes, k-nearest neighbor search, wireless data broadcast