Technique of clustering and compaction of binary trees
US6567815B1 · kind B1 · utility
30Cited by
4References
32Claims
0Family size
Assignee
Inventors
Key dates
| Filing date | Aug 1, 2000 |
| Grant date | May 20, 2003 |
| Priority date | — |
| Expiry date | Aug 1, 2021 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99942
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A technique for improving the performance of binary tree operations involves defining an implicit binary tree structure in a memory array, and clustering of the nodes of the tree in memory in a cache-aware manner. The technique reduces memory latency by improved spatial locality of the binary tree data, and further improves cache performance through reduced size of the data objects resulting from elimination of pointers to other nodes of the tree.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.