US 7,010,522 B1Granted

Method of performing approximate substring indexing

AssigneeAT&T Corp.

InventorsHosagrahar Visvesvaraya Jagadish, Nikolaos Koudas, Shanmugavelayutham Muthukrishnan, Divesh Srivastava

Life of this patent

Estimating the term…

Loading patent…

Abstract

Approximate substring indexing is accomplished by decomposing each string in a database into overlapping “positional q-grams”, sequences of a predetermined length q, and containing information regarding the “position” of each q-gram within the string (i.e., 1st q-gram, 4th q-gram, etc.). An index is then formed of the tuples of the positional q-gram data (such as, for example, a B-tree index or a hash index). Each query applied to the database is similarly parsed into a plurality of positional q-grams (of the same length), and a candidate set of matches is found. Position-directed filtering is used to remove the candidates which have the q-grams in the wrong order and/or too far apart to form a “verified” output of matching candidates. If errors are permitted (defined in terms of an edit distance between each candidate and the query), an edit distance calculation can then be performed to produce the final set of matching strings.

Claims10

Dependent claims

A method of indexing a query substring Q against a collection of data strings in a database D, the method comprising the steps of:

a) preprocessing each string σ in database D to generate a plurality of overlapping q-grams of a predetermined length q augmenting each q-gram with information indicating its position within string σ to form a tuple comprising the position information and the q-gram, and creating an index of the positional q-gram tuple;
b) parsing the query substring Q into a plurality of overlapping positional q-grams of length q;
c) searching each index in database D to retrieve potential matches between the query Q substring plurality of overlapping q-grams and the preprocessed database D plurality of overlapping q-grams, a potential match defined as having a predetermined number of matching overlapping q-grams;
d) applying position-directed filtering to the potential matches retrieved in step c) to form a candidate set including only those potential matches with at least some q-grams in the same position order as substring query Q
e) defining a predetermined maximum edit distance k between the query substring Q and database D;
f) after applying the position-directed filtering, calculating the edit distance between each candidate substring and the query substring;
and
g) verifying the candidate set by removing from the candidate set each candidate substring having an edit distance greater than k.

5 more elements

Dependencies are inferred from the claim text.