Alternative Data Structures in Ruby
summary
Shows concrete tradeoffs: a Bloom filter stores 100 million strings (≈100 chars) in about 280 MB at a 0.00001% false-positive rate versus ~10 GB for a hash set, and it cuts useless file-server 404 checks by ~99% as a prefilter. BK-trees find nearest strings for spelling correction without scanning the whole dictionary and cut comparisons (example saved ~50%). Splay trees bias toward hot keys for power-law access, and tries power autocompletion with O(1) per-letter traversal used in a Rack tag autocomplete.
AI-written summary · about
chapters (18)
- 0:00Intro
- 0:50Why talk about different data structures
- 1:30My favorite data structure
- 1:40The point of this talk
- 2:00Bloom filters
- 2:25Memory
- 3:00Bloom Filter Example
- 5:30Bloom Filter Summary
- 5:45PK Trees
- 6:45Triangle Inequality
- 7:40Example
- 10:50Web Caches
- 11:30Split Tree
- 12:45Try Tree
- 13:30Try Cool
- 13:55Try Demo
- 15:10Try Autocomplete
- 16:00Conclusion
related talks
25mHigh on Cardinality, Low on Memory
37mWhen Probably is Good Enough
27mA gentle introduction to Data Structure Trees
41mProbabilistic Data Structures
10mDon’t forget to sketch! Running with large datasets
11mWhy Hashes Will Be Faster in Ruby 2.0
45mMost of the Time It Works Every Time: The Mindset Behind Using Probabilistic Data Structures
01h 00mHyper Speed: When Big Data Blooms