Independence is good: dependency-based histogram synopses for high-dimensional data

ABSTRACT

Approximating the joint data distribution of a multi-dimensional data set through a compact and accurate histogram synopsis is a fundamental problem arising in numerous practical scenarios, including query optimization and approximate query answering. Existing solutions either rely on simplistic independence assumptions or try to directly approximate the full joint data distribution over the complete set of attributes. Unfortunately, both approaches are doomed to fail for high-dimensional data sets with complex correlation patterns between attributes. In this paper, we propose a novel approach to histogram-based synopses that employs the solid foundation of statistical interaction models to explicitly identify and exploit the statistical characteristics of the data. Abstractly, our key idea is to break the synopsis into (1) a statistical interaction model that accurately captures significant correlation and independence patterns in data, and (2) a collection of histograms on low-dimensional marginals that, based on the model, can provide accurate approximations of the overall joint data distribution. Extensive experimental results with several real-life data sets verify the effectiveness of our approach. An important aspect of our general, model-based methodology is that it can be used to enhance the performance of other synopsis techniques that are based on data-space partitioning (e.g., wavelets) by providing an effective tool to deal with the “dimensionality curse”.

REFERENCES

• 1: Y. M.M. Bishop, S. E. Fienberg, and P. W. Holland. "Discrete Multivariate Analysis". The MIT Press, 1975.
• 2: J. R.S. Blair and B. Peyton. "An Introduction to Chordal Graphs and Clique Trees". In "Graph Theory and Sparse Matrix Computation". Springer-Verlag NY, Inc., 1993.
• 3: Kaushik Chakrabarti , Minos N. Garofalakis , Rajeev Rastogi , Kyuseok Shim, Approximate Query Processing Using Wavelets, Proceedings of the 26th International Conference on Very Large Data Bases, p.111-122, September 10-14, 2000
• 4: R. Christensen. "Log-Linear Models and Logistic Regression". Springer-Verlag NY, Inc. (Springer Series in Statistics), 1997.
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: J.N. Darroch, S.L. Lauritzen, and T.P. Speed. "Markov Fields and Log-Linear Interaction Models for Contigency Tables". The Annals of Statistics, 8(3):522-539, 1980.
• 7: A. Deshpande, M. Garofalakis, and R. Rastogi. "Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data". Bell Labs Tech. Report, 2001.
• 8: D. Edwards. Personal Communication, September 2000.
• 9: Christos Faloutsos , Ibrakim Kamel, Relaxing the uniformity and independence assumptions using the concept of fractal dimension, Journal of Computer and System Sciences, v.55 n.2, p.229-240, Oct. 1997 [doi>10.1006/jcss.1997.1522]
• 10: B. Fox. "Discrete Optimization Via Marginal Analysis". Management Science, 13(3):211-216, 1966.
• 11: Dimitrios Gunopulos , George Kollios , Vassilis J. Tsotras , Carlotta Domeniconi, Approximating multi-dimensional aggregate range queries over real attributes, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.463-474, May 15-18, 2000, Dallas, Texas, United States
• 12: Toshihide Ibaraki , Naoki Katoh, Resource allocation problems: algorithmic approaches, MIT Press, Cambridge, MA, 1988
• 13: Yannis E. Ioannidis , Stavros Christodoulakis, Optimal histograms for limiting worst-case error propagation in the size of join results, ACM Transactions on Database Systems (TODS), v.18 n.4, p.709-748, Dec. 1993 [doi>10.1145/169725.169708]
• 14: Finn V. Jensen and Frank Jensen. "Optimal Junction Trees". In Proc. of the 10th Annual Conf. on Uncertainty in AI, 1994.
• 15: Francesco M. Malvestuto. "Approximating Discrete Probability Distributions with Decomposable Models". IEEE Trans. on Systems, Man, and Cybernetics, 21(5):1287-1294, 1991.
• 16: S. Muthukrishnan , Viswanath Poosala , Torsten Suel, On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity, and Applications, Proceeding of the 7th International Conference on Database Theory, p.236-256, January 10-12, 1999
• 17: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 18: 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
• 19: 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
• 20: J. Whittaker. "Graphical Models in Applied Multivariate Statistics". John Wiley & Sons, Inc., 1990.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

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

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory