Methods and apparatus for estimating similarity

Details Methods and apparatus for estimating similarity Methods and apparatus for estimating similarity

2007-01-02

2007-01-02

Robinson, Greta (Department: 2168)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

10029883

ABSTRACT:
A similarity engine generates compact representations of objects called sketches. Sketches of different objects can be compared to determine the similarity between the two objects. The sketch for an object may be generated by creating a vector corresponding to the object, where each coordinate of the vector is associated with a corresponding weight. The weight associated with each coordinate in the vector is multiplied by a predetermined hashing vector to generate a product vector, and the product vectors are summed. The similarity engine may then generate a compact representation of the object based on the summed product vector.

REFERENCES:
patent: 5067152 (1991-11-01), Kisor et al.
patent: 5101475 (1992-03-01), Kaufman et al.
patent: 5469354 (1995-11-01), Hatakeyama et al.
patent: 5612865 (1997-03-01), Dasgupta
patent: 5794178 (1998-08-01), Caid et al.
patent: 5806061 (1998-09-01), Chaudhuri et al.
patent: 6061734 (2000-05-01), London
patent: 6134532 (2000-10-01), Lazarus et al.
patent: 6349296 (2002-02-01), Broder et al.
patent: 6603470 (2003-08-01), Deering
Moses Sampspn Charikar, “Algorithms for Clustering Problems”, 2001, Stanford University, vol. 62/01-B of Dissertation Abstracts International.
SRC Technical Note; 1997-015; Jul. 25, 1997; “Syntactic Clustering of the Web”; Andrei Z. Broder et al.; pp. 1-14; Digital Equipment Corporation http://gatekeeper.dec.com/pub/DEC/SRC/technical-notes/SRC-1997-015-html/.
“Similarity Search in High Dimensions via Hashing”; Aristides Gionis et al.; Department of Computer Science; Stanford University; pp. 518-529; 1999.
“Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality (preliminary version)”; Piotr Indyk et al.; Department of Computer Science; Stanford University; Jul. 21, 1999; pp. 1-13 and i-vii.
“Chapter 26—Improved approximation algorithms for network design problems”; M.X. Goemans et al.; pp. 223-232.
“Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields”; Jon Kleinberg et al.
“Scalable Techniques for Clustering the Web”; Taher H. Haveliwala et al.
“Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces”; Eyal Kushilevitz et al.; pp. 1-17.
“On the resemblance and containment of documents”; Andrei Z. Broder; Digital Systems Research Center; Palo Alto, CA; pp. 1-9.

Affiliated with

Also associated with

Rating

Methods and apparatus for estimating similarity does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods and apparatus for estimating similarity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for estimating similarity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3768803