Ranking nodes for session-based queries

• US 8,060,503 B2
• Filed: 12/26/2007
• Issued: 11/15/2011
• Est. Priority Date: 12/22/2006
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Stergiou, Stergios, Jain, Jawahar
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Davanlou; Soheila
• Application Number:
  US11/964,249
• Publication Number:
  US 20090171928A1
• Time in Patent Office: 1,420 Days
• Field of Search: 707/104, 707/100, 707/706, 707/726, 707/748
• US Class Current: 707/726
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

In one embodiment, a method includes accessing a model of a set of nodes including a session node and multiple linked nodes linked to the session node. The linked nodes include parent nodes and child nodes. A parent node links one or more child nodes to the session node, and a child node has one or more parent nodes linking the child node to the session node. The method includes generating a probability distribution for the set of nodes that distributes probabilities to all linked nodes within a predetermined number of links from the session node. Each child node receives from each of its parent nodes a predetermined fraction of a probability distributed to the parent node, and the parent node uniformly distributes to each of its child nodes the predetermined fraction of the probability distributed to the parent node.

Claims

1. A method comprising, by one or more computing devices:

accessing a model of a set of nodes comprising a session node and a plurality of linked nodes linked to the session node, the linked nodes comprising parent nodes and child nodes, a parent node linking one or more child nodes to the session node, a child node having one or more parent nodes linking the child node to the session node;

generating a probability distribution for the set of nodes that distributes probabilities to all linked nodes within a predetermined number of links from the session node, each child node receiving from each of its parent nodes a predetermined fraction of a probability distributed to the parent node, the parent node uniformly distributing to each of its child nodes the predetermined fraction of the probability distributed to the parent node; and

communicating the probability distribution for use in ranking the set of nodes.

2. The method of claim 1, wherein the nodes are web pages comprising Hypertext Markup Language (HTML) documents.

3. The method of claim 1, wherein the predetermined number of links models user patience.

4. The method of claim 1, wherein the predetermined number of links derives from:

input provided by a user searching the set of nodes, the input indicating whether the user is novice or expert;

or

data profiling one or more search patterns followed by the user.

5. The method of claim 1, wherein the predetermined number of links is two or more.

6. The method of claim 1, wherein the predetermined number of links is two.

7. The method of claim 1, wherein the predetermined fraction is ½

.

8. The method of claim 1, wherein the model of the set of node comprises a graph modeling at least a portion of the World Wide Web.

9. The method of claim 1, wherein the rankings facilitate searching among the set of nodes to generate a response to a query from a user.

10. The method of claim 1, further comprising:

generating a plurality of probability distributions for the set of nodes that distribute probabilities to all linked nodes within different predetermined numbers of links from the session node;

averaging the probability distributions; and

communicating the averaged probability distribution for use in ranking the set of nodes.

11. The method of claim 1, further comprising:

generating a plurality of probability distributions for the set of nodes that distribute probabilities to all linked nodes within different predetermined numbers of links from the session node; and

communicating the plurality of probability distributions for use in ranking the set of nodes according to preferences specified by a user.

12. The method of claim 1, wherein generating the probability distribution for the set of nodes comprises iteratively computing probability distributions starting from a uniform probability distribution, the generated probability distribution resulting from a convergence of the iteratively computed probability distributions.

13. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

access a model of a set of nodes comprising a session node and a plurality of linked nodes linked to the session node, the linked nodes comprising parent nodes and child nodes, a parent node linking one or more child nodes to the session node, a child node having one or more parent nodes linking the child node to the session node;

generate a probability distribution for the set of nodes that distributes probabilities to all linked nodes within a predetermined number of links from the session node, each child node receiving from each of its parent nodes a predetermined fraction of a probability distributed to the parent node, the parent node uniformly distributing to each of its child nodes the predetermined fraction of the probability distributed to the parent node; and

communicate the probability distribution for use in ranking the set of nodes.

14. The media of claim 13, wherein the nodes are web pages comprising Hypertext Markup Language (HTML) documents.

15. The media of claim 13, wherein the predetermined number of links models user patience.

16. The media of claim 13, wherein the predetermined number of links derives from:

input provided by a user searching the set of nodes, the input indicating whether the user is novice or expert;

or

data profiling one or more search patterns followed by the user.

17. The media of claim 13, wherein the predetermined number of links is two or more.

18. The media of claim 13, wherein the predetermined number of links is two.

19. The media of claim 13, wherein the predetermined fraction is ½

.

20. The media of claim 13, wherein the model of the set of node comprises a graph modeling at least a portion of the World Wide Web.

21. The media of claim 13, wherein the rankings facilitate searching among the set of nodes to generate a response to a query from a user.

22. The media of claim 13, further operable when executed to:

generate a plurality of probability distributions for the set of nodes that distribute probabilities to all linked nodes within different predetermined numbers of links from the session node;

average the probability distributions; and

communicate the averaged probability distribution for use in ranking the set of nodes.

23. The media of claim 13, further operable when executed to:

generate a plurality of probability distributions for the set of nodes that distribute probabilities to all linked nodes within different predetermined numbers of links from the session node; and

communicate the plurality of probability distributions for use in ranking the set of nodes according to preferences specified by a user.

24. The media of claim 13, wherein generating the probability distribution for the set of nodes comprises iteratively computing probability distributions starting from a uniform probability distribution, the generated probability distribution resulting from a convergence of the iteratively computed probability distributions.