Dispelling the N3 myth for the kt jet-finder

被引:1149
作者
Cacciari, Matteo
Salam, Gavin P. [1 ]
机构
[1] Univ Paris 06, LPTHE, Paris, France
[2] Univ Paris 07, LPTHE, Paris, France
[3] CNRS, Paris, France
关键词
D O I
10.1016/j.physletb.2006.08.037
中图分类号
P1 [天文学];
学科分类号
0704 ;
摘要
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 In N time. Code based on these ideas is found to-run faster than all other jet finders in current use. (c) 2006 Elsevier B.V. All rights reserved.
引用
收藏
页码:57 / 61
页数:5
相关论文
共 41 条
[1]   The inclusive jet cross section in pp collisions at √s=1.8 TeV using the k⊥ algorithm [J].
Abazov, VM ;
Abbott, B ;
Abdesselam, A ;
Abolins, M ;
Abramov, V ;
Acharya, BS ;
Adams, DL ;
Adams, M ;
Ahmed, SN ;
Alexeev, GD ;
Alton, A ;
Alves, GA ;
Amos, N ;
Anderson, EW ;
Arnoud, Y ;
Avila, C ;
Baarmand, MM ;
Babintsev, VV ;
Babukhadia, L ;
Bacon, TC ;
Baden, A ;
Baldin, BB ;
Balm, PW ;
Banerjee, S ;
Barberis, E ;
Baringer, P ;
Barreto, J ;
Bartlett, JF ;
Bassler, U ;
Bauer, A ;
Bean, A ;
Beaudette, F ;
Begel, M ;
Belyaev, A ;
Beri, SB ;
Bernardi, G ;
Bertram, I ;
Besson, A ;
Beuselinck, R ;
Bezzubov, VA ;
Bhat, PC ;
Bhatnagar, V ;
Bhattacharjee, M ;
Blazey, G ;
Blekman, F ;
Blessing, S ;
Boehnlein, A ;
Bojko, NI ;
Borcherding, F ;
Bos, K .
PHYSICS LETTERS B, 2002, 525 (3-4) :211-218
[2]   Subjet multiplicity of gluon and quark jets reconstructed with the k⊥ algorithm in p(p)over-bar collisions -: art. no. 052008 [J].
Abazov, VM ;
Abbott, B ;
Abdesselam, A ;
Abolins, M ;
Abramov, V ;
Acharya, BS ;
Adams, DL ;
Adams, M ;
Ahmed, SN ;
Alexeev, GD ;
Alton, A ;
Alves, GA ;
Amos, N ;
Anderson, EW ;
Arnoud, Y ;
Avila, C ;
Baarmand, MM ;
Babintsev, VV ;
Babukhadia, L ;
Bacon, TC ;
Baden, A ;
Baldin, B ;
Balm, PW ;
Banerjee, S ;
Barberis, E ;
Baringer, P ;
Barreto, J ;
Bartlett, JF ;
Bassler, U ;
Bauer, D ;
Bean, A ;
Beaudette, F ;
Begel, M ;
Belyaev, A ;
Beri, SB ;
Bernardi, G ;
Bertram, I ;
Besson, A ;
Beuselinck, R ;
Bezzubov, VA ;
Bhat, PC ;
Bhatnagar, V ;
Bhattacharjee, M ;
Blazey, G ;
Blekman, F ;
Blessing, S ;
Boehnlein, A ;
Bojko, NI ;
Borcherding, F ;
Bos, K .
PHYSICAL REVIEW D, 2002, 65 (05)
[3]   TOPOLOGY OF 3-JET EVENTS IN PBARP COLLISIONS AT SQUARE-ROOT-S=1.8 TEV [J].
ABE, F ;
AMIDEI, D ;
APOLLINARI, G ;
ATAC, M ;
AUCHINCLOSS, P ;
BADEN, AR ;
BACCHETTA, N ;
BAILEY, MW ;
BAMBERGER, A ;
DEBARBARO, P ;
BARNETT, BA ;
BARBAROGALTIERI, A ;
BARNES, VE ;
BAUMANN, T ;
BEDESCHI, F ;
BEHRENDS, S ;
BELFORTE, S ;
BELLETTINI, G ;
BELLINGER, J ;
BENJAMIN, D ;
BENSINGER, J ;
BERETVAS, A ;
BERGE, JP ;
BERTOLUCCI, S ;
BHADRA, S ;
BINKLEY, M ;
BLAIR, R ;
BLOCKER, C ;
BOLOGNESI, V ;
BOOTH, AW ;
BOSWELL, C ;
BRANDENBURG, G ;
BROWN, D ;
BUCKLEYGEER, E ;
BUDD, HS ;
BUSETTO, G ;
BYONWAGNER, A ;
BYRUM, KL ;
CAMPAGNARI, C ;
CAMPBELL, M ;
CANER, A ;
CAREY, R ;
CARITHERS, W ;
CARLSMITH, D ;
CARROLL, JT ;
CASHMORE, R ;
CASTRO, A ;
CERVELLI, F ;
CHADWICK, K ;
CHIARELLI, G .
PHYSICAL REVIEW D, 1992, 45 (05) :1448-1458
[4]   Measurement of the inclusive jet cross section using the kT algorithm in p(p)over-bar collisions at √s=1.96 TeV [J].
Abulencia, A ;
Acosta, D ;
Adelman, J ;
Affolder, T ;
Akimoto, T ;
Albrow, MG ;
Ambrose, D ;
Amerio, S ;
Amidei, D ;
Anastassov, A ;
Anikeev, K ;
Annovi, A ;
Antos, J ;
Aoki, M ;
Apollinari, G ;
Arguin, J-F ;
Arisawa, T ;
Artikov, A ;
Ashmanskas, W ;
Attal, A ;
Azfar, F ;
Azzi-Bacchetta, P ;
Azzurri, P ;
Bacchetta, N ;
Bachacou, H ;
Badgett, W ;
Barbaro-Galtieri, A ;
Barnes, VE ;
Barnett, BA ;
Baroiant, S ;
Bartsch, V ;
Bauer, G ;
Bedeschi, F ;
Behari, S ;
Belforte, S ;
Bellettini, G ;
Bellinger, J ;
Belloni, A ;
Ben Haim, E ;
Benjamin, D ;
Beretvas, A ;
Beringer, J ;
Berry, T ;
Bhatti, A ;
Binkley, M ;
Bisello, D ;
Bishai, M ;
Blair, RE ;
Blocker, C ;
Bloom, K .
PHYSICAL REVIEW LETTERS, 2006, 96 (12) :1-7
[5]   Deterministic annealing as a jet clustering algorithm in hadronic collisions [J].
Angelini, L ;
Nardulli, G ;
Nitti, L ;
Pellicoro, A ;
Perrino, D ;
Stramaglia, S .
PHYSICS LETTERS B, 2004, 601 (1-2) :56-63
[6]   Jet analysis by Deterministic Annealing [J].
Angelini, L ;
de Felice, P ;
Maggi, M ;
Nardulli, G ;
Nitti, L ;
Pellicoro, M ;
Stramaglia, S .
PHYSICS LETTERS B, 2002, 545 (3-4) :315-322
[7]  
[Anonymous], HEPPH0604120
[8]  
Appleby RB, 2002, J HIGH ENERGY PHYS
[9]  
AURENHAMMER F, 1991, COMPUT SURV, V23, P345, DOI 10.1145/116873.116880
[10]  
BARTEL W, 1986, Z PHYS C PART FIELDS, V33, P23, DOI 10.1007/BF01410449