A learning-based approach to estimate statistics of operators in continuous queries: a case study

ABSTRACT

Statistic estimation such as output size estimation of operators is a well-studied subject in the database research community, mainly for the purpose of query optimization. The assumption, however, is that queries are ad-hoc and therefore the emphasis has been on capturing the data distribution. When long standing continuous queries on a changing database are concerned, a more direct approach, namely building an estimation model for each operator, is possible. In this paper, we propose a novel learning-based method. Our method consists of two steps. The first step is to design a dedicated feature extraction algorithm that can be used incrementally to obtain feature values from the underlying data. The second step is to use a data mining algorithm to generate an estimation model based on the feature values extracted from the historical data. To illustrate the approach, this paper studies the case of similarity-based searches over streaming time series. Experimental results show this approach provides accurate statistic estimates with a low overhead.

REFERENCES

• 1: Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993
• 2: Rakesh Agrawal , King-Ip Lin , Harpreet S. Sawhney , Kyuseok Shim, Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.490-501, September 11-15, 1995
• 3: 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]
• 4: Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603884]
• 5: Chungmin Melvin Chen , Nick Roussopoulos, Adaptive selectivity estimation using query feedback, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.161-172, May 24-27, 1994, Minneapolis, Minnesota, United States
• 6: J. Chen, D. J. DeWitt, and J. F. Naughton. Design and evaluation of alternative selection placement strategies in optimizing continuous queries. In ICDE Conference, 2002.
• 7: 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
• 8: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• 9: Like Gao , X. Sean Wang, Continually evaluating similarity-based pattern queries on a streaming time series, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564734]
• 10: Like Gao , Zhengrong Yao , X. Sean Wang, Evaluating continuous nearest neighbor queries for streaming time series via pre-fetching, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584872]
• 11: Minos Garofalakis , Johannes Gehrke , Rajeev Rastogi, Querying and mining data streams: you only get one look a tutorial, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564794]
• 12: Dimitrios Gunopulos , Gautam Das, Time series similarity measures (tutorial PM-2), Tutorial notes of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.243-307, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/349093.349108]
• 13: Banchong Harangsri , John Shepherd , Anne H. H. Ngu, Query Size Estimation Using Machine Learning, Proceedings of the Fifth International Conference on Database Systems for Advanced Applications (DASFAA), p.97-106, April 01-04, 1997
• 14: E. Keogh, K. Chakrabarti, M. Pazzani, and S. Mehrotra. Dimensionality reduction for fast similarity search in large time series databases. Knowledge and Information Systems, 3(3):263--286, 2000.
• 15: Robert Philip Kooi, The optimization of queries in relational databases, 1980
• 16: Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider, Practical selectivity estimation through adaptive sampling, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.1-11, May 23-26, 1990, Atlantic City, New Jersey, United States
• 17: Differential evaluation of continual queries, Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96), p.458, May 27-30, 1996
• 18: Ling Liu , Calton Pu , Wei Tang, Continual Queries for Internet Scale Event-Driven Information Delivery, IEEE Transactions on Knowledge and Data Engineering, v.11 n.4, p.610-628, July 1999 [doi>10.1109/69.790816]
• 19: S. Madden and M. J. Franklin. Fjording the stream: An architecture for queries over streaming sensor data. In ICDE Conference, 2002.
• 20: Samuel Madden , Mehul Shah , Joseph M. Hellerstein , Vijayshankar Raman, Continuously adaptive continuous queries over streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564698]
• 21: Yossi Matias , Jeffrey Scott Vitter , Min Wang, Wavelet-based histograms for selectivity estimation, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.448-459, June 01-04, 1998, Seattle, Washington, United States
• 22: Alan V. Oppenheim , Ronald W. Schafer, Discrete-time signal processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 23: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 24: Davood Rafiei , Alberto Mendelzon, Similarity-based queries for time series data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.13-25, May 11-15, 1997, Tucson, Arizona, United States
• 25: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 26: Wei Sun , Yibei Ling , Naphtali Rishe , Yi Deng, An instant and accurate size estimation method for joins and selections in a retrieval-intensive environment, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.79-88, May 25-28, 1993, Washington, D.C., United States
• 27: Jeffrey D. Taft. The Sliding DFT Page. On-line. http://www.nauticom.net/www/jdtaft/DFT_increm.htm.
• 28: 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
• 29: Stratis D. Viglas , Jeffrey F. Naughton, Rate-based query optimization for streaming information sources, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564697]