Event Bookkeeping for CLEO-3

Jon J Thaler

Physics Department, University of Illinois at Urbana-Champaign, 1110 W.
Green St., Urbana, IL 61801

**Abstract.** Most aspects of data analysis software share a common
bookkeeping task, maintaining relationships between members of two sets
of objects. To simplify the development and maintenance of this
bookkeeping, CLEO has implemented a sharable package that implements all
of the commonly used tools. This allows the physicists to concentrate on
data analysis.

# MOTIVATION {#motivation .INTRODUCTION}

Most aspects of data analysis software share a common bookkeeping task,
maintaining relationships between members of two sets of objects. For
example, the tracks created by pattern recognition algorithms must be
correlated with the detector hits that contribute to them. Conversely,
it is important to be able to determine which tracks contain a given
hit. Similar bi-directional correlations must be established and
maintained in vertex reconstruction and for event kinematics. Data
analysis is the identification of increasingly complex relationships
within the data.

It would simplify the software environment if these relationships were
managed by a single sharable package. The package would only have to be
written and debugged once, and code writers would be freed to
concentrate on the algorithms. To this end, the CLEO collaboration has
written software, called Lattice, which is designed to perform the
bookkeeping tasks described here. Lattice is written in C++, so this
paper uses C++ terminology.

# Specifications

Lattice is designed to be flexible and to have minimal impact on
existing code. This makes it more likely that Lattice will be used.
Lattice\'s internal data storage scheme is transparent to the user.

## Functionality

The user can add and remove links between objects (*e.g.*, hits and
tracks). Data (the Link data in figure 1) can be associated with each
link (*e.g.*, hit contributions to track χ^2^). The user can retrieve a
list of all objects to which a given one is linked (*e.g.*, all hits on
a given track), or all the objects which share links with a given one
(*e.g.*, all tracks which share hits with a given track). The interface
is simple, and all data is returned in STL vectors. Constraints can be
specified that prevent unwanted multiple links between objects.

## Flexibility

Any two sets of data can be linked. Link data is user definable.
Lattices don't interact, so objects can belong to multiple Lattices. A
Lattice can persist over a write/read data cycle, because it does not
use memory pointers. The Lattice can be used even after the data it
links has disappeared (*e.g.*, if hits are not saved after track
reconstruction).

## Minimal Impact

The use of Lattice incurs only a small performance penalty. Lattice is
optimized for fast data retrieval, while making and deleting links is
more expensive. Our experience is that this matches users' needs.

Lattice requires little rewriting of existing code. The only behavioral
requirement is that data objects have identifiers, used by Lattice to
distinguish objects. CLEO data objects already have this property.

Figure 1 shows the general structure. Nodes are invisible to the user.
They maintain the correspondence between user data and the Lattice.

# Examples

It is simplest to explain the Lattice, especially the value of
connectivity constraints, with some examples.

**Track Finding**. Hit sharing not allowed.\
The left data is the tracks; the right is the hits. Eight hits lie on
three tracks. Link data is the hit contribution to χ^2^. Disallowing
multiple links on the right (see figure 2) imposes no hit sharing.

**Track Finding**. Hit sharing allowed.\
Without the connectivity constraint, tracks can share hits, as shown in
figure 3. Resolution of shared hit ambiguities can be deferred until
later in the analysis.

**Calorimeter Clustering**. No overlaps.\
Here, the left data is the clusters. Figure 4 shows the situation,
supposing that clusters have cores and halos.

**Calorimeter Clustering**. Overlaps allowed.\
By relaxing one connectivity constraint, clusters can share halos and
cores, as shown in figure 5. This simple model does not distinguish
halos and cores. To disallow core sharing while allowing halo sharing
would require two Lattices, because a Lattice connects two kinds of
objects, not three.

**Figure 1.** Structure of Lattice. User Data is the data to be linked.
Link Data is the data associated with a link. It is a user-defined
class. Identifiers do not need to be int. They do need to be sortable
and unique (within a set).

**FIGURE 2.** Track finding with no hit sharing. "Many" means multiple
connections are allowed. "One" means single connections only.

**FIGURE 3.** Track finding with hit sharing. One track steals hits from
the others

**FIGURE 4.** Cluster finding with no overlaps. The link data describing
cores and halos must both fit into the same user defined class.

**FIGURE 5.** Cluster finding with overlaps. Two clusters share a halo.

**FIGURE 6.** Find objects on the right that are linked to the given one
on the left..

**FIGURE 7.** Find objects on the left that share links with the given
one on the left.

# Interface

Due to space constraints, I only show some representative interface
operations. A complete set is implemented.

**Make a new Lattice:**

pLattice = new\
Lattice\<LeftData,RightData,LinkData\>\
(Connectivity)

Lattice is a class template. You specify the left, right, and link data
types, and the allowed connectivity. There are 16 possible connectivity
combinations, "one" or "many" at each of the four positions (see,
*e.g.*, figure 2).

**Make a new link:**

pLink = pLattice-\>connect\
(LeftID, RightID, LinkData&);

Returns a pointer to the new link. Zero is returned on failure (*e.g.*,
violation of the connectivity constraint). The link data is copied into
the link. Lattice does not take ownership of the user's data.

**Remove an object from a link:**

pLink = remove(LeftID, Link\*);

A null pointer is returned on failure (*e.g.*, the object was not a
member of the link).

**Find objects that are linked to a given one:**

vRight = pLattice-\>\
vRightGivenLeft(LeftID);

vRight is an STL vector of RightIDs.. This will tell you, for example,
which hits lie on a given track. See figure 6. The verbose nomenclature
is a consequence of the fact that LeftIDs and RightIDs might be the same
type.

**Find objects that share links with a given one:**

vLeft = pLattice-\>\
vLeftGivenLeft(LeftID);

This will tell you, for example, which tracks share hits with a given
one. See figure 7.

**Return a reference to a link's data:**

linkData = pLink-\>linkData();

You have write access to the link data. This allows you to update it
when objects are added or removed.

# Status

Lattice has been an integral part of the CLEO-3 software environment for
two years. It is stable code. Lattice is being considered for use by two
other experiments. It is not quite plug-and-play, but close.

Complete documentation is available on the web at\
<http://web.hep.uiuc.edu/home/jjt/Lattice> . The source code is
available (email: <jjt@uiuc.edu)>. I will be happy to help other
experiments implement Lattice.

# Acknowledgments

This work was partially supported by the US Department of Energy under
grant DE-FG02-91ER40677.