Apparatus and method for efficient prefix search
US6522632B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 25, 1998 |
| Grant date | Feb 18, 2003 |
| Priority date | — |
| Expiry date | Jun 25, 2018 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/9566
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A list of prefix keys, including enclosing prefix key pairs, are stored in leaves of a tree structure. In the leaf nodes, a prefix search key is compared to a set of prefix keys to identify a longest matching prefix. Each leaf node includes a single result pointer to a block of results and a single enclosing pointer to a result in a block of results for another node. Internal nodes which point to subsequent nodes include partitioning nodes and table nodes. In each partitioning node, a prefix search key is compared to a set of prefix keys which point to subsequent nodes through a common pointer and an index. Within each node, a middle prefix key is stored ahead of sets of high and low prefixes.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.