Publication No 36551

Author(s)

Hofstee, P.; Necker, M.C.

Title

Performance and memory bandwidth utilization for tree searches using tree fragmentation

Topics

Computer Architecture

Keywords

ALGORITHM

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.

Year

2006

Reference entry

Hofstee, P.; Necker, M.C.
Performance and memory bandwidth utilization for tree searches using tree fragmentation
Patent, No, December 2006

BibTex file

Download  [BIBTEX]

Full Text

No full text available online. To obtain a copy of the publication, please mail to mail@ikr.uni-stuttgart.de and refer to "Publication number 36551".