Semantic table of contents for search results

• US 8,150,859 B2
• Filed: 02/05/2010
• Issued: 04/03/2012
• Est. Priority Date: 02/05/2010
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Najm, Tarek, Vadlamani, Viswanath, Srivastava, Abhinai, Surendran, Arungunram Chandrasekaran
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Casanova, Jorge A
• Application Number:
  US12/701,338
• Publication Number:
  US 20110196875A1
• Time in Patent Office: 788 Days
• Field of Search: 707/738, 707/748
• US Class Current: 707/748
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/353 into predefined classes

Abstract

A table of contents is generated for search results in response to a search query by identifying semantic concepts as topics for inclusion within the table of contents. When a search query is received, a search is performed to identify search results. The search results are compared to an ontology of topics to identify relevant topics. Additionally, search results are compared to an ontology of partial topics to identify relevant partial topics, which are named. Independent key-phrases are further generated from search results and identified as key-phrase topics. The identified topics, named partial topics, and key-phrase topics are ranked, and topics are selected for inclusion within a table of contents. A search results page is returned in response to the search query that includes search results and the generated table of contents.

Claims

1. One or more computer-readable media storing computer-useable instructions that, when used by one or more computing devices, cause the one or more computing devices to perform a method comprising:

receiving a search query;

performing a search using the search query;

receiving a plurality of documents snippets from the search;

identifying a first set of one or more candidate topics by comparing one or more document snippets to an ontology of topics;

identifying a second set of one or more candidate topics by comparing one or more document snippets to an ontology of partial topics;

identifying a third set of one or more candidate topics by generating key-phrase topics from one or more document snippets, wherein identifying the third set of one or more candidate topics includes computing independent key-phrases from document snippets remaining in the document set by;

generating candidate key-phrases from one or more document snippets, evaluating candidate key-phrases for independence, merging mutually dependent candidate key-phrases, and identifying a most frequent candidate key-phrase for each group of merged mutually dependent key-phrases;

ranking candidate topics from the first, second, and third set of candidate topics;

selecting one or more topics based on ranking of the candidate topics; and

providing a search results page in response to the search query, the search results page having a table of contents containing the one or more topics and a search results area for presenting one or more search results.

2. The one or more computer-readable media of claim 1, wherein identifying the second set of one or more candidate topics by comparing one or more document snippets to the ontology of partial topics comprises identifying one or more partial topics and naming each partial topic, wherein a partial topic is named by:

identifying occurrences of a partial topic identifier word for the partial topic within one or more document snippets;

extracting words and/or phrases occurring around identified occurrences of the partial topic identifier word within the one or more document snippets;

counting frequency of each extracted word and/or phrase;

selecting a most frequently used word or phrase; and

naming the partial topic using the partial topic identifier and the most frequently used word or phrase.

3. The one or more computer-readable media of claim 1, wherein ranking a candidate topic is based on one or more selected from the following:

a total number of documents assigned to the candidate topic;

ranking of each document assigned to the candidate topic;

ranking of a selection of documents assigned to the topic; and

a word length of the candidate topic.

4. The one or more computer-readable media of claim 1, wherein selecting one or more topics based on ranking of the candidate topics comprises one or more selected from the following:

selecting a predetermined number of topics;

selecting all topics having a ranking satisfying a predetermined threshold; and

selecting topics having a significantly higher relevance than other topics.

5. One or more computer-readable media storing computer-useable instructions that, when used by one or more computing devices, cause the one or more computing devices to perform a method comprising:

receiving a search query;

determining an ontology mapping exists for the search query;

if an ontology mapping exists for the search query, retrieving (308) a first set of topics based on the ontology mapping and adding the first set of topics to a list of topics;

performing a search using the search query to obtain a plurality of search results, each search result corresponding with a document snippet;

receiving at least a portion of the document snippets as a document set for further analysis;

comparing each document snippet in the document set to an ontology of topics;

for each document snippet in which positive topic identification is determined, assigning the document snippet to a corresponding topic and removing the document snippet from the document set;

adding at least one topic identified from the ontology of topics to the list of topics;

comparing each document snippet remaining in the document set to an ontology of partial topics;

for each document snippet in which positive partial topic identification is determined, assigning the document snippet to a corresponding partial topic and removing the document snippet from the document set;

naming at least one partial topic having one or more assigned document snippets;

adding at least one named partial topic to the list of topics;

computing independent key-phrases from document snippets remaining in the document set, wherein computing the independent key-phrases from document snippets remaining in the document set comprises;

generating candidate key-phrases from the document snippets remaining the document set, evaluating candidate key-phrases for independence, merging mutually dependent candidate key-phrases, and identifying a most frequent candidate key-phrase for each group of merged mutually dependent key-phrases;

assigning documents to independent key-phrases;

identifying at least one key-phrase topic;

adding the at least one key-phrase topic to the list of topics;

ranking topics within the list of topics;

selecting topics based on ranking;

generating a table of contents using the selected topics; and

providing a search results page in response to the search query, the search results page including the table of contents and a search results area for presenting search results.

6. The one or more computer-readable media of claim 5, wherein receiving at least a portion of the document snippets as the document set for further analysis comprises receiving document snippets corresponding with a predetermined number of search results having the highest relevance to the search query.

7. The one or more computer-readable media of claim 5, wherein comparing each document snippet in the document set to the ontology of topics comprises computing a feature vector for each document snippet based on words contained in each document snippet and comparing each feature vector to topics in the ontology of topics, and wherein positive topic identification for a document snippet is determined by determining that the feature vector for the document snippet is within a predetermined distance of a given topic.

8. The one or more computer-readable media of claim 5, wherein adding at least one topic identified from the ontology of topics to the list of topics comprises adding each topic having greater than a predetermined number of assigned document snippets.

9. The one or more computer-readable media of claim 5, wherein comparing each document snippet remaining in the document set to the ontology of partial topics comprises computing a feature vector for each document snippet based on words contained in each document snippet and comparing each feature vector to partial topics in the ontology of partial topics, and wherein positive partial topic identification for a document snippet is determined by determining that the feature vector for the document snippet is within a predetermined distance of a given partial topic.

10. The one or more computer-readable media of claim 5, wherein naming at least one partial topic having one or more assigned document snippets comprises naming each partial topic having greater than a predetermined number of assigned document snippets.

11. The one or more computer-readable media of claim 5, wherein naming a partial topic comprises:

identifying occurrences of a partial topic identifier word for the partial topic within one or more document snippets assigned to the partial topic;

extracting words and/or phrases occurring around identified occurrences of the partial topic identifier word within the one or more document snippets;

counting frequency of each extracted word and/or phrase;

selecting a most frequently used word or phrase; and

naming the partial topic using the partial topic identifier and the most frequently used word or phrase.

12. The one or more computer-readable media of claim 11, wherein counting frequency of each extracted word and/or phrase comprises tracking position of each extracted word and/or phrase relative to the partial topic identifier word, and wherein naming the partial topic comprises sequencing the partial topic identifier word and the most frequently used word or phrase based on position information for the most frequently used word or phrase.

13. The one or more computer-readable media of claim 5, wherein identifying at least one key-phrase topic comprises identifying each key-phrase having greater than a predetermined number of assigned document snippets as a key-phrase topic.

14. The one or more computer-readable media of claim 5, wherein ranking a topic is based on one or more selected from the following:

a total number of documents assigned to the topic;

ranking of each document assigned to the topic;

ranking of a selection of documents assigned to the topic; and

a word length of the topic.

15. The one or more computer-readable media of claim 5, wherein selecting topics based on ranking comprises one or more selected from the following:

selecting a predetermined number of topics;

selecting all topics having a ranking satisfying a predetermined threshold; and

selecting topics having a significantly higher relevance than other topics.

16. A method for identifying topics from a set of search results for generating a table of contents for the search results, the method comprising:

receiving a search query;

performing a search using the search query;

receiving a plurality of document snippets from the search;

generating candidate key-phrases from at least a portion of the document snippets;

evaluating candidate key-phrases for independence;

merging mutually dependent candidate key-phrases;

identifying a most frequent candidate key-phrase for each group of mutually dependent key-phrases to generate a plurality of independent key-phrases;

assigning one or more document snippets to each independent key-phrases; and

selecting key-phrase topics based on assignment of document snippets to independent key-phrases.

17. The method of claim 16, wherein a Markov chain based method is used to generate the candidate key-phrases.

18. The method of claim 16, wherein independence of candidate key-phrases is evaluated using one or more selected from the following:

number of words shared by candidate key-phrases, analysis of acronyms of words in candidate key-phrases; and

number of documents shared by candidate key-phrases.