本文主要是介绍近似最近邻搜索的QALSH方法-阅读笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
近似最近邻搜索的QALSH方法
LSH和它的变体是解决高维欧氏空间下c-近似最近邻（c-ANN）搜索问题的著名索引方法。传统上，LSH函数在某种意义上是以未知查询的方式构建，即在任何查询到达之前划分桶。然而，距离一个查询越近的目标可能被划分在不同的桶中是令人不快的。由于利用yi遗忘查询桶划分，针对外存的最先进的LSH方案，即C2LSH和LSB森林，整数近似比率仅为c>=2。
在这篇文章中，我们介绍了一个新颖的概念，即查询感知桶划分，利用一个给定查询作为桶的“锚”。因此，一个查询感知函数是外加查询感知划分的随机投影，移除了传统查询健忘的LSH函数的随机偏移。显著地，查询感知划分很容易被实现，以便保证查询性能。我们提出了一个查询感知方法称为QALSH，来解决外存的c-ANN搜索问题。我们的理论研究表明，QALSH能够保证查询质量。感知哈希函数使得QALSH能够满足近似比率c>1。大量实验表明，QALSH超越了C2LSH和LSB森林，尤其在高维空间。特别是，通过c<2的比率，QALSH能够实现更好的查询效率。
1.介绍
NN搜索问题在欧氏空间有广泛的应用，如图像和视频数据库、信息检索和数据挖掘。在许多应用中，数据对象常常会被表示为欧氏向量。例如，在图像搜索应用中，图像会被自然映射为高维特征向量，其中每个像素表示一个维度。c-ANN中更小的c保证更好的查询质量。
现有的方法如LSH等...The seminal work.
根据上述问题引出query-aware LSH函数，受...的激励，我们提出了..本文主要贡献点包括：...The rest of this paper组织如下：...
(感觉开始先描述清楚文章涉及的问题，最好举个小栗子能形象些；然后简单介绍与本文方法相似的最新前沿的方法；引出本文的方法基点以及介绍，贡献点；最后是文章脉络)。
2.准备工作
- 2.1简洁的问题定义（problem setting）
- 2.2遗忘查询LSH族
3.感知查询LSH族
- 3.1（1,c,p1,p2）敏感LSH族
- 3.2碰撞概率的比较
这里主要比较随着c变化的正碰撞和负碰撞概率，以及他们之间的差异（曲线图）。然后跟随当前效果比较好的C2LSH作为基本框架，来展示感知哈希函数族的desirability。 - 3.3virtual rehashing
underlying idea来源于C2LSH的virtual rehashing,这个R很神奇，是c的指数倍， - 3.4准备桶划分
本质上，一个QALSH的哈希表能被视为二次B+树，使得QALSH能支持更新以及曾倩关系数据库的性能。
4.quey-aware LSH方案
- 4.1（R,c)-NN搜索的QALSH
- 4.2 c-ANN搜索的QALSH
- 4.3 c-k-ANN搜索的QALSH
5.理论分析
- 5.1Working with 任意近似比率
- 5.2近似比率的范围
- 5.3参数设置
- 5.4时间和空间复杂度
6.实验
- 6.1实验配置
6.1.1参照方法
6.1.2数据库和查询
6.1.3评估准则 - 6.2参数设置
- 6.3索引规模和索引时间
- 6.4总体比率
- 6.5I/O开销
- 6.6运行时间
- 6.7性能vs.近似比率
- 6.8 QALSH vs.C2LSH
- 6.9 Summery
7.相关工作
8.总结
在这篇文章中，我们引入一个新颖的概念感知哈希函数，因而提出一个新颖的LSH方案QALSH, for高维欧氏空间的c-ANN搜索。一个感知查询哈希函数是一个外加感知查询桶划分的随机投影。该函数无需随机偏移，那在传统LSH函数中是一个前提。感知查询LSH函数也能使QALSH执行在任意近似比率c>1。作为对照，最先进的LSH方案如C2LSH和LSB-森林值用于c>=2。我们的理论分析和表明QALSH实现了c-ANN搜索的一个质量保证。我们也提出了一个自动方式决定QALSH中的桶宽w。四个真实数据集上的实验结果表明，QALSH能够超越C2LSH和LSB-森林，尤其在高维空间。
本文来源于QueryAware LocalitySensitive Hashing for Approximate Nearest Neighbor Search.
这篇关于近似最近邻搜索的QALSH方法-阅读笔记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
