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

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

#121

Post by gvinciguerra » Wed, Jan 27, 2021, 7:06 PM UTC

magicalhippo wrote: post #49

midjji wrote: post #45

Could this be used for/generalized for Nd spatial proximity lookup tables?

Yeah I was curious about using it for raytracing, maybe like a kd-tree where you consider one dimension per level.

Hi @magicalhippo and @midjji. Please, have a look at the main repo, I just uploaded an implementation of the multidimensional PGM-index supporting orthogonal range searches ;)

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

#122

Post by nmsmith » Thu, Jan 28, 2021, 12:57 PM UTC

gvinciguerra wrote: post #120

crazypython wrote: post #75

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.

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!

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

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

#123

Post by midjji » Fri, Jan 29, 2021, 5:32 PM UTC

gvinciguerra wrote: post #71

midjji wrote: post #45

Could this be used for/generalized for Nd spatial proximity lookup tables?

Yep, I'm working on a multidimensional version that I hope to upload to the main repo ( https://github.com/gvinciguerra/PGM-index ) in a few weeks.

Neat :)

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

#124

Post by magicalhippo » Mon, Feb 01, 2021, 9:13 AM UTC

gvinciguerra wrote: post #121

magicalhippo wrote: post #49

Earlier quoted context omitted.

Yeah I was curious about using it for raytracing, maybe like a kd-tree where you consider one dimension per level.

Hi @magicalhippo and @midjji. Please, have a look at the main repo, I just uploaded an implementation of the multidimensional PGM-index supporting orthogonal range searches ;)

Awesome, thanks for the follow-up!