Method and apparatus for estimating transitive closure and reachability
US5752241A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | Nov 14, 1995 |
| Grant date | May 12, 1998 |
| Priority date | — |
| Expiry date | Nov 14, 2015 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99935
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.