PGM Indexes: Learned indexes that match B-tree performance with 83x less space

• PGM-index

  6 760 6.2 C++

  🏅State-of-the-art learned data structure that enables fast lookup, predecessor, range searches and updates in arrays of billions of items using orders of magnitude less space than traditional indexes

Hi @legulere!

Yep, the example of Figure 2 shows only a static PGM-index on a sorted array.

Insertion and deletions are discussed in Section 3 "Dynamic PGM-index" and experimented in Section 7.3.

The Dynamic PGM-index is open-source too: you can find the implementation at https://github.com/gvinciguerra/PGM-index/blob/master/includ... and the documentation at https://pgm.di.unipi.it/docs/cpp-reference/#classpgm_1_1_dyn...

• ALEX

  1 649 2.8 C++

  A library for building an in-memory, Adaptive Learned indEX (by microsoft)

  

Also, a learned index from Microsoft: https://github.com/microsoft/ALEX

• InfluxDB

  www.influxdata.com featured

  Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  

• la_vector

  1 35 0.0 C++

  🔶 Compressed bitvector/container supporting efficient random access and rank queries

Hi Jouni!

You may find interesting these other papers of ours:

- The ALENEX21 paper "A 'learned' approach to quicken and compress rank/select dictionaries" (http://pages.di.unipi.it/vinciguerra/publication/learned-ran..., https://github.com/gvinciguerra/la_vector), where we introduce a compressed bitvector supporting efficient rank and select queries, which is competitive with several well-established implementations of succinct data structures.

- The ICML20 paper "Why are learned indexes so effective?" (http://pages.di.unipi.it/vinciguerra/publication/learned-ind...) where we prove that, under some general assumptions on the input data, the space of the PGM-index is actually O(n/B^2) whp (versus Θ(n/B) of classic B-trees).

• SOSD

  2 260 0.0 C++

  A Benchmark for Learned Indexes

  

For a detailed study of learned indexes, see this work: https://vldb.org/pvldb/vol14/p1-marcus.pdf

All code is available in open source: https://github.com/learnedsystems/SOSD

• RadixSpline

  3 121 0.0 C++

  A Single-Pass Learned Index

  

We index geospatial data using a learned index in this work (cf. Section 3): http://cidrdb.org/cidr2021/papers/cidr2021_paper19.pdf

Code: https://github.com/learnedsystems/RadixSpline

• SaaSHub

  www.saashub.com featured

  SaaSHub - Software Alternatives and Reviews. SaaSHub helps you find the best software and product alternatives

  

Suggest a related project