3 ms·
You can convert static data structures like these into dynamic ones with about a logarithmic slowdown. So it might still be worthwhile. (You could also combin
by eru 2y ago
You can convert static data structures like these into dynamic ones with about a logarithmic slowdown. So it might still be worthwhile.
(You could also combine a static filter with a dynamic bloom filter in front. A bit like generational garbage collection.)
- kanak 2y agoFor others interested in this idea, look up "Bentley-Saxe transformation". These lecture notes are very readable: https://jeffe.cs.illinois.edu/teaching/datastructures/notes/01-statictodynamic.pdf https://jeffe.cs.illinois.edu/teaching/datastructures/notes/... . A recent paper trying to systematically apply the idea to databases "Towards Systematic Index Dynamization" ( https://bpb-us-e1.wpmucdn.com/sites.psu.edu/dist/b/123163/files/2024/08/dynamization-vldb.pdf https://bpb-us-e1.wpmucdn.com/sites.psu.edu/dist/b/123163/fi... )
- eru 2y agoThanks! I got my intro to this topic from Okasaki's Purely Functional Data Structures.