System and method for selecting and displaying hyperlinked information resources

• US 6,256,648 B1
• Filed: 01/29/1998
• Issued: 07/03/2001
• Est. Priority Date: 01/29/1998
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Hill, William Colyer, Terveen, Loren Gilbert
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): Kindred, Alford W.
• Application Number:
  US09/015,341
• Time in Patent Office: 1,251 Days
• Field of Search: 707/516, 707/3-5, 707/500-515, 345/302
• US Class Current: 715/234
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing

Abstract

A set of seed resources S is received that is typically specified by a user. A set of discovered resources D is identified from a hyperlinked collection of resources C such that each resource in D is in a NK clan graph with respect to the set of seed resources S. An NK clan graph is the set of all resources that are in an N clan with at least K seeds. An N clan is a subgraph G of the hyperlinked collection of resources C such that every node in G is connected to every other node in G by a path of length N or less, and the connecting paths traverse only nodes in the subgraph G. The set of discovered resources D is added to the set of seed resources S. At least some of the resources in subgraph G are displayed to the user to convey information about resources in G as well as the relationship between these resources.

Claims

1. A method for selecting resources from a hyperlinked collection of resources C, comprising the steps of:

a. receiving a set of seed resources S;

b. identifying a set of discovered resources D, such that each resource in D is in a NK clan graph in relationship with respect to the set of seed resources, an NK clan graph being the set of all resources that are in an N clan in relationship with at least K seeds, an N clan being a subgraph G of the hyperlinked collection of resources C such that every node in G is connected to every other node in G by a path of length N or less, and the connecting paths traverse only nodes in the subgraph G; and

c. adding the set of discovered resources D to the set of seed resources S.

2. The method of claim 1, wherein identifying the set of discovered resources includes the steps of:

a. fetching the content of each seed resource R in S;

b. adding to a candidate set CS each resource CR to which any seed resource R links;

c. determining a score for each candidate resource CR in CS;

d. removing a highest scored candidate CRH from CS;

e. fetching the content of CRH;

f. adding to CS each resource to which CRH links

g. adding CRH to G;

h. repeating steps a through g until either CS is empty or no resource in CS has a score that is above a specified threshold or G contains a predetermined maximum number of resources.

3. The method of claim 2, wherein determining a score for each candidate resource CR in CS includes the step of counting the number of seed resources to which CR is linked by paths of length 1 or 2.

4. The method of claim 2, wherein a candidate resource includes pages, and wherein fetching the content of CRH includes fetching pages from the resource until an index page of the resource is fetched.

5. The method of claim 4, wherein fetching the index page of the resource includes the step of analyzing the title of the page.

6. The method of claim 4, wherein fetching the index page of the resource includes the step of calculating a ratio of the number of external links in the page to the size of the page.

7. The method of claim 4, wherein fetching the index page of the resource includes the step of determining the number of external links of the page.

8. The method of claim 4, wherein fetching the index page of the resource includes the step of determining if the page contains at least r instances of at least s terms from the group of:

link, links, page, pages, resource, resources, web and internet, where r and s are integers.

9. The method of claim 2, wherein a candidate resource includes pages, and wherein fetching the content of CRH includes fetching at least p(min) pages from a resource and no more than p(max) pages from a resource, p(min) and p(max) being integers such that p(min) is less than or equal to p(max).

10. The method of claim 2, wherein fetching the content of CRH includes the steps of:

a. fetching at least p(min) pages;

b. continuing to fetch pages until a fetched page is identified as an index page; and

c. stopping to fetch pages when the number of fetched pages is equal to p(max).

11. The method of claim 1, further comprising the step of determining properties of subgraph G.

12. The method of claim 11 wherein determining the properties of subgraph G includes the step of determining the number of in-links I and out-links O of each resource in G, I and O being integers.

13. The method of claim 11, wherein determining the properties of subgraph G includes the steps of:

a. identifying a type t of each internal link of a resource in G;

b. determining a number N(t) of each type t of internal link; and

c. storing the number N(t) of each type of link correlated with the resource.

14. The claim of 13, wherein the type t of an internal link is one from the group of:

audio, video, animation, text, hypertext, graphic, and executable.

15. The method of claim 11, wherein the determining the properties of subgraph G includes the step of determining a number Q of N clans in G of which a resource in G is a member.

16. The method of claim 1, further comprising the step of displaying resources in G.

17. The method of claim 16, wherein a resource in G is displayed as a thumbnail graphic.

18. The method of claim 17, wherein the contents of the resource are displayed when the thumbnail graphic is selected.

19. The method of claim 16, wherein resources related to a particular resource are indicated in response to a request from a user.

20. The method of claim 19, wherein the related resources are indicated by changing the color of thumbnail graphics corresponding to related resources.

21. The method of claim 19, wherein the related resources are indicated by changing the color of the unrelated resources.

22. The method of claim 16, wherein a link direction by which a first resource is related to a second resource is indicated by providing an arrow pointing towards the thumbnail graphic corresponding to the second resource when the first resource is linked to the second resource, and providing an arrow pointing away from the thumbnail graphic corresponding to the second resource when the second resource is linked to the first resource.

23. The method of claim 22, wheerein the link direction of relationships of a first resource is indicated in response to the user request.

24. The method of claim 16, wherein displaying resources in G comprising the steps of:

a. sorting resources in G in accordance with a first user specified criterion;

b. displaying at least a portion of the sorted resources such that a highest ranked resources according to the first criterion are shown near a given point on a display, a lowest ranked resources are shown furthest from the point, and intermediately ranked resources are shown therebetween in accordance with their ranking.

25. The method of claim 24, further comprising the steps of:

a. sorting resources in G in accordance with a second user specified criterion;

b. displaying at least a portion of the resources such that the highest ranked resources according to the second criterion are shown near a first edge of the display, the least lowest ranked resources are shown near a second edge of the display, and intermediately ranked resources are shown therebetween in accordance with their ranking.

26. The method of claim 24, further comprising the steps of:

a. sorting resources in G in accordance with a third user specified criterion;

b. displaying at least a portion of the resources such that the highest ranked resources according to the third criterion are shown in a first color, the lowest ranked resources are shown in a second color, and intermediately ranked resources are shown in colors therebetween in accordance with their ranking.

27. An apparatus for selecting resources from a hyperlinked collection of resources C, comprising:

a. a processor;

b. memory that stores instructions adapted to be executed on said processor to receive a set of seed resources S, identify discovered resources that are in a NK clan graph with respect to the set of seed resources,“

S,”

an NK clan graph being the set of all resources that are in an N clan in relationship with at least K seeds, an N clan being a subgraph G of the hyperlinked collection of resources C such that every node in G is connected to every other node in G by a path of length N or less, and the connecting paths traverse only nodes in the subgraph G, and add discovered resources to the set of seed resources S.

28. The apparatus of claim 27, further comprising a port adapted to be coupled to a network, said port coupled to said processor and said memory, and said port adapted to convey a set of seed resources to said processor.

29. A medium that stores instructions adapted to be executed by a processor to perform the steps of:

a. receiving a set of seed resources S;

b. identifying a set of discovered resources D, such that each resource in D is in a NK clan graph with respect to the set of seed resources, an NK clan graph being the set of all resources that are in an N clan with at least K seeds, an N clan being a subgraph G of the hyperlinked collection of resources C such that every node in G is connected to every other node in G by a path of length N or less, and the connecting paths traverse only nodes in the subgraph G, where N and K are integers; and

c. adding the set of discovered resources D to the set of seed resources S.

30. A system for selecting resources from a hyperlinked collection of resources C, comprising:

a. means for receiving a set of seed resources S;

b. means for identifying a set of discovered resources D, such that each resource in D is in a NK clan graph with respect to the set of seed resources, an NK clan graph being the set of all resources that are in an N clan with at least K seeds, an N clan being a subgraph G of the hyperlinked collection of resources C such that every node in G is connected to every other node in G by a path of length N or less, and the connecting paths traverse only nodes in the subgraph G, where N and K are integers; and

c. means for adding the set of discovered resources D to the set of seed resources S.