Method for estimating the probability of collisions of fingerprints

• US 5,974,481 A
• Filed: 09/15/1997
• Issued: 10/26/1999
• Est. Priority Date: 09/15/1997
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Broder, Andrei Zary
• Primary Examiner(s): Pan, Daniel H.
• Application Number:
  US08/929,832
• Time in Patent Office: 771 Days
• Field of Search: 364/715.11, 364/715.09, 395/200.75, 395/835, 395/626, 395/860, 395/20.72, 707/512, 707/513, 707/6, 707/524, 707/540, 370/392, 463/16, 382/294, 382/221, 711/212, 711/216, 710/49, 710/68
• US Class Current: 710/49
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence
• CPC Class Codes: G06F 9/30021 Compare instructions, e.g. Greater-Than, Equal-To, MINMAX

Abstract

Strings, such as Web pages or other documents, are fingerprinted in order to detect substantially similar strings, so as to avoid processing duplicate strings. At the same time determine a computerized method estimates the probability that a collision among fingerprints of dissimilar strings. As fingerprints are generated for strings presented for processing, when the fingerprint of a string is determined not to be identical to any fingerprint in a set of stored fingerprints, the new fingerprint is masked and the unmasked portion of the fingerprint is compared with a corresponding portion of the fingerprints in the stored set. Information is recorded regarding the number of matching masked fingerprints.

Claims

1. A computer implemented method of detecting near-collisions of fingerprints of strings, comprising repeatedly performing the steps of

receiving a string;

applying a one way function to the string to generate a fingerprint;

comparing the generated fingerprint with a set of fingerprints for previously processed strings to generate a comparison result;

processing the received string in accordance with the comparison result;

masking the generated fingerprint to generated a masked fingerprint, the masked fingerprint having an unmasked portion;

detecting near collisions of the generated fingerprint with the fingerprints for previously processed strings by comparing the unmasked portion of the fingerprint with a corresponding portion of the fingerprints for previously processed strings and storing near collision information for each fingerprint of a previously processed string that is not identical to the generated fingerprint and that matches the unmasked portion of the generated fingerprint.

2. The method of claim 1, wherein the received string is a web page having an associated URL and the previously processed strings are web pages each having an associate URL.

3. The method of claim 2, wherein the generated fingerprint consists of a bit string, the unmasked portion of the generated fingerprint comprises a contiguous portion of the bit string.

4. The method of claim 2, wherein:

the generated fingerprint consists of a bit string having a first, fixed number of bits, the masked fingerprint has a masked portion with a second, fixed number of bits; and

the method includes;

for each fingerprint of a previously processed string that is not identical to the generated fingerprint and that matches the unmasked portion of the generated fingerprint, determining how many bits in the masked portion of the generated fingerprint are unequal to corresponding bits of the fingerprint of the previously processed string.

5. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a fingerprinting module for applying a one way function to a string to generate a fingerprint; and

a fingerprint processing module, including;

a first comparison mechanism that compares the generated fingerprint with a set of fingerprints for previously processed strings to generate a comparison result, and directs subsequent processing of the string in accordance with the comparison result; and

a second comparison mechanism that;

masks the generated fingerprint to generated a masked fingerprint, the masked fingerprint having an unmasked portion;

detects near collisions of the generated fingerprint with the fingerprints for previously processed strings by comparing the unmasked portion of the fingerprint with a corresponding portion of the fingerprints for previously processed strings; and

stores near collision information for each fingerprint of a previously processed string that is not identical to the generated fingerprint and that matches the unmasked portion of the generated fingerprint.

6. The computer program product of claim 5, wherein the received string is a web page having an associated URL and the previously processed strings are web pages each having an associate URL.

7. The computer program product of claim 6, wherein the generated fingerprint consists of a bit string, the unmasked portion of the generated fingerprint comprises a contiguous portion of the bit string.

8. The computer program product of claim 6, wherein:

the generated fingerprint consists of a bit string having a first, fixed number of bits, the masked fingerprint has a masked portion with a second, fixed number of bits; and

the second comparison mechanism a mechanism for determining, for each fingerprint of a previously processed string that is not identical to the generated fingerprint and that matches the unmasked portion of the generated fingerprint, how many bits in the masked portion of the generated fingerprint are unequal to corresponding bits of the fingerprint of the previously processed string.