DAF Tracking Algorithm

Complete: 4

Goal of the page

This page is intended to familiarize you with DAF. In this page the main features of the algorithm are presented, togheter with an example on how to run DAF and how to change some parameters.


Antonio Tropiano, Chiara Genta, Pier Giulio Lenzi.


The Deterministic Annealing Filter (also known as DAF) is a track fitting method that implements a soft hit-to-track assignment.

The standard KalmanFilter is not designed to protect himself against the assignment of the wrong hit to a track, being an algorithm based on a hard hit-to-track-assignment (the assignment is binary). In algorithms like DAF each hit is assigned to one or more tracks, with a different weight for each track. The hit-to-track-assignment is no longer binary but is expressed by an assignment probability, that can take any value between 0 and 1.

For each detecting surface hits which are reasonably close to the track are put into competition for a contribution to the track, and the amount of this contribution is measured by an assignment probability. For a detailed description of the algorithm used to calculate the assignment probability look at Mathias Winkler's PhD thesis(pag. 42).

It's possible to use exactly the usual KF formulas for the update of the state vector on a surface with n competing hits if the n hits are replaced with a virtual hit called MultiRecHit. To avoid ending up in local minima an annealing program is applied. The annealing is a procedure that consist in multiplying the covariance matrix associated to each hit of the track for an annealing factor, called β, to artificially increase the hit position errors. A typical annealing scheme is β={80,9,4,1,1,1}.

At the beginning of the track fit the hits to be put in competition are collected in a wide region around the reconstructed position of the track. The weights of the hits in competition for a certain track are nearly equal. In fact the annealing factor β is very large at the beginning of the annealing cycle and all the hits contribute to the estimation of the track parameters. This region is less and less wide with the decreasing of the annealing factor, till the end when only to one of the several hits that compete for the same track is assigned a weight near to 1, while the others are assigned a very low weight. In this way DAF makes a reassignment of the hits that can correct wrong hit-to-track assignments (for example hits that come from delta rays or hits belonging to a different track).

For all these reasons the DAF is particularly suited for noisy environments, where we have a high number of hits, due to particles, electronic noise or pile up effects, that can' t be neglected at CMS. For dense environments a generalization of the DAF, known as Multi Track Filter (also known as MTF) should perform better. In the MTF not only the hits compete for a contribution to the tracks, but also the tracks compete for the hits. Both the DAF and the MTF were implemented in ORCA and we are currently working to put them into CMSSW.

The DAF is implemented in CMSSW since version 2_0_X. For an analysis of DAF performances look at these talks at the Tracking POG Working Meeting:

Usage of the algorithm

When to use this algorithm

DAF is a tracking algorithm designed to improve the efficiency and parameter resolution of reconstructed tracks inside jets. It is complementary to the standard track reconstruction chain and it can be used to improve track reconstruction inside high density jets.

Configuration sequence

The first step of DAF is to take all the Trajectories from the Event, reconstructed by the standard reconstruction procedure (using the iterative tracking algorithm). These Trajectories are then refitted; then the RecHits that make each Trajectory are put togheter in MultiRecHits and their positions on each layer with respect to each Track state are used to compute their weights. After that the annealing cycle starts. The tracks are refitted one at a time taking into account MultiRecHits positions. The weights of the hits in the MultiRecHits are recomputed after each annealing step. At the end of the annealing cycle we have a track collection named ctfWithMaterialTracksDAF that are the tracks in the event refitted with DAF.

In order to refit tracks with DAF one has to refit all the tracks in the event. For this reason all the modules to refit tracks have to be loaded.

#modules to refit tracks

Then one has to load the DAF related module.

#DAF related module

Finally one has to change some parameters related to the input of DAF

#DAF related parameters
process.ctfWithMaterialTracksDAF.src = 'TrackRefitter'
process.TrackRefitter.TrajectoryInEvent = cms.bool(True)
process.ctfWithMaterialTracksDAF.TrajectoryInEvent = cms.bool(True)

To run DAF reconstruction one has to run the following path:

process.p = cms.Path(process.TrackRefitter*process.ctfWithMaterialTracksDAF)

Default parameters

There are three main parameters of the algorithm, which are configurable from the configuration file.

  • Annealing cycle schema: the length of the cycle and the annealing factors β can be tuned. Hits probabilities are computed with the knowledge of the TSOS and RecHit positions and associated covariance matrix V. At each annealing cycle this matrix is artificially increased by a factor β, so that ViiV. Recent studies of DAF performances for different annealing sets hasn't shown a great dependence from the annealing sets.
  • Width of hit-search window : it is defined by a χ2 cut around the smoothed state xsm of the track. In formulas: χ2=(mj-Hxsm)T V-1j(mj-Hxsm) where mj are the vectors of the measurements on a layer and H is the Jacobian matrix between the track parameters vector and its position on a certain layer. From some studies of the dependence of DAF performances from this parameter it was seen a general increase in the efficiency and decrease in fake rate as the window width gets larger.
  • Hit collector method:
    • simple: search for hits only in the detector where the original hit was.
    • grouped: search for hits also in neighbor detectors (it doesn't put in competition hits in overlaps). It is the best method to collect hits for both efficiency and fake rate.

Software architecture

The basic components of the DAF implementation in CMSSW are:

  • DataFormats/TrackerRecHit2D/interface/SiTrackerMultiRecHit.h: it implements the MultiRecHit concept. In addition to the TrackingRecHit it holds an OwnVector<TrackingRecHit> for the component rec hits and a vector<float> for the weights.
  • RecoTracker/Record/interface/MultiRecHitRecord.h: the record holding the DAF related es stuff
  • RecoTracker/TransientTrackingRecHit/interface/TSiTrackerMultiRecHit.h: the transient companion of the above rechit
  • RecoTracker/SiTrackerMRHTools/interface/GenericProjectedRecHit2D.h: since in general the MultiRecHit components may lay on different surfaces, the need of defining all the component hits in a consistent reference frame arises. The GenericProjectedRecHit2D makes use of an analytical propagation of the hit from the original surface to the reference one. This propagation is implemented in the TrackingRecHitPropagator class, as described below.
  • RecoTracker/SiTrackerMRHTools/interface/SiTrackerMultiRecHitUpdator.h: this class is delivered by an ESProducer, living in the MultiRecHitRecord. It either builds a TSiTrackerMultiRecHit out of a vector<TrackingRecHit*>, a TSOS and an annealing value, or updates an existing TSiTrackerMultiRecHit with a TSOS and an annealing factor. It holds the bulk of the code for the weight calculation.
  • RecoTracker/SiTrackerMRHTools/interface/MultiRecHitCollector.h: this class is delivered by an ESProducer, living in the MultiRecHitRecord. It collects the hits for the MultiRecHit construction and builds the MultiRecHit at the beginning of the algorithm. Given a KF trajectory it returns a vector<TrajectoryMeasurement>, and the rec hit in each TrajectoryMeasurement is either a TSiTrackerMultiRecHit or an InvalidTransientRecHit. Two ways are foreseen for the hit collection:
    • SimpleDAFHitCollector: It looks for compatible hits only on the detectors on which the KF TSOS lays. Hits are looked for with a loose chi2 criterion. Notice that it's fair to put hits on the same detector into competition, because they are mutually exclusive for the track (a not pathological track cannot have more than one hit per detector ).
    • GroupedDAFHitCollector: It makes use of the LayerMeasurements::groupedMeasurements method to find hits that can be put into competition. This method returns group of hits. The detectors in each group are mutually exclusive fot the track's passage, so it is fair to build a MultiRecHit out of each group. This hit collection mode is activated by default. N.B. since we are making use of the groupedMeasurement method it's possible to run the non-grouped KF pattern recognition; hits on the overlaps will be recovered in the hit collection step.
  • TrackingTools/KalmanUpdators/interface/TrackingRecHitPropagator.h: it's delivered by an ESProducer living in TrackingComponentsRecord. It performs the "hit propagation" needed to define the MultiRecHit components in a consistent frame.
  • TrackingTools/KalmanUpdators/interface/MRHChi2MeasurementEstimator.h: it's delivered by an ESProducer living in TrackingComponentsRecord. It performs the chi2 estimate for a measurement containing a MultiRecHit.
  • RecoTracker/TrackProducer/plugins/DAFTrackProducer.h: This is the producer that actually runs the algorithm. For each KF TrackCandidate a KF fitting-smoothing is applied to get a Trajectory. The Trajectory is passed to the HitCollector, that recovers hits and builds the MultiRecHits. For each annealing step a full KF fitting-smoothing is applied. Since the use of the MultiRecHits allows to use standard KF update formulas, the standard KFFittingSmoothing esproducer is used (plugging in the MRH chi2 estimator). After each Fitting-smoothing step the MultiRecHits are updated with the new annealing factor, and the assignment weights are recalculated. Once the annealing program has been completed isolated hits with very low weight are replaced with InvalidHits and the fit is repeated for the last time.


Review status

Reviewer/Editor and Date (copy from screen) Comments
KatiLassilaPerini - 29 Jan 2008 created template page
AntonioTropiano - 30 Apr 2009 ported some documentation from old page and added new

Responsible: AntonioTropiano
Last reviewed by: AntonioTropiano

Edit | Attach | Watch | Print version | History: r5 < r4 < r3 < r2 < r1 | Backlinks | Raw View | WYSIWYG | More topic actions
Topic revision: r5 - 2010-11-11 - AntonioTropiano
    • Cern Search Icon Cern Search
    • TWiki Search Icon TWiki Search
    • Google Search Icon Google Search

    CMSPublic All webs login

This site is powered by the TWiki collaboration platform Powered by PerlCopyright & 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback