Probabilistic Models for Query Approximation with Large Sparse Binary Datasets
Dmitry Pavlov, Heikki Mannila, Padhraic Smyth
Large sparse sets of binary transaction data with millions of records and thousands of attributes occur in various domains: customers purchasing products, users visiting web pages, and documents containing words are just three typical examples. Real-time query selectivity estimation (the problem of estimating the number of rows in the data satisfying a given predicate) is an important practical problem for such databases.
We investigate the application of probabilistic models to this problem. In particular, we study a Markov random field (MRF) approach based on frequent sets and maximum entropy, and compare it to the independence model and the Chow-Liu tree model. We find that the MRF model provides substantially more accurate probability estimates than the other methods but is more expensive from a computational and memory viewpoint. To alleviate the computational requirements we show how one can apply bucket elimination and clique tree approaches to take advantage of structure in the models and in the queries. We provide experimental results on two large real-world transaction datasets.
Keywords: Markov random field, maximum entropy, iterative scaling, query selectivity estimation
PS Link: http://www.ics.uci.edu/~datalab/papers/trquery.ps.gz
PDF Link: /papers/00/p465-pavlov.pdf
AUTHOR = "Dmitry Pavlov
and Heikki Mannila and Padhraic Smyth",
TITLE = "Probabilistic Models for Query Approximation with Large Sparse Binary Datasets",
BOOKTITLE = "Proceedings of the Sixteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-00)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "2000",
PAGES = "465--472"