Skip to content

Repository files navigation

* Suffix array searching: 40x faster binary search

This is a research project corresponding to [[https://curiouscoding.nl/posts/static-search-tree/][this blog post]].
Code is not really intended to be used as-is as a dependency in other
projects, and documentation is sub-par for that purpose.

It provides a /static search tree/ data structure that can answer 'binary search' queries much
faster, at the cost of 6% space overhead: given a list of =n= sorted integers
and a list of queries, it returns for each query the first number that is at
least the queried value.

It is on my to-do list, but with low priority, to make this into a nice
standalone crate.

To reproduce experiments and plots, create
the =results= and =plots= directories (the scripts expect them to exist).
1. Run the experiments: =cargo run -r --bin bench -- --release=.

   See =cargo run -r --bin bench -- --help= for more options.

   *Note:* To use SIMD, make sure to compile for your native CPU, e.g. by adding
   the following to =.cargo/config.toml=:

   #+begin_src toml
   [build]
   rustflags = ["-C", "target-cpu=native"]
   #+end_src
2. To generate plots: =python3 ./plot.py=. This will error at some
   point that =results-human-release.json= isn't found. To avoid that, comment
   out the last =plot_blog()= call.

About

High throughput suffix array searching

Resources

Stars

182 stars

Watchers

6 watching

Forks

Used by

Contributors

Languages