Method and system for determining interest levels of online content navigation paths

• US 7,774,335 B1
• Filed: 12/29/2005
• Issued: 08/10/2010
• Est. Priority Date: 08/23/2005
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Scofield, Christopher L., Pope, Elmore Eugene, Marshall, Brad E.
• Primary Examiner(s): Ehichioya; Fred I
• Application Number:
  US11/321,890
• Time in Patent Office: 1,685 Days
• Field of Search: 707/705, 707/709, 707/710, 707/713, 707/736, 707/748, 707/750, 707/751
• US Class Current: 707/709
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A method and system for determining interest levels of online content navigation paths. A method may include determining each of a plurality of navigation paths among a plurality of online content sources, and for each of the navigation paths, determining a corresponding path weight, where a given corresponding path weight is indicative of user activity along a corresponding navigation path. The method may further include identifying a particular aggregate path within the online content sources, where the particular path includes some of the navigation paths, where an aggregate path weight corresponding to the particular path is dependent upon the path weights corresponding to the navigation paths included in the particular path, and where the aggregate path weight satisfies an optimization criterion relative to other aggregate paths. A given navigation path included in the particular aggregate path may correspond to a possible user traversal from a first to a second online content source.

Claims

1. A method, comprising:

one or more computer systems, each comprising at least a processor for performing;

determining each of a plurality of navigation paths among a plurality of online content sources;

for each of said plurality of navigation paths, determining a respective corresponding path weight, wherein different values of said corresponding path weights are indicative of different levels of user activity along corresponding ones of said navigation paths and wherein said user activity comprises a plurality of requests generated by a plurality of users to access individual ones of said online content sources; and

identifying a particular one of a plurality of aggregate paths within said plurality of online content sources, wherein said particular aggregate path includes one or more of said navigation paths, wherein an aggregate path weight corresponding to said particular aggregate path is dependent upon said one or more path weights corresponding to said one or more of said navigation paths included in said particular aggregate path, and wherein said aggregate path weight satisfies an optimization criterion relative to aggregate path weights of other ones of said plurality of aggregate paths within said plurality of online content sources, such that said particular aggregate path is selected from other ones of said aggregate paths dependent upon corresponding path weights of said one or more navigation paths included in said particular aggregate path;

wherein a given one of said one or more navigation paths included in said particular aggregate path corresponds to a possible user traversal from a first one of said online content sources to a second one of said online content sources.

2. The method as recited in claim 1, wherein said determining each of a plurality of navigation paths comprises, for said given navigation path, detecting within said first online content source an explicit navigation reference to said second online content source.

3. The method as recited in claim 2, wherein each of said first and said second online content sources corresponds to a respective web page, and wherein said explicit navigation reference corresponds to a navigation link encoded within said first online content source.

4. The method as recited in claim 1, wherein said determining each of a plurality of navigation paths comprises, for said given navigation path, detecting a content access request directed to said second online content source, wherein said content access request indicates that said first online content source is a referrer of said content access request.

5. The method as recited in claim 1, wherein said given path weight corresponds to a rate at which users traverse said corresponding navigation path.

6. The method as recited in claim 1, wherein said given path weight corresponds to a time rate of change of a rate at which users traverse said corresponding navigation path.

7. The method as recited in claim 6, further comprising determining said time rate of change dependent upon numerically computing a first derivative with respect to time of a time series of data points corresponding to said users traversing said corresponding navigation path.

8. The method as recited in claim 1, wherein said identifying a particular aggregate path comprises determining whether said aggregate path weight satisfies said optimization criterion, and wherein said determining whether said aggregate path weight satisfies said optimization criterion comprises determining whether said aggregate path weight is maximal relative to aggregate path weights of said plurality of aggregate paths within said plurality of online content sources.

9. The method as recited in claim 1, wherein said identifying a particular aggregate path comprises determining whether said aggregate path weight satisfies said optimization criterion, and wherein said determining whether said aggregate path weight satisfies said optimization criterion comprises determining whether said aggregate path weight is minimal relative to aggregate path weights of said plurality of aggregate paths within said plurality of online content sources.

10. The method as recited in claim 1, wherein said identifying a particular aggregate path comprises determining whether said aggregate path weight satisfies said optimization criterion, and wherein said determining whether said aggregate path weight satisfies said optimization criterion comprises determining whether said aggregate path weight equals a target path weight, within a threshold of equality.

11. The method as recited in claim 1, wherein said identifying a particular aggregate path includes limiting a number of navigation paths included in said particular aggregate path.

12. The method as recited in claim 1, wherein said aggregate path weight corresponding to said particular aggregate path is determined as a function of path weights corresponding to said navigation paths included in said particular aggregate path.

13. The method as recited in claim 12, wherein said function corresponds to a summation of said path weights.

14. The method as recited in claim 1, wherein a topology of said navigation paths among said plurality of online content sources differs from a topology of explicit navigation links included among said plurality of online content sources.

15. The method as recited in claim 1, wherein a topology of said navigation paths among said plurality of online content sources differs from a topology of communication paths among systems configured to implement said plurality of online content sources.

16. A computer-accessible storage medium storing instructions, wherein the instructions are executable to:

determine each of a plurality of navigation paths among a plurality of online content sources;

for each of said plurality of navigation paths, determine a corresponding path weight, wherein different values of said corresponding path weights are indicative of different levels of user activity along corresponding ones of said navigation paths, and wherein said user activity comprises a plurality of requests generated by a plurality of users to access individual ones of said online content sources; and

identify a particular one of a plurality of aggregate paths within said plurality of online content sources, wherein said particular aggregate path includes one or more of said navigation paths, wherein an aggregate path weight corresponding to said particular aggregate path is dependent upon said one or more path weights corresponding to said one or more of said navigation paths included in said particular aggregate path, and wherein said aggregate path weight satisfies an optimization criterion relative to aggregate path weights of other ones of said plurality of aggregate paths within said plurality of online content sources, such that said particular aggregate path is selected from other ones of said aggregate paths dependent upon corresponding path weights of said one or more navigation paths included in said particular aggregate path;

wherein a given one of said one or more navigation paths included in said particular aggregate path corresponds to a possible user traversal from a first one of said online content sources to a second one of said online content sources.

17. The computer-accessible storage medium as recited in claim 16, wherein said determining each of a plurality of navigation paths comprises, for said given navigation path, detecting within said first online content source an explicit navigation reference to said second online content source.

18. The computer-accessible storage medium as recited in claim 17, wherein each of said first and said second online content sources corresponds to a respective web page, and wherein said explicit navigation reference corresponds to a navigation link encoded within said first online content source.

19. The computer-accessible storage medium as recited in claim 16, wherein said determining each of a plurality of navigation paths comprises, for said given navigation path, detecting a content access request directed to said second online content source, wherein said content access request indicates that said first online content source is a referrer of said content access request.

20. The computer-accessible storage medium as recited in claim 16, wherein said given path weight corresponds to a rate at which users traverse said corresponding navigation path.

21. The computer-accessible storage medium as recited in claim 16, wherein said given path weight corresponds to a time rate of change of a rate at which users traverse said corresponding navigation path.

22. The computer-accessible storage medium as recited in claim 21, wherein the instructions are further executable to determine said time rate of change dependent upon numerically computing a first derivative with respect to time of a time series of data points corresponding to said users traversing said corresponding navigation path.

23. The computer-accessible storage medium as recited in claim 16, wherein said identifying a particular aggregate path comprises determining whether said aggregate path weight satisfies said optimization criterion, and wherein said determining whether said aggregate path weight satisfies said optimization criterion comprises determining whether said aggregate path weight is maximal relative to aggregate path weights of said plurality of aggregate paths within said plurality of online content sources.

24. The computer-accessible storage medium as recited in claim 16, wherein said identifying a particular aggregate path comprises determining whether said aggregate path weight satisfies said optimization criterion, and wherein said determining whether said aggregate path weight satisfies said optimization criterion comprises determining whether said aggregate path weight is minimal relative to aggregate path weights of said plurality of aggregate paths within said plurality of online content sources.

25. The computer-accessible storage medium as recited in claim 16, wherein said identifying a particular aggregate path comprises determining whether said aggregate path weight satisfies said optimization criterion, and wherein said determining whether said aggregate path weight satisfies said optimization criterion comprises determining whether said aggregate path weight equals a target path weight, within a threshold of equality.

26. The computer-accessible storage medium as recited in claim 16, wherein said identifying a particular aggregate path includes limiting a number of navigation paths included in said particular aggregate path.

27. The computer-accessible storage medium as recited in claim 16, wherein said aggregate path weight corresponding to said particular aggregate path is determined as a function of path weights corresponding to said navigation paths included in said particular aggregate path.

28. The computer-accessible storage medium as recited in claim 27, wherein said function corresponds to a summation of said path weights.

29. The computer-accessible storage medium as recited in claim 16, wherein a topology of said navigation paths among said plurality of online content sources differs from a topology of explicit navigation links included among said plurality of online content sources.

30. The computer-accessible storage medium as recited in claim 16, wherein a topology of said navigation paths among said plurality of online content sources differs from a topology of communication paths among systems configured to implement said plurality of online content sources.

31. A system, comprising:

one or more computer systems, each comprising at least a processor and a memory, wherein the one or more computer systems are configured to store and execute instructions that are configured to implement;

a web services interface configured to receive, according to a web services protocol, respective reports from a plurality of content sources of content request traffic directed to said content sources; and

a traffic analysis engine configured to receive said reports from said web services interface and to;

determine each of a plurality of navigation paths among a plurality of online content sources;

for each of said plurality of navigation paths, determine a corresponding path weight, wherein different values of said corresponding path weights are indicative of different levels of user activity along corresponding ones of said navigation paths, and wherein said user activity comprises a plurality of requests generated by a plurality of users to access individual ones of said online content sources; and

identify a particular one of a plurality of aggregate paths within said plurality of online content sources, wherein said particular aggregate path includes one or more of said navigation paths, wherein an aggregate path weight corresponding to said particular aggregate path is dependent upon said one or more path weights corresponding to said one or more of said navigation paths included in said particular aggregate path, and wherein said aggregate path weight satisfies an optimization criterion relative to aggregate path weights of other ones of said plurality of aggregate paths within said plurality of online content sources, such that said particular aggregate path is selected from other ones of said aggregate paths dependent upon corresponding path weights of said one or more navigation paths included in said particular aggregate path;

wherein a given one of said one or more navigation paths included in said particular aggregate path corresponds to a possible user traversal from a first one of said online content sources to a second one of said online content sources.

32. The system as recited in claim 31, wherein to determine said given one of said plurality of navigation paths, the traffic analysis engine is further configured to detect within said first online content source an explicit navigation reference to said second online content source.

33. The system as recited in claim 32, wherein each of said first and said second online content sources corresponds to a respective web page, and wherein said explicit navigation reference corresponds to a navigation link encoded within said first online content source.

34. The system as recited in claim 31, wherein to determine said given one of said plurality of navigation paths, the traffic analysis engine is further configured to detect a content access request directed to said second online content source, wherein said content access request indicates that said first online content source is a referrer of said content access request.

35. The system as recited in claim 31, wherein said given path weight corresponds to a rate at which users traverse said corresponding navigation path.

36. The system as recited in claim 31, wherein said given path weight corresponds to a time rate of change of a rate at which users traverse said corresponding navigation path.

37. The system as recited in claim 36, wherein said traffic analysis engine is further configured to determine said time rate of change dependent upon numerically computing a first derivative with respect to time of a time series of data points corresponding to said users traversing said corresponding navigation path.

38. The system as recited in claim 31, wherein to identify a particular aggregate path, the traffic analysis engine is further configured to determine whether said aggregate path weight satisfies said optimization criterion, and wherein to determine whether said aggregate path weight satisfies said optimization criterion, the traffic analysis engine is further configured to determine whether said aggregate path weight is maximal relative to aggregate path weights of said plurality of aggregate paths within said plurality of online content sources.

39. The system as recited in claim 31, wherein to identify a particular aggregate path, the traffic analysis engine is further configured to determine whether said aggregate path weight satisfies said optimization criterion, and wherein to determine whether said aggregate path weight satisfies said optimization criterion, the traffic analysis engine is further configured to determine whether said aggregate path weight is minimal relative to aggregate path weights of said plurality of aggregate paths within said plurality of online content sources.

40. The system as recited in claim 31, wherein to identify a particular aggregate path, the traffic analysis engine is further configured to determine whether said aggregate path weight satisfies said optimization criterion, and wherein to determine whether said aggregate path weight satisfies said optimization criterion, the traffic analysis engine is further configured to determine whether said aggregate path weight equals a target path weight, within a threshold of equality.

41. The system as recited in claim 31, wherein to identify a particular aggregate path, the traffic analysis engine is further configured to limit a number of navigation paths included in said particular aggregate path.

42. The system as recited in claim 31, wherein said traffic analysis engine is further configured to determine said aggregate path weight corresponding to said particular aggregate path as a function of path weights corresponding to said navigation paths included in said aggregate path.

43. The system as recited in claim 42, wherein said function corresponds to a summation of said path weights.

44. The system as recited in claim 31, wherein a topology of said navigation paths among said plurality of online content sources differs from a topology of explicit navigation links included among said plurality of online content sources.

45. The system as recited in claim 31, wherein a topology of said navigation paths among said plurality of online content sources differs from a topology of communication paths among systems configured to implement said plurality of online content sources.