Continuous query processing in data streams using duality of data and queries

ABSTRACT

Recent data stream systems such as TelegraphCQ have employed the well-known property of duality between data and queries. In these systems, query processing methods are classified into two dual categories -- data-initiative and query-initiative -- depending on whether query processing is initiated by selecting a data element or a query. Although the duality property has been widely recognized, previous data stream systems do not fully take advantages of this property since they use the two dual methods independently: data-initiative methods only for continuous queries and query-initiative methods only for ad-hoc queries. We contend that continuous query processing can be better optimized by adopting an approach that integrates the two dual methods. Our primary contribution is based on the observation that spatial join is a powerful tool for achieving this objective. In this paper, we first present a new viewpoint of transforming the continuous query processing problem to a multi-dimensional spatial join problem. We then present a continuous query processing algorithm based on spatial join, which we name Spatial Join CQ. This algorithm processes continuous queries by finding the pairs of overlapping regions from a set of data elements and a set of queries, both defined as regions in the multi-dimensional space. The algorithm achieves the advantages of the two dual methods simultaneously. Experimental results show that the proposed algorithm outperforms earlier algorithms by up to 36 times for simple selection continuous queries and by up to 7 times for sliding window join queries.

REFERENCES

• 1: 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]
• 2: Stefan Berchtold , Christian Böhm , Hans-Peter Kriegal, The pyramid-technique: towards breaking the curse of dimensionality, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.142-153, June 01-04, 1998, Seattle, Washington, United States
• 3: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
• 4: [4] Chandrasekaran, S. and Franklin, M. J., "Streaming Queries over Streaming Data," In Proc. the 28th Int'l Conf. on Very Large Data Bases, Hong Kong, China, pp. 203-214, Aug. 2002.
• 5: [5] Chandrasekaran, S. et al., "TelegraphCQ: Continuous Dataflow Processing for an Uncertain World," In Proc. the First Biennial Conf. on Innovative Data Systems Research, Asiloma, Califonia, pp. 269-280, Jan. 2003.
• 6: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 7: C. Faloutsos , S. Roseman, Fractals for secondary key retrieval, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.247-252, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73746]
• 8: Edward A. Fox , Qi Fan Chen , Amjad M. Daoud , Lenwood S. Heath, Order-preserving minimal perfect hash functions and information retrieval, ACM Transactions on Information Systems (TOIS), v.9 n.3, p.281-308, July 1991 [doi>10.1145/125187.125200]
• 9: Lukasz Golab , M. Tamer Özsu, Issues in data stream management, ACM SIGMOD Record, v.32 n.2, p.5-14, June 2003 [doi>10.1145/776985.776986]
• 10: Eric N. Hanson , Moez Chaabouni , Chang-Ho Kim , Yu-Wang Wang, A predicate matching algorithm for database rule systems, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.271-280, May 23-26, 1990, Atlantic City, New Jersey, United States
• 11: [11] Hinrichs, K. and Nievergelt, J., "The Grid File: A Data Structure Designed to Support Proximity Queries on Spatial Objects," In Proc. Int'l Workshop on Graphtheoretic Concepts in Computer Science, Linz, Austria, pp. 100-113, Aug. 1983.
• 12: Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations, Proceedings of the 23rd International Conference on Very Large Data Bases, p.396-405, August 25-29, 1997
• 13: [13] Kang, J., Naughton, J. F., and Viglas, S. D., "Evaluating Window Joins over Unbounded Streams," In Proc. the 19th IEEE Int'l Conf. on Data Engineering(ICDE), Bangalore, India, pp. 341-352, Mar. 2003.
• 14: Hans-Peter Kriegel , Martin Pfeifle , Marco Pötke , Thomas Seidl, Spatial Query Processing for High Resolutions, Proceedings of the Eighth International Conference on Database Systems for Advanced Applications, p.17, March 26-28, 2003
• 15: Mohamed F. Mokbel , Xiaopeing Xiong , Walid G. Aref, SINA: scalable incremental processing of continuous queries in spatio-temporal databases, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007638]
• 16: [16] Motwani, R. et al., "Query Processing, Approximation, and Resource Management in a Data Stream Management System," In Proc. the First Biennial Conf. on Innovative Data Systems Research, Asiloma, California, pp. 245-256, Jan. 2003.
• 17: J. A. Orenstein , T. H. Merrett, A class of data structures for associative searching, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588037]
• 18: Bernhard Seeger , Hans-Peter Kriegel, Techniques for Design and Implementation of Efficient Spatial Access Methods, Proceedings of the 14th International Conference on Very Large Data Bases, p.360-371, August 29-September 01, 1988
• 19: Ju-Won Song , Kyu-Young Whang , Young-Koo Lee , Min-Jae Lee , Sang-Wook Kim, Spatial Join Processing Using Corner Transformation, IEEE Transactions on Knowledge and Data Engineering, v.11 n.4, p.688-695, July 1999 [doi>10.1109/69.790844]
• 20: Douglas Terry , David Goldberg , David Nichols , Brian Oki, Continuous queries over append-only databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.321-330, June 02-05, 1992, San Diego, California, United States
• 21: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 22: [22] Whang, K.-Y. and Krishnamurthy, R., Multilevel Grid Files, IBM Research Report RC11516, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, Nov. 1985.
• 23: Kyu-Young Whang , Ravi Krishnamurthy, The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure, Proceedings of the Second International Symposium on Database Systems for Advanced Applications, p.449-459, April 02-04, 1991
• 24: [24] Zdonik, S. et al., "The Aurora and Medusa Projects," IEEE Data Engineering Bulletin, Vol. 26, No. 1, pp. 3-10, Mar. 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Experimentation, Performance

Keywords:
batch processing, continuous queries, data streams, duality, spatial join