Methods and Systems For Pathing Analysis

• US 20120124030A1
• Filed: 11/12/2010
• Published: 05/17/2012
• Est. Priority Date: 11/12/2010
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: SEETHARAMA, Gururaj, KUNNUMMEL, Shaji Illias Chennan
• Granted Patent: US 9,471,696 B2
• Time in Patent Office: Days
• US Class Current: 707/716
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/953 Querying, e.g. by the use of web search engines
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Methods, systems and computer program products for pathing analysis are provided. The method includes receiving at a server, a query comprising one or more nodes. The method further includes identifying one or more prior queries, wherein the one or more prior queries comprise at least one of the one or more nodes. The method accesses metadata associated with the one or more prior queries. The method then selects based on the metadata, one or more data partitions for further processing. Next, the method causes one or more computers to identify one or more paths in the selected data partitions, wherein the one or more paths comprise at least the one or more nodes. Finally, the method presents the identified paths as an output to the query.

Claims

1. A method for pathing analysis, the method comprising:

receiving, at a server, a query identifying one or more nodes;

identifying one or more prior queries that include at least one of the one or more nodes;

accessing metadata associated with the one or more prior queries;

selecting, based on the metadata, one or more data partitions for further processing;

causing one or more computers to identify one or more paths in the selected data partitions, wherein the one or more paths comprise at least the one or more nodes; and

presenting the identified paths as an output to the query.

2. The method of claim 1 wherein identifying the one or more prior queries comprises searching one or more hash maps associated with the one or more nodes.

3. The method of claim 2 further comprising updating the one or more hash maps associated with the one or more nodes.

4. The method of claim 1 wherein the metadata comprises one or more of an identifier of a data partition, a number of unique paths comprising at least the one or more nodes, a maximum frequency associated with a first unique path, and a minimum frequency associated with a second unique path.

5. The method of claim 1 further comprising ordering the selected data partitions to form a processing order.

6. The method of claim 1 wherein causing the one or more computers to identify the one or more paths comprises transferring a processing order of the selected data partitions to the one or more computers.

7. The method of claim 1 further comprising storing metadata associated with the query.

8. A system for path analysis, the system comprising:

one or more network interfaces;

at least one processor;

a memory; and

computer program code stored in a computer readable storage medium, wherein the computer program code, when executed, is operative to cause the at least one processor to;

receive at a server, a query comprising one or more nodes;

identify one or more prior queries, wherein the one or more prior queries comprise at least one of the one or more nodes;

access metadata associated with the one or more prior queries;

select based on the metadata, one or more data partitions for further processing;

cause one or more computers to identify one or more paths in the selected data partitions, wherein the one or more paths comprise at least the one or more nodes; and

present the identified paths as an output to the query.

9. The system of claim 8, wherein the computer program code is further operative to cause the at least one processor to identify the one or more prior queries comprises searching one or more hash maps associated with the one or more nodes.

10. The system of claim 9, wherein the computer program code is further operative to cause the at least one processor to update the one or more hash maps associated with the one or more nodes.

11. The system of claim 8 wherein the metadata comprises one or more of an identifier of a data partition, a number of unique paths comprising at least the one or more nodes, a maximum frequency associated with a first unique path, and a minimum frequency associated with a second unique path.

12. The system of claim 8, wherein the computer program code is further operative to cause the at least one processor to order the selected data partitions to form a processing order.

13. The system of claim 8, wherein the computer program code is further operative to cause the at least one processor to transfer a processing order of the selected data partitions to the one or more computers.

14. The system of claim 8, wherein the computer program code is further operative to cause the at least one processor to store metadata associated with the query.

15. One or more computer-readable non-transitory storage media embodying software operable when executed by one or more computer systems to:

receive at a server, a query comprising one or more nodes;

identify one or more prior queries, wherein the one or more prior queries comprise at least one of the one or more nodes;

access metadata associated with the one or more prior queries;

select based on the metadata, one or more data partitions for further processing;

cause one or more computers to identify one or more paths in the selected data partitions, wherein the one or more paths comprise at least the one or more nodes; and

present the identified paths as an output to the query.

16. The computer-readable non-transitory storage media of claim 15 further embodying software operable when executed by one or more computer systems to identify the one or more prior queries comprises searching one or more hash maps associated with the one or more nodes.

17. The computer-readable non-transitory storage media of claim 16 further embodying software operable when executed by one or more computer systems to update the one or more hash maps associated with the one or more nodes.

18. The computer-readable non-transitory storage media of claim 15 wherein the metadata comprises one or more of an identifier of a data partition, a number of unique paths comprising at least the one or more nodes, a maximum frequency associated with a first unique path, and a minimum frequency associated with a second unique path.

19. The computer-readable non-transitory storage media of claim 15 further embodying software operable when executed by one or more computer systems to order the selected data partitions to form a processing order.

20. The computer-readable non-transitory storage media of claim 15 further embodying software operable when executed by one or more computer systems to transfer a processing order of the selected data partitions to the one or more computers.

21. The computer-readable non-transitory storage media of claim 15 further embodying software operable when executed by one or more computer systems to cause the at least one processor to store metadata associated with the query.