Method for determining near duplicate data objects

• US 8,015,124 B2
• Filed: 07/07/2005
• Issued: 09/06/2011
• Est. Priority Date: 07/21/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Israel Research And Development (2002) Ltd (Microsoft Corporation)
• Original Assignee: Equivio Ltd. (Microsoft Corporation)
• Inventors: Milo, Amir, Ravid, Yiftach
• Primary Examiner(s): Vincent; David R
• Assistant Examiner(s): Tran; Mai T
• Application Number:
  US11/572,441
• Publication Number:
  US 20090028441A1
• Time in Patent Office: 2,252 Days
• Field of Search: 706/21, 707/999.101, 707/999.102
• US Class Current: 706/12
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 40/194 Calculation of difference between files

Abstract

A system for determining that a document B is a candidate for near duplicate to a document A with a given similarity level th. The system includes a storage for providing two different functions on the documents, each function having a numeric function value. The system further includes a processor associated with the storage and configured to determine that the document B is a candidate for near duplicate to the document A, if a condition is met. The condition includes: for any function ƒ_i from among the two functions, ƒ_i(A)−ƒ_i(B)≦δ_i(ƒ,A,th).

Claims

1. A method for determining that at least one data object B is a candidate for near duplicate to a data object A with a given similarity level th, comprising:

(i) providing from a storage at least two different functions on a data object, each function having a numeric function value;

(ii) determining by a processor that at least one data object B is a candidate for near duplicate to a data object A, if a condition is met, the condition includes;

for any function ƒ

_i from among said at least two functions, |ƒ

_i(A)−

ƒ

_i(B)|≦

δ

_i(ƒ

,th), wherein δ

_i is dependent upon at least ƒ

,th.

2. The method according to claim 1, wherein said data objects being documents.

3. The method according to claim 2 wherein said documents include at least text and/or numbers.

4. The method according to claim 2 wherein said documents are word processor documents.

5. The method according to claim 2, wherein said documents are e-mails in selected format.

6. The method according to claim 5, wherein said format being a member selected from a group that includes Microsoft Outlook, Lotus Notes.

7. The method according to claim 2, wherein at least one of said functions being the number of features from known type in a document.

8. The method according to claim 2, for use in one or more members of the group that includes the following applications:

document management, content management, digitization, legal, business intelligence, military intelligence, search engines results pre- and post-processing, archiving, source code comparisons, management of email servers, management of file servers.

9. The method according to claim 8, wherein said applications are marketed as a stand-alone application.

10. The method according to claim 8, wherein said applications are marketed as (OEM).

11. The method according to claim 1, wherein for a function ƒ

said at least one characteristic being that ƒ

is bound by a minimum value min and a maximum value max, and wherein said δ

(ƒ

,th)=α

(th)·

|max−

min|.

12. The method according to claim 11, wherein α

(th)=1−

th.

13. The method according to claim 1, wherein for a function ƒ

said at least one characteristic being that ƒ

is not bound by a minimum value min and a maximum value max, and wherein said δ

is also dependent upon A wherein δ

(ƒ

,th,A)=α

(th)·

ƒ

(A).

14. The method according to claim 13, wherein α

(th)=1−

th.

15. The method according to claim 1, wherein at least one of said functions being a classifier.

16. The method according to claim 15, wherein said classifiers being of a classifier type selected from a group that includes Bayesian Classifier, Decision Trees, Support Vector Machine Classifier.

17. The method according to claim 1, wherein at least one of said functions is a distance function.

18. The method according to claim 17, wherein the providing of distance function includes:

generating for each document a vector of features where each entry in the vector is the frequency/occurrence of the feature, a feature being words from the documents.

19. The method according to claim 17, wherein said distance function is a member of a group that includes:

L^∞

(Maximum distance), L² (Euclidian distance), L¹ (sum of differences), and JS (Jensen-Shannon) distance between the two vectors.

20. The method according to claim 1, wherein said (i) and (ii) are applied on-line in respect of each new received object.

21. The method according to claim 1, further comprising:

providing a database for storing signatures of data objects and determining if a data object has already been processed, including;

i) associating to a data object a respective unique identification code;

ii) calculating a signature for the data object;

iii) checking if the calculated signature is stored in the database in which case the data object has already been processed;

if not applying said (i) and (ii) in respect of the data object and at least one other data object in order to determine whether said data object and at least one other data object are near candidates.

22. The method according to claim 21, wherein said signature being checksum on an object or derivative thereof.

23. The method according to claim 21, wherein said database being hash table.

24. The method according to claim 1, further comprising applying at least one additional calculation phase in order to determine whether candidates of near duplicate data objects meet a criterion for near duplicate data objects.

25. The method according to claim 24, wherein the additional calculation phase including calculating a resemblance between two documents.

26. The method according to claim 24, wherein additional calculation phase including:

i. calculating intersection between two candidates for near duplicate objects by calculating number of shingles that are shared by the two;

ii. calculating union of two candidates for near duplicate data objects by calculating number of shingles that reside in either data objects;

iii. determining that the two data objects are near duplicate by calculating the resemblance, and in case the result exceeding a predetermined value constituting said criterion, the data objects are near duplicate.

27. The method according to claim 26, further comprising, applying an optimization for discarding candidates for near duplicate data objects having a resemblance that drops below said predetermined value.

28. The method according to claim 24, wherein the at least one additional calculation phase is slower than the calculation of candidates of near duplicate documents, for any two documents.

29. The method according to claim 1, further comprising:

a) applying at least one additional calculation phase in order to determine whether candidates of near duplicate data objects meet a criterion for near duplicate data objects;

b) applying a learning phase based on data objects that are determined to be candidates for near duplicate, but did not meet the criterion for near duplicate data objects.

30. The method according to claim 29, wherein said (b) further comprisesproviding additional at least one function capable of discerning between data objects which were classified as candidates for near duplicate in a first phase, but did not meet said criterion in the additional phase;

and

applying (a) and (b) for determining candidates for near duplicate, for any function from among said at least two functions and the additional at least one function.

31. The method according to claim 30, wherein at least one of said additional functions being a classifier.

32. The method according to claim 1, further comprising:

applying said (i) and (ii) in respect of more than two data objects in order to determine whether at least two of said data objects are near duplicate.

33. The method according to claim 1, wherein at least two of said functions are of different type.

34. The method according to claim 1, wherein said condition is implemented using bucket data structure.

35. The method according to claim 1, wherein said data objects being voice data, and further comprising, converting said data objects to respective text based documents.

36. A method for determining that a document A is a candidate for near duplicate to at least one other document B, comprising:

i) providing from a storage at least two different bounded functions fon document, and for each classifier providing a vector with n buckets where n is a function of th, each of size 1/n

ii) receiving the document A, associating a unique document id to the document, and calculating a list of features by a processor;

iii) calculating by the processor a rank=ƒ

(A), where A being the list of features of the documents;

iv) calculating by the processor, add document id to buckets in the vector, as follows;

Floor(n·

rank) (if greater than zero, otherwise discard this option), Floor(n·

rank)+1, and Floor(n·

rank)+2 (if less than n, otherwise discard this option)

v) calculating union on documents id in the buckets, giving rise to set of documents id;

vi) applying by the processor (ii)-(v), in respect to a different classifier from among said at least two classifiers, giving rise to respective at least two sets of documents id;

vii) applying by the processor intersection to the at least two of the sets, stipulated in (vi), giving rise to at least two documents id, if any, being candidates for near duplicate.

37. The method according to claim 36, wherein said list of features being 1-grams, 2-grams, 3-grams, . . . , n-grams, where n is selected.

38. The method according to claim 36, further comprising

applying at least one additional calculation phase in order to determine whether candidates of near duplicate documents meet a criterion for near duplicate documents.

39. The method according to claim 38, wherein the additional calculation phase including calculating the resemblance to verify the near-equivalence.

40. The method according to claim 38, wherein additional calculation phase including:

i) calculating intersection between two candidates for near duplicate documents by calculating number of shingles that are shared by the two;

ii) calculating union of two candidates for near duplicate documents by calculating number of shingles that reside in either documents;

iii) determining that the two documents are near duplicate by calculating intersection divided by union, and in case the result exceeding a predetermined value constituting said criterion, the documents are near duplicate.

41. The method according to claim 40, further comprising, applying an optimization for discarding candidates for near duplicate documents having a shingle ratio that drops below said predetermined value.

42. The method according to claim 38, wherein the at least one additional calculation phase is slower than the calculation of candidates of near duplicate documents, for any two documents.

43. The method according to claim 36, wherein said documents being voice data, and further comprising, converting said documents to respective text based documents.

44. A method for determining that at least one data object B is a candidate for near duplicate to a data object A, comprising

(i) providing from a storage at least two different functions on a data object, each function having a numeric function value;

(ii) determining by a processor that at least one data object B is a candidate for near duplicate to a data object A, if a condition is met, the condition includes;

for any function ƒ

_i from among said at least two functions, |ƒ

_i(A)−

ƒ

_i(B)|≦

δ

_i(ƒ

,A), wherein δ

_i is dependent upon at least ƒ and

A.

45. The method according to claim 44, wherein said documents being voice data, and further comprising, converting said documents to respective text based documents.

46. A method for determining that at least one data object B is a candidate for near duplicate to a data object A, comprising

(i) providing from a storage at least two different functions on a data object, each function having a numeric function value;

(ii) determining by a processor that at least one data object B is a candidate for near duplicate to a data object A, if a condition is met, the condition includes;

for any function ƒ

_i from among said at least two functions a relationship between results of the function when applied to the data objects meets a given score.

47. The method according to claim 46, wherein said relationship being

|ƒ

_i(A)−

ƒ

_i(B)|, and said score being δ

_i(ƒ

,A), wherein δ

_i is dependent upon at least ƒ and

A, and wherein said condition is met if |ƒ

_i(A)−

ƒ

_i(B)|≦

δ

_i(ƒ

,A).

48. The method according to claim 46, wherein said documents being voice data, and further comprising, converting said documents to respective text based documents.

49. A system for determining that at least one object B is a candidate for near duplicate to an object A, comprising:

a storage providing at least two different functions on an object, each function having a numeric function value;

a processor associated with said storage and configured to determine that at least one object B is a candidate for near duplicate to an object A, if a condition is met, the condition includes;

for any function ƒ

_i from among said at least two functions, |ƒ

_i(A)−

ƒ

_i(B)|≦

δ

_i(ƒ

,A), wherein δ

_i is dependent upon at least ƒ and

A.

50. The system according to claim 49, wherein said determining that at least one object B is a candidate for near duplicate to an object A with a given similarity level th, and wherein said δ

_i is further dependent upon th.

51. A system for determining that at least one object B is a candidate for near duplicate to an object A, comprising:

a storage providing at least two different functions on an object, each function having a numeric function value;

a processor associated with said storage, configured to determine that at least one object B is a candidate for near duplicate to an object A, if a condition is met, the condition includes;

for any function ƒ

_i from among said at least two functions a relationship between results of the function when applied to the objects meets a given score.