Vladimir Braverman
Some Applications of Sublinearity

Abstract: In this talk we will demonstrate their applicability of
sublinear algorithms in cosmological N-body simulations, network
monitoring for Software Defined Networks (SDN) and other areas. For
SDN, we will present the UnivMon (short for Universal Monitoring)
framework that can simultaneously achieve both generality and high
fidelity across a broad spectrum of monitoring tasks. UnivMon builds on
and extends recent theoretical advances in universal sketching and we
will describe the connection of universal sketches to the
concentration of measure and Milman's theorem. For cosmological
simulations, we will describe efficient algorithms for the
identification of "halos," which are concentrations of mass in the
output of the simulations. Traditional in-memory methods for these
tasks do not scale to the datasets that are forbiddingly large in
modern simulations. Our experiments show that our tool can scale to
datasets with up to 1012 particles, while using less than an hour of
running time on a single Nvidia GTX GPU. Our methods are based on
streaming algorithms for Heavy Hitters, or most popular items in a
stream and we will discuss our recent and nearly optimal algorithms
for L2 heavy hitters in insertion only streams.