Structured contextual clustering method and system in a federated search engine

• US 6,944,612 B2
• Filed: 11/13/2002
• Issued: 09/13/2005
• Est. Priority Date: 11/13/2002
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Mahe, Yves, Roustant, Bruno, Chevalier, Pierre-Yves
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US10/065,731
• Publication Number:
  US 20040093321A1
• Time in Patent Office: 1,035 Days
• Field of Search: 707/1, 707/2, 707/3, 707/10, 707/6, 707/5, 707/100, 707/101, 717/8, 715/517, 715/512, 715/513, 715/537
• US Class Current: 707/706
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A federated search engine groups search results from information sources using attributes of the search results. In grouping the search results, a first set and a second set of attributes are extracted from content in each set of search results received using information source wrappers. The first set of attributes defines a main clustering strategy, and the second set of attributes defines a sub-clustering strategy. A main grouping of the sets of search results received from the information sources is generated using the first set of attributes. The main grouping of search results includes a plurality of labeled groups with a plurality of search results in each group. A sub-grouping of search results is generated for each labeled group of search results in the main grouping of search results using the second set of attributes.

Claims

1. A method for grouping search results received from information sources, comprising:

receiving a query with user-selected keywords to be evaluated in an information domain;

identifying a plurality of information sources associated with the information domain;

submitting the query to at least two of the plurality of information sources identified;

receiving a set of search results from the at least two information source for the query submitted thereto;

extracting a plurality of attributes from content in each set of search results received using information source wrappers;

specifying a first set of the plurality of attributes, which defines a main clustering strategy, and a second set of the plurality of attributes, which defines a sub-clustering strategy;

each clustering strategy defining a unique set of attributes that may be extracted from the content of search results using the information source wrappers;

generating a main grouping of the sets of search results received from the information sources using the first set of attributes;

the main grouping of search results including a plurality of labeled groups with a plurality of search results in each group; and

generating a sub-grouping of search results for each labeled group of search results in the main grouping of search results using the second set of attributes.

2. The method according to claim 1, wherein each grouping of search results are computed using attributes of a specified clustering strategy by:

normalizing the attribute content of identified search results according to the specified clustering strategy;

stemming the normalized attribute content using a stemmer;

clustering the stems of the normalized attribute content based on their similarity; and

grouping the identified search results using the clustered stems.

3. The method according to claim 2, further comprising determining each label of the plurality of labeled groups using short representative sentences in each grouping of search results.

4. The method according to claim 2, further comprising rejecting a label of the plurality of labeled groups when it contains a subset of the user-selected keywords or stop words.

5. The method according to claim 4, further comprising refining the query by augmenting the user-selected keywords with ones of the labels of the plurality of labeled groups.

6. The method according to claim 2, wherein the grouping of the identified set of search results further comprises computing a relevancy score based on the user-selected keywords in the identified set of search results to rank possible groupings.

7. The method according to claim 2, wherein the identified set of search results is grouped using the clustered stems according to one of a plurality of grouping modes.

8. The method according to claim 7, wherein the plurality of grouping modes comprise:

a first grouping mode that defines approximately five groups that account for approximately 85% of the identified set of search results;

a second grouping mode that defines approximately ten groups that account for approximately 65% of the identified set of search results; and

a third grouping mode that defines approximately twenty groups that account for approximately 65% of the identified set of search results.

9. The method according to claim 2, further comprising filtering the set of search results received from each of the at least two information source by removing results that do not satisfy the query.

10. The method according to claim 9, wherein the attribute content is normalized in accordance with the specified clustering strategy.

11. The method according to claim 10, further comprising guessing the language of each set of search results to select the stemmer for the set of search results.

12. The method according to claim 11, wherein the plurality of information sources associated with the identified information domain are specified using:

(a) a set of user-selected information sources, (b) a set of information sources automatically identified by the search engine, and (c) a combination of (a) and (b).

13. The method according to claim 12, wherein the query includes user-selected operators that define relationships between the user-selected keywords.

14. The method according to claim 13, further comprising translating at least one of the user-selected operators of the original query that is not supported by one of the plurality of information sources to an alternate operator that is supported by the one of the plurality of information sources.

15. The method according to claim 10, wherein the attribute content is normalized to an attribute specific hierarchy.

16. The method according to claim 2, wherein the main clustering strategy and the sub-clustering strategy are specified:

(a) manually by a user of the search engine;

(b) automatically by the search engine;

or (c) a combination of (a) and (b).

17. The method according to claim 2, wherein each sub-grouping of search results includes a plurality of labeled groups and wherein the method further comprises:

specifying a third set of the plurality of attributes, which defines a sub-sub-clustering strategy; and

generating a sub-sub-grouping of search results for each labeled group of search results in each sub-grouping of search results using the third set of attributes.

18. The method according to claim 1, wherein the search engine is a federated search engine.

19. A method for grouping search results in an information source, comprising:

receiving a query with user-selected keywords to be evaluated in an information domain of the information source;

querying the information domain of the information source with the query;

identifying a set of search results for the query submitted to the information domain of the information source;

extracting a plurality of attributes from content in the set of search results received for the submitted query;

specifying a first set of the plurality of attributes, which defines a main clustering strategy, and a second set of the plurality of attributes, which defines a sub-clustering strategy;

each clustering strategy defining a unique set of attributes that may be extracted from the content of search results;

generating a main grouping of the set of search results received from the information sources using the first set of attributes;

the main grouping of search results including a plurality of labeled groups with a plurality of search results in each group; and

generating a sub-grouping of search results for each labeled group of search results in the main grouping of search results using the second set of attributes.

20. A system for grouping search results received from information sources, comprising:

a query translation module for receiving a query with user-selected keywords to be evaluated in an information domain;

the query translation module identifying a plurality of information sources associated with the information domain and submitting the query to at least two of the plurality of information sources identified;

an attribute extraction module for receiving a set of search results from the at least two information source for the query submitted thereto;

the attribute extraction module extracting a plurality of attributes from content in each set of search results received using information source wrappers;

a clustering module for specifying a first set of the plurality of attributes, which defines a main clustering strategy, and a second set of the plurality of attributes, which defines a sub-clustering strategy;

each clustering strategy defining a unique set of attributes that may be extracted from the content of search results using the information source wrappers;

wherein the clustering module generates a main grouping of the sets of search results received from the information sources using the first set of attributes;

the main grouping of search results including a plurality of labeled groups with a plurality of search results in each group; and

wherein the clustering module generates a sub-grouping of search results for each labeled group of search results in the main grouping of search results using the second set of attributes.