The H3 Compressor: A compression scheme tailored for H3 cell indexes.

Related tags

Security tools thc
Overview

thc — The H3 Compressor

Crates.io Docs.rs CI Status Coverage License

This library allows to compress an H3 cell set into a compacted space-efficient representation.

This is especially useful for on-disk storage or on-wire transmission.

Compression results

Dense set

Test data: the 54,812 H3 cells at resolution 11 that covers Paris (contiguous shape, no holes).

Format size (in bytes) bits/index
Raw 438 496 64.00
THC 16 330 2.38
Compact 16 192 2.36
Compact+THC 933 0.14

Dense set composed of contiguous indexes are the easier to compress. We can see that the compact routine from H3 is really efficient and performs as well as THC by encoding an index on ~2 bits.

Now, the interesting part is that by first compacting the indexes set and then applying THC we can reduce the size even more (the resulting payload is ~470x smaller than the original one)!

This is due to the fact that H3 compaction, unlike THC, doesn't really compress the data (an index is always encoded on 64-bit) but reduces the number of indexes by replace groups of children by their ancestors.

The denser the set is, the higher is the compression: mainland France at resolution 11 (267,532,208 indexes, 1.99 Gio) is compacted and compressed down to 100.93Kio!

Sparse set

Test data: the 690,451 H3 cells at resolution 11 that covers cycle lanes in mainland France.

Format size (in bytes) bits/index
Raw 5 523 608 64.00
Compact 5 519 768 63.95
THC 539 405 6.25
Compact+THC 539 265 6.25

Sparse sets like this one are harder to compress because there is less redundancy to exploit.

H3 compaction completely falls apart here (only shaving 480 indexes from the 600k), since it cannot find enough complete groups of children to replace them by their ancestors.

THC, on the other hand, still produces remarkable results (though not as good as the one on the dense sets), producing a payload 10x smaller than the original one and using ~6.25 bits/index.

Installation

Cargo

  • Install the rust toolchain in order to have cargo installed by following this guide.
  • run cargo install thc

Usage

Load the shape of a city, compute the H3 coverage at resolution 10 and save the compressed result on disk:

use geojson::GeoJson;
use h3o::{
    geom::{Geometry, ToCells},
    CellIndex, Resolution,
};
use std::{fs::File, io::BufReader};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let file = BufReader::new(File::open("city.geojson")?);
    let geojson = GeoJson::from_reader(file)?;
    let geometry = Geometry::try_from(&geojson)?;

    let mut file = File::create("coverage.thc")?;
    thc::compress(
        &mut file,
        CellIndex::compact(geometry.to_cells(Resolution::Ten))?,
    )?;

    Ok(())
}

License

BSD 3-Clause

You might also like...
An implementation of Joshua Yanovski's Ghost Cell paper.

A novel safe and zero-cost borrow-checking paradigm from the GhostCell paper. Motivation A number of collections, such as linked-lists, binary-trees,

Lossless compressor and decompressor for numerical data using quantiles
Lossless compressor and decompressor for numerical data using quantiles

This rust library compresses and decompresses sequences of numerical data very well. It currently supports the following data types: i32, i64, u32, u64, f32, f64. Smaller data types like i16 can be efficiently compressed by casting to i32. Timestamp support may come soon in the future.

A cell-based esoteric programming language

Tape A cell-based esoteric programming language Tape is a cell-based, brainfuck-like programming language that has a readable syntax and a non-wasted

A Rust no-std (de)compressor based on PAQ

MASHI まし A 100% no-std compatible Rust implementation of a PAQ style arithmetic coding, context mixing compressor. Its intended use case is compressin

Like a cell, but make lifetimes dynamic instead of ownership

LendingCell is a mutable container that allows you to get an owned reference to the same object. When the owned reference is dropped, ownership return

A quasi-lossless Balkanoidal meta-lingual compressor.
A quasi-lossless Balkanoidal meta-lingual compressor.

A quasi-lossless Balkanoidal meta-lingual compressor. Background It has long been accepted that Serbian is a compact variant of Russian, with less lib

Statically allocated, runtime initialized cell.

static-cell Statically allocated, initialized at runtime cell. StaticCell provides a no-std-compatible, no-alloc way to reserve memory at compile time

Simulator of viral infection spread and containment in cell monolayer.

Overview VIS-A-VIS is an agent-based simulator of viral infection spread and viral infection self-containment in a monolayer of cell. The simulation m

An alternative to `qcell` and `ghost-cell` that instead uses const generics

Purpose This crate is another attempt at the ghost-cell / qcell saga of cell crates. This provides an alternative to std::cell::RefCell that can allow

Fast Symbol Ranking based compressor. Based on the idea of Matt Mahoney's SR2

Fast Symbol Ranking based compressor. Based on the idea of Matt Mahoney's SR2

Authenticate to Minecraft using the Microsoft Authentication Scheme from Rust.

Authenticating to Minecraft with the Microsoft Authentication Scheme from Rust This program showcases an implementation of the microsoft authenticatio

Pure Rust implementation of the Leighton Micali Signature scheme.

Leighton-Micali Hash-Based Signatures LMS implementation in Rust according to the IETF RFC 8554. This implementation is binary compatible with the ref

`decaf377-rdsa` is a randomizable signature scheme using the `decaf377` group.

decaf377-rdsa is a variant of RedDSA, instantiated using the decaf377 group. Signatures are parameterized by domain (for instance, Binding and SpendAu

A set of cryptographic primitives for building a multi-hop Proxy Re-encryption scheme, known as Transform Encryption.

recrypt A pure-Rust library that implements a set of cryptographic primitives for building a multi-hop Proxy Re-encryption scheme, known as Transform

Apprentice-vscode - a port of @romainl’s excellent Apprentice Vim colour scheme to VS Code
Apprentice-vscode - a port of @romainl’s excellent Apprentice Vim colour scheme to VS Code

Apprentice for VS Code apprentice-vscode is a port of @romainl’s excellent Apprentice Vim colour scheme to VS Code. The theme is available in two vari

FRI low-degree-testing & polynomial commitment scheme

fri-commitment FRI low degree testing & FRI polynomial commitment using [VP19]'s trick. Implementation using arkworks libraries. Note: done in my free

libbz2 (bzip2 compression) bindings for Rust

bzip2 Documentation A streaming compression/decompression library for rust with bindings to libbz2. # Cargo.toml [dependencies] bzip2 = "0.4" License

A Rust implementation of the Zopfli compression algorithm.

Zopfli in Rust This is a reimplementation of the Zopfli compression tool in Rust. I have totally ignored zopflipng. More info about why and how I did

Image Compression Algorithm
Image Compression Algorithm

Image Compression Algorithm 🦭 A new lossless image compression algorithm. In the newest version the algorithm performs rather good, but manages to su

Owner
Hydronium Labs
Hydronium Labs
Easy c̵̰͠r̵̛̠ö̴̪s̶̩̒s̵̭̀-t̶̲͝h̶̯̚r̵̺͐e̷̖̽ḁ̴̍d̶̖̔ ȓ̵͙ė̶͎ḟ̴͙e̸̖͛r̶̖͗ë̶̱́ṉ̵̒ĉ̷̥e̷͚̍ s̷̹͌h̷̲̉a̵̭͋r̷̫̊ḭ̵̊n̷̬͂g̵̦̃ f̶̻̊ơ̵̜ṟ̸̈́ R̵̞̋ù̵̺s̷̖̅ţ̸͗!̸̼͋

Rust S̵̓i̸̓n̵̉ I̴n̴f̶e̸r̵n̷a̴l mutability! Howdy, friendly Rust developer! Ever had a value get m̵̯̅ð̶͊v̴̮̾ê̴̼͘d away right under your nose just when

null 294 Dec 23, 2022
A todo list app that indexes your app to find TODO:'s

forgot A todo list app that indexes your app to find TODO:'s Usage to list all your todos forgot list list all your todos ignoring search in ./target,

null 2 Oct 6, 2022
reth-indexer reads directly from the reth db and indexes the data into a postgres database all decoded with a simple config file and no extra setup alongside exposing a API ready to query the data.

reth-indexer reth-indexer reads directly from the reth db and indexes the data into a postgres database all decoded with a simple config file and no e

Josh Stevens 306 Jul 12, 2023
A Rust library for building modular, fast and compact indexes over genomic data

mazu A Rust library for building modular, fast and compact indexes over genomic data Mazu (媽祖)... revered as a tutelary deity of seafarers, including

COMBINE lab 6 Aug 15, 2023
An implementation of the A-Star pathfinding algorithm tailored for traversing a bespoke collection of weighted hexagons.

An implementation of the A-Star pathfinding algorithm tailored for traversing a bespoke collection of weighted hexagons. It's intended to calculate the most optimal path to a target hexagon where you are traversing from the centre of one hexagon to the next along a line orthogonal to a hexagon edge

null 19 Dec 11, 2022
Multi-threaded CLI torrent scraper for displaying searched for magnet links; tailored for use with plex & ssh.

magnetfinder Multi-threaded CLI torrent aggregator; scrapes torrent results from multiple websites and delivers them into a table in your terminal! Su

Ryan 59 Dec 10, 2022
A lightweight and flexible framework to build your tailored blockchain applications.

TRINCI Blockchain Core A lightweight and flexible framework to build your tailored blockchain applications. Requirements The required dependencies to

Affidaty S.p.A. 11 Sep 26, 2022
Multi-threaded CLI torrent scraper for displaying searched for magnet links; tailored for use with plex & ssh.

magnetfinder Multi-threaded CLI torrent aggregator; scrapes torrent results from multiple websites and delivers them into a table in your terminal! Su

null 59 Dec 10, 2022
A customizable MCTS planner with advanced featured tailored to multi-agent simulations and emergent narratives.

NPC engine Core:  Utils:  © 2020-2022 ETH Zurich and other contributors. See AUTHORS.txt for more details. A customizable Monte Carlo Tree Search (MCT

Game Technology Center, ETH Zurich 30 Jun 6, 2023
Brotli compressor and decompressor written in rust that optionally avoids the stdlib

rust-brotli What's new in 3.2 into_inner conversions for both Reader and Writer classes What's new in 3.0 A fully compatible FFI for drop-in compatibi

Dropbox 659 Dec 29, 2022