Multiplicative synopses for relative-error metrics

ABSTRACT

Existing hierarchical summarization techniques fail to provide synopses good in terms of relative-error metrics. This paper introduces multiplicative synopses: a summarization paradigm tailored for effective relative-error summarization. This paradigm is inspired from previous hierarchical index-based summarization schemes, but goes beyond them by altering their underlying data representation mechanism. Existing schemes have decomposed the summarized data based on sums and differences of values, resulting in what we call additive synopses. We argue that the incapacity of these models to handle relative-error metrics stems exactly from this additive nature of their representation mechanism. We substitute this additive nature by a multiplicative one. We argue that this is more appropriate for achieving low-relative-error data approximations. We develop an efficient linear-time dynamic programming scheme for one-dimensional multiplicative synopsis construction under general relative-error-based metrics, and a special scheme for the case of maximum relative error. We generalize our schemes to higher data dimensionality and we show a surprising additional benefit gained by our special scheme for maximum relative error in this case. In our experimental study, we verify the higher efficacy of our model on relative-error-oriented summarization problems.

REFERENCES

• 1: Ashraf Aboulnaga , Surajit Chaudhuri, Self-tuning histograms: building histograms without looking at data, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.181-192, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 2: Deepak Agarwal , Dhiman Barman , Dimitrios Gunopulos , Neal E. Young , Flip Korn , Divesh Srivastava, Efficient and effective explanation of change in hierarchical summaries, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281197]
• 3: Nicolas Bruno , Surajit Chaudhuri , Luis Gravano, STHoles: a multidimensional workload-aware histogram, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.211-222, May 21-24, 2001, Santa Barbara, California, United States
• 4: Kaushik Chakrabarti , Minos Garofalakis , Rajeev Rastogi , Kyuseok Shim, Approximate query processing using wavelets, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.2-3, p.199-223, September 2001
• 5: Kaushik Chakrabarti , Eamonn Keogh , Sharad Mehrotra , Michael Pazzani, Locally adaptive dimensionality reduction for indexing large time series databases, ACM Transactions on Database Systems (TODS), v.27 n.2, p.188-228, June 2002 [doi>10.1145/568518.568520]
• 6: S. Chen and A. Nucci. Dynamic nonuniform data approximation in databases with Haar wavelet. Journal of Computers, 2(8):64--76, 2007 (also DCC 2007).
• 7: G. Cormode, M. Garofalakis, and D. Sacharidis. Fast approximate wavelet tracking on streams. In EDBT, 2006.
• 8: Antonios Deligiannakis , Minos Garofalakis , Nick Roussopoulos, Extended wavelets for multiple measures, ACM Transactions on Database Systems (TODS), v.32 n.2, p.10-es, June 2007 [doi>10.1145/1242524.1242527]
• 9: Amol Deshpande , Minos Garofalakis , Rajeev Rastogi, Independence is good: dependency-based histogram synopses for high-dimensional data, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.199-210, May 21-24, 2001, Santa Barbara, California, United States
• 10: Minos Garofalakis , Phillip B. Gibbons, Probabilistic wavelet synopses, ACM Transactions on Database Systems (TODS), v.29 n.1, p.43-90, March 2004 [doi>10.1145/974750.974753]
• 11: Minos Garofalakis , Amit Kumar, Wavelet synopses for general error metrics, ACM Transactions on Database Systems (TODS), v.30 n.4, p.888-928, December 2005 [doi>10.1145/1114244.1114246]
• 12: Phillip B. Gibbons , Yossi Matias , Viswanath Poosala, Fast incremental maintenance of approximate histograms, ACM Transactions on Database Systems (TODS), v.27 n.3, p.261-298, September 2002 [doi>10.1145/581751.581753]
• 13: Anna C. Gilbert , Sudipto Guha , Piotr Indyk , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, Fast, small-space algorithms for approximate histogram maintenance, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509966]
• 14: Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Marin J. Strauss, Optimal and approximate computation of summary statistics for range aggregates, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.227-236, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375598]
• 15: Sudipto Guha, On the space---time of optimal, approximate and streaming algorithms for synopsis construction problems, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.6, p.1509-1535, November 2008 [doi>10.1007/s00778-007-0083-9]
• 16: S. Guha and B. Harb. Approximation algorithms for wavelet transform coding of data streams. IEEE Transactions on Information Theory, 54(2):811--830, 2008 (also SODA 2006).
• 17: Sudipto Guha , Piotr Indyk , S. Muthukrishnan , Martin Strauss, Histogramming Data Streams with Fast Per-Item Processing, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.681-692, July 08-13, 2002
• 18: Sudipto Guha , Chulyun Kim , Kyuseok Shim, XWAVE: optimal and approximate extended wavelets, Proceedings of the Thirtieth international conference on Very large data bases, p.288-299, August 31-September 03, 2004, Toronto, Canada
• 19: Sudipto Guha , Nick Koudas , Kyuseok Shim, Approximation and streaming algorithms for histogram construction problems, ACM Transactions on Database Systems (TODS), v.31 n.1, p.396-438, March 2006 [doi>10.1145/1132863.1132873]
• 20: Sudipto Guha , Nick Koudas , Divesh Srivastava, Fast algorithms for hierarchical range histogram construction, 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.543637]
• 21: Sudipto Guha , Hyoungmin Park , Kyuseok Shim, Wavelet synopsis for hierarchical range queries with workloads, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.5, p.1079-1099, August 2008 [doi>10.1007/s00778-007-0052-3]
• 22: Sudipto Guha , Kyuseok Shim , Jungchul Woo, REHIST: relative error histogram construction algorithms, Proceedings of the Thirtieth international conference on Very large data bases, p.300-311, August 31-September 03, 2004, Toronto, Canada
• 23: Dimitrios Gunopulos , George Kollios , J. Tsotras , Carlotta Domeniconi, Selectivity estimators for multidimensional range queries over real attributes, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.2, p.137-154, April 2005 [doi>10.1007/s00778-003-0090-4]
• 24: Yannis E. Ioannidis, Universality of Serial Histograms, Proceedings of the 19th International Conference on Very Large Data Bases, p.256-267, August 24-27, 1993
• 25: H. V. Jagadish , Hui Jin , Beng Chin Ooi , Kian-Lee Tan, Global optimization of histograms, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.223-234, May 21-24, 2001, Santa Barbara, California, United States
• 26: H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Viswanath Poosala , Kenneth C. Sevcik , Torsten Suel, Optimal Histograms with Quality Guarantees, Proceedings of the 24rd International Conference on Very Large Data Bases, p.275-286, August 24-27, 1998
• 27: Panagiotis Karras , Nikos Mamoulis, One-pass wavelet synopses for maximum-error metrics, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 28: P. Karras and N. Mamoulis. The Haar⁺ tree: a refined synopsis data structure. In ICDE, 2007.
• 29: Panagiotis Karras , Dimitris Sacharidis , Nikos Mamoulis, Exploiting duality in summarization with deterministic guarantees, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281235]
• 30: Sanjeev Khanna , S. Muthukrishnan , Steven Skiena, Efficient Array Partitioning, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.616-626, July 07-11, 1997
• 31: Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Optimal histograms for hierarchical range queries (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.196-204, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335223]
• 32: Ju-Hong Lee , Deok-Hwan Kim , Chin-Wan Chung, Multi-dimensional selectivity estimation using compressed histogram information, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.205-214, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 33: Yossi Matias , Daniel Urieli, Optimal workload-based weighted wavelet synopses, Theoretical Computer Science, v.371 n.3, p.227-246, February 2007 [doi>10.1016/j.tcs.2006.11.018]
• 34: 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
• 35: M. Muralikrishna and D. J. DeWitt. Equi-depth histograms for estimating selectivity factors for multi-dimensional queries. In SIGMOD, 1988.
• 36: S. Muthukrishnan. Subquadratic algorithms for workload-aware Haar wavelet synopses. In FSTTCS, 2005.
• 37: S. Muthukrishnan , Viswanath Poosala , Torsten Suel, On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity, and Applications, Proceedings of the 7th International Conference on Database Theory, p.236-256, January 10-12, 1999
• 38: S. Muthukrishnan , Martin Strauss, Rangesum histograms, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 39: S. Muthukrishnan, M. Strauss, and X. Zheng. Workload-optimal histograms on streams. In ESA, 2005.
• 40: S. Muthukrishnan , Torsten Suel, Approximation algorithms for array partitioning problems, Journal of Algorithms, v.54 n.1, p.85-104, January 2005 [doi>10.1016/j.jalgor.2003.11.006]
• 41: Gregory Piatetsky-Shapiro , Charles Connell, Accurate estimation of the number of tuples satisfying a condition, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 42: V. Poosala, V. Ganti, and Y. E. Ioannidis. Approximate query answering using histograms. IEEE Data Eng. Bull., 22(4):5--14, 1999.
• 43: Viswanath Poosala , Yannis E. Ioannidis, Selectivity Estimation Without the Attribute Value Independence Assumption, Proceedings of the 23rd International Conference on Very Large Data Bases, p.486-495, August 25-29, 1997
• 44: 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
• 45: Lin Qiao , Divyakant Agrawal , Amr El Abbadi, RHist: adaptive summarization over continuous data streams, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584870]
• 46: Frederick Reiss , Minos Garofalakis , Joseph M. Hellerstein, Compact histograms for hierarchical identifiers, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 47: U. Srivastava , P. J. Haas , V. Markl , M. Kutsch , T. M. Tran, ISOMER: Consistent Histogram Construction Using Query Feedback, Proceedings of the 22nd International Conference on Data Engineering, p.39, April 03-07, 2006 [doi>10.1109/ICDE.2006.84]
• 48: E. Terzi and P. Tsaparas. Efficient algorithms for sequence segmentation. In SIAM SDM, 2006.
• 49: Nitin Thaper , Sudipto Guha , Piotr Indyk , Nick Koudas, Dynamic multidimensional histograms, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564741]
• 50: Jeffrey Scott Vitter , Min Wang, Approximate computation of multidimensional aggregates of sparse data using wavelets, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.193-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States