fst-rs

FST (Fast Succinct Trie) implementation in Rust.

Master API Docs | Released API Docs | Benchmark Results | Changelog

FST is a building block of SuRF (Succinct Range Filter). SuRF and FST is first introduced in the SIGMOD 2018 best paper.

FST is a memory efficient and high performance trie. FST is like LOUDS based trie (e.g. trie-rs) but does not use pure LOUDS. It instead uses LOUDS-DS (abbrev of LOUDS-Dense & LOUDS-Sparse), which uses bitmap-based encoding (fast but fat) for upper levels of a trie tree and LOUDS-based encoding (slow but memory-efficient) for lower levels.

Quickstart

To use fst-rs, add the following to your Cargo.toml file:

[dependencies]
fst-rs = "0.1"  # NOTE: Replace to latest minor version.

Usage Overview

(TBD)

Features

(TBD)

Versions

fst-rs uses semantic versioning.

Since current major version is 0, minor version update might involve breaking public API change (although it is carefully avoided).

Rust Version Supports

fst-rs is continuously tested with these Rust versions in Travis CI:

• 1.33.0
• Latest stable version

So it expectedly works with Rust 1.33.0 and any newer versions.

Older versions may also work, but are not tested or guaranteed.

Contributing

Any kind of pull requests are appreciated.

Guidelines

• README.md is generated from $ cargo readme command. Do not manually update README.md but edit src/lib.rs and then $ cargo readme > README.md.
• Travis CI automatically does the following commit & push to your pull-requests:
  • $ cargo readme > README.md
  • $ cargo fmt --all

License

MIT OR Apache-2.0