PATH INDEXING FOR NETWORK DATA

• US 20080195635A1
• Filed: 02/12/2007
• Published: 08/14/2008
• Est. Priority Date: 02/12/2007
• Status: Abandoned Application

• Current Assignee: Oath Inc. (Verizon Communications Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Chand, Jagdish, Narayanareddy, Jagannatha, Antony, Suresh, Nadgir, Avanti, Bhargava, Rajesh
• Application Number:
  US11/673,864
• Publication Number:
  US 20080195635A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A solution is provided wherein path information is stored for efficient retrieval. Raw path information may be stored in a path file. A node path index file may then be created containing entries for each of one or more corresponding nodes in the path information. Each node path entry corresponds to a unique appearance of the corresponding node in the path file, and wherein each node path entry contains a path file offset and a position of the corresponding node in the path file in the path indicated by the path file offset. A node index file may then be created containing, for one or more nodes in the path information, a single node entry containing an indication of the number of times the corresponding node in the node path index file appears in the node path index file and also containing a node path index file offset.

Claims

1. A method for storing path information for efficient access, wherein the path information relates to network nodes visited by users of a computer network, the method comprising:

storing the path information in at least one path file;

creating at least one node path index file containing one or more node path entries for each of the nodes in the path information, wherein each node path entry corresponds to a unique appearance of the corresponding node in the path file, and wherein each node path entry contains a path file offset indicating a starting point of a path containing the corresponding node in the path file, and wherein each node path entry further contains a position of the corresponding node in the path file in the path indicated by the path file offset; and

creating at least one node index file containing, for one or more nodes in the path information, a single node entry containing an indication of a number of times the corresponding node in the node path index file appears in the node path index file and also containing a node path index file offset indicating a starting point of node path entries for the corresponding node in the node path.

2. The method of claim 1, further comprising:

dividing the path information into two or more buckets prior to storing the path information in a path file.

3. The method of claim 2, wherein the storing the path information includes storing the path information in its own path file for each of the buckets.

4. The method of claim 3, wherein a single path file, node path index file, and node index file are created for each of the buckets.

5. The method of claim 4, wherein the node index file further contains one or more entries corresponding to nodes appearing in the path information corresponding to a different bucket but not appearing in the path information corresponding to the bucket for the node index file.

6. The method of claim 4, wherein the node index file only contains entries corresponding to nodes appearing in the path information corresponding to the bucket for the node index file.

7. A method for efficiently accessing path information stored in a path file, wherein the path information relates to network nodes visited by users of a computer network, the method comprising:

receiving a first node of interest;

determining a first node path index file offset and a number of times the first node of interest occurs in a node path index file by accessing a node index file;

retrieving a first number of entries in the node path index file, beginning at an entry indicated by the first node path index file offset, wherein the number of entries retrieved is equal to the number of times the first node of interest occurs in the node path index file; and

for each of the first number of retrieved entries from the node path index file, locating a starting point, in the path file, for a path corresponding to the retrieved entry and locating a position of the first node of interest in the path.

8. The method of claim 7, wherein the node index file contains, for one or more corresponding nodes in the path information, a single node entry containing an indication of the number of times the first node of interest appears in the node path index file and also containing an offset into a node path index file indicating a starting point of node path entries for the first node of interest.

9. The method of claim 8, wherein the node path index file contains one or more node path entries for each of one or more corresponding nodes in the path information, wherein each node path entry corresponds to a unique appearance of the corresponding node in the path file, and wherein each node path entry contains a path file offset indicating a starting point of a path containing the corresponding node, and wherein each node path entry further contains a position of the corresponding node in the path indicated by the path file offset

10. The method of claim 7, wherein the first node of interest is received from a user.

11. The method of claim 7, wherein the first node of interest is received from a software component.

12. The method of claim 7, further comprising:

receiving a second node of interest;

determining a second node path index file offset and a number of times the second node of interest occurs in the node path index file by accessing the node index file;

retrieving a second number of entries in the node path index file, beginning at an entry indicated by the second node path index file offset, wherein the number of entries retrieved is equal to the number of times the second node of interest occurs in the node path index file; and

for each of the second number of retrieved entries from the node path index file that contain a starting point identical to a starting point contained in one of the first number of retrieved entries, locating a starting point, in the path file, for a path corresponding to the retrieved entry and locating a position of the second node of interest in the path.

13. An apparatus for storing path information for efficient access, wherein the path information relates to network nodes visited by users of a computer network, the apparatus comprising:

a path information path file storer;

a node path index file creator coupled to the path information path storer; and

a node index file creator coupled to the node path index file creator.

14. An apparatus for efficiently accessing path information stored in a path file, wherein the path information relates to network nodes visited by users of a computer network, the apparatus comprising:

a node of interest receiver;

a node path index file offset determiner coupled to the node of interest receiver;

a node of interest node path index file occurrence frequency determiner coupled to the node path index file offset determiner;

a node path index file entry retriever coupled to the node of interest node path index file occurrence frequency determiner;

a path file starting point locator coupled to the node path index file entry retriever; and

a node path position locator coupled to the path file starting point determiner.

15. An apparatus for storing path information for efficient access, wherein the path information relates to network nodes visited by users of a computer network, the apparatus comprising:

means for storing the path information in at least one path file;

means for creating at least one node path index file containing one or more node path entries for each of the nodes in the path information, wherein each node path entry corresponds to a unique appearance of the corresponding node in the path file, and wherein each node path entry contains a path file offset indicating a starting point of a path containing the corresponding node in the path file, and wherein each node path entry further contains a position of the corresponding node in the path file in the path indicated by the path file offset; and

means for creating at least one node index file containing, for one or more nodes in the path information, a single node entry containing an indication of a number of times the corresponding node in the node path index file appears in the node path index file and also containing a node path index file offset indicating a starting point of node path entries for the corresponding node in the node path.

16. An apparatus for efficiently accessing path information stored in a path file, wherein the path information relates to network nodes visited by users of a computer network, the apparatus comprising:

means for receiving a first node of interest;

means for determining a first node path index file offset and a number of times the first node of interest occurs in a node path index file by accessing a node index file;

means for retrieving a first number of entries in the node path index file, beginning at an entry indicated by the first node path index file offset, wherein the number of entries retrieved is equal to the number of times the first node of interest occurs in the node path index file; and

means for, for each of the first number of retrieved entries from the node path index file, locating a starting point, in the path file, for a path corresponding to the retrieved entry and locating a position of the first node of interest in the path.

17. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method for storing path information for efficient access, wherein the path information relates to network nodes visited by users of a computer network, the method comprising:

storing the path information in at least one path file;

creating at least one node path index file containing one or more node path entries for each of the nodes in the path information, wherein each node path entry corresponds to a unique appearance of the corresponding node in the path file, and wherein each node path entry contains a path file offset indicating a starting point of a path containing the corresponding node in the path file, and wherein each node path entry further contains a position of the corresponding node in the path file in the path indicated by the path file offset; and

creating at least one node index file containing, for one or more nodes in the path information, a single node entry containing an indication of a number of times the corresponding node in the node path index file appears in the node path index file and also containing a node path index file offset indicating a starting point of node path entries for the corresponding node in the node path.

18. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method for efficiently accessing path information stored in a path file, wherein the path information relates to network nodes visited by users of a computer network, the method comprising:

receiving a first node of interest;

determining a first node path index file offset and a number of times the first node of interest occurs in a node path index file by accessing a node index file;

retrieving a first number of entries in the node path index file, beginning at an entry indicated by the first node path index file offset, wherein the number of entries retrieved is equal to the number of times the first node of interest occurs in the node path index file; and

for each of the first number of retrieved entries from the node path index file, locating a starting point, in the path file, for a path corresponding to the retrieved entry and locating a position of the first node of interest in the path.