Performance and memory bandwidth utilization for tree searches using tree fragmentation
US7146371B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 5, 2002 |
| Grant date | Dec 5, 2006 |
| Priority date | — |
| Expiry date | Aug 31, 2024 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99943
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A data structure and corresponding search methods are disclosed for improving the performance of table lookups. A data structure for the table is employed using a single hash table with hash table entries pointing to tree fragments that are contiguous in main memory and can be efficiently loaded into a local data store or cache. Decision nodes are stored in a contiguous block of memory in a relative position based on the position of the decision node in the tree structure, including blank positions. Leaf nodes are stored in a contiguous block of memory based on the position of the leaf node in the tree structure, concatenating leaf nodes to eliminate blank positions. Leaf nodes of the tree fragments contain indicia of a data record, or indicia of another tree fragment. The data structure and corresponding search algorithm are employed for searches based on a longest prefix match in an internet routing table.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.