METHOD FOR DETERMINING NEAR DUPLICATE DATA OBJECTS

• US 20090028441A1
• Filed: 07/07/2005
• Published: 01/29/2009
• Est. Priority Date: 07/21/2004
• Status: Active Grant

• Current Assignee: Microsoft Israel Research And Development (2002) Ltd (Microsoft Corporation)
• Original Assignee: Equivio Ltd. (Microsoft Corporation)
• Inventors: Milo, Amir, Ravid, Yiftach
• Granted Patent: US 8,015,124 B2
• Time in Patent Office: Days
• US Class Current: 382/218
• 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 object B is a candidate for near duplicate to an object A with a given similarity level th, comprising

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

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

for any functions ƒ

_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 objects being documents.

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

said at least one characteristics being that ƒ

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

(ƒ

,th)=α

(th)·

|max-min|.

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

said at least one characteristics 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).

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

6. The method according to claim 2 wherein said documents are Microsoft office®

documents.

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

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

9. The method according to claim 3, wherein α

(th)=1-th.

10. The method according to claim 4, wherein α

(th)=1-th.

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

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

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

14. The method according to claim 13, 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.

15. The method according to claim 13, wherein said distance function 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.

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

17. The method according to any one of the preceding claims, wherein at least two of said functions are of different type.

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

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

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

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

ii) calculating a signature for the object;

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

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

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

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

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

23. The method according to claim 22, wherein the additional calculation phase including calculating a Resemblance between two documents.

24. The method according to claim 22, 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 objects by calculating number of shingles that reside in either objects;

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

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

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

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

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

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

28. The method according to claim 27, wherein said (ii) further comprising

(1) providing additional at least one function capable of discerning between objects which were classified as candidates for near duplicate in a first phase, but did not meet said criterion in the additional phase;

and

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

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

30. The method according to any one of the preceding claims, further comprising:

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

31. 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.

32. The method according to claim 31, wherein said applications are marketed as a stand alone application.

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

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

48. A computer product comprising a storage for storing computer code portions capable of performing the method stages according to claim 1.

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

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

i) providing at least two different bounded functions ƒ

on 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;

iii) calculating a rank=ƒ

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

iv) 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 (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 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.

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

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

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

38. The method according to claim 36, 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 objects by calculating number of shingles that reside in either objects;

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

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

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

49. A computer product comprising a storage for storing computer code portions capable of performing the method stages according to claim 34.

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

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

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

(ii) determining that at least one objects 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. A computer product comprising a storage for storing computer code portions capable of performing the method stages according to claim 42.

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

43. A method for determining that at least one object B is a candidate for near duplicate to an object A, comprising (i) providing at least two different functions on an object, each function having a numeric function value;

(ii) determining that at least one objects 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.

44. The method according to claim 43, 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).

51. A computer product comprising a storage for storing computer code portions capable of performing the method stages according to claim 43.

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

45. A system for determining that at least one object B is a candidate for 30 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 objects 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.

46. The system according to claim 45, 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.

47. 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 objects 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.