8 ms·
PGM Indexes: Learned indexes that match B-tree performance with 83x less space
- legulere 6y agoIn 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.
- latch 6y agoThey 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. http://www.vldb.org/pvldb/vol13/p1162-ferragina.pdf http://www.vldb.org/pvldb/vol13/p1162-ferragina.pdf
- X6S1x6Okd1st 6y agoSkimming the paper it appears so. B-trees also require sorted data.
- AlphaSite 6y agoIsn’t sorting required for range based indexes?
- YesThatTom2 6y agoSame question. Can you give me an example of an indexing scheme that works on non-sortable data? I can’t think of any.
- jandrewrogers 6y agoThe canonical example is indexing rectangles. They have no total order. It is far from the only example. Any data type where equality and intersection are not equivalent test functions will effectively be non-sortable. There are many indexing schemes for data with these properties. They focus on topological relationships rather than order relationships.
- AnbeSivam 6y agoDo you know of any blog/papers which talks about this - using topology for such interval data types.
- jandrewrogers 6y agoNot necessarily. If you have indexing structures for data types that do not have a total order, only a partial order, you can store and do an indexed range search on data types that do have a total order. The primary implication is that the output of the range search will not reflect the total order in the way it would for a traditional B+Tree.
- gvinciguerra 6y agoHi @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/include/pgm/pgm_index_dynamic.hpp https://github.com/gvinciguerra/PGM-index/blob/master/includ... and the documentation at https://pgm.di.unipi.it/docs/cpp-reference/#classpgm_1_1_dynamic_p_g_m_index https://pgm.di.unipi.it/docs/cpp-reference/#classpgm_1_1_dyn...
- contravariant 6y agoIn the full paper they quote a rather interesting method [1] that allows you to insert values in amortized O(log(n)) time (deletes are apparently handled with tombstones, presumably rebuilding the whole thing when a sufficiently large proportion is deleted). A very abridged explanation of how they handle inserts: you split the collection in a list of collections where position k contains either nothing or a collection size 2^k. When you want to add a new value you find the first empty spot and fill it by building a set of your new value together with the collections of all the preceding spots (because the sizes are all sequential powers of two this will fit exactly). Provided that merging the collections takes linear time this takes an amortized O(log(n)) per inserted item. Of course once you have this you can use it for any learned index that can be learned in linear time. [1]: M. H. Overmars. The Design of Dynamic Data Structures, volume 156 of Lecture Notes in Computer Science. Springer, 1983.
- harperlee 6y agoThey should have chosen another name, the acronym PGM already stands for Probabilistic Graphical Model and they overlap in possible usages.
- cmrx64 6y agoportable grey map? precision guided missiles? idk.
- zxcvbn4038 6y agoYou 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?
- brokencode 6y agoThis type of comment is pretty common, but never adds to the discussion. Some things are going to have similar names, and usually it just doesn’t matter. Take Rust the game and Rust the programming language. How often do people confuse them? I’ve never seen it happen. Never mind the fact that rust is also a compound that forms when iron combines with oxygen. In my book, it’s better to come up with a name that makes sense or is memorable as long as it’s not very confusing.
- steveklabnik 6y agoPeople confuse the game and the language all the time in Reddit. We even had a talk at RustConf a few years back about teaching an ML model how to distinguish them. (That said I agree with your post generally...)
- etaioinshrdlu 6y agoHow 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?
- karsinkk 6y agoThe 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 [1] http://www.vldb.org/pvldb/vol13/p1162-ferragina.pdf http://www.vldb.org/pvldb/vol13/p1162-ferragina.pdf
- gvinciguerra 6y agoHi @etaioinshrdlu! The worst-case bounds are discussed in *Section 2.2* and *Theorem 1*. Essentially, we have the following bounds: Query: O(log_c(m) log_2(ε/B)) I/Os Space of the index: O(m) where: n = number of input keys B = disk page size ε = user-given maximum error of the piecewise linear approximation (determines how many keys you need to search at each level) m = number of segments in the piecewise linear approximation c = fan out of the data structure (differently from standard B-trees it is not fixed, and it is potentially large) Intuitively, the query complexity comes from the fact that the PGM-index has O(log_c(m)) levels, and at each level you do a binary search that costs O(log_2(ε/B)) I/Os. Note that m and c depend on the "linearity" of the given input data. For example, if the input data can be approximated by a few segments, i.e. if m=O(1), and you choose ε=Θ(B), then the PGM-index takes O(1) space and answer queries in O(1) I/Os! In general, you can remove the dependence from m and c if you can prove a lower bound on the length of a segment (i.e. the number of keys it "covers"), irrespective of the input data. We proved that the length of a single segment is at least 2ε (thus c≥2ε), or equivalently, that the number of segments m is upper bounded by n/(2ε) [Lemma 2, the proof is very straightforward]. Again, if you choose ε=Θ(B), then you have the following (rather pessimistic) worst-case bounds: Query: O(log_B(n)) I/Os Space of the index: O(n/B) Basically, these bounds tell you that the PGM-index is *never* worse in time and in space complexity than a B-tree! --- However, in our experiments, the performance of the PGM-index was better than what the above bounds show, and this motivated us to study what happens when you make some (general) assumptions on the input data. The results of this study are in the ICML20 paper "Why are learned indexes so effective?" (http://pages.di.unipi.it/vinciguerra/publication/learned-indexes-effectiveness/ http://pages.di.unipi.it/vinciguerra/publication/learned-ind...). We found that, if you assume that the gaps between input sorted keys are taken from a distribution with finite mean and variance, then you can prove (Corollary 2 of the ICML20 paper) that the space of the PGM-index is actually O(n/B^2) whp (versus Θ(n/B) of classic B-trees). Note that the result applies to *any* distribution, as long as the mean and variance of the RVs modelling the gaps are finite. Indeed, we specialised our main result to some well-known distributions, such as Uniform, Lognormal, Pareto, Exponential, and Gamma (Corollary 1 of the paper).
- est 6y agoReminds me of TokuDB. What happened to it?
- saurabhnanda 6y agoAny Postgres implementation of this yet?
- petergeoghegan 6y agoNot likely. I have done a lot of work on B-Tree indexing in Postgres in the past several years, and this is all Greek to me.
- Traudl 6y agoIt looks like it found its way into Google Bigtable though: https://arxiv.org/abs/2012.12501 https://arxiv.org/abs/2012.12501
- joe_the_user 6y agoI don't get it. I've implemented B-trees. The majority of space the used by a B-tree is the data itself. Each N-ary leaf of the tree is a basically a vector of data with maybe some bookkeeping at the ends. The leaves are more than half of the tree. Sure, you can compress the data. But that depends on the data, completely random data can't be compress. Other data can be. But a point blank 83x space claim seems bizarre - or it's comparing to a very inefficient implementation of a B-tree. Edit: It seems the 83x claim is a product of the HN submission. I could not find it on the page. But even the page should say something like "a compressed index that allows full speed look-up" (akin to succinct data structures) and then it would make sense.
- sa46 6y agoIf there's even a rough order to the underlying data, I'll buy their claim. On ordered data, a Postgres block-range index (BRIN) is often several orders of magnitude smaller than a B-tree index. If the data is random, I suspect you're right and the PGM index is no-better than a B-tree index. Most data does have an order and would probably see similar gains.
- hansvm 6y agoNot only is there a rough order, they explicitly require the ability to meaningfully embed data into the reals, and the performance gains come from assuming those embeddings have simple delta distributions. I wouldn't be surprised if the technique is worse than useless when that assumption is violated. Edit: I don't have time right now, but a toy example I like to throw at these kinds of problems is mapping primes to their indices (e.g. 2->0, 3->1, 5->2, ...). General-purpose learning algorithms can usually make a little headway with it, but not much, and only with substantial resources thrown at the problem. I'd be shocked if that toy example were any faster with their solution than a b-tree.
- xucheng 6y agoDue to the prime number theorem, your toy example actually has a very good approximated mapping.
- jabberwcky 6y agoOnly watched the video, was disappointed by https://youtu.be/gCKJ29RaggU?t=408 https://youtu.be/gCKJ29RaggU?t=408 , where they are comparing against tiny b*tree page sizes that nothing uses any more - 4k, 16k and 64k are way more common
- xucheng 6y agoI assumed that a bigger page size would incur a worse query performance. You can already see the trend in the figure. So the index size comparison is based on the b+-tree which has a similar query performance with the proposed learned index.
- plq 6y agoAFAIK sqlite's default page size is 4k
- gvinciguerra 6y agoHi @jabberwcky! The plot refers to a B+tree implementation optimised for main-memory (https://panthema.net/2007/stx-btree/ https://panthema.net/2007/stx-btree/). We didn't show the performance for larger/smaller page sizes because in our machine they performed poorly. Indeed, you can see from the figure that the fastest B+tree configuration had page size set to 512 bytes. The one using 1024-byte pages is already much slower, that's why we didn't clutter the plot with page sizes larger than 1k ;)
- mr_gibbins 6y agoThis sounds like a great advancement, however an implementation in RDBMS products may be some way away yet - MSSQL uses 8KB pages by default, and I believe (without checking) that most other RDBMSes use at least 4KB. B+ tree index implementations on RDBMS products may be here to stay for a while yet unless these performance issues can be minimised, or unless there is a paradigm shift to use smaller pages - which would have a knock-on effect to query performance unrelated to indexes, such as number of page lookups, increased I/O for non-contiguous page reads...
- 6y ago
- whyuselearning 6y agoWhy use learning when you can fit? http://databasearchitects.blogspot.com/2019/05/why-use-learning-when-you-can-fit.html http://databasearchitects.blogspot.com/2019/05/why-use-learn...
- RMarcus 6y agoWe produced a detailed comparison of such "fitting" and "learning" techniques, available here: https://vldb.org/pvldb/vol14/p1-marcus.pdf https://vldb.org/pvldb/vol14/p1-marcus.pdf (Thomas Neumann, one of authors of the blog post, is a co-author of the linked paper)
- jltsiren 6y agoSome context: A few years ago, there was a paper from Google (https://dl.acm.org/doi/10.1145/3183713.3196909 https://dl.acm.org/doi/10.1145/3183713.3196909) that made learned data structures popular for a while. They started from the idea that indexes such as B-trees approximate an increasing function with one-sided error. By using that perspective and allowing two-sided error, they were able to make the index very small (and consequently quite fast). Many data structure researchers got interested in the idea and developed a number of improvements. The PGM-index is one of those. Its main idea is to use piecewise linear approximations (that can be built in a single quick pass over the data) instead of the machine learning black box the Google paper was using.
- danbruc 6y agoOnly having skimmed the work, read the following as a somewhat educated guess. I think one could see this similar to repeated applications of interpolation search. If you are looking for x in a sorted array of n numbers between a and b, then index (x - a) / (b - a) * (n - 1) would be a good guess assuming uniform distribution of the numbers. But as one can not assume a uniform distribution in general, one does that repeatedly. The first interpolation leads to better interpolation coefficients for the relevant subrange, which may lead to even better interpolation coefficient for an even smaller subrange until one eventually finds what one was looking for. If there is no structure in the data that can be exploited, this degenerates into a more or less ordinary tree as we one certainly fit a line through two points, but if at some level a larger range of the data can be well approximated with the interpolation function, then it can save space and search time because one can get close to all the values in the range with only one set of interpolation coefficients and only one interpolation.
- Out_of_Characte 6y agoIsn't it sometimes better to assume data has a structure rather than having less performance but knowing it works equally well with unstructured semi-random data?
- danbruc 6y ago
- gigatexal 6y agoAny chance it will make its way to Postgres?
- ddorian43 6y agoThere are a lot of fixes PostgreSQL can do before this exotic one. Starting from ZHeap etc etc.
- ldng 6y agoZHeap a fix ? A different data management option, yes. A fix, no.
- ddorian43 6y agoIn the sense of lowering per-row-overhead, supposed to be faster on commit and slower on rollback(usual workloads).
- claytonjy 6y agoCan custom index types be packaged into an extension, or would implementing this require deeper integration?
- xucheng 6y agoAlso, a learned index from Microsoft: https://github.com/microsoft/ALEX https://github.com/microsoft/ALEX
- zupa-hu 6y agoThe slides: https://pgm.di.unipi.it/slides-pgm-index-vldb.pdf https://pgm.di.unipi.it/slides-pgm-index-vldb.pdf It seems they are only talking about compressing the index (keys) not the values. Also, the slides seem to imply the keys need to be set in sorted order? That way their memory locations will be in increasing order too. That’s quite an important limitation, that means the index is read-only in practice once populated. Though it may still be useful in some cases. Did I misunderstand?
- zupa-hu 6y agoOf course it begs the question: if the keys are sorted, what do we need an index for? A simple halfing method would trivially do it then with btree like performance and infinitely better index size (0). Maybe they may have made an improvement here trading some space for even better lookup times? In that case, the 83x space over btree indexes is certainly possible - given that infinite improvement is possible too.
- ncmncm 6y agoBinary search is quite slow on modern hardware, particularly for this use, where you would need to fault in a page for each probe. With a billion records that is 30 probes. They get much better than log2(n). This is a lot like how you look up words in the dictionary. It is roughly radix-like, but the closer you get, the better the fit. If you are looking up a word that starts with S, you adjust to how broad S is as you home in.
- eloff 6y agoThis is on in memory data. So binary search would seem reasonable except that you can't do inserts, updates, or deletes efficiently in an ordered array. That inevitably leads to using a btree or trie structure.
- ncmncm 6y ago"In-memory" doesn't mean so much as it once did. Faulting a page into cache from RAM takes hundreds or even thousands of cycles. Same for faulting an index page, if the whole index doesn't fit in cache. A B-tree replaces a log2(N) binary search of the whole range into a K-ary search, with log-base-K(N) probes; but adds searches through the K keys per tree node, which all have to be brought into cache. Even once the K keys have been brought into cache, a binary search in the index page is quite slow on modern hardware because the iterations involve randomly mispredicted branches. A great advantage of PGM indexes seems to be that the whole index can be held in (L3) cache. Faulting a line from L3 to L1 cache takes only ~30 cycles. Once the index has been walked, you are close to the desired record and can walk forward or back a few steps to locate it. If you have to handle insertions, it is often better to keep an overflow table searched first (or last) so you can batch-rebuild during downtime. Deletions may be handled by marking dead entries, and updates are easy. Most multigigabyte tables don't see much churn, relative to their size.
- inciampati 6y agoThis is a major practical advance from the succinct data structure community. This community has produced so many brilliant results in the past years. But, they work in the shadows. Since the rise of interest in neural network methods, I've often described their work as "machine learning where epsilon goes to 0." It's not sexy, but it is extremely useful. For instance, Ferragina previously helped to develop the FM-index that enabled the sequence alignment algorithms used for the primary analysis of short genomic reads (100-250bp). These tools were simply transformative, because they reduced the amount of memory required to write genome mappers by orders of magnitude, allowing the construction of full-text indexes of the genome on what was then (~2009) commodity hardware.
- gvinciguerra 6y agoHello everyone. I'm Giorgio, the co-author of the PGM-index paper together with Paolo Ferragina. First of all, I'd like to thank @hbrundage for sharing our work here and also all those interested in it. I'll do my best to answer any doubt in this thread. Also, I'd like to mention two other related papers: - "Why are learned indexes so effective?" presented at ICML 20, and co-authored with Paolo Ferragina and Fabrizio Lillo. PDF, slides and video: http://pages.di.unipi.it/vinciguerra/publication/learned-indexes-effectiveness/ http://pages.di.unipi.it/vinciguerra/publication/learned-ind... TL;DR: In the VLDB 20 paper, we proved a (rather pessimistic) statement that "the PGM-index has the same worst-case query and space bounds of B-trees". Here, we show that actually, under some general assumptions on the input data, the PGM-index improves the space bounds of B-trees from O(n/B) to O(n/B^2) with high probability, where B is the disk page size. - "A 'learned' approach to quicken and compress rank/select dictionaries" presented at ALENEX 21, and co-authored with Antonio Boffa and Paolo Ferragina. PDF and code: http://pages.di.unipi.it/vinciguerra/publication/learned-rank-select/ http://pages.di.unipi.it/vinciguerra/publication/learned-ran... TL;DR: You can use piecewise linear approximations to compress not only the index but the data too! We present a compressed bitvector/container supporting efficient rank and select queries, which is competitive with several well-established implementations of succinct data structures.
- BenoitP 6y agoThank you for your work! Are there current efforts in your research going in mainstream RDBMS (say postgres)? The space improvements are so great columns could just be indexed by default.
- gvinciguerra 6y agoThank you so much for your interest, BenoitP! Right now I'm focusing more on the design of compressed data structures. RDBMS are complex systems, and gaining sufficient knowledge of their internals would require several months of work. Though, it would wonderful for me to collaborate with some RDBMS engineers to integrate my current research efforts in their system. Actually, some time ago, we asked a bachelor's student at the University of Pisa to integrate the PGM-index in Redis (which is simpler than an RDBMS). He did it, and the results were really promising, -3x overall memory usage with respect to Redis ZSETs.
- midjji 6y agoCould this be used for/generalized for Nd spatial proximity lookup tables?
- magicalhippo 6y agoYeah I was curious about using it for raytracing, maybe like a kd-tree where you consider one dimension per level.
- gvinciguerra 6y agoHi @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 ;)
- magicalhippo 6y agoAwesome, thanks for the follow-up!
- gvinciguerra 6y agoYep, I'm working on a multidimensional version that I hope to upload to the main repo (https://github.com/gvinciguerra/PGM-index https://github.com/gvinciguerra/PGM-index) in a few weeks.
- asdfcorona 6y agoHow does it compare to RTree?
- midjji 6y agoNeat :)
- dmos62 6y agoI've only heard of B-trees in passing. In what kinds of situations are these data structures used?
- lincolnq 6y agoDatabases. If you want to be able to quickly do a lot of useful operations on large amounts of data, B-trees and their variants (B+ trees) are the way to go. Using a B-tree, you can find an entry, sort and do range queries by key, and inserts and deletes are fast.
- jokoon 6y agoI've already thought about the idea of making statistics to optimize access time, so I guess this a viable implementation to do it correctly. That's pretty amazing... I can somehow imagine this tech landing on every modern computer, allowing users to search for anything that is on their machine.
- thesz 6y agoTheir slides https://pgm.di.unipi.it/slides-pgm-index-vldb.pdf https://pgm.di.unipi.it/slides-pgm-index-vldb.pdf about PGM index, page 21. They stop at page size of 1024 bytes - that indicates they are tested in-memory situation. And, which is worse, their compression ratio advantage almost halves when block size is doubled. Thus, what about B-tree with blocks of 16K or even 256K? Also, what about log-structured merge trees where bigger levels can use bigger pages and, which is quite important, these bigger levels can be constructed using (partial) data scan. These bigger levels can (and should) be immutable, which enables simple byte slicing of keys and RLE compression. So, where's a comparison with more or less contemporary data structures and algorithms? Why beat half a century old data structure using settings of said data structure that favors your approach? My former colleague once said "give your baseline some love and it will surprise you". I see no love for B-trees in the PGM work.
- gvinciguerra 6y agoHi @thesz! The experiment you are referring to is done in main memory with an optimised in-memory B+tree implementation. We didn't plot the performance for larger page sizes because in our machine they performed poorly, as you can already see from the configuration with 1024-byte pages. So we're not favouring our approach at all. Note also that next-gen memories have smaller and smaller access granularities. For example, the Intel's Optane DC Persistent Memory accesses blocks of 256 bytes, while the Intel's Optane DC SSD accesses blocks of 4 KB. I guess that data structures with blocks of 16K-256K are disproportionate in these cases. About LSM-trees, nothing prevents you to use a PGM-index (which you can construct during the compaction of levels, thus without scanning data twice) to speed up the search on a long immutable level. Or also, to use a PGM-index on data which is organised into RLE-compressed disk pages ;)
- thesz 6y agoThese blocks of 256 bytes most probably are stored in wear-leveling database of some sort hidden inside NVME. These databases are often LSM-tree-based. So, writing larger blocks still has benefits, especially when you use compression. If you think you only need 256 byte pages, average price for 10G hard disk drive is ~$300 [1] and average price for 2G SSD drive is also ~$300 [2]. [1] https://pcpartpicker.com/trends/internal-hard-drive/?__cf_chl_jschl_tk__=eb7d19a0fee0bae06773db51e2c24a49f42029c3-1611596989-0-Adt7I3palOe6T-fvjO6FGFk_pRP00ftthDItecT3JfzPGiQ6CuX-Hfa2JO6g_EKqbCnhalJe3Gt1Pm7IJ7erKPDnlDBr6q_0Ms3wwqQ5DHDSJlIfxr9bn6QkzIZ-aYwpf8MM1M3Vwodn4nHYJLrmhTgQt1Z9-ucN8O_wO1WH1LldGQJHiJczZ2M4hzr8jNn1S2XRQ4VHL7QVc90F5tujaUVKKugPerNYyUJPaF-TdnyuA_WYHBp8BomZy8xwmEPHaAq_cBGxHrISynx9gdIW9Xb2-hxVpy8i3251obIYBMQcFSWihe4NfSUt8b_-6zLzBWfuLMkXpTz_qWS5NT_7r7QoMwf8KoJGYj6zKKYYQUmekyRk6nqTsd-oG6mU47co4GR57lLLjX2hlgVVnz6vGok#storage.hdd350.12000 https://pcpartpicker.com/trends/internal-hard-drive/?__cf_ch... [2] https://pcpartpicker.com/trends/internal-hard-drive/?__cf_chl_jschl_tk__=eb7d19a0fee0bae06773db51e2c24a49f42029c3-1611596989-0-Adt7I3palOe6T-fvjO6FGFk_pRP00ftthDItecT3JfzPGiQ6CuX-Hfa2JO6g_EKqbCnhalJe3Gt1Pm7IJ7erKPDnlDBr6q_0Ms3wwqQ5DHDSJlIfxr9bn6QkzIZ-aYwpf8MM1M3Vwodn4nHYJLrmhTgQt1Z9-ucN8O_wO1WH1LldGQJHiJczZ2M4hzr8jNn1S2XRQ4VHL7QVc90F5tujaUVKKugPerNYyUJPaF-TdnyuA_WYHBp8BomZy8xwmEPHaAq_cBGxHrISynx9gdIW9Xb2-hxVpy8i3251obIYBMQcFSWihe4NfSUt8b_-6zLzBWfuLMkXpTz_qWS5NT_7r7QoMwf8KoJGYj6zKKYYQUmekyRk6nqTsd-oG6mU47co4GR57lLLjX2hlgVVnz6vGok#storage.ssdm2nvme.2000 https://pcpartpicker.com/trends/internal-hard-drive/?__cf_ch... Five times price/Gb difference. If you need large storage, you need hard disks. B-trees are good with hard disks, is PGM index good with them too?
- crazypython 6y agoThis 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?
- The_rationalist 6y agoI wonder if databases and/or browsers will make use of it
- byteshift 6y agoFor a detailed study of learned indexes, see this work: https://vldb.org/pvldb/vol14/p1-marcus.pdf https://vldb.org/pvldb/vol14/p1-marcus.pdf All code is available in open source: https://github.com/learnedsystems/SOSD https://github.com/learnedsystems/SOSD
- mooneater 6y agoAnd here I was thinking probabilistic graphical models were finally getting the spotlight :)
- fulafel 6y agoMany devs are probably familiar with perfect hashes as the gperf tool seems omnipresent on Linux machines. Is this a related concept? The learning part makes me suspect so but the slopes and interpolation part makes me doubt it.