3 ms·
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 i
by crazypython 6y ago
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.
- gaogao 6y agoMaybe space filling curve 2D to !D map gets you most of the way there?
- byteshift 6y agoWe index geospatial data using a learned index in this work (cf. Section 3): http://cidrdb.org/cidr2021/papers/cidr2021_paper19.pdf http://cidrdb.org/cidr2021/papers/cidr2021_paper19.pdf Code: https://github.com/learnedsystems/RadixSpline https://github.com/learnedsystems/RadixSpline
- RMarcus 6y agoCheck out work by Jialin Ding and Vikram Nathan, they both work on multi-dimensional learned index structures. https://arxiv.org/pdf/2006.13282.pdf https://arxiv.org/pdf/2006.13282.pdf
- gvinciguerra 6y agoHi @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 6y agoThe multidimensional version definitely looks exciting! Do you have any benchmarks for it yet? And will you be publishing a paper on it?