System and method for retrieval of hyperlinked information resources

• US 5,855,015 A
• Filed: 05/12/1995
• Issued: 12/29/1998
• Est. Priority Date: 03/20/1995
• Status: Expired due to Term

• Current Assignee: Knapp Investment Company Limited
• Original Assignee: Interval Research Corporation
• Inventors: Shoham, Yoav
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Choules, Jack M.
• Application Number:
  US08/440,206
• Time in Patent Office: 1,327 Days
• Field of Search: 395/601, 395/602, 395/603, 395/604, 395/605, 395/606, 707/4, 707/5, 707/6, 707/3
• US Class Current: 715/205
• CPC Class Codes: G06F 16/3326 using relevance feedback from the user, e.g. relevance feedback on documents, documents sets, document terms or passages
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing
• CPC Class Codes: G06F 16/9558 Details of hyperlinks; Management of linked annotations
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A system and method for adaptively traversing a network of linked textual or multi-media information utilizes one or more heuristics to explore the network and present information to a user. An exploration or search heuristic governs activity while examining and exploring the linked information resources, while a presentation heuristic controls presentation of a manageable amount of information resources to the user. The system and method accept relevance feedback from the user which is used to refine future search, retrieval, and presentation of information resources. The user may present an information query of various degrees of specificity or the system and method may search and present information resources based entirely on relevance feedback from the user.

Claims

1. A system for retrieval of hyperlinked information resources, the system comprising:

a user interface for selecting system parameters, for providing system output to a user, and for accepting input from the user;

a processor in communication with the user interface, the microprocessor being operative to explore the hyperlinked information resources using a first heuristic to select at least one information resource, to present the at least one information resource to the user via the user interface based on a second heuristic, to obtain feedback from the user via the user interface corresponding to a period of time during which the user views each of the at least one information resources to determine relevance of the at least one information resource, and to modify the first and second heuristics based on the feedback.

2. The system of claim 1 further comprising a memory accessible by the processor, wherein the memory contains the first and second heuristics and logic rules operative to modify the first and second heuristics upon execution of the logic rules by the processor.

3. The system of claim 1 wherein the processor is further operative to evaluate a metric which characterizes relevance of at least one information resource in order to select the at least one information resource for presentation to the user.

4. The system of claim 1 wherein the processor is further operative to characterize relevance of at least one information resource containing a plurality of objects in order to select the at least one information resource by evaluating the expression:

space="preserve" listing-type="equation">VALUE.sub.ik =FREQ.sub.ik * log.sub.2 (n)-log.sub.2 (DOCFREQ.sub.k)+1!

where FREQ_ik represents the number of times object k occurs in resource i, DOCFREQ_k represents the number of resources in which object k occurs, and n represents the total number of resources.

5. The system of claim 1 wherein the processor is operative to obtain feedback from the user by monitoring a parameter indicative of relevance of the at least one information resource presented to the user.

6. The system of claim 1 wherein the processor is operative to repeatedly explore the hyperlinked information resources until interrupted by the user.

7. The system of claim 1 wherein the processor is operative to select a predetermined number of information resources for presentation to the user.

8. The system of claim 1 wherein the processor is operative to obtain numerical feedback from the user.

9. The system of claim 1 wherein the processor is operative to extract at least one feature of the at least one information resource, the feature being indicative of relevance of the resource to the user.

10. The system of claim 9 wherein the at least one feature is a structural feature of the at least one information resource.

11. The system of claim 10 wherein the at least one feature includes length of each of the at least one information resource.

12. The system of claim 10 wherein the at least one feature includes number of pictures contained within the at least one information resource.

13. The system of claim 1 wherein the processor is further operative to repeatedly modify at least one of the first and second heuristics so as to accommodate changing interests of the user represented by changing indications of relevance from the user.

14. The system of claim 1 wherein the processor is further operative to obtain a value for each of at least one system parameter which determines how many selected information resources to present to the user.

15. The system of claim 1 wherein the processor is further operative to automatically determine at least one of the first and second heuristics based on a predetermined number of training examples ranked by the user wherein each rank indicates the relevance of an associated training example.

16. The system of claim 15 wherein the processor is operative to modify at least one of the first and second heuristics only during an initial training period, the initial training period being followed by a use period during which the first and second heuristics are not modified.

17. A method for retrieval of hyperlinked information resources, the method comprising:

exploring the hyperlinked information resources using a first heuristic;

selecting at least one information resource based on the first heuristic;

presenting the at least one information resource to a user via a user interface based on a second heuristic;

obtaining feedback from the user via the user interface corresponding to a period of time during which the user views each of the at least one information resources to determine relevance of the at least one information resource; and

modifying at least one of the first and second heuristics based on the feedback.

18. The method of claim 17 wherein the step of modifying comprises modifying at least one of the first and second heuristics based on the feedback and the at least one information resource.

19. The method of claim 17 further comprising:

selecting system parameters via the user interface prior to exploring the hyperlinked information resources.

20. The method of claim 19 wherein selecting system parameters comprises selecting a predetermined number to determine how many selected information resources to be presented by the system to the user.

21. The method of claim 17 further comprising:

repeating the steps of exploring, selecting, presenting, obtaining, and modifying until interrupted by the user.

22. The method of claim 17 wherein the step of selecting at least one information resource comprises:

selecting at least one information resource containing at least one object based on evaluation of the expression;

space="preserve" listing-type="equation">VALUE.sub.ik =FREQ.sub.ik * log.sub.2 (n)-log.sub.2 (DOCFREQ.sub.k)+1!

where FREQ_ik represents the number of times object k occurs in resource i, DOCFREQ_k represents the number of resources in which object k occurs, and n represents the total number of resources.

23. The method of claim 17 wherein the step of obtaining feedback from the user comprises:

monitoring a parameter indicative of relevance of the at least one information resource presented to the user.

24. The method of claim 17 wherein the step of selecting at least one information resource comprises:

extracting at least one feature of the at least one information resource, the feature being indicative of relevance of the resource to the user.

25. The method of claim 24 wherein extracting at least one feature comprises extracting at least one structural feature of the at least one information resource.

26. The method of claim 25 wherein extracting at least one structural feature comprises extracting length of each of the at least one information resource.

27. The method of claim 17 wherein the step of modifying is repeatedly performed so as to accommodate changing interests of the user represented by changing indications of relevance from the user.

28. The method of claim 17 further comprising:

automatically determining at least one of the first and second heuristics based on a predetermined number of training examples having an associated ranking determined by the user wherein each ranking indicates relevance of the associated training example to the user.

29. The method of claim 17 wherein the step of modifying at least one of the first and second heuristics is performed only during an initial training period, the initial training period being followed by a use period during which the first and second heuristics are not modified.

30. A method for retrieval of hyperlinked information resources in an environment including a plurality of computers wherein each of the plurality of computers communicates with at least one other computer and wherein at least one of the plurality of computers contains a plurality of information resources having associated hyperlinks which define a hyperlinked network, the method comprising:

exploring the hyperlinked network using a first heuristic, wherein the first heuristic characterizes relevance of at least one information resource on the hyperlinked network;

selecting at least one information resource based on the associated relevance as determined by the first heuristic;

presenting the at least one information resource to a user via a user interface based on a second heuristic, wherein the second heuristic filters the at least one information resource so as to present a limited number of information resources;

obtaining feedback from the user via the user interface, the feedback indicative of actual relevance of the at least one information resource to the user based on at least length of time during which the user views each of the at least one information resource; and

modifying at least one of the first and second heuristics based on the feedback and the at least one information resource.

31. The method of claim 30 wherein the first heuristic is based on a series of training examples including an information resource with an associated ranking indicative of relevance to the user.

32. The method of claim 30 wherein the first and second heuristics are substantially similar.

33. The method of claim 30 further comprising:

repeating the steps of exploring, selecting, presenting, obtaining, and modifying until interrupted by the user.

34. The method of claim 30 wherein the step of selecting at least one information resource comprises:

selecting at least one information resource containing at least one object based on evaluation of the expression;

space="preserve" listing-type="equation">VALUE.sub.ik =FREQ.sub.ik * log.sub.2 (n)-log.sub.2 (DOCFREQ.sub.k)+1!

where FREQ_ik represents the number of times object k occurs in resource i, DOCFREQ_k represents the number of resources in which object k occurs, and n represents the total number of resources.

35. A system for retrieval of hyperlinked information resources, the system comprising:

a user interface for selecting system parameters, for providing system output to a suer, and for accepting input from a user;

a processor in communication with the user interface, the processor being operative to explore the hyperlinked information resources using a first heuristic to select at least one information resource, to extract at least one feature from the at least one information resource including a number of pictures within the resource, to present the at least one information resource to the user via the user interface based on the second heuristic, to obtain feedback from the user via the user interface, the feedback being indicative of relevance of the at least one information resource including an indication of a period of time during which the user views the least one information resources, and to modify the first and second heuristics based on the feedback.

36. A method for retrieval of hyperlinked information resources, the method comprising;

exploring the hyperlinked information resources using a first heuristic, the first heuristic including a metric for evaluating a number of pictures within the hyperlinked information resources;

selecting at least one information resource based on the first heuristic;

presenting the at least one information resource to a user via a user interface based on a second heuristic;

obtaining passive feedback from the user via the user interface indicative of relevance of the at least one information resource; and

modifying at least one of the first and second heuristics based on the feedback.

37. The method of claim 36 wherein the step of obtaining passive feedback from the user comprises:

monitoring a parameter indicative of relevance of the at least one information resource presented to the user.

38. The method of claim 36 wherein the step of obtaining passive feedback from the user comprises:

recording a value representing a period of time during which the user views each of the at least one information resources.