Last modified 9 years ago Last modified on 04/06/2010 01:39:27 PM

FindTracklets, LinkTracklets assisted by Databases

With large input data sets, it is possible that findTracklets will generate too many tracklets to fit in memory. This can be a problem both for findTracklets and for linkTracklets, which must use these tracklets as input. Also, linkTracklets may generate too many tracks to fit in memory, which can be a problem of its own.

In order to account for this, we plan to develop database-backed versions of these two algorithms, which will be used for DC3b. They will use a local "scratch" database to store and retrieve data items which do not fit in memory.


We will assume the following: All DiaSources? from a given night will fit in memory. All tracklets "rooted at" (i.e., with their first detection in) a given image will fit in memory. Since we can make leaf nodes arbitrarily large and thus make our trees arbitrarily small, we also assume that we can fit as many trees as necessary into memory.


Psuedocode for the implementations of our algorithms follow. Points of DB interaction are encased in (((triple-parens))).


FindTracklets works on DiaSources? from a night; these will fit into memory. The output set of tracklets from an entire night may not fit into memory. Hence, we use the database for writing tracklets on a per-image basis.

   sortedDiaSources = nightlyDiaSources sorted by image time
   trees = []
   for image in sortedDiaSources:
      kdt = build KD-Tree on sortedDiaSources
      trees[image] = kdt
   for image in trees:
      results = []
      for image2 in trees, with image2 later than image:
         results += find tracklets between image and image2 using range searches on trees
      (((write results to tracklets table)))

Note that the tracklets table will now have data inserted in order of image time, ascending.


   for each image time t between today and today - (linkTracklets time window):
      tracklets = fetch tracklets "rooted at" image time t
      kdt = build KD-Tree on tracklets
      (((write kdt,t to trackletTree table)))
      (((clear cache of KDTrees from memory)))
   for every pair kdt1, kdt2 of tracklet trees:
      (((fetch kdt1 from trackletTree table)))
      (((fetch kdt2 from trackletTree table)))
      supportTrees = (((fetch all trees with times between kdt1 and kdt2)))
   findTracks(kdt1, supportTrees, kdt2)  

The findTracks function will be as presented on the LinkTracklets page. It operates only on the trees.

When recursion hits the terminal point, the following function is called on a pair of compatible leaf nodes, with a set of compatible support nodes:

findTracksBruteForce(startLeafNode, supportTrees, endLeafNode):
   results = {}
   (((fetch DiaSources owned by all tracklets in startLeafNode and endLeafNode)))
   for startTracklet in startLeafNode:
      for endTracklet in endLeafNode:         
         newTrack := [startTracklet.DiaSources + endTracklet.DiaSources]
         if newTrack has a well-fitting line:
           (((fetch all DiaSources owned by all tracklets in supportTrees, if not fetched already)))
           for each support DiaSources sup owned by supportTrees:
              if sup lies along newTrack and is a better fit than the best 
               point at sup.time:
                  newTrack := newTrack + [sup]
         if newTrack has enough support:
           results += newTrack
    (((write results to Track table)))