[crazypython]

This is interesting. Could this be adapted to store 2D data, like how a quadtree is a 2D range tree? (If you link me to a paper / pseudocode for that, I could implement it.) I imagine it would be useful in GIS, gaming, etc.

[RMarcus]

Check out work by Jialin Ding and Vikram Nathan, they both work on multi-dimensional learned index structures.

https://arxiv.org/pdf/2006.13282.pdf

[byteshift]

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

[gvinciguerra]

Hi @crazypython and thank you! Yep, I just added an implementation of the multidimensional PGM-index in the main repo. If you want to improve it, you are more than welcome. Drop me an email if you have some ideas. Thanks again!

[nmsmith]

The multidimensional version definitely looks exciting! Do you have any benchmarks for it yet? And will you be publishing a paper on it?

[gaogao]

Maybe space filling curve 2D to !D map gets you most of the way there?