 |
|
|
|
|
|
 Title: |
US5752241:
Method and apparatus for estimating transitive closure and reachability
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Cohen, Edith; Chatham, NJ
|
| Assignee: |
Lucent Technologies Inc., Murray Hill, NJ
other patents from LUCENT TECHNOLOGIES INC. (722326) (approx. 6,959)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1998-05-12
/ 1995-11-14
|
| Application Number: |
US1995000557223
|
| IPC Code: |
Advanced:
G06F 17/30;
Core:
more...
IPC-7:
G06F 17/30;
|
| ECLA Code: |
G06F17/30S4P3T5S; G06F17/30G3;
|
| U.S. Class: |
Current:
707/003;
707/002;
707/004;
707/005;
707/E17.012;
Original:
707/003;
707/002;
707/004;
707/005;
|
| Field of Search: |
395/605,603,602,604
707/003,5,2,4
|
| Priority Number: |
| 1995-11-14 |
US1995000557223 |
|
| 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.
|
| Primary / Asst. Examiners: |
Black, Thomas G.; Robinson, Greda L.
|
| INPADOC Legal Status: |
Show legal status actions
|
| Family: |
None
|
First Claim:
Show all 25 claims |
I claim:
1. A database query method using estimates of the size of reachability sets in a database including a plurality of elements each including reachability information to other elements comprising the steps:
- assigning random ranks to elements in the database;
- computing the rank of the least ranked element in each of a plurality of reachability sets;
- applying an estimator to the rank of the least ranked element in each of the plurality of reachability sets to provide an estimate of the size of each of the plurality of reachability sets;
- using said estimate of the size of each of the plurality of reachability sets to perform a database query.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 15 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS G98-297399
DERG98-297399
|
| Other References: |
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), , 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.
|
|
 Nominate this for the Gallery...
|
|
