Open Collections

Description

Geometric data sets that arise in modern applications are very large and change dynamically over time. A popular framework for modeling such data sets is the evolving data framework, where a discrete structure continuously varies over time due to the unseen actions of an "evolver", which makes small changes to the data. An algorithm probes the current state through an oracle, and the objective is to maintain a hypothesis of the data set's current state that is close to its actual state at all times. In this talk, we discuss how to apply the evolving framework to maintaining a set of n point objects moving in d-dimensional space. We introduce a scale-invariant motion model, called the "local model", in which in each time step, any object can move up to a fraction of its nearest-neighbor distance. Uncertainty in the object locations, both the ground truth and hypothesis, is modeled using spatial probability distributions. The distance between them is measured by the Kullback-Leibler divergence. We present a simple algorithm that, in steady state, maintains a distance between the truth and hypothesis that is within a constant factor of the optimum.