2026-07-20T05:32:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8231 2024-03-06T10:41:51Z ddc:004 open_access

Range-Efficient Consistent Sampling and Locality-Sensitive Hashing for Polygons Gudmundsson, Joachim Pagh, Rasmus Locality-sensitive hashing probability distribution polygon min-wise hashing consistent sampling 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joachim Gudmundsson and Rasmus Pagh 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.42 urn:nbn:de:0030-drops-82316 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.42 eng https://creativecommons.org/licenses/by/3.0/legalcode