Collaborative searching by query induction

• US 6,732,088 B1
• Filed: 12/14/1999
• Issued: 05/04/2004
• Est. Priority Date: 12/14/1999
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Glance, Natalie S.
• Primary Examiner(s): Rones, Charles
• Application Number:
  US09/464,454
• Time in Patent Office: 1,603 Days
• Field of Search: 707/2, 707/3, 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method and system to facilitate searching a data collection, such as the World Wide Web, that takes advantage of the collective ability of all users to create queries to the data collection. First, a node-link graph of all queries submitted to a data collection within a given period of time is constructed. In the case of the World Wide Web, the queries would be to a particular search engine. In the graph, each node is a query. There is a link made between two nodes whenever the two queries are judged to be related. A first key idea is that the determination of relatedness depends on the documents returned by the queries, not on the actual terms in the queries themselves. For example, a criterion for relatedness could be that of the top ten documents returned for each query, the two lists have at least one document in common. The invention also describes a way to allow the user to peruse the network of related queries in an ordered way: following a path from a first cousin, to a second cousin to a third cousin, etc. to a set of results. By doing this, the user is exposed to related documents that were not returned as a result of their query. A second key idea is that the construction of the query graph transforms single user usage of the data collection (e.g. search) into collaborative usage: all users can tap into the knowledge base of queries submitted by others. This is because each of the related queries represents the knowledge of the user who submitted the query.

Claims

1. A network based information retrieval system comprising:

a) a search interface for enabling a user to submit a query to one or more search engines;

b) a community search assistant for providing a list of queries related to the query submitted by said user, said community search assistant further comprising;

b1) a search engine Interface for interfacing with a query graph creation search engine used for identifying related queries to obtain query information, said query information including query result lists obtained with at least one query of the related queries having a search term that is different from a search term of another one of the related queries;

b2) query relationship processing means for processing the query information so that related queries may be identified, said related queries identified based on said corresponding query result lists and independent of their corresponding search terms; and

c) a storage device coupled to said community search assistant for storing a query database, said query database for storing said query information.

2. The information retrieval system as recited in claim 1 wherein said query relationship processing means is further comprised of query result comparing means, said query result processing means for comparing the query result lists of query pairs to determine if a relationship exists between said query pairs.

3. The information retrieval system as recited in claim 2 wherein said query result comparing means determines a relationship exists when an overlap is identified between said query result lists.

4. The information retrieval system as recited in claim 3 wherein said query result comparing means determines a relationship exists based on a textual analysis between said query result lists.

5. The information retrieval system as recited in claim 1 wherein said search interface further comprises means for displaying a user interface to a user, said user interface defining a first area for displaying query results and a second area for displaying related queries.

6. The information retrieval system as recited in claim 5 wherein said second area of said user interface displays said related queries in a tree-like structure.

7. For an information retrieval system, a method for facilitating document searching comprising the steps of:

a) obtaining a set of queries with at least one query in the set of queries having a search term that is different from a search term of another query in the set of queries;

b) creating a graph of nodes and links with each node in the graph identifying a query in the set of queries and each link in the graph identifying related queries based on the results for each query of said set of queries and independent of their corresponding search terms;

c) responsive to a user query, identifying related queries based on said graph of related queries; and

d) presenting said related queries to said user for their selection.

8. The method as recited in claim 7 wherein said step of creating a graph of related queries is further comprised of the steps of:

b1) submitting each query in said set of queries to a query graph generation search engine and obtaining the top N results for each of said queries;

b2) storing each query and corresponding top N results in a database;

b3) for each query in said set of queries, comparing the query results to the results of other queries to create a related query list; and

b4) storing the related query list for each query in said set of queries in said database.

9. The method as recited in claim 8 wherein said step of responsive to a user query, identifying related queries based on said graph of related queries performing the steps of:

c1) submitting said user query to said graph generation search engine and obtaining the top N results for said user query;

c2) storing said user query and corresponding top N results in said database;

c3) comparing the user query results to the results of other queries in said database to create a related query list for said user query;

c4) storing the related query list for said user query in said database; and

c5) returning said related query list for display to said user.

10. The method as recited in claim 7 wherein said step of presenting said related queries to said user for their selection is further comprised of the steps of presenting a tree structure representation of said related structures.

11. The method as recited in claim 7 further comprising the step of:

e) responsive to a user selecting a related query, performing the step of presenting to said user the results list of said selected related query and the related queries of said selected query.

12. The method as recited in claim 11 wherein prior to said step of presenting to said user the results and the related queries of said selected query, performing the steps of:

submitting said selected related user query to said graph generation search engine and obtaining the top N results for said selected related user query;

storing corresponding top N results of said selected related query in said database;

comparing the selected related user query results to the results of other queries in said database to create a related query list for said selected related user query;

storing the related query list for said user selected related query in said database; and

returning said related query list of said selected related query for display to said user.

13. A method for information retrieval comprising the steps of:

a) creating a database of queries from a community of users, said database storing queries and corresponding results list for said queries with at least one query in said database having a search term that is different from a search term of another query in said database;

b) responsive to a user query performing the steps of;

b1) submitting said user query to a first search engine to obtain a first list of results;

b2) submitting said user query to a second search engine to obtain a second list of results;

b3) comparing said second list of results to results lists of other queries in said database independent of search terms of the corresponding queries;

b4) determining a related query exists when a predetermined relationship is found between said second list of results and results lists of other queries;

b5) presenting said first list of results and related queries identified in step b4) as a list of related queries for said query to said user;

c) responsive to a user selection of a related query, performing the steps of;

c1) submitting said selected related query to said second search engine to obtain a list of results for said selected related query;

c2) comparing said list of results for said selected related query to results lists of other queries in said database independent of search terms of the corresponding queries;

c3) determining a related query exists when said predetermined relationship is found between said list of results for said selected related query and results lists of other queries; and

c4) presenting said list of results of said selected related query and related queries identified in step c3) as a list of related queries for said query to said user.

14. The method as recited in claim 13 wherein said predetermined relationship is when a predetermined number of documents exist in both of the results lists being compared.

15. The method as recited in claim 13 wherein said step of creating a database of queries from a community of users, said database storing queries and corresponding results list for said queries is comprised of the steps of:

a1) obtaining a set of queries;

a2) submitting each query in said set of queries to said second search engine and obtaining the top N results for each of said queries;

a3) storing each query and corresponding top N results in a database;

a4) for each query in said set of queries, comparing the query results to the results of other queries to create a related query list;

a5) storing the related query list for each query in said set of queries in said database.