Disk-based probabilistic set-similarity indexes

Details Disk-based probabilistic set-similarity indexes Disk-based probabilistic set-similarity indexes

2007-06-12

2009-10-27

Trujillo, James (Department: 2159)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

07610283

ABSTRACT:
Input set indexing for set-similarity lookups. The architecture provides input to an indexing process that enables more efficient lookups for large data sets (e.g., disk-based) without requiring a full scan of the input. A new index structure is provided, the output of which is exact, rather than approximate. The similarity of two sets is specified using a similarity function that maps two sets to a numeric value that represents similarity of the two sets. Threshold-based lookups are addressed where two sets are considered similar if the numeric similarity score is above a threshold. The structure efficiently identifies all input sets within a distance k (e.g., a hamming distance) of the query set. Additional information in the form of frequency of elements (the number of input sets in which an element occurs) is used to improve index performance.

REFERENCES:
patent: 5497486 (1996-03-01), Stolfo et al.
patent: 6032146 (2000-02-01), Chadha et al.
patent: 6236985 (2001-05-01), Aggarwal et al.
patent: 6260038 (2001-07-01), Martin et al.
patent: 6675174 (2004-01-01), Bolle et al.
patent: 6681222 (2004-01-01), Kabra et al.
patent: 6922700 (2005-07-01), Aggarwal et al.
patent: 7031555 (2006-04-01), Troyanker
patent: 7043474 (2006-05-01), Mojsilovic et al.
patent: 2004/0260694 (2004-12-01), Chaudhuri et al.
patent: 2005/0262144 (2005-11-01), Teng et al.
patent: 2007/0094024 (2007-04-01), Kristensson et al.
White, et al., “Similarity Indexing with the SS-tree”, IEEE, 1996, pp. 516-523.
White, et al., “Similarity Indexing: Algorithms and Performance”, Proceedings SPIE, vol. 2670, pp. 1-12.
Seidl, et al., “Optimal Multi-Step k-Nearest Neighbor Search”, SIGMOD'98, ACM, 1998, pp. 154-165.
Katayama, et al., “The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries”, SIGMOD'97, ACM, 1997, pp. 369-380.

Affiliated with

Also associated with

Rating

Disk-based probabilistic set-similarity indexes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Disk-based probabilistic set-similarity indexes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Disk-based probabilistic set-similarity indexes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4055245