Home / Curated / Algorithms / GRINCH clustering

GRINCH clustering

Algorithms AIMech:GRINCHClustering DRAFT

Aliases: Grinch algorithm

An incremental hierarchical clustering algorithm that uses set-wise linkage scores to revise a binary cluster tree through local rotations, nonlocal subtree grafting and restructuring.

Identity Notes & Concept Scope Compared all 442 pinned AIO and 658 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 31, 0, 0 lines. All distinct match contents were read, including pending discovery entries and source-reading observations. Recovery hits concern pending GRINCH discovery notes and primary-source context; none identifies an existing standalone GRINCH record. Both other checkouts returned no matches including ignored and hidden files. Semantic matching covered 26 AIO and 175 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 incremental set-wise-linkage tree grafting and restructuring. PERCH uses geometric masking/balance tests; BIRCH compresses feature summaries; NN chains and Genie choose agglomerative merges; RCC optimizes representatives. These mechanisms do not identify GRINCH.

Claims & Grounded Evidence

6 Claims

Mechanism #incremental-tree-revision

GRINCH builds a binary cluster hierarchy incrementally under a set-wise linkage function. It places a new observation near a nearest leaf, applies local rotations, and attempts nonlocal grafts followed by restructuring. Earlier groupings can therefore change as observations arrive.

supports Source: Scalable Hierarchical Clustering with Tree Grafting · Locator: Sections2–3, PDF pp.2–8; Algorithms1–3
supports Source: GRINCH author implementation: src/scala/grinch/core/Grinch.scala · Locator: Grinch.insert, rotate and graft

Scope #model-based-separation

The paper defines separation using a latent graph: for a common set, a partner producing a connected union must score higher than one producing a disconnected union. Under that assumption, Theorem1 states that the intended exact construction contains the graph connected components as a tree-consistent partition for any arrival order. This is a conditional result about cluster recovery, not identical trees across orders or an unconditional guarantee for approximate implementations.

supports Source: Scalable Hierarchical Clustering with Tree Grafting · Locator: Definition1, PDF p.3; Theorem1, p.7; AppendixA, pp.19–23

Mechanism #grafting-and-tie-boundary

A graft searches outside the current subtree and requires a candidate pair to prefer one another over their current siblings. Candidate ancestors are considered when a sibling is preferred. The printed Algorithm1 uses strict inequalities that leave certain tied non-sibling states unchanged; the inspected Scala implementation treats equality as rejection and advances a candidate. Its behavior is not inferred from a literal transcription of that pseudocode.

supports Source: Scalable Hierarchical Clustering with Tree Grafting · Locator: Section3.2, Equation2 and Algorithm1, PDF pp.6–7
supports Source: GRINCH author implementation: src/scala/grinch/core/Grinch.scala · Locator: Grinch.graft, i_like_you/you_like_me and candidate-parent updates

Scope #restructuring-and-source-scope

The intended restructuring operation compares a subtree with siblings of its ancestors below a specified common ancestor, swapping when that improves the linkage. Strong connectivity requires every descendant subtree of a connected node to be connected; this differs from merely containing a complete cluster. The inspected Scala routine differs from Algorithm2: it scores with the original z as curr advances, does not use its computed r_ancs set to restrict candidates, and its node swap changes pointers without updating cached summaries. These static differences preclude assuming exact paper-to-code equivalence.

supports Source: Scalable Hierarchical Clustering with Tree Grafting · Locator: Section3.3, Algorithm2, PDF pp.6–8; Definitions3–4 and Lemma4, pp.19,22–23
supports Source: GRINCH author implementation: src/scala/grinch/core/Grinch.scala · Locator: Grinch.restructure
supports Source: GRINCH author implementation: src/scala/grinch/core/GrinchNode.scala · Locator: GrinchNode.swap, score and updatedFromChildren

Scope #approximation-and-control-flow

The paper considers capped operations, single-elimination grafting, reuse of an insertion-time neighbor search, and approximate navigable-small-world search. Such approximations do not automatically inherit the exact separation theorem. The pinned Scala caps use subtree point counts, whereas the paper describes height caps. Its graft_attempts variable stays zero and its positive-beam exit predicate is graft_attempts < graft_beam, causing exit after a completed outer iteration with the default positive beam. This is a static control-flow observation, not a measured clustering failure.

supports Source: Scalable Hierarchical Clustering with Tree Grafting · Locator: Section4.2, PDF pp.9–11
supports Source: GRINCH author implementation: src/scala/grinch/core/Grinch.scala · Locator: Grinch.graft, rotate, restructure and graft_cknn_search
supports Source: GRINCH author implementation: src/scala/grinch/core/Config.scala · Locator: GrinchConfigOpts and Config, graft_beam and size-cap defaults

Scope #implementation-and-evaluation-boundaries

The paper distinguishes dendrogram purity from pairwise F1 after flat-cluster extraction and evaluates both fixed and learned linkage functions. Its approximations and data-order experiments are empirical comparisons, not universal quality or speed rankings. The pinned author repository provides Scala implementations and experiment scripts, but that later source snapshot is not assumed to reproduce every historical result. The inspected average-link implementation averages negative squared Euclidean distances over stored points; its name alone does not establish an average of unsquared distances.

supports Source: Scalable Hierarchical Clustering with Tree Grafting · Locator: Sections4.1–4.6, PDF pp.8–14; Tables1–4
supports Source: GRINCH author implementation: src/scala/grinch/core/Grinch.scala · Locator: AvgLinkGrinch.e_score and minusNorm
supports Source: GRINCH author implementation: README.md · Locator: Run and Notes sections

⚠️ Curated Limitations & Negative Results

The exact recovery statement assumes model-based separation and intended exact operations. Arbitrary linkage scores, approximate searches and caps do not establish those conditions.
The printed Algorithm3 does not show an update to p in its final loop; Algorithm1 also leaves certain ties without progress. The record describes the intended method and preserves these source limitations.
Equation1 and Algorithm3 use different node roles for rotation. The insertion implementation ascends a candidate sibling before attaching the new leaf; variable names are not silently identified across descriptions.
The finite tied-score example is a standalone tree state, not an established insertion history or author execution. It does not refute the intended theorem or quantify clustering quality.
The pinned Scala source has explicit control-flow and restructuring differences. No full reachable counterexample or correctness certification of that implementation is claimed.
The 23-page arXiv version and complete cited files were read. The separate Python implementation, NSW and Ent internals, other revisions, datasets and historical benchmark runs were not audited or executed.
The record remains DRAFT. No model fitting, paid service, data upload or benchmark replication was performed.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:HierarchicalClustering` Hierarchical Clustering	related_match	GRINCH constructs a hierarchy through insertions and reversible subtree placement. The AIO target denotes the task, not this algorithm or an equivalent implementation.
`AIO:UnsupervisedClustering` Unsupervised Clustering	related_match	The construction groups observations using supplied linkage scores. Reference labels assess quality; learning a linkage in a separate supervised application does not make the generic grouping algorithm a classifier.

Evidence Sources & Primary Literature

5 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`grinch2019`	Scalable Hierarchical Clustering with Tree Grafting Nicholas Monath, Ari Kobren, Akshay Krishnamurthy, Michael Glass, Andrew McCallum	primary paper full_text	ID: arXiv:2001.00076v1 sha256:eb0a381b33e3…
`grinch-scala`	GRINCH author implementation: src/scala/grinch/core/Grinch.scala GRINCH authors	official documentation documentation	sha256:9b1d415e15c9…
`grinch-node`	GRINCH author implementation: src/scala/grinch/core/GrinchNode.scala GRINCH authors	official documentation documentation	sha256:f4aac5f280ff…
`grinch-config`	GRINCH author implementation: src/scala/grinch/core/Config.scala GRINCH authors	official documentation documentation	sha256:d1a497ec0a91…
`grinch-readme`	GRINCH author implementation: README.md GRINCH authors	official documentation documentation	sha256:08660d0b0179…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-13T23:45:33Z

Updated: 2026-10-13T23:45:33Z

Source File: data/curated/GRINCHClustering.yaml