Detecting query-specific duplicate documents

• US 7,779,002 B1
• Filed: 06/24/2003
• Issued: 08/17/2010
• Est. Priority Date: 02/22/2000
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gomes, Benedict Anthony, Smith, Benjamin Thomas
• Primary Examiner(s): Ly; Cheyne D
• Application Number:
  US10/602,965
• Time in Patent Office: 2,611 Days
• Field of Search: 707 1- 6, 707/10
• US Class Current: 707/728
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/38 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 40/226 Validation
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

An improved duplicate detection technique that uses query-relevant information to limit the portion(s) of documents to be compared for similarity is described. Before comparing two documents for similarity, the content of these documents may be condensed based on the query. In one embodiment, query-relevant information or text (also referred to as “snippets”) is extracted from the documents and only the extracted snippets, rather than the entire documents, are compared for purposes of determining similarity.

Claims

1. A method comprising:

receiving search results in response to a query, the query including one or more keywords, the search results including a first search result and a second search result;

generating a set of final search results from the received search results with one or more processors, including;

adding the first search result to the set of final search results;

determining that a first document corresponding to the first search result and a second document corresponding to the second search result are query-specific duplicate documents from a comparison of one or more first query-relevant parts of the first document and one or more second query-relevant parts of the second document, where each query-relevant part includes at least one of the one or more keywords; and

in response to the determination, not adding the second search result to the set of final search results; and

presenting the set of final search results.

2. The method of claim 1 wherein:

the received search results further include a third search result; and

generating the set of final search results further includes;

determining that the first document and a third document corresponding to the third search result are not query-specific duplicate documents based on a comparison of the one or more first query-relevant parts of the first document and one or more third query-relevant parts of the third document; and

in response to the determination, adding the third search result to the set of final search results.

6. The method of claim 1 wherein the set of final search results includes Web pages.

9. The method of claim 1 wherein the receiving search results and generating a set of final search results are performed automatically, without the need for user intervention.

11. The method of claim 1 wherein the query-relevant parts include a predetermined number of characters.

12. The method of claim 1 wherein the query-relevant parts include a predetermined number of words.

13. The method of claim 1 wherein the query-relevant parts are sentences.

14. The method of claim 1 wherein the query-relevant parts are paragraphs.

3. An apparatus comprising:

at least one processor; and

at least one storage device storing processor executable instructions which, when executed by the at least one processor, processes search results by;

receiving search results in response to a query, the query including one or more keywords, the search results including a first search result and a second search result;

generating a set of final search results from the received search results, including;

adding the first search result to the set of final search results;

determining that a first document corresponding to the first search result and a second document corresponding to the second search result are query-specific duplicate documents from a comparison of one or more of the first query-relevant parts of the first document and one or more second query-relevant parts of the second document, where each query-relevant part includes at least one of the one or more keywords; and

in response to the determination, not adding the second search result to the set of final search results; and

presenting the set of final search results.

4. The apparatus of claim 3 wherein:

the received search results further include a third search result; and

generating the set of final search results further includes;

determining that the first document and a third document corresponding to the third search result are not query-specific duplicate documents based on a comparison of the one or more first query-relevant parts of the first document and one or more third query-relevant parts of the third document; and

in response to the determination, adding the third search result to the set of final search results.

7. The apparatus of claim 3 wherein the set of final search results includes Web pages.

5. An apparatus for processing search results, the apparatus comprising:

a storage device for storing search results generated in response to a query, the query including one or more keywords, and for storing at least one of the one or more keywords, where the search results include a first search result and a second search result;

a final results generator for generating a set of final search results from the search results stored in the storage facility, the generating including;

adding the first search result to the set of final search results;

determining whether a first document corresponding to the first search result and a second document corresponding to the second search result are query-specific duplicate documents from a comparison of one or more first query-relevant parts of the first document and one or more second query-relevant parts of the second document, where each of the query-relevant parts includes at least one of the one or more keywords stored in the storage facility; and

adding the second search result to the set of final search results when the similarity determination facility determines that the first document and the second document are not query-specific duplicate documents and not adding the second search result to the set of final search results when the similarity determination facility determines the first document and the second document are query-specific duplicate documents; and

a final results presenter for presenting the set of final search results.

8. The apparatus of claim 5 wherein the set of final search results includes Web pages.

10. The apparatus of claim 5 wherein the final results generator operates automatically, without the need for user intervention.

15. The apparatus of claim 5 wherein the query-relevant parts include a predetermined number of characters.

16. The apparatus of claim 5 wherein the query-relevant parts include a predetermined number of words.

17. The apparatus of claim 5 wherein the query-relevant parts are sentences.

18. The apparatus of claim 5 wherein the query-relevant parts are paragraphs.

19. A method comprising:

receiving search results that have been generated in response to a query, the query including one or more keywords, the search results including a first search result and a second search result;

identifying, with one or more processors, a first document corresponding to the first search result and a second document corresponding to the second search result as query-specific duplicate documents based on a comparison of one or more first query-relevant parts of the first document and one or more second query-relevant parts of the second document, where each query-relevant part includes at least one of the one or more keywords;

generating a set of final search results from the received set of search results, where the set of final search results includes the first search result but not the second search result according to the identification of the first and second documents as a query-specific duplicate documents; and

presenting the set of final search results.

20. An apparatus comprising:

at least one processor; and

at least one storage device storing processor executable instructions which, when executed by the at least one processor, causes the at least one processor to perform operations comprising;

receiving search results that have been generated in response to a query, the query including one or more keywords, the search results including a first search result and a second search result;

identifying a first document corresponding to the first search result and a second document corresponding to the second search result as query-specific duplicate documents based on a comparison of one or more first query-relevant parts of the first document and one or more second query-relevant parts of the second document, where each query-relevant part includes at least one of the one or more keywords;

generating a set of final search results from the received set of search results, where the set of final search results includes the first search result but not the second search result according to the identification of the first and second documents as a query-specific duplicate documents; and

presenting the set of final search results.