Something for kvrocks? MARISA: Matching Algorithm with Recursively Implemented StorAge

[adulau]

I recently discovered that data structure which seems an interesting improvement over Bloom Filters. I was wondering if this is something which could make sense in kvrocks as a new data-structure?

Matching Algorithm with Recursively Implemented StorAge (MARISA) is a space-efficient, fairly fast, and static trie data structure. MARISA serves as a dictionary structure, and by definition, it supports exact match lookup, which is the basic operation of dictionary. In addition, MARISA supports reverse lookup, common prefix search, and predictive search. In most cases, MARISA is much more compact than a plain text which consists of the registered keys. This means that the traditional dictionary implementations, a binary tree (std::map<std::string, T>) and a hash table (std::unordered_map<std::string, T>), require more and more and more spaces than MARISA. Bloom Filter, a probabilistic data structure, is more space-efficient than MARISA but causes false positives and does not support reverse lookup, common prefix search, and predictive search. libmarisa is a C++ library for an implementation of MARISA. Users can build dictionaries and search keys from the dictionaries. The package also provides command line tools to test basic operations of libmarisa, and the tools are useful to test the performance.

• MARISA: Matching Algorithm with Recursively Implemented StorAge