Multiway trie data structure that dynamically adjusts node sizes in a manner that reduces memory footprint and improves access speed
US8495093B2 · kind B2 · utility
Assignee
Inventor
Key dates
| Filing date | Sep 7, 2010 |
| Grant date | Jul 23, 2013 |
| Priority date | — |
| Expiry date | Aug 12, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/322
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method, system and computer program product for dynamically adjusting node sizes in a multiway trie data structure. Upon inserting a key/value pair in a node in a multiway trie data structure that causes the number of entries in the multiway trie data structure to exceed a threshold, a splitting method is implemented. The splitting method involves doubling the width of the node in the multiway trie data structure thereby resizing the node in a resized multiway trie data structure. Furthermore, a sub-node of the original node may be split into two sections and stored in two child level nodes of the resized node under certain circumstances. Hence, only the original node and its direct successors are resized. Such a data structure outperforms hash tables by taking advantage of patterns found in the key distribution to optimize both storage requirements and access speed.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.