Dispelling the N3 myth for the kt jet-finder

By Matteo Cacciari, G. Salam. 2005

1,634 citations recorded by the source corpus.

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 k t 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 k t 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 k t 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, k t 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.

Subfields: Artificial Intelligence, Computer Graphics and Computer-Aided Design, Nuclear and High Energy Physics

View Paper: https://www.semanticscholar.org/paper/929dab16b1e5def07427b4deefa00dd900be5c77

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Cms Collaboration
2. Atlas Collaboration
3. G. Soyez
4. Gudrun Heinrich
5. Jesse Thaler
6. A. Larkoski
7. G. Salam
8. P. Nason

In Computer Graphics and Computer-Aided Design

1. Cms Collaboration
2. Atlas Collaboration
3. E. Re
4. P. Nason
5. Carlo Oleari
6. G. Soyez
7. Simone Alioli
8. L. Lonnblad

In Nuclear and High Energy Physics

1. Cms Collaboration
2. Atlas Collaboration
3. Gudrun Heinrich
4. A. Larkoski
5. M. Schönherr
6. Fabio Maltoni
7. F. Krauss
8. S. Höche

Citations in the corpus

• Search for direct production of charginos, neutralinos and sleptons in final states with two leptons and missing transverse momentum in pp collisions at √s = 8 TeV with the ATLAS detector (2014, methodology): “Jet candidates are reconstructed from calorimeter energy clusters using the anti-kt jet clustering algorithm [86, 87] with a radius parameter of 0.”
• The ATLAS Experiment at the CERN Large Hadron Collider (2008, methodology): “The k⊥ algorithm in ATLAS is implemented following the suggestions in [270], which makes it efficient even for a rather large number of input objects and avoids the usual pre-clustering step.”
• MadAnalysis 5, a user-friendly framework for collider phenomenology (2012, background): “, those included in the FastJet program [53].”
• Search for electroweak production of charginos and neutralinos in multilepton final states in proton-proton collisions at s=13$$ \sqrt{s}=13 $$ TeV (2017, methodology): “4, as implemented in the FASTJET package [46, 47].”
• NLO single-top production matched with shower in POWHEG: s- and t-channel contributions (2009, methodology): “Jets have been defined according to the kT algorithm [45], as implemented in the FASTJET package [46], setting R = 1 and imposing a lower 10 GeV cut on jet transverse momenta.”
• ATLAS search for new phenomena in dijet mass and angular distributions using pp collisions at √s=7 TeV (2012, methodology): “The default jet algorithm in ATLAS is the anti-kt algorithm [28, 29].”
• Search for a Higgs boson decaying into a Z and a photon in pp collisions at $s$ = 7 and 8 TeV (2013, methodology): “Jets used in the dijet-tagged event selection defined below are built by clustering the PF candidates with the anti-kT clustering algorithm [21] with distance parameter of 0.”
• Search for lepton-flavour-violating decays of the Higgs boson (2015, positive): “Jets are reconstructed from all the PF objects using the anti-kT jet clustering algorithm [53] implemented in FastJet [54], with a distance parameter of 0.5.”
• HW±/HZ + 0 and 1 jet at NLO with the POWHEG BOX interfaced to GoSam and their merging within MiNLO (2013, methodology): “Jets have been reconstructed using the anti-kT jet algorithms, as implemented in the fastjet package [42, 43] with R = 0.”
• Evidence for the Higgs-boson Yukawa coupling to tau leptons with the ATLAS detector (2015, neutral): “Jets are reconstructed using the anti-kt jet clustering algorithm [31, 32] with a radius parameter R = 0.”