Method and apparatus for implementing Q-trees
US5664184A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Nov 29, 1995 |
| Grant date | Sep 2, 1997 |
| Priority date | — |
| Expiry date | Nov 29, 2015 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99944
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method and apparatus for increasing the speed of a search through leaf nodes of an inventive key index tree structure, known as a "Q-tree". The present invention identifies "decision-bits" within leaf node entries and uses these decision-bits to accelerate searches for a particular record or for a record adjacent to which a new record is to be inserted. A decision-bit is a particular type of distinction-bit having the smallest value and associated with a search key a greater value then the keys associated with other distinction-bits of the same value within a specified search range. Each decision-bit divides a search range into "left" and "right" parts. One of the two parts will constitute a "new" search range. A "quit-bit" having an ordinal number equal to the value of the decision-bit for the search range, is tested. If the quit-bit is "on", then the right, or greater value, part becomes the new search range. Otherwise, the left, or lesser value, part becomes the new search range. A decision-bit pointer which identifies the relative location of a "root" decision-bit is placed in a predetermined location within the prologue of each leaf node. Additional decision-bit pointers are…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.