US6119124A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for clustering closely resembling data objects
Assignee: AltaVista Co
•
Filing: 1998-03-26
•
Granted: 2000-09-12
•
Expires: 2018-03-26
Abstract
Abstract A computer-implemented method determines the resemblance of data objects such as Web pages. Each data object is partitioned into a sequence of tokens. The tokens are grouped into overlapping sets of the tokens to form shingles. Each shingle is represented by a unique identification element encoded as a fingerprint. A minimum element from each of the images of the set of fingerprints associated with a document under each of a plurality of pseudo random permutations of the set of all fingerprints are selected to generate a sketch of each data object. The sketches characterize the resemblance of the data objects. The sketches can be further partitioned into a plurality of groups. Each group is fingerprinted to form a feature. Data objects that share more than a certain numbers of features are estimated to be nearly identical.
Inventors
- 👤 Andrei Z. Broder
- 👤 Steven C. Glassman
- 👤 Charles G. Nelson
- 👤 Mark S. Manasse
- 👤 Geoffrey G. Zweig
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 06:44
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/35; G06F16/355; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99935; Y10S707/99941; Y10S707/99944
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
112 words
A computer-implemented method of determining the resemblance of a plurality of data objects, comprising the steps of: parsing each data object into a canonical sequence of tokens; grouping overlapping sequences of the tokens of each data object into shingles; assigning a unique identification element to each shingle; permuting the elements of the data objects to form image sets; selecting a predetermined number of minimum elements from each image to form a sketch; partitioning the selected elements of each sketch into a plurality of groups; and assigning another unique identification to each group to generate the features of each data object to determine a level of resemblance of the plurality of data objects.
Claim 2
Dependent Claim
112 words
A computer-implemented method of determining the resemblance of a plurality of data objects, comprising the steps of: parsing each data object into a canonical sequence of tokens; grouping overlapping sequences of the tokens of each data object into shingles; assigning a unique identification element to each shingle; permuting the elements of the data objects to form image sets; selecting a predetermined number of minimum elements from each image to form a sketch; partitioning the selected elements of each sketch into a plurality of groups; and assigning another unique identification to each group to generate the features of each data object to determine a level of resemblance of the plurality of data objects.
Claim 3
Dependent Claim
28 words
The method of claim 1 wherein the sketches are a fixed size and the permuting is a single random permutation of the universe of all of the elements.
Claim 4
Dependent Claim
29 words
The method of claim 1 wherein the size of a particular sketch is proportional to the size of the image set and the permutation is a single random permutation.
Claim 5
Dependent Claim
17 words
The method of claim 3 further including the step of determining a containment of the data objects.
Claim 6
Dependent Claim
43 words
The method of claim 1 wherein the permuting is a predetermined number of independent random permutations of the universe of all of the elements and selecting the minimum element of each image set under each of the predetermined number of independent random permutations.
Claim 7
Dependent Claim
31 words
The method of claim 1 further including the step of tracking a level of resemblance of each data object, and clustering data objects having a predetermined level of resemblance into clusters.
Claim 8
Dependent Claim
44 words
The method of claim 6 wherein the data objects are Web pages indexed by a search engine and in response to a search query returning all resembling Web pages in a particular cluster if one Web page of the particular cluster satisfies the query.
Claim 9
Dependent Claim
26 words
The method of claim 1 further including the step of representing each data object by a super-shingle, and determining levels of resemblance based on the super-shingles.
Claim 10
Dependent Claim
28 words
The method of claim 1 further including the step of representing each data object by a plurality of features, and clustering data objects sharing predetermined number of features.
Claim 11
Dependent Claim
11 words
The method of claim 1 wherein frequently occurring shingles are eliminated.
Claim 12
Dependent Claim
16 words
The method of claim 1 wherein the parsing, permuting, and selecting are performed with first parameters.
Claim 13
Dependent Claim
25 words
The method of claim 11 wherein the parsing, grouping, and selecting are repeated with second parameters to perform variable threshold filtering of the data objects.
Claim 14
Dependent Claim
31 words
The method of claim 1 wherein the data objects are Web pages to be indexed by a search engine, and wherein frequently occurring shingles are eliminated before assigning the unique identifications.
Claim 15
Dependent Claim
40 words
The method of claim 13 wherein the frequently occurring shingles include HTML comment tags that identify a program that generated the HTML comment tags of the Web pages, shared headers or footers, and text sequences including a sequence of numbers.
Claim 16
Dependent Claim
13 words
The method of claim 13 and wherein only different Web pages are indexed.
Claim 17
Dependent Claim
15 words
The method of claim 15 wherein the different Web pages include lexically different Web pages.
Claim 18
Dependent Claim
20 words
The method of claim 1 further including the step of determining the resemblance of the data objects in real time.
Claim 19
Dependent Claim
17 words
The method of claim 1 further including the step of tracking multiple versions of the data objects.
Claim 20
Dependent Claim
18 words
The method of claim 1 further comprising the step of identifying illegal copies of a particular data object.
Claim 21
Dependent Claim
14 words
The method of claim 1 wherein the data objects encode audio and video signals.
Claim 22
Dependent Claim
11 words
The method of claim 1 wherein the unique identifications are fingerprints.
Claim 23
Dependent Claim
110 words
A computer-implemented method of determining the resemblance of a plurality of data objects, comprising the steps of: parsing each data object into a canonical sequence of tokens; grouping overlapping sequences of the tokens of each data object into shingles; assigning a unique identification element to each shingle; permuting the elements of the data objects to form image sets; selecting a predetermined number of minimum elements from each image to form a sketch; wherein a first and a second data object are designated as fungible when the first and the second data objects share at least one common feature, and collecting fungible data objects into clusters of closely resembling data objects.
Claim 24
Dependent Claim
110 words
A computer-implemented method of determining the resemblance of a plurality of data objects, comprising the steps of: parsing each data object into a canonical sequence of tokens; grouping overlapping sequences of the tokens of each data object into shingles; assigning a unique identification element to each shingle; permuting the elements of the data objects to form image sets; selecting a predetermined number of minimum elements from each image to form a sketch; wherein a first and a second data object are designated as fungible when the first and the second data objects share at least one common feature, and collecting fungible data objects into clusters of closely resembling data objects.
Claim 25
Dependent Claim
79 words
The method of claim 22 further comprising the steps of storing a first list of pairs in a memory, each pair including a data object identification and a particular feature of the identified data object, sorting the first list to produce a second list, each entry in the second list identifying a unique feature and all data objects that include the unique feature, and processing the second list to identify data objects sharing the at least one common feature.
Claim 26
Dependent Claim
101 words
An information processing system for determining the resemblance of a plurality of data objects, comprising program instructions for: parsing each data object into a canonical sequence of tokens; grouping overlapping sequences of the tokens of each data object into shingles; assigning a unique identification element to each shingle; permuting the elements of the data objects to form image sets; selecting a predetermined number of minimum elements from each image to form a sketch; partitioning the selected elements of each sketch into a plurality of groups; and assigning another unique identification to each group to generate the features of each data object.
Claim 27
Dependent Claim
101 words
An information processing system for determining the resemblance of a plurality of data objects, comprising program instructions for: parsing each data object into a canonical sequence of tokens; grouping overlapping sequences of the tokens of each data object into shingles; assigning a unique identification element to each shingle; permuting the elements of the data objects to form image sets; selecting a predetermined number of minimum elements from each image to form a sketch; partitioning the selected elements of each sketch into a plurality of groups; and assigning another unique identification to each group to generate the features of each data object.
References Cited (Backward Citations)
US5488725A
Cited
US5675819A
Cited
US5724571A
Cited
US5937084A
Cited
US5909677A
Cited
US5857179A
Cited
US5819258A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-09-12 | 2004-03-13 | 2004-09-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-09-12 | 2008-03-13 | 2008-09-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-09-12 | 2012-03-13 | 2012-09-12 | $7700.00 | Window Closed / Lapsed |