CERN Summer Student Work Project Report

Particle reconstruction based on information from tracker and calorimeters is important for various aspects of physical analysis in the CMS experiment [1]. A charged hadron leaves a track and electromagnetic and hadronic clusters. Thus to reconstruct it we need to link these signatures. Current particle-flow algorithm [2] based on this principle was developed for proton-proton collisions. It was found out to be prohibitively slow for processing heavy ion collision events, where multiplicity of produced particles (up to 50000) is much higher than in case of pp collisions, therefore we need to find faster solution. To simplify the problem, our first idea was to search only for the nearest electromagnetic cluster for a given track. In computer science, this is a well-known problem of looking for the nearest neighbor. There exist several fast, i.e. with complexity O(N log N), solutions for this task, e.g. one can use Voronoi diagrams technique, it has been used in the FastJet algorithm [2]. We decided to utilize a data structure called kd-tree [3], because expected complexity is similar to Voronoi diagrams, while the implementation is far easier and less complex. At this stage we focus only on one type of links, i.e. Links between tracks and barrel clusters. If we succeed we will try to apply the same or similar solution for the other types of links.