Minimum leaf spanning tree
US6105018A · kind A · utility
57Cited by
3References
26Claims
0Family size
Assignee
Inventors
Key dates
| Filing date | Mar 26, 1998 |
| Grant date | Aug 15, 2000 |
| Priority date | — |
| Expiry date | Mar 26, 2018 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99935
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
An efficient set of indexes to cover a plurality of anticipated query types is determined by building a directed acyclic graph whose nodes correspond to anticipated query types. A minimum leaf spanning tree for the equivalent graph is determined by repeatedly finding an augmenting path for a current spanning tree and producing a reduced leaf spanning tree based on the current spanning tree and the augmenting path until an augmenting path can no longer be found. The leaves of the minimum leaf spanning tree indicate which indexes should be built.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.