Method for duplicate detection and suppression
A method detects similar objects in a collection of such objects by modification of a previous method in such a way that per-object memory requirements are reduced while false detections are avoided approximately as well as in the previous method. The modification includes (i) combining k samples of features into s supersamples, the value of k being reduced from the corresponding value used in the previous method; (ii) recording each supersample to b bits of precision, the value of b being reduced from the corresponding value used in the previous method; and (iii) requiring l matching supersamples in order to conclude that the two objects are sufficiently similar, the value of l being greater than the corresponding value required in the previous method. One application of the invention is in association with a web search engine query service to determine clusters of query results that are near-duplicate documents.
1. A method for detecting similar objects in a collection of such objects, the method comprising:
processing, by a computer processor, a query to produce the collection of objects;
constructing a plurality of has tables collecting objects produced by processing the query; and, for each of two objects:
modifying a previous method for detecting similar objects so that memory requirements are reduced while avoiding false detections approximately as well as in the previous method, wherein the modifying comprises:
combining. by the computer processor, four samples of features into seven supersamples;
compressing each of the seven supersamples into sixteen bits of precision;
constructing fifteen hash tables storing combinations of the supersamples;
comparing the supersamples using the fifteen hash tables; and
requiring a number of matching supersamples out of the seven supersamples in order to concluded that the two objects are sufficiently similar, wherein the number of matching supersamples is greater than a number of matching supersamples required in the previous method.
2. The method of claim 1 , wherein requiring the number of matching supersamples comprises requiring at least six of the seven supersamples to match.
3. The method of claim 1 , wherein requiring the number of matching supersamples comprises requiring at least five of the seven supersamples to match.
4. The method of claim 1 , wherein requiring the number of matching supersamples comprises requiring all seven supersamples to match.
5. The method of claim 1 , wherein the objects are documents, and the method is used in association with a search engine query service to determine clusters of query results that are near-duplicate documents.
6. The method of claim 5 , further comprising selecting a single document in each cluster to report.
7. The method of claim 6 , wherein selecting the single document is by way of a ranking function.
8. A method for determining groups of near-duplicate items in a search engine query result, the method comprising constructing a plurality of hash tables collecting items in the search engine query result and, for each of two items being compared:
combining, by a computer processor, four samples of features into each of seven supersamples;
compressing, by the computer processor, each supersample into 16 bits of precision;
constructing fifteen hash tables storing combinations of four supersamples;
using the fifteen hash tables to compare the supersamples; and
requiring five of the seven supersamples to match.
9. The method of claim 8 , farther comprising selecting a single document in each cluster to report.
10. The method of claim 9 , wherein selecting the single document is by way of a ranking function.
11. A computer-readable storage medium embodying machine instructions implementing a current method for detecting similar objects in a collection of such objects, wherein the current method comprises modification of a previous method for detecting similar objects so that memory requirements are reduced while avoiding false detections approximately as well as in the previous method, the current method comprising:
processing a query to produce the collection of objects;
constructing a plurality of hash tables of collecting objects produced by processing the query; and, for each of two objects,
combining four samples of features into each of seven supersamples, and
compressing each of the seven supersamples to sixteen bits of precision;
constructing fifteen hash tables storing combinations of the supersamples;
comparing the supersamples using the fifteen hash tables; and
requiring a number of matching supersamples in order to conclude that the two objects are sufficiently similar, wherein the number of matching supersamples is greater than a number of matching supersamples required in the previous method.
12. The computer-readable storage medium of claim 11 , wherein requiring the number of matching supersamples comprises requiring at least six of the seven supersamples to match.
13. The computer-readable storage medium of claim 11 , wherein requiring the number of matching supersamples comprises requiring at least five of the seven supersamples to match.
14. The computer-readable storage medium of claim 11 , wherein requiring the number of matching supersamples comprises requiring all seven supersamples to match.
15. A computer-readable storage medium embodying machine instructions implementing a method for determining groups of near-duplicate items in a search engine query result, the method comprising constructing a plurality of hash tables collecting items in the search engine query result and, for each of two items being compared:
combining four samples of features into each of seven supersamples;
compressing each supersample into 16 bits of precision;
constructing fifteen hash tables storing combinations of four supersamples;
using the fifteen hash tables to compare the supersamples; and
requiring five of the seven supersamples to match.