Selectivity Estimation for Boolean Queries Zhiyuan Chen, Flip Korn, Nick Koudas, and S. Muthukrishnan   View Paper (PDF)   Return to Range Queries / Selectivity Estimation Abstract In a variety of applications ranging from optimizing queries on alphanumeric attributes to providing approximate counts of documents containing several query terms, there is an increasing need to quickly and reliably estimate the number of strings (tuples, documents, etc.) matching a Boolean query. Boolean queries in this context consist of substring predicates composed using Boolean operators. While there has been some work in estimating the selectivity of substring queries, the more general problem of estimating the selectivity of Boolean queries over substring predicates has not been studied. Our approach is to extract selectivity estimates from relationships between the substring predicates of the Boolean query. However, storing the correlation between all possible predicates in order to provide an exact answer to such predicates is clearly infeasible, as there is a super-exponential number of possible combinations of these predicates. Instead, our novel idea is to capture correlations in a space-efficient but approximate manner. We employ a Monte Carlo technique called set hashing to succinctly represent the set of strings containing a given substring as a signature vector of hash values. Correlations among substring predicates can then be generated on-the-fly by operating on these signatures. We formalize our approach and propose an algorithm for estimating the selectivity of any Boolean query using the signatures of its substring predicates. We then experimentally demonstrate the superiority of our approach over a straight-forward approach based on the independence assumption wherein correlations are not explicitly captured. References Note: References link to DBLP on the Web. [1] ... [2] Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher : Min-Wise Independent Permutations (Extended Abstract). STOC 1998 : 327-336 [3] ... [4] ... [5] Edith Cohen : Size-Estimation Framework with Applications to Transitive Closure and Reachability. JCSS 55(3) : 441-453(1997) [6] Edith Cohen , Mayar Datar , Shinji Fujiwara , Aristides Gionis , Piotr Indyk , Rajeev Motwani , Jeffrey D. Ullman , Cheng Yang : Finding Interesting Associations without Support Pruning. ICDE 2000 : 489-499 [7] William B. Frakes , Ricardo A. Baeza-Yates (Eds.): Information Retrieval: Data Structures & Algorithms. Prentice-Hall 1992, ISBN 0-13-463837-9 Contents [8] H. V. Jagadish , Olga Kapitskaia , Raymond T. Ng , Divesh Srivastava : Multi-Dimensional Substring Selectivity Estimation. VLDB 1999 : 387-398 [9] H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Viswanath Poosala , Kenneth C. Sevcik , Torsten Suel : Optimal Histograms with Quality Guarantees. VLDB 1998 : 275-286 [10] H. V. Jagadish , Raymond T. Ng , Divesh Srivastava : Substring Selectivity Estimation. PODS 1999 : 249-260 [11] P. Krishnan , Jeffrey Scott Vitter , Balakrishna R. Iyer : Estimating Alphanumeric Selectivity in the Presence of Wildcards. SIGMOD Conf. 1996 : 282-293 [12] ... [13] Edward M. McCreight : A Space-Economical Suffix Tree Construction Algorithm. JACM 23(2) : 262-272(1976) [14] ... [15] Gerard Salton , Michael McGill : Introduction to Modern Information Retrieval. McGraw-Hill Book Company 1984, ISBN 0-07-054484-0 [16] ... [17] ... [18] Bienvenido Vélez , Ron Weiss , Mark A. Sheldon , David K. Gifford : Fast and Effective Query Refinement. SIGIR 1997 : 6-15 [19] Min Wang , Jeffrey Scott Vitter , Balakrishna R. Iyer : Selectivity Estimation in the Presence of Alphanumeric Correlations. ICDE 1997 : 169-180 BIBTEX @inproceedings{DBLP:conf/pods/ChenKKM00,   author    = {Zhiyuan Chen and                 Flip Korn and                 Nick Koudas and                 S. Muthukrishnan},    title     = {Selectivity Estimation for Boolean Queries},    booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium                 on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,                 USA},    publisher = {ACM},    year      = {2000},    isbn      = {1-58113-214-X},    pages     = {216-225},    crossref  = {DBLP:conf/pods/00},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.