• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Similarity Search and Applications >Fast Locality-Sensitive Hashing Frameworks for Approximate Near Neighbor Search
【24h】

Fast Locality-Sensitive Hashing Frameworks for Approximate Near Neighbor Search

机译：适用于近似近邻搜索的快速局部敏感哈希框架

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The Indyk-Motwani Locality-Sensitive Hashing (LSH) framework (STOC 1998) is a general technique for constructing a data structure to answer approximate near neighbor queries by using a distribution H over locality-sensitive hash functions that partition space. For a collection of n points, after preprocessing, the query time is dominated by O(n~ρ log n) evaluations of hash functions from H and O(n~ρ) hash table lookups and distance computations where p ∈ (0, 1) is determined by the locality-sensitivity properties of H. It follows from a recent result by Dahlgaard et al. (FOCS 2017) that the number of locality-sensitive hash functions can be reduced to O(log2 n), leaving the query timeto be dominated by O(n~p) distance computations and O(n~ρ log n) additional word-RAM operations. We state this result as a general framework and provide a simpler analysis showing that the number of lookups and distance computations closely match the Indyk-Motwani framework. Using ideas from another locality-sensitive hashing framework by Andoni and Indyk (SODA 2006) we are able to reduce the number of additional word-RAM operations to O(n~ρ).
机译：Indyk-Motwani局部敏感哈希（LSH）框架（STOC 1998）是一种通用技术，可通过在分区空间的局部敏感哈希函数上使用分布H来构造数据结构，以回答近似的近邻查询。对于n个点的集合，在预处理之后，查询时间主要由H（）和O（n〜ρ）哈希表查找以及距离计算（其中p∈（0，1）的哈希函数的O（n〜ρlog n）评估决定）是由H的位置敏感性特性决定的。它是根据Dahlgaard等人的最新结果得出的。 （FOCS 2017），可以将对位置敏感的哈希函数的数量减少到O（log2 n），而查询时间则由O（n〜p）距离计算和O（n〜ρlog n）额外的单词控制- RAM操作。我们将此结果陈述为一般框架，并提供了更简单的分析，表明查找次数和距离计算非常接近Indyk-Motwani框架。使用Andoni和Indyk（SODA 2006）提出的另一种对局部性敏感的哈希框架的思想，我们能够将额外的word-RAM运算数量减少为O（n〜ρ）。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号