Data processing: database and file management or data structures – Database design – Data structure types
Patent
1995-11-14
1998-05-12
Black, Thomas G.
Data processing: database and file management or data structures
Database design
Data structure types
707 2, 707 4, 707 5, G06F 1730
Patent
active
057522413
ABSTRACT:
The invention relates to method and apparatus for computing transitive closure and reachability in directed graphs. These are fundamental graph problems with many applications such as database query optimization. A random rank is applied to each node (or record or element, as the case may be) and the least rank reachable from each such node is determined. This least rank value reachable from a node is highly correlatable to the size of the reachable set. An estimator can therefore be applied to convert the least reachable rank value to an estimate of the size of the reachable set. The accuracy of the estimate can be increased by repeating the random rank assignments together with the least reachable rank determinations and averaging the results.
REFERENCES:
patent: 5201046 (1993-04-01), Goldberg et al.
patent: 5321833 (1994-06-01), Chang et al.
patent: 5497486 (1996-03-01), Stolfo et al.
patent: 5504887 (1996-04-01), Malhotra et al.
patent: 5542073 (1996-07-01), Schiefer et al.
patent: 5546571 (1996-08-01), Shan et al.
Edith Cohen, "Estimating the Size of the Transitive Closure in Linear Time", Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 190-200, Nov. 20, 1994.
Esko Nuutila, Transitive Closure (visited on Jan. 27, 1997), <http://www.cs.fi/.about.enu/tc.html>, Oct. 9, 1995.
Frederic Andres et al., "Estimating Recursive Query Costs for Various Parallel Environments", IEEE Publications, pp. 365-372, Sep. 1991.
Carlos Escalante et al., "Estimating the Cost of GraphLog Queries", IEEE Publications, pp. 145-148, May 1995.
Black Thomas G.
Lucent Technologies - Inc.
Robinson Greda L.
LandOfFree
Method and apparatus for estimating transitive closure and reach does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for estimating transitive closure and reach, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for estimating transitive closure and reach will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-996534