Dept Banner
Dept Banner

Calendar - Weekly View

Download as iCal file

DIMACS Theory of Computing Seminar

Practical Data-Dependent Metric Compression with Provable Guarantees

Ilya Razenshteyn, Columbia University

Location:  CoRe 301
Date & time: Wednesday, 11 October 2017 at 11:00AM - 12:00PM

Abstract:  How well can one compress a dataset of points from a high-dimensional space while preserving pairwise distances? Indyk and Wagner have recently obtained almost optimal bounds for this problem, but their construction (based on hierarchical clustering) is not practical. In this talk, I will show a new practical, quadtree-based compression scheme, whose provable performance essentially matches that of the result of Indyk and Wagner.

 In additional to the theoretical results, we will see experimental comparison of the new scheme and Product Quantization (PQ)--one of the most popular heuristics for distance-preserving compression--on several datasets. Unlike PQ and other heuristics that rely on the clusterability of the dataset, the new algorithm ends up being more robust.

 The talk is based on a joint work with Piotr Indyk and Tal Wagner.

Contact Us

HillCenter small

Department of Mathematics

Department of Mathematics
Rutgers University
Hill Center - Busch Campus
110 Frelinghuysen Road
Piscataway, NJ 08854-8019, USA

Phone: +1.848.445.2390
Fax: +1.732.445.5530