Title: Range-efficient consistent sampling and locality-sensitive hashing for polygons,
Abstract: Locality-sensitive hashing (LSH) is a fundamental technique for similarity
search and similarity estimation in high-dimensional spaces. The basic idea is
that similar objects should produce hash collisions with probability
significantly larger than objects with low similarity. We consider LSH for
objects that can be represented as point sets in either one or two dimensions.
To make the point sets finite size we consider the subset of points on a grid.
Directly applying LSH (e.g. min-wise hashing) to these point sets would require
time proportional to the number of points. We seek to achieve time that is much
lower than direct approaches.
Technically, we introduce new primitives for range-efficient consistent
sampling (of independent interest), and show how to turn such samples into LSH
values. Another application of our technique is a data structure for quickly
estimating the size of the intersection or union of a set of preprocessed
polygons. Curiously, our consistent sampling method uses transformation to a
geometric problem.