TL;DR
This paper introduces a novel algorithm for creating Voronoi treemaps that preserve non-hierarchical similarity relationships (like geographic borders or semantic closeness) between data points. By integrating similarity constraints directly into the cell relaxation and optimization phases—rather than just at initialization—the method ensures related items remain spatial neighbors in the final visualization.
What Problem Does This Paper Address?
Treemaps are excellent for visualizing hierarchical data using nested shapes, and Voronoi treemaps offer an organic, polygon-based alternative to traditional rectangular layouts. However, real-world data often contains critical non-hierarchical relationships. For example, countries belong to continents (hierarchy), but they also share physical borders with countries on other continents (similarity).
While previous techniques have tried to place similar items near each other during the initial layout step, these relationships are usually destroyed during the subsequent optimization phase, where cells are resized and relaxed to fit their data attributes. In fact, up to 50% of these neighborhood relationships can be lost. This paper addresses the challenge of maintaining these multi-level similarity relationships throughout the entire treemap generation pipeline.
Methods
The authors extend the traditional top-down Voronoi treemap pipeline by introducing similarity awareness at every stage:
- Preprocessing & Propagation: Similarity features (e.g., word embeddings or shared borders) are aggregated bottom-up from leaf nodes to parent nodes. Virtual nodes are added to handle relationships that cross different levels of the hierarchy.
- Similarity Binning & Filtering: To prevent a messy, fully connected graph, a binning function filters out weak relationships, leaving only the strongest similarity connections as hard constraints.
- Geometric Initialization: Instead of random placement, the algorithm uses a Kuhn–Munkres matching algorithm to map nodes to an optimized, equal-sized Centroidal Voronoi Tessellation (CVT) based on similarity. A greedy swapping step further refines cell positions to maximize fulfilled constraints.
- Neighborhood-Preserving Optimization: During the cell relaxation phase (traditionally driven by Lloyd's algorithm), the authors introduce an attraction force. If two cells share a similarity constraint but are not neighbors, they are pulled toward each other. Crucially, cells are only allowed to grow to their final size during the last 20% of the iterations, preventing size imbalances from blocking cell movement early on.
- Visual Encoding: To explicitly show which neighbors are actually related by data similarity, the authors introduce a symmetric "Interlocking" puzzle-piece metaphor on the shared cell boundaries.
Datasets
The method was evaluated using a mix of synthetic and real-world datasets across multiple domains:
- Country Population: Countries with >50 million people grouped by continent, using shared physical borders as the similarity metric.
- CIFAR-10 (Language Embeddings): Image labels enriched with semantic text embeddings from ConceptNet.
- IMDB Top100 Movies: Movies grouped by director, with similarity defined by shared genres.
- Flare Data Repository: A standard software file hierarchy where similarity represents code contributions by the same authors.
- SP500 Variance: 429 stocks grouped by industry sectors, using price movement correlation as the similarity metric.
Key Insights and Ideas
- Resizing Too Early Destroys Neighborhoods: A major "aha" moment in the paper is that cell growth must be delayed. If cells grow to match their data weights at the beginning of optimization, large cells act as immovable obstacles, preventing smaller, similar cells from finding each other.
- Upward Aggregation is Essential: For items under different parent nodes to become neighbors, their parents must also be forced to be neighbors. Propagating similarity attributes up the tree ensures the macro-layout supports the micro-neighborhoods.
- The Interlocking Metaphor: Simply placing cells near each other isn't enough for the viewer; explicitly styling the shared edges like interlocking puzzle pieces immediately communicates a data-driven relationship without cluttering the view with link lines.
Key Results
The neighborhood-preserving optimization significantly outperformed baseline methods across all datasets:
- Constraint Preservation: Across all tested datasets, the proposed method preserved an average of 62.45% of similarity constraints as direct geometric neighbors, compared to just 34.63% for a random CVT initialization and 39.3% for traditional projection-and-scale methods.
- Country Dataset Success: For the country dataset, the algorithm successfully realized 83.33% of the border constraints (15 out of 18), successfully placing cross-continental neighbors like Russia (Europe) and China (Asia) next to each other.
Limitations and Future Work
While highly effective for shallow hierarchies, the algorithm's performance degrades as the height of the tree increases beyond 3 levels, because movement on lower levels becomes highly restricted by parent boundaries. Additionally, the overall computational complexity is $O(d \cdot n^3)$ (where $d$ is depth and $n$ is the number of leaf nodes), meaning the matching and optimization steps can take several seconds per level, limiting its applicability to massive, interactive real-time datasets. Future work aims to explore greedy planar graph embedding techniques to reduce this complexity.
Summary updated