The Third Hard Problem
3 days ago
- #graph-theory
- #hierarchies
- #systems-design
- Tree mapping is the hard problem of embedding a general graph (web) into a hierarchical structure (tree), causing distortion, and it's pervasive in computing and beyond.
- Hierarchies are natural for organizing physical space, but ideas and information form webs that resist such rigid taxonomies, leading to dilemmas in systems like file systems and code repositories.
- Examples include file system organization (e.g., grouping by application vs. type, or by component vs. language), writing (linear books vs. underlying idea webs), and city design (artificial tree-like cities vs. natural semilattice structures).
- In biology, morphological taxonomy is a flawed tree-mapping, while cladistics uses genetics for a more accurate classification by preserving evolutionary connections.
- The problem appears in database modeling, object-oriented hierarchies, Rust's borrow checker, and other areas, requiring intentionality to assess what web is flattened and if a tree is necessary.