Home / Curated / Algorithms / Batch reciprocal-nearest-neighbor agglomeration

Batch reciprocal-nearest-neighbor agglomeration

Algorithms AIMech:BatchReciprocalNearestNeighborClustering DRAFT

Aliases: Reciprocal-neighbor batch clustering, de Rham reciprocal-neighbor clustering

An agglomerative clustering procedure that alternates finding reciprocal nearest-neighbor pairs across the current clusters with merging a batch of such pairs and updating cluster dissimilarities, rather than choosing one globally closest pair or extending a reusable nearest-neighbor chain.

Identity Notes & Concept Scope Compared all 442 pinned AIO and 653 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 57, 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 batch-procedure discovery notes; none identifies an existing standalone batch record. Both other checkouts returned no matches including ignored and hidden files. Semantic matching covered 26 AIO and 170 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 the two-phase batch reciprocal-pair search from deRham1980. It differs from a linkage criterion, a reusable nearest-neighbor chain, globally certified cached-bound selection and nearest-neighbor label voting. The later RS pruning/representative method has a different procedure and remains a separate lead.

Claims & Grounded Evidence

6 Claims

Mechanism #reciprocal-batch-passes

For each current cluster, find the set of other clusters attaining its minimum dissimilarity. A pair is reciprocal when each belongs to the other’s nearest-neighbor set, equivalently its pair distance attains both minima. The method alternates finding reciprocal pairs, merging a batch, and recomputing nearest-neighbor information until a single cluster remains. Simultaneous disjoint pair merges are a logical batch, not a claim of parallel hardware execution.

supports Source: La classification hiérarchique ascendante selon la méthode des voisins réciproques · Locator: Introduction and Sections2.3,3.2, printedpp135,137,140 / PDFpp2,4,7

Mechanism #matrix-distance-updates

The stored-distance realization updates dissimilarities between the new clusters and remaining clusters. When both endpoints represent newly merged pairs, the paper extends the usual two-cluster recurrence to four original clusters; the linkage coefficients and cluster weights determine that update. This separates the merge-search procedure from the selected linkage criterion.

supports Source: La classification hiérarchique ascendante selon la méthode des voisins réciproques · Locator: Sections2.1,3.1–3.3, printedpp136,139–140 / PDFpp3,6–7

Mechanism #vector-realization

For the cited centroid and variance strategies, a second realization retains the observation coordinates, merged representative coordinates and cluster weights and recomputes distances from them. It avoids retaining the full pairwise-distance matrix. The reported N(K+5) storage formula is accounting for that specific implementation with N observations and K variables, not a universal memory bound for every reciprocal-neighbor method.

supports Source: La classification hiérarchique ascendante selon la méthode des voisins réciproques · Locator: Sections4.1–4.2 and5, printedpp141–143 / PDFpp8–10

Scope #criterion-and-tie-scope

The source presents exact hierarchical construction for the named monotone single-link, diameter, average and variance strategies, while explicitly treating nonmonotone centroid strategies as heuristic. This does not establish correctness for arbitrary history-dependent recurrences. With ties, reciprocal pairs can overlap; a disjoint selection convention is needed to make a batch executable, and the printed merge-all-pairs instruction does not specify one.

supports Source: La classification hiérarchique ascendante selon la méthode des voisins réciproques · Locator: Introduction, Sections2.1,2.3,3.2 and4.1, printedpp135–137,140–141 / PDFpp2–4,7–8
supports Source: Modern hierarchical, agglomerative clustering algorithms · Locator: Section3.2, Theorem1 and footnote1, PDFpp12–16: limits of general reciprocal-pair arguments

Limitation #passes-and-output-boundaries

A pass need not merge many pairs: the batch procedure can find only one reciprocal pair and therefore require repeated global scans. Few passes in examples do not imply the later nearest-neighbor-chain algorithm’s quadratic bound. Merge heights within a batch need not be globally ordered; constructing a stepwise sequence requires attention to linkage conditions, chronological dependencies and tie handling.

supports Source: Construction d’une classification ascendante hiérarchique par la recherche en chaîne des voisins réciproques · Locator: Section1, printedpp209–210 / PDFpp2–3
supports Source: La classification hiérarchique ascendante selon la méthode des voisins réciproques · Locator: Section3.3, printedp140 / PDFp7
supports Source: Modern hierarchical, agglomerative clustering algorithms · Locator: Sections2.2 and3.2, PDFpp4–5,11–16

Performance #historical-evaluation-scope

The reported comparison uses three constructed hierarchies with 32, 64 and 128 observations and two variables on a CDC6500, with time in milliseconds and storage in words. BASE and DIST timings average seven strategies, while DONN averages only the three coordinate-compatible strategies. These differing workloads and small synthetic examples do not establish a universal speedup or a modern hardware ranking.

Evaluation Context:

Task: Historical hierarchical-clustering timing and memory comparison.

Dataset: Three constructed two-variable hierarchies with32,64 and128 observations; no train/test split.

Model: deRham1980 BASE,DIST and DONN implementations as described in Section5; no author code executed.

Metric: CPU time in milliseconds and storage in machine words.

Result: The source reports comparison tables for these three constructed inputs; this record draws no universal speedup or contemporary ranking from them. (Baseline: BASE conventional implementation compared with DIST stored-distance and DONN coordinate implementations.)

supports Source: La classification hiérarchique ascendante selon la méthode des voisins réciproques · Locator: Section5 and comparison table, printedp143 / PDFp10

⚠️ Curated Limitations & Negative Results

Section2.3 gives the correct mutual-membership definition, but its displayed M shortcuts include a self-membership expression and equate equality of nearest-distance minima with reciprocity. The supported definition requires the pair distance to attain both minima; equal minima alone are insufficient.
The finite curator implementation makes tied batches executable through an explicit lexicographic disjoint matching. This is a curator extension, not a tie rule attributed to the source or a claim of identical trees under arbitrary ties.
Curator checks cover2,880 four-object cases with distinct initial distances and2,916 cases allowing ties across four linkages. Later merges may introduce ties even in the first set. Stable height ordering is checked against greedy merge admissibility; this is finite evidence, not a universal proof.
The original six-point variance example is checked using exact ESS increments:125,212.5,250,1381.25 and19225/12. The source rounds displayed values, including212.5 to213; the rounded tables are not exact recurrence identities.
This record does not conflate the batch scan, a reusable reciprocal chain, or cached-bound selection of a globally closest pair. None implies a globally optimal fixed-count partition or automatic selection of a unique cluster count.
Complete cited primary PDFs were visually inspected. No author software, CDC benchmark, modern implementation or floating-point behavior was executed; only finite curator calculations were run.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:HierarchicalClustering` Hierarchical Clustering	related_match	The batch procedure constructs a hierarchy; the AIO target denotes a clustering task, not this algorithm or a task/algorithm is-a relation.
`AIO:UnsupervisedClustering` Unsupervised Clustering	related_match	Clusters are formed from supplied dissimilarities without known class labels. The task target does not specify reciprocal batches, linkages or tie conventions.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`derham1980`	La classification hiérarchique ascendante selon la méthode des voisins réciproques C. de Rham	primary paper full_text	sha256:c62314df59e7…
`benzecri1982`	Construction d’une classification ascendante hiérarchique par la recherche en chaîne des voisins réciproques J.-P. Benzécri	primary paper full_text	sha256:2569b4b21a2e…
`mullner2011`	Modern hierarchical, agglomerative clustering algorithms Daniel Müllner	primary paper full_text	ID: arXiv:1109.2378v1 sha256:3d8ea802c328…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-13T21:53:58Z

Updated: 2026-10-13T21:53:58Z

Source File: data/curated/BatchReciprocalNearestNeighborClustering.yaml