Patent · US Active

Classification-based method and apparatus for string selectivity estimation

US7987180B2 · kind B2 · utility

5Cited by

4References

19Claims

0Family size

Assignee

International Business Machines Corporation · US

Inventors

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

Key dates

Filing date	Mar 28, 2008
Grant date	Jul 26, 2011
Priority date	—
Expiry date	Aug 21, 2029

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 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.

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