A stratified approach to progressive approximate joins

ABSTRACT

Users often do not require a complete answer to their query but rather only a sample. They expect the sample to be either the largest possible or the most representative (or both) given the resources available. We call the query processing techniques that deliver such results 'approximate'. Processing of queries to streams of data is said to be 'progressive' when it can continuously produce results as data arrives. In this paper, we are interested in the progressive and approximate processing of queries to data streams when processing is limited to main memory. In particular, we study one of the main building blocks of such processing: the progressive approximate join. We devise and present several novel progressive approximate join algorithms. We empirically evaluate the performance of our algorithms and compare them with algorithms based on existing techniques. In particular we study the trade-off between maximization of throughput and maximization of representativeness of the sample.

REFERENCES

• 1: Mohammed Al-Kateb , Byung Suk Lee , X. Sean Wang, Reservoir Sampling over Memory-Limited Stream Joins, Proceedings of the 19th International Conference on Scientific and Statistical Database Management, p.23, July 09-11, 2007 [doi>10.1109/SSDBM.2007.40]
• 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: Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603884]
• 4: Don Carney , Uǧur Çetintemel , Mitch Cherniack , Christian Convey , Sangdon Lee , Greg Seidman , Michael Stonebraker , Nesime Tatbul , Stan Zdonik, Monitoring streams: a new class of data management applications, Proceedings of the 28th international conference on Very Large Data Bases, p.215-226, August 20-23, 2002, Hong Kong, China
• 5: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, On random sampling over joins, ACM SIGMOD Record, v.28 n.2, p.263-274, June 1999
• 6: W. G. Cochran. Sampling Techniques, 3rd Edition. John Wiley, 1977.
• 7: Abhinandan Das , Johannes Gehrke , Mirek Riedewald, Approximate join processing over data streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872765]
• 8: Abhinandan Das , Johannes Gehrke , Mirek Riedewald, Semantic Approximation of Data Stream Joins, IEEE Transactions on Knowledge and Data Engineering, v.17 n.1, p.44-59, January 2005 [doi>10.1109/TKDE.2005.17]
• 9: Phillip B. Gibbons, Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports, Proceedings of the 27th International Conference on Very Large Data Bases, p.541-550, September 11-14, 2001
• 10: Michael Greenwald , Sanjeev Khanna, Space-efficient online computation of quantile summaries, ACM SIGMOD Record, v.30 n.2, p.58-66, June 2001
• 11: C. J. Hahn, S. G. Warren, and J. London. Edited synoptic cloud reports from ships and land stations over the globe, 1982--1991, http://cdiac.esd.ornl.gov/ftp/ndp026b, 1996.
• 12: J. Lin. Divergence measures based on the shannon entropy. IEEE Transactions on Information Theory, 37(1):145--151, 1991.
• 13: Gurmeet Singh Manku , Rajeev Motwani, Approximate frequency counts over data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.346-357, August 20-23, 2002, Hong Kong, China
• 14: Mohamed F. Mokbel , Ming Lu , Walid G. Aref, Hash-Merge Join: A Non-blocking Join Algorithm for Producing Fast and Early Join Results, Proceedings of the 20th International Conference on Data Engineering, p.251, March 30-April 02, 2004
• 15: F. Olken. Random Sampling from Databases. Ph.D. dissertation, Computer Science, University of California, 1993.
• 16: Frank Olken , Doron Rotem, Simple Random Sampling from Relational Databases, Proceedings of the 12th International Conference on Very Large Data Bases, p.160-169, August 25-28, 1986
• 17: Yufei Tao , Man Lung Yiu , Dimitris Papadias , Marios Hadjieleftheriou , Nikos Mamoulis, RPJ: producing fast join results on streams through rate-based optimization, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066200]
• 18: W. H. Tok, S. Bressan, and M.-L. Lee. RRPJ : Result-rate based progressive relational join. In DASFAA, pages 43--54, 2007.
• 19: T. Urhan and M. J. Franklin. XJoin: Getting fast answers from slow and bursty networks. Technical Report CS-TR-3994, University of Maryland, 1999.
• 20: Jeffrey S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.37-57, March 1985 [doi>10.1145/3147.3165]

INDEX TERMS

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