Patent ID: 8161046

Claim:
A selectivity estimation system, comprising: a memory that stores computer-executable components including: a user interface component configured to obtain a search query; and a query component configured to estimate a number of data incidents in a data store that resemble the search query based on a pre-specified similarity function and a criterion defined by the search query, wherein the query component comprises: an evaluation component configured to generate an inverted index comprising a plurality of inverted lists by decomposition of data incidents in the data store that resemble the search query into a set, comprising at least one token, and generate a list comprising a partial weight for respective tokens of the at least one token and a set identification for respective data incidents in the data store that resemble the search query; and a sample construction component configured to select a hash function that imposes a random permutation of elements in a domain of set identifications from a plurality of universal hash functions, and sample, from an inverted list of the plurality of inverted lists, a subset of the set identifications with respective hash values less than a threshold; and a processor that facilitates execution of at least one of the computer-executable components.