Browse Prior Art Database

Method and System for Caching Metadata Associated with Complex Pathing Analysis Queries

IP.com Disclosure Number: IPCOM000200456D
Publication Date: 2010-Oct-14
Document File: 7 page(s) / 74K

Publishing Venue

The IP.com Prior Art Database

Related People

Gururaj S: INVENTOR [+2]

Abstract

A method and system for caching metadata associated with complex pathing analysis queries is disclosed. The meta-data generated from a history of pathing queries is efficiently cached thereby improving performance of currently submitted query. The method and system may be applied to any querying system, with a concept of a node and a path having queries run on a huge data set wherein indexing of data is practically impossible.

This text was extracted from a Microsoft Word document.
This is the abbreviated version, containing approximately 20% of the total text.

Method and System for Caching Metadata Associated with Complex Pathing Analysis Queries

Abstract

A method and system for caching metadata associated with complex pathing analysis queries is disclosed.  The meta-data generated from a history of pathing queries is efficiently cached thereby improving performance of currently submitted query.  The method and system may be applied to any querying system, with a concept of a node and a path having queries run on a huge data set wherein indexing of data is practically impossible.

Description

Disclosed is a method and system for efficient caching of metadata associated with complex pathing analysis queries. 

In an instance, a system may need to support following type of queries:

1.    List all path segments which starts with a given node or a set of nodes based on number of visits;

2.    List all the path segments which starts with a given node or a set of nodes and end at a given node or a set of nodes based on the number of visits; and

3.    List all the path segments that starts with a given node or a set of nodes, end at a given node or a set of nodes and pass through a given node or a set of nodes based on the number of visits.  

In this case, assuming that system may have two number of nodes i.e., N = 2, then total path-segments may be equivalent to the number of ways in which these two nodes can be connected.  Hence, if n1 and n2 are the nodes, then the paths are (n1; n2) and (n2; n1).  The number of paths is equivalent to permutation of N over number of ways the paths may be created.  Therefore, TotalPath(2) = P(2, 2) = 2.

Further, when N = 3, one may have paths of size 3 and size 2.  Hence, TotalPath(3) = P(3, 3) + P(3, 2) = 6 + 6 = 12.  Similarly, when N = 4 the

TotalPath (4) = P(4, 4) + P(4, 3) + P(4, 2) = 24 + 24 + 12 = 60. 

Moreover, when number of nodes N = n, the

TotalPath (n) = P(n, n) + P(n, n - 1) + P(n, 2).

Based on this example, indexing all the paths available in the system may be practically impossible.

Therefore, in order to overcome this problem, a caching mechanism disclosed herein is employed for expediently processing queries that are either processed earlier or "relaxed" to some earlier processed queries.  A query q1 may be referred to as “relaxed” query of a query q2 if any path that qualifies for query q1 also qualifies for query q2 but not vice versa.

For example, a query q1 may have a path s1 as q1 = (s1); and the query q2 may have paths s1 and d1 as q2 = (s1, d1).

In this case, the query q1 is referred to as “relaxed” query of the query q2 as the path s1 that qualifies for the query q1 also qualifies for the query q2.  Whereas, the path d1 that qualifies for the query q2 does not qualify for the query q1.

The problem described addressed herein may be solved in a distributed environment called as a Master-Drone environment.  In a Master-Drone environment, there is a designated processing node called as a Master and a set of other processing nodes called as...