SMILE tree: a stream data multi-query indexing technique with level-dimension nodes and extended-range nodes

ABSTRACT

A sensor network consists of a network of sensors that can perform computation and also communicate with each other through wireless communication. Some important characteristics of sensor networks are that the network should be self administered and the power efficiency should be greatly considered due to the fact that it uses battery power. In sensor networks, when large amounts of various stream data is produced and multiple queries need to be processed simultaneously, the power efficiency should be maximized. This work proposes a technique to create an index on multiple monitoring queries so that the multi-query processing performance could be increased and the memory and power could be efficiently used. The proposed SMILE tree modifies and combines the ideas of spatial indexing techniques such as k-d trees and R+-trees. The k-d tree can divide the dimensions at each level, while the R+-tree improves the R-tree by dividing the space into a hierarchical manner and reduces the overlapping areas. By applying the SMILE tree on multiple queries and using it on stream data in sensor networks, the response time for finding an indexed query takes in some cases 50% of the time taken for a linear search to find the query.

REFERENCES

• 1: 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
• 2: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 3: Christian Böhm , Stefan Berchtold , Daniel A. Keim, Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases, ACM Computing Surveys (CSUR), v.33 n.3, p.322-373, September 2001 [doi>10.1145/502807.502809]
• 4: J. Gehrke and S. Madden, "Query Proc00essing in Sensor Networks," IEEE ComSoc, 2004.
• 5: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 6: Kun-Lung Wu , Shyh-Kwei Chen , S. Yu, Query indexing with containment-encoded intervals for efficient stream processing, Knowledge and Information Systems, v.9 n.1, p.62-90, January 2006 [doi>10.1007/s10115-005-0202-0]
• 7: N. Trigoni, Y. Yao, A. Demers, J. Gehrke, and R. Rajaraman. "Multi-query Optimization for Sensor Networks," International Conference on Distributed Computing in Sensor Systems, pp. 307--321, 2005.
• 8: Samuel R. Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TinyDB: an acquisitional query processing system for sensor networks, ACM Transactions on Database Systems (TODS), v.30 n.1, p.122-173, March 2005 [doi>10.1145/1061318.1061322]
• 9: STREAM project, http://infolab.stanford.edu/stream/
• 10: 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
• 11: TinyDB, http://berkeley.intel-research.net/tinydb/

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms

Keywords:
R+-tree, k-d tree, sensor network, spatial indexing techniques, stream data