Pluggable Trie Implementations

[ghost]

It would be illuminating to compare various Trie implementations to see if there can be any significant performance gains to be made. This would require creating a common Trie interface that can be used, independent of the underlying implementation.

Implementations

Java

• https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/trie/PatriciaTrie.html
• http://www.stochasticgeometry.ie/2008/05/06/implementing-hat-tries-in-java/ (incomplete)
• https://github.com/colindean/autocomplete/tree/master/java/src/main/java/com/marcusmccurdy/trie
• https://github.com/krukow/clj-ds/blob/master/src/main/java/com/github/krukow/clj_lang/PersistentHATTrie.java (missing HATTrieNode.java, also the persistence overhead would not be desired).

C/C++

• https://github.com/malbrain/HatTrie
• https://github.com/dcjones/hat-trie
• https://github.com/dlecocq/hat-trie
• https://git.devuan.org/dev1fanboy/knot/tree/2b26112acb49bcc33d9c8b8176fa9ad7504663d8/src/common/hattrie

Papers

• http://crpit.com/confpapers/CRPITV62Askitis.pdf
• http://www.cs.vu.nl/~frankh/postscript/ESWC2015.pdf
• http://www.iaeng.org/publication/WCECS2014/WCECS2014_pp109-114.pdf
• https://www.researchgate.net/profile/Izzat_Alsmadi/publication/278020625_KP-Trie_Algorithm_for_Update_and_Search_Operations/links/56faf82d08ae3c0f264c0793.pdf?origin=publication_detail (KP-Trie)