用点采样生成多边形短签名，快速近似匹配相似多边形。
PolyMinHash: Efficient Area-Based MinHashing of Polygons for Approximate Nearest Neighbor Search
- 通过随机采点直到落入多边形内部，生成面积保真的哈希值。
- 查询时候选数减少98%，相比暴力搜索提升效率。
- 适合大规模地理信息、空间数据库中的多边形相似性检索。
相似性搜索在数据挖掘中至关重要。随着数据集增大，精确最近邻搜索变得不可行，促使近似最近邻（ANN）搜索的采用。虽然文本、图像和轨迹已有大量研究，但针对空间数据库与地理信息系统中的多边形，尚未有系统性进展。本文提出 PolyMinHash，一种将 MinHash 扩展至二维多边形的新方法，通过统计随机采样点首次落入多边形内部所需的次数，生成短而保留面积-杰卡德相似度的哈希签名。该方法在搜索精度与运行时间间实现权衡。实验表明，相比暴力算法，其可将查询精炼阶段需处理的候选数量减少高达98%。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。