Efficient on-line data summarization using extremum summaries

We are interested in the task of online summarization of the data observed by a mobile robot, with the goal that these summaries could be then be used for applications such as surveillance, identifying samples to be collected by a planetary rover, and site inspections to detect anomalies. In this paper, we pose the summarization problem as an instance of the well known k-center problem, where the goal is to identify k observations so that the maximum distance of any observation from a summary sample is minimized. We focus on the online version of the summarization problem, which requires that the decision to add an incoming observation to the summary be made instantaneously. Moreover, we add the constraint that only a finite number of observed samples can be saved at any time, which allows for applications where the selection of a sample is linked to a physical action such as rock sample collection by a planetary rover. We show that the proposed online algorithm has performance comparable to the offline algorithm when used with real world data.