Multi-Key Radix PATRICIA Fast Search - Embedded.com

Multi-Key Radix PATRICIA Fast Search

rdx is a library of routines for building a data structure based on the radix PATRICIA algorithm(modified) for storing data nodes accessible by an arbitrary number of keys of arbitrary length. The search algorithm characteristics for all keys is identical. Among 8 routines is rdx_pat_verify() that at any time can be used to verify the integrity of the data structure with 25 checks.

See article “Using multikey radix PATRICIA fast search” by Richard Hogaboom, June 2007, Embedded Systems Programming /Embedded Systems Design magazine.

Download the latest Github code.

Multi-key Radix PATRICIA Fast Search – OO C++ – A header only class(MKRdxPat.hpp)

The MKRdxPat class allows the allocation of a fixed sized contiguous data store that holds data nodes of an arbitrary structure that may be accessed with any number of keys of any size with the PATRICIA (Practical Algorithm To Retrieve Information Coded In Alphanumeric)(1,2,3) fast search algorithm. MKRdxPat is particularly suited to applications that require complex data structures be contiguously stored and accessed with an algorithm of known fast character with any of several possible keys, either singly of several simultaneously. MKRdxPat is unique, as far as I know, in allowing search with multiple keys of any length. If the application only requires a single key, this is OK; just set num_keys to 1 in the constructor call. 

Github repo: https://github.com/rahogaboom/rdx

4 thoughts on “Multi-Key Radix PATRICIA Fast Search

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.