 |
ACTS
Experiment-independent tracking
|
|
ACTS
Experiment-independent tracking
|
Seeding by building and filtering a graph of hit doublets.
Classical ACTS seeding (Seeding) enumerates triplets of space points from a binned grid and cuts on the helix they describe. The combinatorics of that enumeration grow steeply with occupancy, and every triplet is judged in isolation.
GBTS inverts the order. It first builds a graph: nodes are space points, and a directed edge joins two space points on connected detector layers whenever the pair passes a set of cheap two-point cuts. Only then does it look for structure in that graph — long chains of mutually compatible edges — and turn the best chains into seeds. The expensive per-candidate work is therefore done once per edge rather than once per triplet, and the chain length itself becomes a quality signal.
The workflow has four stages, each documented below:
GBTS does not use the ACTS tracking geometry. It works on its own lightweight description: a flat list of GbtsLayer logical layers, each subdivided into eta bins.
Acts::Experimental::GbtsLayerDescription gives a layer its ID, its type (barrel or endcap), its sensor technology and its extent. For a barrel layer refCoord is the radius and the bounds are in \(z\); for an endcap it is the other way round. The ID is the caller's own numbering, and the algorithm never decodes it.
A pixel barrel layer carries one more field, barrelOrder: the position of the layer in the inside-out ordering of the pixel barrel. Every other layer keeps the default -1, so the sign of the field also says whether a layer is a pixel barrel layer. If the caller leaves the field unset, Acts::Experimental::GbtsGeometry sorts the pixel barrel layers by refCoord and fills it in. Set it on every pixel barrel layer or on none of them, because the constructor rejects a partial ordering.
The cuts that were tuned on the pixel barrel read barrelOrder and nothing else. The adaptive \(\tau\) correction of Building the graph asks whether three layers are radially consecutive, and the two innermost-layer cuts of the same section ask how deep a layer sits. GBTS therefore runs on any layer numbering.
Which layer pairs may be joined by an edge is a list of Acts::Experimental::GbtsLayerConnection, each naming a source (outer) and a destination (inner) layer. Acts::Experimental::GbtsGeometry combines the layer descriptions with those connections and precomputes, for every pair of connected layers, which eta bin pairs are geometrically compatible with the allowed \(z_0\) range. The result is a bin group list — one inner bin together with all outer bins it may connect to — which serves as the graph builder's iteration schedule, ordered so that outer bins are processed before the inner bins that depend on them.
The binning it worked out is readable back off the geometry, so a consumer that runs the same algorithm elsewhere does not have to recompute or pre-generate it: Acts::Experimental::GbtsGeometry::layerBinning gives a layer's Acts::Experimental::GbtsLayerBinning, the eta bins it owns in the global numbering, and Acts::Experimental::GbtsGeometry::binGroups the schedule itself. Eta bins are numbered globally and a layer's are contiguous, so the layers tile the numbering in order. This is what the GPU implementation is configured from.
Acts::Experimental::GbtsNodeStorage holds the graph nodes. Space points are fed in one at a time through insert, which takes plain scalars rather than an ACTS container:
As with Acts::CylindricalSpacePointGrid, an experiment can therefore fill the storage straight from its own space point EDM. Overloads exist for callers that already have \(r\) and \(\phi\), and for an Acts::ConstSpacePointProxy together with the columns carrying the layer index, cluster width and local \(y\) position.
Two different layer numbers meet here, and they are separate types:
| Type | What it is |
|---|---|
| GbtsExperimentLayerId | the layer id the experiment assign. Sparse and structured – the layer descriptions and connections are written in terms of it. The algorithm treats it as an opaque key. |
| GbtsLayerIndex | where that layer sits in one Acts::Experimental::GbtsGeometry, dense from zero. It indexes the geometry, and it is what a node carries. |
insert takes the index, because it is on the per-space-point path. Acts::Experimental::GbtsGeometry::layerIndex hands it out. It is the geometry's own numbering and is not derivable from the id.
insert assigns the node to an eta bin via GbtsLayer::getEtaBin and buffers it. finalize then sorts each bin by \(\phi\) and materialises the nodes into a space point container ordered by eta bin and then by \(\phi\), so that every eta bin is one contiguous range of node indices. A node index is therefore all that the rest of the algorithm needs to pass around.
The per-node data the graph builder reads lives in dynamic columns on that same container. It is packed rather than split into one array per field, because the innermost loop reads all of it together:
\(\tau = \cot\theta\). The infinite defaults disable the \(\tau\) cut entirely; only the optional machine-learning lookup table narrows them (see Machine-learning assisted acceptance). Alongside it sits the bookkeeping the graph builder writes:
Each eta bin carries its node range plus the \(\phi\) index used by the sliding window. The \(\phi\) index duplicates entries shifted by \(\pm 2\pi\) near the wrap-around, so the window never has to handle wrapping:
The builder walks the bin groups from Geometry and layer connections. For each inner bin it prepares one sliding window in \(\phi\) per connected outer bin, whose half-width grows with the radial separation of the two bins — the further apart they are, the more a low- \(p_T\) track can bend between them. It then loops over the inner nodes, and for each one scans only the outer nodes inside the window.
A candidate pair \((n_1, n_2)\) becomes an edge if it survives, in order:
| Cut | Meaning |
|---|---|
| \(\Delta r > \) minDeltaRadius | the two hits are radially separated enough for \(\tau\) to be meaningful |
| \(\lvert\tau\rvert < \) maxAbsTau | within the detector's angular acceptance |
| \(\tau\) inside both nodes' windows | per-node acceptance from the ML lookup table |
| \(z_0\) inside [minZ0, maxZ0], and \(z\) at the outer radius inside the ROI | the pair points back to the luminous region |
| \(\lvert\kappa\rvert\) below an \(\eta\)-dependent bound | consistent with the \(p_T\) threshold |
with \(\tau = \Delta z/\Delta r\), \(z_0 = z_1 - r_1\tau\) and the curvature proxy \(\kappa = (\phi_2-\phi_1)/\Delta r\).
Surviving pairs are appended to a flat edge array:
The three fit parameters p are \(\{\exp(-\eta),\ \kappa,\ \phi_1 + \kappa r_1\}\).
Because the inner node's edges are written contiguously, the edges incoming to a node form a contiguous range, recorded in that node's GbtsNodeEdgeInfo. Immediately after creating an edge \((n_1, n_2)\), the builder scans the edges incoming to \(n_2\) — that is, edges \((n_2, n_3)\) — and links the two whenever the implied triplet is consistent: the \(\tau\) ratio, the \(\phi\) continuation and the curvature difference must all agree within tolerance. For pixel-barrel triplets an optional validateTriplets step also fits a circle through the three points and cuts on \(d_0\) and \(p_T\). Each edge stores up to kGbtsMaxEdgeNeighbours (6) such neighbours.
Two further cuts apply on the innermost pixel barrel layers, where the combinatorics are worst. Each cut has its own depth limit on the barrelOrder of the inner layer, and a negative limit switches the cut off:
With the edge graph built, a cellular automaton assigns each edge a level: the length of the longest chain of linked edges ending at it. All edges start at level 1; in each iteration an edge whose level equals that of one of its neighbours proposes an increment, and the proposals are committed at the end of the iteration. The sweep repeats until nothing changes, or for at most 15 iterations.
The level is the chain-length signal that drives extraction: an edge at level \(L\) is the head of a chain spanning \(L+1\) space points.
Edges whose level clears the minimum chain length become chain heads, sorted by level so the longest chains are collected first. Each head is then followed back through the graph by Acts::Experimental::GbtsTrackingFilter.
The filter is a small Kalman filter over the chain. It carries a state of two independent parts — a quadratic in the bending plane and a linear \(z\) versus \(r\) model — and at each step extrapolates to the next node, forms a \(\chi^2\) residual for each part and rejects the branch if either exceeds its threshold (maxDChi2X, maxDChi2Y).
Every accepted hit adds a fixed reward addHit to the branch score, minus its two \(\chi^2\) increments weighted by weightX and weightY. The score therefore counts the hits on the chain, discounted by how badly they fit the circle and the \(z\) versus \(r\) line. Where an edge has several neighbours the filter branches, recursing into each; the branch with the best accumulated score wins.
The result is a set of seed candidates. These are reduced in two passes:
The surviving candidates are written to the output Acts::SeedContainer, with node indices translated back to the caller's own space point indices.
When useClusterWidthCuts is enabled, GBTS narrows the per-node \(\tau\) window using a pre-trained lookup table indexed by pixel cluster width. The cluster a track leaves in a pixel module grows with the incidence angle, so the width alone constrains \(\cot\theta\) before any pairing is attempted.
The table carries two sets of bounds per width bin: one for clusters comfortably inside the module, and one for clusters within moduleEdgeTolerance of the module edge, where the cluster may be truncated and the width therefore underestimates the angle. Wide clusters in the pixel endcap are dropped entirely (maxEndcapClusterWidth).
The main knobs on GraphBasedTrackSeeder::Config:
| Option | Stage | Effect |
|---|---|---|
| useStripConnections | Geometry and layer connections | take the strip layer connections from the connector file instead of the pixel ones |
| minPt | Building the graph | drives the curvature and \(\phi\)-window bounds |
| nMaxPhiSlice | Building the graph | sets the base \(\phi\) sliding-window width |
| minDeltaRadius, maxAbsTau | Building the graph | doublet acceptance |
| minZ0, maxZ0, doubletFilterRZ | Building the graph | luminous-region cuts on the doublet |
| tauRatioCut, cutDPhiMax, cutDCurvMax | Building the graph | edge-to-edge linking tolerances |
| useAdaptiveCuts, tauRatioCorr | Building the graph | widen the \(\tau\) tolerance when a layer is skipped |
| validateTriplets, d0Max | Building the graph | circle fit on pixel-barrel triplets |
| nMaxEdges | Building the graph | hard cap on the edge array (2M by default); exceeding it costs efficiency |
| matchBeforeCreate, tauRatioPrecut, matchBeforeCreateMaxBarrelOrder | Building the graph | require a compatible incoming edge before creating one, down to that depth in the pixel barrel |
| z0HistogramMaxBarrelOrder, z0Resolution | Building the graph | \(z_0\) histogram cut, down to that depth in the pixel barrel |
| hitShareThreshold | Seed extraction | fraction of shared hits above which a candidate is a clone |
| maxSeedSplitEta, maxInvRadDiff | Seed extraction | seed splitting |
| addTriplets, maxAbsEtaAddTriplets | Seed extraction | allow shorter chains within an \(\eta\) range |
| useClusterWidthCuts, tauLookupTable | Machine-learning assisted acceptance | cluster-width based \(\tau\) windows |
| maxEndcapClusterWidth, moduleHalfLengthY, moduleEdgeTolerance | Machine-learning assisted acceptance | cluster-width acceptance and module-edge handling |
GbtsTrackingFilter::Config separately controls the chain-following filter of seed extraction:
| Option | Effect |
|---|---|
| sigmaX, sigmaY | measurement resolution in the bending plane and along \(z\) |
| maxDChi2X, maxDChi2Y | per-step \(\chi^2\) ceilings; a branch exceeding either is dropped |
| addHit, weightX, weightY | the reward and the two \(\chi^2\) weights in the branch score |
| sigmaMS, radLen | multiple-scattering inflation added before each extrapolation |
| maxCurvature, maxZ0 | track-level bounds checked after each update |
A GPU implementation of the same algorithm, using an equivalent struct-of-arrays layout, lives in the traccc plugin under Traccc/device/common/include/traccc/gbts_seeding.
1.15.0