PGM Indexes: Learned indexes that match B-tree performance with 83x less space
1–10 of 124 posts
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#2In the example they sort the data array. Does that mean this works just on sorted arrays? Insert and delete performance would be horrible I guess.
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#3In the example they sort the data array. Does that mean this works just on sorted arrays? Insert and delete performance would be horrible I guess.
They propose a solution for dynamic PGM indexes in the paper (section 3) and benchmark it (section 6). A summary is that, in their benchmark, their index is faster by 13%-71% in most cases, but can be slower (1%-15.2%) in a few cases.
I agree the example would be more eye-catching without that sort.
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#4They should have chosen another name, the acronym PGM already stands for Probabilistic Graphical Model and they overlap in possible usages.
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#5How would one (very roughly) approximate what this index does in terms of big-O notation for time and space? Is it the same as a b-tree in time but with linearly less space?
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#6They should have chosen another name, the acronym PGM already stands for Probabilistic Graphical Model and they overlap in possible usages.
portable grey map? precision guided missiles? idk.
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#7How would one (very roughly) approximate what this index does in terms of big-O notation for time and space? Is it the same as a b-tree in time but with linearly less space?
The paper submitted to VLDB [1] has a table (Table 1) which lists the time complexity for the PGM Index and compares it with a Sorted Array, a B-Tree and another type of Data Aware/Learned Index - FITing-tree
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#8In the example they sort the data array. Does that mean this works just on sorted arrays? Insert and delete performance would be horrible I guess.
Skimming the paper it appears so. B-trees also require sorted data.
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#9They should have chosen another name, the acronym PGM already stands for Probabilistic Graphical Model and they overlap in possible usages.
You mean like they had to call the bug planet in Starship Troopers “Planet P” because all the other names in the universe had been taken?
Re: PGM Indexes: Learned indexes that match B-tree performance with 83x less space
#10In the example they sort the data array. Does that mean this works just on sorted arrays? Insert and delete performance would be horrible I guess.
Isn’t sorting required for range based indexes?