Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.)



For others interested in this idea, look up "Bentley-Saxe transformation". These lecture notes are very readable: 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/fi... )


Thanks! I got my intro to this topic from Okasaki's Purely Functional Data Structures.




Consider applying for YC's Winter 2027 batch! Applications are open till November 2.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: