Compressing a Dataset via Linear Conditional Probability Densities on Voronoi Regions

Abstract In this paper we consider the compression of a large dataset in order to efficiently broadcast to other coalition members. The compression works by first partitioning the space, via a Voronoi diagram, into Voronoi regions. For each region we then consider the set of probability densities that satisfies: 1) Outside the region the probability density is zero. 2) Inside the region the probability density is a linear function. We give an algorithm that finds the probability density, from this set, that maximises the likelihood of the points of the dataset that lie in the region. Our compression then consists of the following objects: 1) The Voronoi centre of each region. The centres enable the reconstruction of the regions. 2) For each region, the gradient of the probability density found for that region. The gradient enables the reconstruction of the probability density. 3) The number of points, from the original dataset, that lie in each region. We give experimental results that demonstrate the efficiency of our compression.
Authors
  • Stephen Pasteris (UCL)
  • Mark Herbster (UCL)
  • Richard Tomsett (IBM UK)
  • Dinesh Verma (IBM US)
Date Sep-2020
Venue 4th Annual Fall Meeting of the DAIS ITA, 2020