PolyMinHash: Efficient Area-Based MinHashing of Polygons for Approximate Nearest Neighbor Search

• URL: http://arxiv.org/abs/2511.16576v1
• Date: Thu, 20 Nov 2025 17:31:14 GMT
• Title: PolyMinHash: Efficient Area-Based MinHashing of Polygons for Approximate Nearest Neighbor Search
• Abstract summary: PolyMinHash is a system for approximate polygon similarity search that adapts MinHash into a novel 2D polygon-hashing scheme.<n> Minhash is generated by counting the number of randomly sampled points needed before the sampled point lands within the polygon's interior area.<n>Our hashing mechanism reduces the number of candidates to be processed in the query refinement phase by up to 98% compared to the number of candidates processed by the brute-force algorithm.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Similarity searches are a critical task in data mining. As data sets grow larger, exact nearest neighbor searches quickly become unfeasible, leading to the adoption of approximate nearest neighbor (ANN) searches. ANN has been studied for text data, images, and trajectories. However, there has been little effort to develop ANN systems for polygons in spatial database systems and geographic information systems. We present PolyMinHash, a system for approximate polygon similarity search that adapts MinHashing into a novel 2D polygon-hashing scheme to generate short, similarity-preserving signatures of input polygons. Minhash is generated by counting the number of randomly sampled points needed before the sampled point lands within the polygon's interior area, yielding hash values that preserve area-based Jaccard similarity. We present the tradeoff between search accuracy and runtime of our PolyMinHash system. Our hashing mechanism reduces the number of candidates to be processed in the query refinement phase by up to 98% compared to the number of candidates processed by the brute-force algorithm.

Related papers

• PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search [7.466687780705626]
  This paper studies density-based clustering of point sets.<n>It unifies the different variants of density peaks clustering into a single framework, PECANN.<n>We implement five clustering algorithms with PECANN and evaluate them on synthetic and real-world datasets with up to 1.28 million points and up to 1024 dimensions on a 30-core machine with two-way hyper-threading.
  arXiv  Detail & Related papers  (2023-12-06T22:43:50Z)
• Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Sampling [37.6593006747285]
  Minwise hashing (MinHash) is a standard algorithm widely used in the industry for large-scale search and learning applications. One permutation hashing (OPH) is an efficient alternative of MinHash which splits the data vectors into $K$ bins and generates hash values within each bin. We propose DP-OPH framework with three variants: DP-OPH-fix, DP-OPH-re and DP-OPH-rand, depending on which densification strategy is adopted to deal with empty bins in OPH.
  arXiv  Detail & Related papers  (2023-06-13T10:38:12Z)
• Unified Functional Hashing in Automatic Machine Learning [58.77232199682271]
  We show that large efficiency gains can be obtained by employing a fast unified functional hash. Our hash is "functional" in that it identifies equivalent candidates even if they were represented or coded differently. We show dramatic improvements on multiple AutoML domains, including neural architecture search and algorithm discovery.
  arXiv  Detail & Related papers  (2023-02-10T18:50:37Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• SLOSH: Set LOcality Sensitive Hashing via Sliced-Wasserstein Embeddings [18.916058638077274]
  This paper focuses on non-parametric and data-independent learning from set-structured data using approximate nearest neighbor (ANN) solutions. We propose Sliced-Wasserstein set embedding as a computationally efficient "set-2-vector" mechanism that enables downstream ANN. We demonstrate the effectiveness of our algorithm, denoted as Set-LOcality Sensitive Hashing (SLOSH), on various set retrieval datasets.
  arXiv  Detail & Related papers  (2021-12-11T00:10:05Z)
• Graph Sampling Based Deep Metric Learning for Generalizable Person Re-Identification [114.56752624945142]
  We argue that the most popular random sampling method, the well-known PK sampler, is not informative and efficient for deep metric learning. We propose an efficient mini batch sampling method called Graph Sampling (GS) for large-scale metric learning.
  arXiv  Detail & Related papers  (2021-04-04T06:44:15Z)
• Unsupervised Multi-Index Semantic Hashing [23.169142004594434]
  We propose an unsupervised hashing model that learns hash codes that are both effective and highly efficient by being optimized for multi-index hashing. We experimentally compare MISH to state-of-the-art semantic hashing baselines in the task of document similarity search. We find that even though multi-index hashing also improves the efficiency of the baselines compared to a linear scan, they are still upwards of 33% slower than MISH.
  arXiv  Detail & Related papers  (2021-03-26T13:33:48Z)
• Distributed Tera-Scale Similarity Search with MPI: Provably Efficient Similarity Search over billions without a Single Distance Computation [40.75034970144169]
  SLASH is a distributed system for approximate similarity search over terabyte scale datasets. We show how SLASH can index this 2.3 terabyte data over 20 nodes in under an hour, with query times in a fraction of milliseconds.
  arXiv  Detail & Related papers  (2020-08-05T18:15:36Z)
• Reinforcing Short-Length Hashing [61.75883795807109]
  Existing methods have poor performance in retrieval using an extremely short-length hash code. In this study, we propose a novel reinforcing short-length hashing (RSLH) In this proposed RSLH, mutual reconstruction between the hash representation and semantic labels is performed to preserve the semantic information. Experiments on three large-scale image benchmarks demonstrate the superior performance of RSLH under various short-length hashing scenarios.
  arXiv  Detail & Related papers  (2020-04-24T02:23:52Z)
• LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew [58.21885402826496]
  All-pairs set similarity is a widely used data mining task, even for large and high-dimensional datasets. We present a new distributed algorithm, LSF-Join, for approximate all-pairs set similarity. We show that LSF-Join efficiently finds most close pairs, even for small similarity thresholds and for skewed input sets.
  arXiv  Detail & Related papers  (2020-03-06T00:06:20Z)
• A Survey on Deep Hashing Methods [52.326472103233854]
  Nearest neighbor search aims to obtain the samples in the database with the smallest distances from them to the queries. With the development of deep learning, deep hashing methods show more advantages than traditional methods. Deep supervised hashing is categorized into pairwise methods, ranking-based methods, pointwise methods and quantization. Deep unsupervised hashing is categorized into similarity reconstruction-based methods, pseudo-label-based methods and prediction-free self-supervised learning-based methods.
  arXiv  Detail & Related papers  (2020-03-04T08:25:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.