String predicate selectivity estimation

Details String predicate selectivity estimation String predicate selectivity estimation

2006-12-12

2006-12-12

Mizrahi, Diane D. (Department: 2165)

Data processing: database and file management or data structures

Database design

Data structure types

Reexamination Certificate

active

07149735

ABSTRACT:
A method of estimating selectivity of a given string predicate in a database query. In the method selectivities of substrings of various substring lengths are estimated. For example, the selectivity of substrings between length l (or some constant q) to the length of the given string predicate may be estimated. The method then selects a candidate sub string for each sub string length based on estimated selectivities of the substrings. The estimated selectivities of the candidate substrings are combined. The combined estimated selectivity of the candidate substrings is returned as the estimated selectivity of the given string predicate.

REFERENCES:
patent: 6738755 (2004-05-01), Freytag et al.
patent: 6738762 (2004-05-01), Chen et al.
patent: 6865567 (2005-03-01), Oommen et al.
H.V. Jagadish et al., Multi-dimensional substring selectivity estimation, Proc. of 25th VLDB Conference—ACM, 1999, pp. 387-398.
A. Aboulnaga, A. R. Alameldeen and Jeffrey F. Naughton.Estimating the Selectivity of XML Path Expressions for Internet Scale Applications. In the 27thInternational Conference on Very Large Data Bases, pp. 591-600, 2001.
Z. Chen, F. Korn, N. Koudas and S. Muthukrishnan.Selectivity estimation for Boolean queries. In Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. May 15-17, 2000. Dallas, TX, USA, pp. 216-225. ACM, 2000.
Y. Ioannidis and V. Poosala.Balancing Histogram Optimality and Practicality for Query Result Size Estimation, InProceedings of the 1995 ACM SIGMOD Int'l Conference on Management of Data, San Jose, CA. May 22-25, 1995, pp. 233-244 ACM Press, 1995.
H.V. Jagadish, O. Kapitskaia, R. T. Ng and D. Srivastava.Multi-Dimensional Substring Selectivity Estimation. Proceedings of 25thInt'l Conference on Very Large Data Bases, Sep. 7-10, 1999, Edinburgh, Scotland, UK, pp. 387-398. Morgan Kaufmann, 1999.
H.V. Jagadish, R.T. Ng and D. Srivastava.Substring Selectivity Estimation. In Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 31-Jun. 2, 1999, Philadelphia, Pennsylvania, pp. 249-260. ACM Press 1999.
P. Krishnan, J.S. Scott Vitter and B. Iyer.Estimation Alphanumeric Selectivity in the Presence of Wildcards. InProceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, Jun. 4-6, 1996, pp. 282-293. ACM Press, 1996.
Wei-Yin LohGeneralized, Unbiased, Interaction Detection and Estimation. 2 pages, www.stat.wise.edu/˜loh/guide.html.
L. Lim, M. Wang, S. Padmanabhan, J. Vitter and R. Parr.XpathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation. InProceedings of the 28thInt'l Conference on Very Large Database(VLDB), 12 pages, Hong Kong, Aug. 20-23, 2002.
Wei-Yin Loh.Regression Trees with Unbiased Variable Selection and Interaction Detection. Statistica Sinica(2002) vol. 12, pp. 361-386.

Affiliated with

Also associated with

Rating

String predicate selectivity estimation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with String predicate selectivity estimation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and String predicate selectivity estimation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3657877