Digital Symposium Collection 2000  

 
 
 
 
 
 

 


















Substring Selectivity Estimation

H. V. Jagadish, Raymond T. Ng, and Divesh Srivastava

  View Paper (PDF)  

Return to Novel Data

Abstract
With the explosion of the Internet, LDAP directories and XML, there is an ever greater need to evaluate queries involving (sub)string matching. Effective query optimization in this context requires good selectivity estimates. In this paper, we use pruned count-suffix trees as the basic framework for substring selectivity estimation. We present a novel technique to obtain a good estimate for a given substring matching query, called MO (for Maximal Overlap), that estimates the selectivity of a query based on all maximal substrings of the query in the pruned count-suffix tree. We show that MO is provably better than the (independence-based) substring se- lectivity estimation technique proposed by Krishnan et al. [6], called KVI, under the natural assumption that strings exhibit the so-called “short memory” property. We complement our analysis with an experiment, using a real AT&T data set, that demonstrates that MO is substantially superior to KVI in the quality of the estimate. Finally, we develop and analyze two selectivity estimation algorithms, MOC and MOLC, based on MO and a constraint-based characterization of all possible completions of a given pruned count-suffix tree. We show that KVI, MO, MOC and MOLC illustrate an interesting tradeoff between estimation accuracy and computational efficiency.


References

Note: References link to DBLP on the Web.

[1]
Mauricio A. Hernández , Salvatore J. Stolfo : The Merge/Purge Problem for Large Databases. SIGMOD Conference 1995 : 127-138
[2]
...
[3]
Yannis E. Ioannidis : Universality of Serial Histograms. VLDB 1993 : 256-267
[4]
Yannis E. Ioannidis , Viswanath Poosala : Balancing Histogram Optimality and Practicality for Query Result Size Estimation. SIGMOD Conference 1995 : 233-244
[5]
H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Viswanath Poosala , Kenneth C. Sevcik , Torsten Suel : Optimal Histograms with Quality Guarantees. VLDB 1998 : 275-286
[6]
P. Krishnan , Jeffrey Scott Vitter , Balakrishna R. Iyer : Estimating Alphanumeric Selectivity in the Presence of Wildcards. SIGMOD Conf. 1996 : 282-293
[7]
Richard J. Lipton , Jeffrey F. Naughton : Query Size Estimation by Adaptive Sampling. PODS 1990 : 40-46
[8]
Edward M. McCreight : A Space-Economical Suffix Tree Construction Algorithm. JACM 23(2) : 262-272(1976)
[9]
M. Muralikrishna , David J. DeWitt : Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries. SIGMOD Conference 1988 : 28-36
[10]
Viswanath Poosala , Yannis E. Ioannidis , Peter J. Haas , Eugene J. Shekita : Improved Histograms for Selectivity Estimation of Range Predicates. SIGMOD Conf. 1996 : 294-305
[11]
...
[12]
Patricia G. Selinger , Morton M. Astrahan , Donald D. Chamberlin , Raymond A. Lorie , Thomas G. Price : Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979 : 23-34
[13]
...
[14]
...
[15]
Peter Weiner : Linear Pattern Matching Algorithms. FOCS 1973 : 1-11

Referenced by

  1. H. V. Jagadish , Olga Kapitskaia , Raymond T. Ng , Divesh Srivastava : Multi-Dimensional Substring Selectivity Estimation. VLDB 1999 : 387-398

BIBTEX

@inproceedings{DBLP:conf/pods/JagadishNS99,
  author    = {H. V. Jagadish and
                Raymond T. Ng and
                Divesh Srivastava},
   title     = {Substring Selectivity Estimation},
   booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium
                on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,
                Pennsylvania},
   publisher = {ACM Press},
   year      = {1999},
   isbn      = {1-58113-062-7},
   pages     = {249-260},
   crossref  = {DBLP:conf/pods/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM