Home / Curated / Algorithms / Generic lazy-neighbor agglomerative clustering

Generic lazy-neighbor agglomerative clustering

Algorithms AIMech:GenericLazyNeighborAgglomerativeClustering DRAFT

Aliases: Generic linkage algorithm (Müllner), GENERIC_LINKAGE

An agglomerative clustering algorithm that caches candidate nearest neighbors and lower bounds on row-minimum dissimilarities in a priority queue, rescanning a stale row only when necessary to certify the next globally closest pair before merging it.

Identity Notes & Concept Scope Compared all 442 pinned AIO and 652 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 38, 0, 0 lines. All distinct match contents were read, including generated index rows repeating the fully read corrected nearest-neighbor-chain record. Recovery hits concern shared primary-source references, chain implementation context or pending generic-procedure discovery notes; none identifies an existing standalone cached-bound record. Both other checkouts returned no matches including ignored and hidden files. Semantic matching covered 26 AIO and 169 native definitions, all read; unchanged definitions were byte-compared with the preceding full assessment. 9 full annotated AIO node/edge/generated contexts and 4 full native records were inspected. Retain Mullner’s stored-matrix generic linkage with deferred candidate-neighbor rescans and a lower-bound priority queue. It is not a generic label for every agglomerative algorithm, a linkage criterion, reciprocal-chain search or neighbor-voting classification. The Section6 alternative and vector implementations are not silently asserted as identical interfaces.

Claims & Grounded Evidence

6 Claims

Mechanism #candidate-lower-bounds

For each active row except the largest index, keep a candidate neighbor among higher-index clusters and a lower bound on that row’s minimum dissimilarity. Initialize the bounds by row scans and index them in a minimum-priority queue. Symmetry ensures these upper-triangular rows collectively contain a globally closest pair.

supports Source: Modern hierarchical, agglomerative clustering algorithms · Locator: Section3.1, Figure3 lines5–9, PDF pp.8–10
supports Source: fastcluster src/fastcluster.cpp · Locator: generic_linkage initialization, src/fastcluster.cpp lines940–1000 at the pinned commit

Mechanism #deferred-rescan-and-certification

Take a row with smallest queued bound. If its bound equals the actual distance to its candidate, the pair attains a global minimum. Otherwise rescan that row, raise its bound to the true row minimum, update the queue and reconsider the smallest entry. Candidate invalidation can therefore remain unresolved while its lower bound is larger than the current global minimum.

supports Source: Modern hierarchical, agglomerative clustering algorithms · Locator: Section3.1, Figure3 lines11–20 and explanation, PDF pp.9–11
supports Source: fastcluster src/fastcluster.cpp · Locator: generic_linkage invariant comments and stale-minimum loop, src/fastcluster.cpp lines1000–1060

Mechanism #merge-and-cache-maintenance

After accepting a pair, record the merge, remove its smaller row index and reuse the larger index for the union. Update distances under the selected linkage using the premerge cluster sizes. Redirect references to the removed representative, lower bounds when a new distance is smaller, and recompute the merged row’s higher-index minimum when such a row exists. These updates preserve the lower-bound and attained-bound invariants.

supports Source: Modern hierarchical, agglomerative clustering algorithms · Locator: Section3.1, Figure3 lines21–40 and explanation, PDF pp.9–11
supports Source: fastcluster src/fastcluster.cpp · Locator: generic_linkage merge and per-method updates, src/fastcluster.cpp lines1060–1348

Scope #inversions-and-linkage-scope

The method certifies a globally closest pair at each step without the nearest-neighbor-chain reducibility condition. It accommodates the paper’s centroid and median linkages, whose merge heights can decrease. Preserve their chronological merge dependencies rather than sorting those heights. Ties may select any valid closest pair; agreement with one fixed arbitrary tie convention is not required.

supports Source: Modern hierarchical, agglomerative clustering algorithms · Locator: Section2.2 and Section3.1, PDF pp.4–5,8–11
supports Source: fastcluster src/fastcluster_python.cpp · Locator: Matrix dispatch and generate_SciPy_dendrogram<true> for centroid/median, src/fastcluster_python.cpp lines313–353

Scope #time-and-memory-boundaries

For the stored-matrix setting and constant-time scalar distance updates, the paper gives quadratic best-case time and a cubic worst-case upper bound because stale row minima may require repeated scans. The algorithm retains a writable quadratic-size distance matrix plus linear auxiliary storage for candidates, bounds and the indexed queue. Empirically near-quadratic timing does not establish a universal quadratic guarantee.

supports Source: Modern hierarchical, agglomerative clustering algorithms · Locator: Section3.1 and Section4.1, PDF pp.10–11,20–21
supports Source: fastcluster src/fastcluster.cpp · Locator: binary_min_heap and generic_linkage storage, src/fastcluster.cpp lines779–1000

Limitation #literal-source-and-implementation-limits

The printed Figure3 updates the retained cluster size before passing sizes to its update formula and requests a higher-index minimum even at the terminal boundary. The later pinned matrix implementation saves both old sizes and guards that row update. Its lower-bound prose and operations imply bound≤true minimum despite a reversed sign in a comment. This record uses the supported invariant and those explicit boundaries rather than treating every printed line or code comment as an executable specification.

supports Source: Modern hierarchical, agglomerative clustering algorithms · Locator: Section3.1, Figure3 lines23–26,39–40 and invariant explanation, PDF pp.9–11
supports Source: fastcluster src/fastcluster.cpp · Locator: generic_linkage comments, saved sizes and idx2<N_1 guards, src/fastcluster.cpp lines1000–1348

⚠️ Curated Limitations & Negative Results

This record covers the stored-matrix generic procedure of Section3.1. Section6’s fresh-lowest-label variant and vector-data implementations require separate implementation assessments; they are not asserted as interchangeable APIs.
A valid greedy hierarchy is the output contract. The method does not infer a cluster count or establish globally optimal fixed-count partitions. Linkage geometry and admissible dissimilarities remain requirements of the chosen criterion.
The paper’s generic applicability concerns distance-update formulas in its symmetric-dissimilarity setting. The inspected fastcluster implementation dispatches a fixed set of linkage rules; no arbitrary callback API is claimed.
A finite centroid/median example merges points (−1,0) and (1,0) at squared height 4, then merges (0,9/5) at height 81/25. Sorting those heights would violate the dependency on the earlier union.
All 29 pages of the primary paper were visually read. The complete matrix generic_linkage and indexed heap, relevant distance updates and specified wrapper passages were statically inspected at the pinned commit; no author code, empirical timing or floating-point behavior was executed.
Curator calculations verify the lower-bound/equality invariant and global merge admissibility for 3,645 four-object matrix/linkage cases and 243 Euclidean cases, plus inversion, history-dependent-update and one/two-object boundaries. Their reference implementation uses linear queue selection and does not measure the paper’s time or memory bounds.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:HierarchicalClustering` Hierarchical Clustering	related_match	The algorithm constructs an agglomerative hierarchy. The target is a clustering task, so this is a related task context without algorithm/task equivalence or subclass assertion.
`AIO:UnsupervisedClustering` Unsupervised Clustering	related_match	The method groups unlabeled observations under supplied dissimilarities and a linkage update. The task target does not specify cached row bounds or deferred rescans.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`mullner2011`	Modern hierarchical, agglomerative clustering algorithms Daniel Müllner	primary paper full_text	ID: arXiv:1109.2378v1 sha256:3d8ea802c328…
`fastcluster-core`	fastcluster src/fastcluster.cpp Daniel Müllner, fastcluster contributors	official documentation documentation	ID: 9d0e48609283edaae90593a6967d3f2217786d2d sha256:9ba52420e373…
`fastcluster-wrapper`	fastcluster src/fastcluster_python.cpp Daniel Müllner, fastcluster contributors	official documentation documentation	ID: 9d0e48609283edaae90593a6967d3f2217786d2d sha256:b7fc7d732572…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-13T21:38:38Z

Updated: 2026-10-13T21:38:38Z

Source File: data/curated/GenericLazyNeighborAgglomerativeClustering.yaml