PERCH clustering
Algorithms AIMech:PERCHClustering DRAFT
Aliases: Purity Enhancing Rotations for Cluster Hierarchies
An online hierarchical clustering algorithm that inserts observations near existing leaves of a binary cluster tree and uses masking and balance rotations to revise subtree placement.
Identity Notes & Concept Scope
Compared all 442 pinned AIO and 657 native IDs, names, aliases and scoped synonyms; no normalized identity match. Ignored- and hidden-inclusive fixed-string searches of the recovery, older discovery and original Documents checkouts returned 18, 0, 0 lines. All distinct match contents were read, including pending discovery entries and source-reading observations. Recovery hits concern pending PERCH discovery notes and primary-source context; none identifies an existing standalone PERCH record. Both other checkouts returned no matches including ignored and hidden files. Semantic matching covered 26 AIO and 174 native definitions, all read; unchanged definitions were byte-compared with the preceding full assessment. 9 full annotated AIO node/edge/generated contexts and 5 full native records were inspected. Retain online nearest-leaf insertion with masking and balance rotations. It differs from immutable linkage chains, BIRCH feature compression, CURE representatives, RS pruning and Genie inequality-based merging. PERCH-C/B/BC name modes with additional assumptions, not unconditional exact-theory aliases.
Claims & Grounded Evidence
7 Claims
Mechanism
#online-insertion-and-rotation
Insert each arriving observation by locating a nearest leaf and creating a new parent whose children are that leaf and the new observation. A subtree is masked when some point in it is farther from a point in its sibling subtree than from a point in its aunt subtree. A masking rotation swaps the sibling and aunt, changing earlier grouping decisions while retaining a binary hierarchy.
Scope
#conditional-purity-theory
The paper’s exact construction has dendrogram purity one for arbitrary arrival order under strict separation: the largest within-class distance is smaller than the smallest between-class distance. This theorem concerns the stated exact conditions; it is not an unrestricted guarantee for nonseparable data, approximate beam search, arbitrary leaf caps or every implementation of a distance summary.
Mechanism
#balancing-and-search
Balance rotations use subtree point counts together with a distance-compatibility test. Practical search uses bounding-box distance information, with a finite beam as an approximate alternative. Balancing aims to reduce traversal cost, but it does not establish logarithmic tree height or insertion cost on all inputs; the paper explicitly acknowledges quadratic worst-case total work in the number of observations.
Scope
#implementation-boundary-of-geometric-summaries
The inspected Python implementation caches sibling-distance summaries by evaluating all-minimum and all-maximum coordinate corners in both directions. These expressions are not universal lower and upper bounds on the corresponding point-set distances. Standalone explicit point sets show a cached lower distance of 4 when the true minimum is 1, and a cached maximum squared distance of 202 when the true maximum squared distance is 221. These expression-level counterexamples do not establish a reachable full-PERCH execution or a measured purity failure.
Scope
#collapsed-mode-and-storage
Collapsed variants limit the number of active tree leaves by replacing eligible sibling leaves with a summarized leaf, without later re-expanding that collapsed cluster. The paper’s exact collapse result additionally requires strict separation and a leaf limit L greater than the true cluster count K. Its storage discussion retains point IDs. The inspected Python collapse routine instead retains original leaf objects and their point arrays, so deletion of all collapsed feature vectors is not attributed to that implementation.
Scope
#flat-extraction-and-pruning-cost
Flat clustering is a subsequent tree-pruning operation with a requested cluster count. The paper’s diagonal-length-times-count expression and the inspected Python half-child-distance-times-count heuristic are not general upper bounds on squared-error k-means cost: for points 0 and 10 they give 20 and 10 respectively, while squared error to the mean is 50. The inspected Scala entrypoint records insertion time before flat extraction and serialization; that timing excludes those later steps.
Performance
#reported-evaluation
The paper compares hierarchy quality by dendrogram purity and flat partitions by pairwise F1 on nine datasets. It reports results across random arrival permutations and selected hyperparameters, with beam, collapse and parallel settings depending on the experiment. These historical comparisons do not establish a universal quality or speed ranking.
Evaluation Context:
Task: Online hierarchical clustering and subsequent flat partition extraction.
Dataset: Nine datasets described in the paper; five random-order repetitions for the two largest and ten for the others. No held-out hyperparameter selection established.
Model: PERCH and collapsed/beam variants in arXiv1704.01858v1. The pinned2019 implementation is inspected as implementation evidence, not assumed identical to every2017 benchmark run.
Metric: Dendrogram purity and pairwise F1; experiment-specific runtime and normalized insertion-time plots.
Result: Source tables report dataset-specific quality/runtime tradeoffs; some batch methods exceed PERCH on smaller datasets. No single aggregate superiority figure is curated. (Baseline: Reported hierarchical agglomerative, BIRCH, stream/flat clustering and k-means baselines. The adversarial-arrival experiment modifies online minibatch k-means and is not equated with its standard setting.)
⚠️ Curated Limitations & Negative Results
- Exact separation theorems, practical geometric summaries, beam search and collapsed representations have distinct conditions. No unconditional purity, order-invariance or logarithmic-runtime guarantee is asserted.
- Geometric checks evaluate standalone scalar expressions on explicit point sets. They do not construct an insertion history, establish reachability, execute PERCH or measure clustering quality.
- The Python implementation retains leaf objects and features after collapse; paper storage claims are not silently assigned to that version. Retaining all point IDs also has a cost that grows with the observation count.
- The pruning-cost checks distinguish linear-distance heuristics from squared error. No exact optimal k-means pruning or universally valid SSE upper bound is inferred.
- The2017 arXivv1 and pinned2019 author implementation were inspected. The conference typeset version and complete Scala core were not compared; only the cited Scala entrypoint was fully read.
- All20 paper pages and all cited implementation files were read. Static inspection and curator arithmetic only; no author code, model training, data upload or benchmark replication.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:HierarchicalClustering
Hierarchical Clustering
|
related_match | PERCH constructs a hierarchy through online insertions and rotations. The AIO target denotes the task, not this algorithm or an equivalent implementation. |
AIO:UnsupervisedClustering
Unsupervised Clustering
|
related_match | The merge and rotation construction uses observations and distances without class labels; reference labels enter the reported external quality evaluation. |
Evidence Sources & Primary Literature
4 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
perch2017
|
Ari Kobren, Nicholas Monath, Akshay Krishnamurthy, Andrew McCallum
|
primary paper
full_text
|
ID: arXiv:1704.01858v1
sha256:28b8a3c5566b…
|
perch-python
|
xcluster authors
|
official documentation
documentation
|
sha256:dcc14168ac85…
|
perch-pruning
|
xcluster authors
|
official documentation
documentation
|
sha256:9cc682a6566d…
|
perch-entry
|
xcluster authors
|
official documentation
documentation
|
sha256:aae079842b58…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-13T23:01:39Z
Updated: 2026-10-13T23:08:34Z
Source File:
data/curated/PERCHClustering.yaml