DIVERSE QUERY RECOMMENDATIONS USING CLUSTERING-BASED METHODOLOGY

• US 20100114929A1
• Filed: 11/06/2008
• Published: 05/06/2010
• Est. Priority Date: 11/06/2008
• Status: Abandoned Application

• Current Assignee: Oath Inc. (Verizon Communications Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Gionis, Aristides, Bonchi, Francesco, Donato, Debora
• Application Number:
  US12/265,949
• Publication Number:
  US 20100114929A1
• Time in Patent Office: Days
• US Class Current: 707/759
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence

Abstract

A computer-implemented method provides suggested search queries based on an input search query. The input search query is received. A first list of documents is determined that correspond to processing the query by a search engine determining the list of result queries, including processing the first list of documents to determine clusters of documents and determining potential queries that correspond to the determined clusters by comparing results of the potential queries with documents in the determined clusters. A list of result queries is determined, wherein executing the list of result queries would correspond to a second list of documents, that result from presenting the result queries to the search engine; and the documents of the second list of documents cover the documents of the first list of documents. The list of result queries based on the potential queries determined to correspond to the determined clusters.

Claims

1. A computer-implemented method to provide suggested search queries based on an input search query, the method comprising:

receiving the input search query;

determining a first list of documents that correspond to processing the query by a search engine determining the list of result queries, including

processing the first list of documents to determine clusters of documents;

determining potential queries that correspond to the determined clusters by comparing results of the potential queries with documents in the determined clusters;

determining a list of result queries, wherein;

executing the list of result queries would correspond to a second list of documents, that result from presenting the result queries to the search engine; and

the documents of the second list of documents cover the documents of the first list of documents; and

providing the list of result queries based on the potential queries determined to correspond to the determined clusters.

2. The method of claim 1, wherein:

providing the list of result queries includes evaluating coverage of the first list of documents by the determined clusters determined to have corresponding potential queries and providing the result queries based on a result of the evaluation.

3. The method of claim 1, wherein:

evaluating coverage includes considering a penalization characteristic based on documents in the first list of documents that are not covered by the determined clusters determined to have corresponding potential queries.

4. The method of claim 1, wherein:

processing the first list of documents to determine clusters of documents includes

hierarchically clustering of the documents of the first list of documents such that, at any level of the hierarchy, clusters are non-overlapping and have high coherence, are covering documents in the first list of documents and not are not covering documents not in the first list of documents; and

determining which of the potential queries to provide as the result queries based on the determined clusters includes determining which of the potential queries to provide as the result queries based on the hierarchical clustering.

5. The method of claim 1, wherein:

processing the first list of documents to determine clusters of documents includes

generating a dendogram whose leaves are documents in the first list of documents and wherein every node in the dendogram corresponds to a cluster of documents of the first group of documents; and

processing the dendogram to determine clusters of documents that match to potential queries and wherein the documents corresponding to the potential queries to which the determined clusters have small overlap among each other, and collectively have large coverage of documents in the first list of documents and small coverage of documents not in the first list of documents.

6. The method of claim 1, wherein:

determining clusters of documents is based on a compactness of the clusters in a topic space.

7. The method of claim 1, wherein:

processing the first list of documents to determine clusters of documents includes applying a hierarchical agglomerative clustering algorithm.

8. The method of claim 5, wherein:

determining a list of result queries includes using a dynamic programming algorithm to select determined clusters of documents that cover the documents of the first list of documents;

wherein the determined result queries include the potential queries that correspond to the selected determined clusters of documents.

9. The method of claim 8, wherein:

the dynamic programming algorithm includes processing the selected determined clusters of the dendogram in a bottom-up fashion.

10. The method of claim 8, wherein:

the dynamic programming algorithm includes processing the selected determined clusters of the dendogram in a bottom-up fashion to minimize a scatter cost associated with selected determined clusters relative to covering the documents in the first list of documents.

14. The computing system of claim 1, wherein:

processing the first list of documents to determine clusters of documents includes

hierarchically clustering of the documents of the first list of documents such that, at any level of the hierarchy, clusters are non-overlapping and have high coherence, are covering documents in the first list of documents and not are not covering documents not in the first list of documents; and

determining which of the potential queries to provide as the result queries based on the determined clusters includes determining which of the potential queries to provide as the result queries based on the hierarchical clustering.

11. A computing system configured to provide suggested search queries based on an input search query, the computer system configured to, the computing system configured to:

receive the input search query;

determine a first list of documents that correspond to processing the query by a search engine determining the list of result queries, including

processing the first list of documents to determine clusters of documents;

determining potential queries that correspond to the determined clusters by comparing results of the potential queries with documents in the determined clusters;

determine a list of result queries, wherein;

executing the list of result queries would correspond to a second list of documents, that result from presenting the result queries to the search engine; and

the documents of the second list of documents cover the documents of the first list of documents; and

provide the list of result queries based on the potential queries determined to correspond to the determined clusters.

12. The computing system of claim 11, wherein:

providing the list of result queries includes evaluating coverage of the first list of documents by the determined clusters determined to have corresponding potential queries and providing the result queries based on a result of the evaluation.

13. The computing system of claim 11, wherein:

evaluating coverage includes considering a penalization characteristic based on documents in the first list of documents that are not covered by the determined clusters determined to have corresponding potential queries.

15. The computing system of claim 11, wherein:

processing the first list of documents to determine clusters of documents includes

generating a dendogram whose leaves are documents in the first list of documents and wherein every node in the dendogram corresponds to a cluster of documents of the first group of documents; and

processing the dendogram to determine clusters of documents that match to potential queries and wherein the documents corresponding to the potential queries to which the determined clusters have small overlap among each other, and collectively have large coverage of documents in the first list of documents and small coverage of documents not in the first list of documents.

16. The computing system of claim 11, wherein:

determining clusters of documents is based on a compactness of the clusters in a topic space.

17. The computing system of claim 11, wherein:

processing the first list of documents to determine clusters of documents includes applying a hierarchical agglomerative clustering algorithm.

18. The computing system of claim 15, wherein:

determining a list of result queries includes using a dynamic programming algorithm to select determined clusters of documents that cover the documents of the first list of documents;

wherein the determined result queries include the potential queries that correspond to the selected determined clusters of documents.

19. The computing system of claim 18, wherein:

the dynamic programming algorithm includes processing the selected determined clusters of the dendogram in a bottom-up fashion.

20. The computing system of claim 18, wherein:

the dynamic programming algorithm includes processing the selected determined clusters of the dendogram in a bottom-up fashion to minimize a scatter cost associated with selected determined clusters relative to covering the documents in the first list of documents.

21. A tangible computer-readable medium having computer program instructions recorded tangibly thereon, the computer program instructions to configure a computing system comprising at least one computing device to provide suggested search queries based on an input search query, the computer program instructions to configured the computing system to:

receive the input search query;

determine a first list of documents that correspond to processing the query by a search engine determining the list of result queries, including

processing the first list of documents to determine clusters of documents;

determining potential queries that correspond to the determined clusters by comparing results of the potential queries with documents in the determined clusters;

determine a list of result queries, wherein;

executing the list of result queries would correspond to a second list of documents, that result from presenting the result queries to the search engine; and

the documents of the second list of documents cover the documents of the first list of documents; and

provide the list of result queries based on the potential queries determined to correspond to the determined clusters.