Method and apparatus for duplicate detection

• US 7,899,825 B2
• Filed: 04/04/2008
• Issued: 03/01/2011
• Est. Priority Date: 06/27/2001
• Status: Expired due to Fees

• Current Assignee: Business Objects Americas (SAP SE)
• Original Assignee: SAP America Incorporated (SAP SE)
• Inventors: Murphy, John, Davis, Mark W., Carter, Paul Grant
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): BURKE, JEFF A
• Application Number:
  US12/098,333
• Publication Number:
  US 20080243837A1
• Time in Patent Office: 1,061 Days
• Field of Search: 707/736, 707/737, 707/754
• US Class Current: 707/737
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

The present invention includes a method and device for detecting duplicate documents by triangulation. Particular aspects of the present invention are described in the claims, specification and drawings.

Claims

1. A computer readable storage medium, comprising executable instructions to:

compute a first measure of similarity between a first document and a reference document, wherein the first measure of similarity is a scalar or a multi-dimensional indication of distance between the first document and the reference document;

compute a second measure of similarity between a second document and the reference document, wherein the second measure of similarity is a scalar or a multi-dimensional indication of distance between the second document and the reference document;

compare the first measure of similarity and the second measure of similarity through triangulation to identify a non-exact similarity match between the first document and the second document; and

perform a direct comparison of the first document and the second document in response to the identified non-exact similarity match to compute a third measure of similarity, wherein the third measure of similarity is a scalar or a multi-dimensional indication of distance between the first document and the second document, and the third measure of similarity has a finer granularity than the first measure of similarity and the second measure of similarity.

2. The computer readable storage medium of claim 1 wherein the executable instructions to compute the first measure of similarity and the second measure of similarity include executable instructions to process a first feature vector associated with the first document, a second feature vector associated with the second document, and a third feature vector associated with the reference document.

3. The computer readable storage medium of claim 1 wherein the executable instructions to compare the first measure of similarity and the second measure of similarity include executable instructions to compare the first measure of similarity and the second measure of similarity to a threshold value.

4. The computer readable storage medium of claim 1 wherein the executable instructions to perform the direct comparison include executable instructions to perform a direct pattern comparison between the first document and the second document.

5. The computer readable storage medium of claim 1 wherein the executable instructions to perform the direct comparison include executable instructions to perform a feature vector comparison between the first document and the second document.

6. The computer readable storage medium of claim 1 wherein both the first measure of similarity and the second measure of similarity are coordinate matching values.

7. The computer readable storage medium of claim 1 wherein both the first measure of similarity and the second measure of similarity are inner product similarity values.

8. The computer readable storage medium of claim 1 wherein both the first measure of similarity and the second measure of similarity are relative term frequency measures.

9. The computer readable storage medium of claim 8 wherein both the first measure of similarity and the second measure of similarity are term frequency-inverse document frequency measures.

10. The computer readable storage medium of claim 1 wherein both the first measure of similarity and the second measure of similarity are cosine measures of angles between n-dimensional vectors.