Patent · US Active

Classification-based method and apparatus for string selectivity estimation

US7395270B2 · kind B2 · utility

25Cited by

4References

1Claims

0Family size

Assignee

International Business Machines Corporation · US

Inventors

Lipyeow Lim · North White Plains, US
Min Wang · San Jose, US

Key dates

Filing date	Jun 26, 2006
Grant date	Jul 1, 2008
Priority date	—
Expiry date	Mar 2, 2027

Classification

Technology area (CPC Y)Emerging Cross-Sectional Technologies
CPC primaryY10S707/99942
WIPO fieldComputer technology
WIPO sectorElectrical engineering

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 partitions the collection 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.

Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.