System and method for finding information in a distributed information system using query learning and meta search

• US 6,418,432 B1
• Filed: 07/24/1998
• Issued: 07/09/2002
• Est. Priority Date: 04/10/1996
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Cohen, William W, Singer, Yoram
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US09/117,312
• Time in Patent Office: 1,446 Days
• Field of Search: 707/5
• US Class Current: 1/1
• CPC Class Codes: G06F 16/353 into predefined classes
• 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/99935 Query augmenting and refining, e.g. inexact access

Abstract

An information retrieval system finds information in a Distributed Information System (DIS), e.g. the Internet using query learning and meta search for adding documents to resource directories contained in the DIS. A selection means generates training data characterized as positive and negative examples of a particular class of data residing in the DIS. A learning means generates from the training data at least one query that can be submitted to any one of a plurality of search engines for searching the DIS to find “new” items of the particular class. An evaluation means determines and verifies that the new item(s) is a new subset of the particular class and adds or updates the particular class in the resource directory.

Claims

1. A method of adding new documents to a resource list of existing documents, executable in a computer system, comprising the steps of:

learning a rule for which the documents on the resource list are positive examples of a class of selection information which selects the documents on the resource list;

making a persistent association between the selection information and the resource list;

using the selection information independent for a meta search engine to identify data on a plurality of items characterized as positive and/or negative examples of the class of information to select a set of documents which the information specifies; and

adding new documents to the resource list, the new documents being added belonging to a subset of the selected set of documents which contains documents which are not already on the resource list.

2. The method set forth in claim 1 wherein the step of adding documents comprises the steps of:

interactively determining whether a document in the subset should be added to the resource list; and

adding the document only if it has been determined that the document should be added.

3. The method set forth in claim 2 further comprising the steps of:

using a document for which it has been determined that the document should not be added together with documents on the resource list to learn new selection information; and

associating the new selection information with the resource list.

4. The method set forth in claim 1 wherein the step of learning the selection information comprises the steps of:

learning a rule for which the documents on the resource list are positive examples;

translating the rule into a query; and

in the step of using the selection information, using the query to select the set of documents.

5. The method set forth in any of claims 1 through 4 wherein:

the system in which the method is practiced has access to a plurality of searching means;

the step of learning the selection information learns a plurality of queries as required by the plurality of searching means; and

the step of using the selection information to select a set of documents uses the plurality of queries in the plurality of searching means.

6. The method set forth in claim 5 wherein:

the system in which the method is practiced has access to the world wide web; and

the searching means are searching means in the world wide web.

7. An improved web page of a type which contains a list of documents, the improvement comprising:

a machine learning system for learning a rule for which the documents on the web page are positive examples of a class of selection information which selects the documents on the web page;

a meta search engine using selection information to identify data on a plurality of items characterized as positive and/or negative examples of a class of information associated with the web page which selects documents having content which is similar to the documents on the list, whereby the list of documents on the web page is updated using the selection information.

8. In a computer system, apparatus, for making a resource list of documents which have contents belonging to the same class, the apparatus comprising:

a first list of documents, all of which have contents as positive examples belonging to the class;

a second list of documents, none of which have contents as negative examples belonging to the class;

learning means responsive to the first list of documents and the second list of documents for learning a rule for which the documents on the resource list arc positive examples of the class of selection information which specifies documents whose contents belong to the class;

meta search means responsive to the selection information for finding the documents whose contents belong to the class, using the documents to make the resource list, and making a persistent association between the selection information and the resource list.

9. The apparatus set forth in claim 8 further comprising:

first interactive means for indicating whether a given document is to be added to the first list or the second list.

10. The apparatus set forth in claim 9 further comprising:

second interactive means for activating the learning means.

11. The apparatus set forth in claim 10 further comprising:

third interactive means for activating the means for finding the documents.

12. The apparatus set forth in any of claims 9 through 11 wherein:

the apparatus is used in a system which includes a document browser; and

the interactive means of the claim are implemented in the document browser.

13. In an information system which stores related data and information as items for a plurality of interconnected computers accessible by a plurality of users, a method for finding items of a particular class residing in the information system comprising the steps of:

a) identifying as training data a plurality of items characterized as positive and/or negative examples of the class;

b) using a learning technique to generate from the training data at least one query that can be submitted to any of a plurality of methods for searching the information system;

c) submitting said query to meta search means and collecting any new item(s) as a response to the query;

d) evaluating the new item(s) by a learned model with the aim of verifying that the new item(s) is indeed a new subset of the particular class; and

e) presenting the new subset of the new item(s) to a user of the system.

14. The method of claim 13 wherein the information system is a distributed information system (DIS) and the items are documents collected in resource directories in the DIS.

15. The method of claim 14 wherein step a) the positive examples are a set of documents in the resource directories and the negative examples are a selection of documents obtained by using the process of steps a-d.

16. The method of claim 15 wherein step b) the query is (i) a conjunction of terms which must appear in a document as a positive example;

(ii) contains all the terms appearing in the training data covered by the query, and (iii) learned by the system using a propositional rule—

learning or prediction algorithm method.

17. The method of claim 16 wherein step d) a learning technique generates from the training data a learned model that computes a score for the new item(s), such that the new item(s) which has a low probability of being classified within the particular class.

18. The method of claim 17 further comprising the step of providing a user on the system an ordered list of the new item(s) according to the score assigned by the learned model.

19. The method of claim 17 further comprising the step of providing a user by electronic mail or facsimile an ordered list of the new item(s) having a score exceeding a threshold probability.

20. The method of claim 17 further comprising the step of using an batch process to identify documents as positive or negative examples of the search concept.

21. The method of claim 17 further comprising the step of using an interactive process to identify documents as positive examples of the search concept by browsing the distributed information system.

22. The method of claim 17 further comprising the step of resubmitting a query to the system to detect any new item added to the system and related to the query.

23. An information system which stores related data and information as items for a plurality of interconnected computers accessible by a plurality of users for finding items of a particular class residing in the information system using query learning and meta search, comprising:

a) means for identifying as training data in the system a plurality of items characterized as positive and/or negative examples of the class;

b) means for using a learning technique to generate from the training data at least one query that can be submitted to any of a plurality of search engines for searching the information system;

c) means for submitting said query to a meta search engine and collecting any new item(s) as a response to the query;

d) means for evaluating the new item(s) by the at least one search engine with the aim of verifying that the new item(s) is indeed a new subset of the particular class; and

e) means for presenting the new subset of the new item(s) to a user of the system.

24. The system of claim 23 wherein the information system is a distributed information system (DIS) and the items are documents stored in resource directories in the DIS.

25. The system of claim 24 wherein the positive examples are a set of items in the resource directories and the negative examples are a selection of documents obtained by the search engine in responding to the query.

26. The system of claim 25 the query is (i) a conjunction of terms which must appear in a document as a positive example;

(ii) contains all the terms appearing in the training data covered by the query, and iii) learned by the system using a propositional rule—

learning or prediction algorithm method.

27. The system of claim 26 wherein step the learning technique generates from the training data a learned model that computes a score for the new item(s), such that the new item(s) which has a high probability of being classified within the particular class will be assigned a higher score than the new item(s) which has a low probability of being classified within the particular class.

28. The system of claim 27 further comprising means for providing a user on the system an ordered list of the new item(s) according to the score assigned by the learned model.

29. The system of claim 27 further comprising means for providing a user by electronic mail or facsimile an ordered list of the new item(s) having a score exceeding a threshold probability.

30. The system of claim 27 further comprising means for using a batch process to select documents as positive examples of the search concept.

31. The system of claim 27 further comprising means for using an interactive process to identify documents as positive examples of the query by browsing the distributed information system.

32. The system of claim 27 further comprising means for resubmitting a query to the system to detect any new item added to the system and related to the query.

33. An article of manufacture comprising:

a computer useable medium having computer readable program code means embodied therein for finding items of a particular class residing an information system which stored related data and information as items for a plurality of interconnected computers accessible by a plurality of users, the computer readable program code means in said article of manufacture comprising;

a) program code means for identifying as training data a plurality of items characterized as positive and/or negative examples of the class;

b) program code means for using a learning technique to generate from the training data at least one query that can be submitted to any of a plurality of methods for searching the information system;

c) program code means for submitting said query to meta search means and collecting any new item(s) as a response to the query;

d) program code means for evaluating the new item(s) by meta search means with the aim of verifying that the new item(s) is indeed a new subset of the particular class; and

e) program code means for presenting the new subset of new item(s) to a user of the system.