Florian Kurpicz

Distributed Patricia Trie

The distributed Patricia trie is a distributed full-text index that can answer existential, counting, and enumeration queries. It is based on the suffix array and longest common prefix (LCP) array.

We implemented different trie representations. In addition to the pointer-based trie implementation we provide succinct trie implementations that require only 2n bits to represent a trie with n nodes (and additional o(n) bits to be able to navigate in the trie).

Implementation

All implementations are available at https://github.com/kurpicz/dpt.

Posts Related to the Distributed Patricia Trie

Presentation at ALENEX 2017
2017-01-28

Engineering a Distributed Full-Text Index