# US 2013/0159352 A1 · Generating sketches sensitive to high-overlap estimation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2013/0159352 A1 - Document ID: US20130159352A1 - Status: Published application - Kind: A1 - Application number: 13/328,901 - Filed: 2011-12-16 - Published: 2013-06-20 - Earliest claimed: 2011-12-16 - Assignees: Palo Alto Research Center Incorporated - Inventors: Marshall W. Bern - Web page: https://patentgrep.com/patent/US20130159352A1 ## CPC - G06F 16/184: {implemented as replicated file system} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A versioning system determines an amount by which a first collection and a second collection of data objects overlap. The system divides the first collection of data objects into m possibly overlapping groups of average size s and computes one combined hash result for each group. The system then constructs a first sketch vector with n elements based on the combined hash results. A respective element of the first sketch vector is selected, using a selection function, from the combined hash results that are computed with the hash function corresponding to the element's index. Next, the system receives a second sketch vector for the second collection of data objects, and determines a sketch-vector overlap between the first and second sketch vectors. The system then computes a data-object overlap between the first and second collections of data objects based on the sketch-vector overlap. ## Claims ### Claim 1 A computer-implemented method comprising: dividing, by a computer, a first collection of data objects into m groups of average size s, wherein a data object of the first collection is assigned to one or more of the m groups; computing a combined hash result for all members of a respective group, for each hash function in n hash functions; constructing a first sketch vector with n elements, wherein a respective element is selected, using a selection function, from the combined hash results computed with the hash function corresponding to the element's index; receiving a second sketch vector for a second collection of data objects; determining a sketch-vector overlap between the first and second sketch vectors; and computing a data-object overlap between the first and second collections of data objects based on the sketch-vector overlap. ### Claim 2 (depends on 1) The method of claim 1, wherein computing the data-object overlap comprises entering the sketch-vector overlap into a conversion function: data-object overlap=(sketch-vector overlap)1/s; wherein s indicates an average number of data objects per group. ### Claim 3 (depends on 1) The method of claim 1, wherein dividing the first collection of data objects comprises using a hash function to map each of the first collection of data objects into one of the m groups. ### Claim 4 (depends on 1) The method of claim 1, wherein computing a combined hash result for a group involves: computing a hash result for each of the data objects corresponding to the group; and computing a combined hash result for the group based on the hash results. ### Claim 5 (depends on 1) The method of claim 1, wherein the first sketch vector and the second sketch vector have a matching length. ### Claim 6 (depends on 5) The method of claim 5, wherein determining the sketch-vector overlap comprises determining a fraction of corresponding vector elements between the first and second sketch vectors that have matching values. ### Claim 7 A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method comprising: dividing a first collection of data objects into m groups of average size s, wherein a data object of the first collection is assigned to one or more of the m groups; computing a combined hash result for all members of a respective group, for each hash function in n pair-wise independent hash functions; constructing a first sketch vector with n elements, wherein a respective element is selected, using a selection function, from the combined hash results computed with the hash function corresponding to the element's index; receiving a second sketch vector for a second collection of data objects; determining a sketch-vector overlap between the first and second sketch vectors; and computing a data-object overlap between the first and second collections of data objects based on the sketch-vector overlap. ### Claim 8 (depends on 7) The storage medium of claim 7, wherein computing the data-object overlap comprises entering the sketch-vector overlap into a conversion function: data-object overlap=(sketch-vector overlap)1/s; wherein s indicates an average number of data objects per group. ### Claim 9 (depends on 7) The storage medium of claim 7, wherein dividing the first collection of data objects comprises using a hash function to map each of the first collection of data objects into one of the m groups. ### Claim 10 (depends on 7) The storage medium of claim 7, wherein computing a combined hash result for a group involves: computing a hash result for each of the data objects corresponding to the group; and computing a combined hash result for the group based on the hash results. ### Claim 11 (depends on 7) The storage medium of claim 7, wherein the first sketch vector and the second sketch vector have a matching length. ### Claim 12 (depends on 11) The storage medium of claim 11, wherein determining the sketch-vector overlap comprises determining a fraction of corresponding vector elements between the first and second sketch vectors that have matching values. ### Claim 13 An apparatus comprising: a data-grouping mechanism to divide a first collection of data objects into m groups of average size s, wherein a data object of the first collection is assigned to one or more of the m groups; a hashing mechanism to compute a combined hash result for all members of a respective group, for each hash function in n pair-wise independent hash functions; a sketch-generating mechanism to construct a first sketch vector with n elements, wherein a respective element is selected, using a selection function, from the combined hash results computed with the hash function corresponding to the element's index; a communication mechanism to receive a second sketch vector for a second collection of data objects; a comparison mechanism to determine a sketch-vector overlap between the first and second sketch vectors; and a computing mechanism to compute a data-object overlap between the first and second collections of data objects based on the sketch-vector overlap. ### Claim 14 (depends on 13) The apparatus of claim 13, wherein while computing the data-object overlap, the computing mechanism is further configured to enter the sketch-vector overlap into a conversion function: data-object overlap=(sketch-vector overlap)1/s; wherein s indicates an average number of data objects per group. ### Claim 15 (depends on 13) The apparatus of claim 13, wherein while dividing the first collection of data objects, the data-grouping mechanism is further configured to use a hash function to map each of the first collection of data objects into one of the m groups. ### Claim 16 (depends on 13) The apparatus of claim 13, wherein while computing a combined hash result for a group, the hashing mechanism is further configured to: compute a hash result for each of the data objects corresponding to the group; and compute a combined hash result for the group based on the hash results. ### Claim 17 (depends on 13) The apparatus of claim 13, wherein the first sketch vector and the second sketch vector have a matching length. ### Claim 18 (depends on 17) The apparatus of claim 17, wherein while determining the sketch-vector overlap, the comparison mechanism is further configured to determine a fraction of corresponding vector elements between the first and second sketch vectors that have matching values.