Efficient Algorithms for the Identification of Potential Track/Observation Associations in Continuous Time Data

Abstract

In this paper we examine the problem of spatial data association - identifying which track/observations pairs could feasibly be associated. Efficiently and accurately finding these potential associations is vital for most tracking applications, because these associations both identify which target caused a given observation and update the estimate of a target's position and trajectory. However, previous work on efficiently answering this query often makes the limiting assumption that observations arrive in batches at discrete time steps. In many real world applications this may not be the case. Observations may arrive individually or in small batches distributed over a range of time. In this paper we focus on the question of efficiently identifying potential track/observations pairs in data where the observations can occupy a range of times. We examine the new data structures and algorithms for efficient spatial data association on this type of data. We show that it is possible to adapt algorithms designed for discrete time data, providing the benefits of continuous time while retaining the tractability of discrete approaches. We introduce a novel data structure for dealing with large sets of tracks these queries. Empirically we show that these data structures provide a significant benefit both in decreased computational cost and increased accuracy when contrasted with treating the observations as arriving at a single time. Further, we show that in some cases it is more efficient to treat observations that do arrive at discrete time steps as if it were continuous time data and apply our techniques.