Pith. Sign in

REVIEW

Dispelling the N^3 myth for the Kt jet-finder

PaperPDF from arXiv

data files

ReviewThe objections and verdict, as JSON Paper breakdownThe authors' claims, conditions and measurements, as JSON Signed receiptProof this review has not been altered
X Bluesky LinkedIn Reddit Hacker News
Matteo Cacciari, Gavin P. Salam

High Energy Physics - Phenomenology · Submitted 16 Dec 2005 · 33 references

Pith's verdict: The reduction is real and the code shipped; the only soft spots are how hard the abstract leans on an expected-case complexity bound and on a speed claim the figures don't quite support.

T0 · AI review

How this review was made: An AI referee (selfhosted/deepseek-v4.1-flash) read the paper on October 29, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

  1. T0 AI review An AI read the paper and answered a fixed list of questions.
  2. T1 Audit Automatic checks that the references and files the paper relies on exist and match.
  3. T2 Compute The paper's code or calculations re-run with the same results.
  4. T3 Formal statement The claims written out in a formal math language a computer can read.
  5. T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 6 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv IDhep-ph/0512210 (version 2)
Pith IDXUZAWBUZ, Pith's permanent record of this paper and its review
CitationGavin P. Salam, Matteo Cacciari. "Dispelling the N^3 myth for the Kt jet-finder." arXiv:hep-ph/0512210 (2005). https://pith.science/paper/XUZAWBUZ
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

Why Pith says this

Highlight any text to comment on it.

Referee report

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

The kt jet-finder's apparent cubic cost is an artifact of how it was implemented: by reducing the hard part of clustering to dynamic nearest-neighbour search on a plane, the same jets can be built in $N$ ln $N$ time.

The reading

The kt jet-finder is a rule for grouping the hundreds or thousands of particles produced in a high-energy collision into jets. It is valued because it approximately retraces the sequence in which quarks and gluons branched, but it had been assumed to cost $N^3$ operations for $N$ particles, which at LHC multiplicities means seconds per event and at heavy-ion multiplicities means a day. The paper argues that this cubic cost is not intrinsic to the jet definition but to the standard bookkeeping: a full table of all pairwise distances is built and rescanned at every step. The authors show that the only distances that can ever be minimal are each particle's distance to its nearest geometrical neighbour, so the $N^2$ table can be replaced by an $N$-entry array maintained with computational-geometry data structures. If that holds, the same jets come out, only fast enough to be used on every calorimeter cell and on heavy-ion events.

What carries the argument

The lemma relating the smallest kt distance to geometrical nearest neighbours. It converts a problem about a dynamically shrinking set of weighted points into the classical computational-geometry problem of maintaining nearest neighbours under insertion and deletion, for which Voronoi diagrams, Delaunay triangulations, and balanced search trees supply $O(ln N)$ update costs. The Voronoi cell picture is what makes the argument concrete: a vertex's nearest neighbour is always in one of the few cells sharing an edge with its own, so the search is local rather than global.

Extended reading notes

Core claim

The central claim is a reduction: the computationally expensive part of kt clustering is exactly two-dimensional nearest-neighbour location for a set of points that changes as particles are merged and removed. The load-bearing step is a lemma in Section 3. If particles $i$ and $j$ give the smallest $d_{ij}$ and $k_{ti} < k_{tj}$, then $R_{ij} < R_{iell}$ for every other particle $ell$, so $j$ is $i$'s geometrical nearest neighbour; otherwise a smaller $d_{iell}$ would exist, contradicting minimality. Consequently one never needs the full $N^2$ table of $d_{ij} = min(k_{ti}^2, k_{tj}^2) R_{ij}^2$; a size-$N$ array of nearest-neighbour distances $d_{iG_i}$ plus beam distances $d_{iB}$ suffices. Nearest neighbours are then found and maintained with a Voronoi diagram and its Delaunay dual, the minimum is tracked in a balanced binary tree, and each of the $N$ iterations costs $O(ln N)$ rather than $O(N^2)$. The authors implement both an $N^2$ and an $N ln N$ version in FastJet and report that the better of the two runs at least an order of magnitude faster than the standard $N^3$ code KtJet across the whole range of $N$ they test, and faster than the other publicly available jet-finders they compare against.

Load-bearing premise

The $N ln N$ accounting assumes that on average only a constant number of particles have any given particle as their nearest neighbour, so each merge or removal touches only a bounded amount of nearest-neighbour information; the paper states this in a footnote rather than proving a worst-case bound, and dense or degenerate particle configurations are exactly where it could fail.

Editorial extensions

If this is right

  • kt clustering becomes practical on all finely segmented calorimeter cells, removing the motivation for physically questionable preclustering to shrink $N$.
  • Heavy-ion events with $O(50000)$ particles, previously estimated at more than a day of CPU per event, become clusterable in reasonable time.
  • Jet areas can be measured by adding $O(10^4)$ soft ghost particles and counting how many land in each jet, which is only feasible with a fast clusterer.
  • Because the algorithm is functionally equivalent to the standard one, existing physics results are unchanged; only the cost of obtaining them falls.
  • The same reduction applies to the Cambridge/Aachen algorithm, which shares the pairwise-distance structure with different distance definitions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The reduction is really a statement about which comparisons are redundant, so it should transfer to any sequential-recombination scheme whose distance is a transverse-momentum weight times a monotone function of a two-dimensional separation.
  • Worst-case behaviour on degenerate configurations, such as particles packed on a line or in a dense core, is where a practical implementation would most plausibly degrade; a benchmark on deliberately adversarial point sets would test how much of the speed survives outside typical simulated events.
  • The mirror-copy trick for the periodic azimuth boundary is a heuristic for embedding a cylinder in a plane; an exact cylindrical nearest-neighbour structure would remove the need for it and could be checked directly against brute force on small events.
  • If jet areas can be computed reliably from ghost counts, the same machinery invites a per-event estimate of pileup density, turning a fast clusterer into a pileup-subtraction tool rather than only a jet definition.
Original abstract

At high-energy colliders, jets of hadrons are the observable counterparts of the perturbative concepts of quarks and gluons. Good procedures for identifying jets are central to experimental analyses and comparisons with theory. The Kt family of successive recombination jet finders has been widely advocated because of its conceptual simplicity and flexibility and its unique ability to approximately reconstruct the partonic branching sequence in an event. Until now however, it had been believed that for an ensemble of N particles the algorithmic complexity of the Kt jet finder scaled as N^3, a severe issue in the high multiplicity environments of LHC and heavy-ion colliders. We here show that the computationally complex part of Kt jet-clustering can be reduced to two-dimensional nearest neighbour location for a dynamic set of points. Borrowing techniques developed for this extensively studied problem in computational geometry, Kt jet-finding can then be performed in N ln N time. Code based on these ideas is found to run faster than all other jet finders in current use.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13-20260917 via OpenRouter, question bank abstract-p1-20260923, 2026-09-23: 1 request, 5,598 input tokens, $0.0002 reported.

What the abstract itself states, as probabilities: claims first 0.16 · states limitation 0.09 · human participants 0.02 · controlled comparison 0.15 · randomized assignment 0.01 · states quantitative result 0.84 · compares with prior results 0.92 · mentions code or data availability 0.07.

The abstract, sentence by sentence

arXiv listing abstract v2. Results and the main claim are underlined; .

At high-energy colliders, jets of hadrons are the observable counterparts of the perturbative concepts of quarks and gluons. Good procedures for identifying jets are central to experimental analyses and comparisons with theory. The Kt family of successive recombination jet finders has been widely advocated because of its conceptual simplicity and flexibility and its unique ability to approximately reconstruct the partonic branching sequence in an event. Until now however, it had been believed that for an ensemble of N particles the algorithmic complexity of the Kt jet finder scaled as N^3, a severe issue in the high multiplicity environments of LHC and heavy-ion colliders. We here show that the computationally complex part of Kt jet-clustering can be reduced to two-dimensional nearest neighbour location for a dynamic set of points. Borrowing techniques developed for this extensively studied problem in computational geometry, Kt jet-finding can then be performed in N ln N time. Code based on these ideas is found to run faster than all other jet finders in current use.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
s0 At high-energy colliders, jets of hadrons are the observable counterparts of the perturbative concepts of quarks and gluons. background 1.00 0.04 0.01 asserted 1.00
s1 Good procedures for identifying jets are central to experimental analyses and comparisons with theory. background 1.00 0.04 0.02 asserted 1.00
s2 The Kt family of successive recombination jet finders has been widely advocated because of its conceptual simplicity and flexibility and its unique ability to approximately reconstruct the partonic branching sequence in an event. background 1.00 0.05 0.02 asserted 1.00
s3 Until now however, it had been believed that for an ensemble of N particles the algorithmic complexity of the Kt jet finder scaled as N^3, a severe issue in the high multiplicity environments of LHC and heavy-ion colliders. gap 0.83 0.04 0.05 asserted 0.96
s4 We here show that the computationally complex part of Kt jet-clustering can be reduced to two-dimensional nearest neighbour location for a dynamic set of points. method 0.49 0.93 0.52 asserted 1.00
s5 Borrowing techniques developed for this extensively studied problem in computational geometry, Kt jet-finding can then be performed in N ln N time. result 0.59 0.78 0.71 asserted 0.97
s6 Code based on these ideas is found to run faster than all other jet finders in current use. result 1.00 0.93 0.14 asserted 1.00

What kind of paper the classifier reports this is: method or tool 0.85 · evidence from proof or derivation 0.57.

What was examined, and what was not

sources read
  • arXiv listing abstract v2
not examined
  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers
levels run
  • P abstract
not run
  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures
Figure 1. The Voronoi diagram for ten random points. The Delaunay triangulation (red) connecting the ten points is also shown. In this example the points 1, 4, 2, 8 and 3 are the ‘Voronoi’ neighbours of 7, and 3 is its nearest neighbour. 10-5 10-4 10-3 10-2 10-1 100 101 102 103 104 105 t (s) N KtJet FastJet N2 FastJet N ln N
Figure 2. The running times (on a 3 GHz Pentium 4 processor with 1 GB of memory, 512 kB of cache, and version 3.4 of the GNU g++ compiler) of the KtJet [22] and FastJet implementations of the kt-clustering jet-finder versus the number of initial particles. Different values of N have been obtained by taking a LHC dijet event with pt ≃ 60 GeV and adding on variable numbers of minimum bias events. Both kinds of events have been simulated with Pythia 6.3 [28]. Computational Geometry Algorithms Library (CGAL) [26], in particular its triangulation components [27].6 For the binary tree we made use…
Figure 3. The running times of various jet-finders versus the number of initial particles. JetClu is a widely-used cone-type jet-finder, however it is ‘almost infrared unsafe’, i.e. perturbative predictions have large logarithmic dependence on small parameters (e.g. seed threshold) [29, 30]. MidPoint [29] is an infrared safe cone-type jet finder. For both we use code and parameters from CDF [31]. The Optimal Jet Finder [9] (OJF) has been run with Ωcut = 0.15 and a maximum of 8 jets, so as to produce a final state similar to that returned by the kt and cone jet-finders and to limit its run time

Figures reproduced from arXiv:hep-ph/0512210 by the authors.

References
How later papers used it

629 later papers cite it

Evidence: substantial. 611 of the citing papers share no author with it, and 569 of those carry a confident label from Pith's citation classifier.

Pith read 39 of the 681 citing sentences, choosing only those whose citation markers point at this paper alone, and wrote the paraphrases from them. The summary, the counts, the evidence level, the links and the quotes come from code; the summary counts the papers listed below. A later paper is listed under a label when Pith's citation classifier gives one of its sentences that label at probability 0.8 or more (0.95 for support), Pith's reading finds that the citing paper itself did it, and a second check confirms the paraphrase against the sentence. This section lists uses only. It does not list criticism or disagreement, so their absence here says nothing about how the paper has been received. Papers that share an author with this one are listed apart, under "By the same authors". A quote is the citing authors' own sentence, shown when their paper's licence is CC BY, CC BY-SA or CC0. JSON

Uses its method or tool 36 of 580 papers with this label · 1 by the same authors

By the same authors

How the literature uses it

575 arXiv papers cite this in 620 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 52 sentences without a confident label

Uses its method or tool 532 papers
Compares with it 1 paper
Cites it as background 4 papers
  • As mentioned in the Introduction, the last few years have seen many developments in the field of jet clustering, with the appearance of fast implementations [ref] of the $k_t$ [ref] and the Cambridge/Aachen [ref] sequential recombination algorithms, and the introduction of the SISCone [ref] and anti-$k_t$ [ref] algorithms.

    Jet Reconstruction in Heavy Ion Collisions · Jet definitions · 0.94

  • Combined with the seminal introduction of robust jet algorithms [ref] , this initiated the field of jet substructure [ref] .

    A New Paradigm for Precision Top Physics: Weighing the Top with Energy Correlators · Introduction · 0.82

  • For sequential recombination algorithms like the $k_⊥$- or anti-$k_⊥$-algorithms [ref] this is not a problem, since the CPU time for the jet algorithm is negligible against the CPU time required for the matrix element associated with the subtraction term.

    The SISCone jet algorithm optimised for low particle multiplicities · Introduction · 0.91

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.