Method of performing approximate substring indexing

Details Method of performing approximate substring indexing Method of performing approximate substring indexing

2005-12-21

2008-10-28

Le, Debbie M (Department: 2168)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

07444326

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., 1stq-gram, 4thq-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.

REFERENCES:
patent: 5553272 (1996-09-01), Ranganathan et al.
patent: 5761538 (1998-06-01), Hull
patent: 5852821 (1998-12-01), Chen et al.
patent: 6026398 (2000-02-01), Brown et al.
patent: 6757675 (2004-06-01), Aiken et al.
patent: 6963865 (2005-11-01), Bera
Burkhardt et al (Q-gram Based Database Searching Using a Suffix Array (QUASAR), Copyright ACM 1999).

Affiliated with

Also associated with

Rating

Method of performing approximate substring indexing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of performing approximate substring indexing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of performing approximate substring indexing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4013644