P-fast trie, but smaller
17 days ago
- #trie
- #data-structures
- #search-algorithms
- A p-fast trie is a wide fan-out variant of an x-fast trie for finding the longest matching prefix or nearest predecessor/successor of a query string in O(log k) time.
- It stores lexicographically ordered names, with every unique prefix added to a hash table.
- Hash table entries contain a reference to the closest name, prefix length, and a bitmap of possible next characters.
- Search involves a longest-prefix match using binary chop on the query string length.
- Predecessor search is more complex, requiring comparisons and bitmap checks to navigate the trie correctly.
- Compared to qp-tries, p-fast tries may require fewer probes (3–5 for DNS names) but hash table probes might be slower.
- Predecessor searches in p-fast tries could need up to 30 probes, suggesting linked lists of leaf objects might be more efficient.