研究排列相似度的局部敏感哈希扭曲度，发现两种常用相似度的效率差异。
On the LSH Distortion of Ulam and Cayley Similarities
- 分析排列相似度的局部敏感哈希设计可行性
- 乌兰相似度扭曲度为O(n/√log n)，凯莱相似度为Θ(n)
- 揭示不同相似度在近似搜索中的理论效率差距
局部敏感哈希（LSH）是加速最近邻搜索的核心技术。一个针对相似度函数S: X × X → [0,1] 的LSH方案，是指定义在X上的哈希函数分布，使得任意两点x,y∈X的碰撞概率恰好等于S(x,y)。然而，并非所有相似度函数都存在精确的LSH方案。LSH扭曲度衡量相似度函数与可实现精确LSH方案之间的乘法接近程度。本文研究了排列上两种常用相似度——乌兰相似度和凯莱相似度的LSH扭曲度。我们证明乌兰相似度具有次线性扭曲度O(n / √log n)，并给出Ω(n^0.12)的下界；而凯莱相似度的扭曲度为Θ(n)。结果表明两者在高效近似搜索方面存在显著理论差异。
原文摘要 · Abstract (English)
Locality-sensitive hashing (LSH) has found widespread use as a fundamental primitive, particularly to accelerate nearest neighbor search. An LSH scheme for a similarity function $S:\mathcal{X} \times \mathcal{X} \to [0,1]$ is a distribution over hash functions on $\mathcal{X}$ with the property that the probability of collision of any two elements $x,y\in \mathcal{X}$ is exactly equal to $S(x,y)$. However, not all similarity functions admit exact LSH schemes. The notion of LSH distortion measures how multiplicatively close a similarity function is to having an LSH scheme. In this work, we study the LSH distortion of the Ulam and Cayley similarities, which are popular similarity measures on permutations of $n$ elements. We show that the Ulam similarity admits a sublinear LSH distortion of $O(n / \sqrt{\log n})$; we also prove a lower bound of $Ω(n^{0.12})$ on the best LSH distortion achievable. On the other hand, we show that the LSH distortion of the Cayley similarity is $Θ(n)$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。