2013/01/16 by Dmitry Pavlov, Dmitry Y. Pavlov, Pavlov, Dmitry Y. +4
Computer Science · #Advanced Database Systems and Queries #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Data Management and Algorithms #Data Mining Algorithms and Applications #Databases (cs.DB) #FOS: Computer and information sciences #cs.AI #cs.DB
paper · pdf · doi:10.48550/arxiv.1301.3884
Appears in Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence (UAI2000)
arxiv created 2013/01/16 · openalex publication_date 2013/01/16 · arxiv updated 2013/01/18 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
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.