Data processing: database and file management or data structures – Database and file access – Query optimization
Reexamination Certificate
2011-07-26
2011-07-26
Robinson, Greta L (Department: 2169)
Data processing: database and file management or data structures
Database and file access
Query optimization
Reexamination Certificate
active
07987180
ABSTRACT:
Histogram construction and selectivity estimation for string and substring match queries in databases of data having strings associated with attributes. The histogram construction counts string-attribute pairs in the documents, and outputs string-attribute-count triples sorted by count. The collection is partitioned into buckets. A synopsis is generated for the partition, having an average selectivity or count of the string-attribute-count triples in the partition and summary information representing the set of string-attribute pairs belonging to the bucket. Subsequent queries, both for exact and substring matches, use the synopsis to estimate the selectivity of buckets.
REFERENCES:
patent: 6401088 (2002-06-01), Jagadish et al.
patent: 6662184 (2003-12-01), Friedberg et al.
patent: 6865567 (2005-03-01), Oommen et al.
patent: 6876999 (2005-04-01), Hill et al.
patent: 2006/0179052 (2006-08-01), Pauws et al.
Chaudhuri et al., Selectivity Estimation for String Predicates: Overcoming the Underestimation Problem, Proceedings of the 20th International Conference on Data Engineering (published 2004).
Lim et al., XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation, Proceedings of the 28th VLDB Conference (published 2002).
A Query Language for XML; A. Deutsch, et al.; http/www.8.org/w8-papers/lc-xml/query/query.html; pp. 1-18.
XPathLearner; An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation; L. Lim, et al.; Proceedings of the 28th VLDB Conference; Hong Kong, China, 2002 pp. 1-12.
Estimating Answer Sizes for XML Queries; Y. Wu, et al.; pp. 1-18 (Abstract).
Counting Twig Matches in a Tree; Z. Chen, et al.; http:/Informatik.unl-trier.dc/ley/db/Index.html. pp. 1-10.
STATIX; Making XML Count; J. Freire, et al.; ACM SIGMOD Jun. 4-6, 2002; Madison, Wisconsin; Copyright 2002; pp. 1-11.
Bloom Histogram; Path Selectivity Estimation for XML Data With Updates; W. Wang, et al.; Proceedings of the 30th VLDB Conference, Toronto, Canada, 2004; (abstract) pp. 240-251.
Structure and Value Synopses for XML Data Graphs; N. Polyzotis, et al.; Proceedings of the 28th VLDB Conference, Hong Kong, 2002; pp. 1-12.
Statistical Synopses for Graph-Structured XML Database; N. Polyzotis, et al.; ACM SIGMOD, Jun. 4-6, 2002, Madison Wisconsin; pp. 1-12.
Estimating the Selectivity of XML Path Expressions for Internet Scale Applications; A. Aboulnaga, et al.; Proceedings of the 27 VLDB Conference, Roma, Italy, 2001; pp. 1-10.
Lim Lipyeow
Wang Min
Hu Jensen
International Business Machines - Corporation
Kaufman Stephen C.
Robinson Greta L
Whitham Curtis Christofferson & Cook, P.C.
LandOfFree
Classification-based method and apparatus for string... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Classification-based method and apparatus for string..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Classification-based method and apparatus for string... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2735286