Harvard Computer Science Technical Reports for 2013

TR-01-13 [tr-01-13.pdf (219K)]
Ruonan Li, Parker Porfilio, Todd Zickler. 2013. ``Finding Group Interactions in Social Clutter''
We consider the problem of finding distinctive social interactions involving groups of agents embed- ded in larger social gatherings. Given a pre-defined gallery of short exemplar interaction videos, and a long input video of a large gathering (with approximately-tracked agents), we identify within the gather- ing small sub-groups of agents exhibiting social interactions that resemble those in the exemplars. The participants of each detected group interaction are localized in space; the extent of their interaction is localized in time; and when the gallery of exemplars is annotated with group-interaction categories, each detected interaction is classified into one of the pre-defined categories. Our approach represents group behaviors by dichotomous collections of descriptors for (a) individual actions, and (b) pair-wise inter- actions; and it includes efficient algorithms for optimally distinguishing participants from by-standers in every temporal unit and for temporally localizing the extent of the group interaction. Most importantly, the method is generic and can be applied whenever numerous interacting agents can be approximately tracked over time. We evaluate the approach using three different video collections, two that involve humans and one that involves mice.
TR-02-13 [tr-02-13.pdf (644K)]
Nicolas Bonneel, Hanspeter Pfister. 2013. ``Sliced Wasserstein Barycenter of Multiple Densities''
The optimal mass transportation problem provides a framework for interpolating between different probability density functions (pdfs), warping one function toward another. Interpolating between two arbitrary pdfs can be challenging, but interpolating between more than two pdfs just remains untractable. We propose an approximation of such interpolations based on 1D projections, that is efficiently solved via Radon transforms. We observe the expected translational behavior of this interpolation on smooth 2D functions, and prove that it corresponds to the exact interpolant in a few particular cases.
TR-03-13 [tr-03-13.pdf (644K)]
Peter Macko, Daniel Margo, Margo Seltzer. 2013. "Local Clustering in Provenance Graphs (Extended Version)"
Systems that capture and store data provenance, the record of how an object has arrived at its current state, accumulate historical metadata over time, forming a large graph. Local clustering in these graphs, in which we start with a seed vertex and grow a cluster around it, is of paramount importance because it supports critical provenance applications such as identifying semantically meaningful tasks in an object's history and selecting appropriate truncation points for returning an object's ancestry or lineage. Generic graph clustering algorithms are not effective at producing semantically meaningful clusters in provenance graphs. We identify three key properties of provenance graphs and exploit them to justify two new centrality metrics we developed, specifically for use in performing local clustering on provenance graphs.