Last modified 9 years ago Last modified on 08/17/2010 01:39:17 PM

FindTracklets is an algorithm designed by Jeremy Kubica as part of his PhD thesis. The idea is to generate all plausible linkages between detections which could be attributed to moving objects; this linking is usually done over a short period of time (15-90 minutes or so) and generates short, linear approximations of the sky-plane motion of moving objects; since these linkages are short and simple they are called "tracklets."

"Tracklets" exist to be linked into tracks; they are a helpful tool since they give an approximate velocity at a given time, and the sky-plane motion of solar system objects is generally linear in (RA, Dec) space in a single night but quadratic in (RA, Dec) space over the course of a month.

FindTracklets will return all tracklets within certain user-specified limitations. The (most interesting) limitations which can be specified are:

  • Min and max time between endpoints of the tracklet
  • Min and max sky-plane velocity of the tracklet (sky-plane distance between the endpoint detections / time between the endpoint detections)

To find the tracklets, FindTracklets is implemented as a series of range searches. These ranges are performed with KD-Trees.

One range search is illustrated below. In an attempt to find all endpoints from field visit 2 which are compatible with a given detection d in visit 1, the location of d is used as the center of a circular range search with radius dt*maxV (time between visit 1 and visit 2 times the user-specified maximum tracklet velocity).

Illustration of a single query within findTracklets

In this case, one tracklet will be created from the query detection d to each of the black detections in field visit 2.

A range search centered on d will be performed for each field revisit which is between the user-specified min and max time between endpoints.

The following illustrates the dangers of using too high a max time between endpoints and/or too high a max velocity setting. Note that the area of the range search grows quadratically with respect to dt*maxV; if our detections are distributed randomly throughout the visits, then we should expect a quadratic growth in the number of tracklets as a result.

Illustration of a single query within findTracklets with a large area

Also note that the density of observations will affect the number of tracklets generated by FindTracklets. The following shows the original example query, with more dense detections:

Illsutration of a single query within findTracklets with dense data

Since the number of queries scales upward linearly with the number of detections, and the number of tracklets generated by each query is determined by the density of detections within the range search area, increasing density of detections causes a quadratic increase in the number of output tracklets.

This chart from MopsRunlog demonstrates the quadratic increase of tracklets as a function of input number of detections(DiaSources?), which does not mimic the effect of increasing density (instead the increase in number of diasources here reflects the increase of area input into the simulation). Similarly, at each data point on the x-axis it demonstrates the (quadratic??) scaling of the number of output tracklets given max velocity limits of .5 deg/day, 1.0 deg/day and 2.0 deg/day. Missing data points are due to the FindTracklets process filling memory with output tracklets and being killed by the OS.