What Can Vectorised Trees Do for You?
summary
Represents trees as a numeric parent vector plus separate data vectors so the whole hierarchy fits an inverted table and APL primitives operate on levels in parallel. Case studies: code analysis (co‑dfns/static analysis) and file system queries gain clear speedups for large irregular trees using bottom-up traversal, particle N‑body using a top‑down quadtree approximation turns out slower on a laptop, while union‑find/disjoint‑set merges become cheap by reassigning a few parent pointers.
AI-written summary · about
chapters (10)
- 0:00About Asher
- 2:07Representing tree structures
- 7:04Examples of operations on trees
- 9:57When parent vectors are useful
- 11:42Case study: Co-dfns and static analysis
- 12:25Case study: File system queries
- 15:38Case study: Particle simulation
- 18:56Case study: Disjoint set data structure
- 21:15Conclusion
- 22:25Questions
related talks
46mVisualize your data structures
21mActual trees, not b-trees: or how I found PostgreSQL through PostGIS
26mTwisty Little Passages
48mA Tree Full of Object Data
27mTopological Data Analysis: Information from moving Data
39mDesigning for high-performance execution with Arrow and Polars
11mScaling the Urban Forest: An Integrated Framework for Managing Cities by Fusing Raster(…)
34mVisualizations in Golang