tinygraph is a modern and idiomatic library optimized for compact and efficient graphs using succinct data structures. Think of the routing graph for continental-scale street networks with street segments, intersections, and turns.
Read our technical design document outlining design decisions for tinygraph here!
We work in the open and you can contact us if you want to get involved:
High Performance
We use a compressed sparse row format to represent graphs in compact and efficient ways: ideal for large scale and high-performance use-cases.
The trade-off is limited support for modification. The use-cases we support: build a graph, work on the graph, and potentially build new graphs from there.
Graph Compression
For compression we use techniques like: succinct data structures, storing deltas in vbyte format, and permuting graphs based on space filling curves.
Compressed graphs not only have a much smaller footprint, but we also keep an eye on viability and practicality: this is not a pure research project.
Modern Hardware
Vector instruction sets are widely deployed with AVX2 available for 10+ years by now: we target modern hardware for efficiency gains at no cost.
We provide scalar fallbacks and baseline implementations in case vector instructions are not supported: at the cost of runtime efficiency.
Stable Library
We work on a stable API and ABI using semantic versioning: a stable ABI allows for simple shared library upgrades across minor versions.
On top of the stable API and ABI we work on bindings to other languages: they come with their own stability and support guarantees.
File Format
We work on a file format for storing large graphs effectively and efficiently and for sharing graphs in a portable and compact way.
The tinygraphio file format stores graph in a compressed sparse row format for a compact representation. The on-disk representation is based on Protocol Buffers.