Selectively estimation for Boolean queries

Summary

This work formalizes the approach and proposes an algorithm for estimating the selectivity of any Boolean query using the signatures of its substring predicates, and demonstrates the superiority of this approach over a straight-forward approach based on the independence assumption.

Keywords

Substring, Computer science, Boolean expression, Boolean conjunctive query, Matching (statistics)

References

Multi-Dimensional Substring Selectivity EstimationH. V. Jagadish, Olga Kapitskaia, Raymond T. Ng — 1999
Paths, Flows, and VLSI-LayoutAlexander Schrijver, László Lovász, Bernhard Körte — 1990
Optimal Histograms with Quality GuaranteesH. V. Jagadish, Nick Koudas, S. Muthukrishnan — 1998
Introduction to Modern Information RetrievalGerard Salton, Michael J. McGill — 1983
Size-Estimation Framework with Applications to Transitive Closure and ReachabilityEdith Cohen — 1997
Min-wise independent permutations (extended abstract)Andrei Broder, Moses Charikar, Alan Frieze — 1998
Design and evaluation of incremental data structures and algorithms for dynamic query interfacesEgemen Tanin, Richard Beigel, Ben Shneiderman — 1996
Substring selectivity estimationH. V. Jagadish, Raymond T. Ng, Divesh Srivastava — 1999
Finding interesting associations without support pruningEdith Cohen, Mayur Datar, Shintaro Fujiwara — 2000
Estimating alphanumeric selectivity in the presence of wildcardsP. Krishnan, Jeffrey Scott Vitter, B. R. Iyer — 1996
Fast and effective query refinementBienvenido Vélez, Ron J. Weiss, Mark A. Sheldon — 1997
A Space-Economical Suffix Tree Construction AlgorithmEdward M. McCreight — 1976
Selectivity estimation in the presence of alphanumeric correlationsMin Wang, Jeffrey Scott Vitter, B. R. Iyer — 2002
On the resemblance and containment of documentsArndt Bröder — 1997
Relevance ranking for one to three term queriesCharles L. A. Clarke, Gordon V. Cormack, Elizabeth A. Tudhope — 1997
Min-Wise Independent PermutationsAndrei Broder, Moses Charikar, Alan Frieze — 2000
PAT expressions: an algebra for text searchAiri Salminen, Frank Wm. Tompa — 1994
Relevance ranking for one to three term queriesCharles L. A. Clarke, Gordon V. Cormack, Elizabeth A. Tudhope — 2000
Design and evaluation of incremental data structures and algorithms for dynamic query interfacesEgemen Tanin, Richard Beigel, Ben Shneiderman — 2002
Analysis of a Very Large AltaVista Query LogCraig Silverstein, Monika Henzinger, Hannes Marais — 1998

Cited by

A Sketch-based Sampling Algorithm on Sparse DataPing Li, Kenneth Church, Trevor Hastie — 2006
Selectivity Estimation on Streaming Spatio-Textual Data Using Local CorrelationsXiaoyang Wang, Ying Zhang, Wenjie Zhang — 2014
Template Extraction from Heterogeneous Web PagesK. P. Chaudhari, Miss. Poonam Rangnath Dholi — 2013
Pruning subscriptions in distributed publish/subscribe systemsSven Bittner, Annika Hinze — 2006
Extraction of Template using Clustering from Heterogeneous Web DocumentsRashmi DThakare, Manisha R. Patil — 2015
Using histograms to estimate answer sizes for XML queriesYuqing Wu, Jignesh M. Patel, H. V. Jagadish — 2003
Improved count suffix trees for natural language dataGuido Sautter, Cristina Abba, Klemens Böhm — 2008
Approximate substring selectivity estimationHongrae Lee, Raymond T. Ng, Kyuseok Shim — 2009
Mining database structure; or, how to build a data quality browserTamraparni Dasu, Theodore Johnson, S. Muthukrishnan — 2002
Result-size estimation for information-retrieval subqueriesGuido Sautter, Klemens Böhm, Andranik Khachatryan — 2010
Tracking set-expression cardinalities over continuous update streamsŠumit Ganguly, Minos Garofalakis, Rajeev Rastogi — 2004
Similarity estimation techniques from rounding algorithmsMoses Charikar — 2002
GPGPU: general purpose computation on graphics hardwareDavid Luebke, Mark Harris, Jens Krüger — 2004
An effective candidate generation method for improving performance of edit similarity query processingJongik Kim — 2015
Efficient processing of substring match queries with inverted q-gram indexesYounghoon Kim, Kyoung-Gu Woo, Hyoung-Min Park — 2010
Algorithmics and applications of tree and graph searchingDennis Shasha, Jason T. L. Wang, Rosalba Giugno — 2002
Fast computation of database operations using graphics processorsNaga K. Govindaraju, Brandon Lloyd, Wei Wang — 2005
Fast computation of database operations using graphics processorsNaga K. Govindaraju, Brandon Lloyd, Wei Wang — 2004
Optimized union of non-disjoint distributed data setsItay Dar, Tova Milo, Elad Verbin — 2009
Selectivity Estimation for Fuzzy String Predicates in Large Data SetsLiang Jin, Chen Li — 2005

Related papers

A Boolean extraction technique for multiple-level logic optimizationOh-Hyeong Kwon — 2003
On Partial Differential Encodings, with Application to Boolean CircuitsEdinah K. Gnang — 2020
Non-cancellative Boolean circuits: A generalization of monotone boolean circuitsRimli Sengupta, H. Venkateswaran — 1996
Solving Non-Boolean Satisfiability Problems with Stochastic Local SearchAlan M. Frisch, Timothy J. Peugniez — 2001
A Note on the Inversion Complexity of Boolean Functions in Boolean FormulasHiroki Morizumi — 2008
Construction Method of Probabilistic Boolean Networks Based on Imperfect InformationKatsuaki Umiji, Koichi Kobayashi, Yuh Yamashita — 2019
Redundancy removal and test generation for circuits with non-Boolean primitivesSrimat Chakradhar, S.G. Rothweiler, Vishwani D. Agrawal — 1995
SAT-based group method for verification of logical descriptions with functional indeterminacyЛ. Д. Черемисинова, D. Ya. Novikov — 2010