近似最近邻搜索的QALSH方法-阅读笔记_query-aware localitysensitive hashing for approxim

近似最近邻搜索的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
2

1.介绍

NN搜索问题在欧氏空间有广泛的应用，如图像和视频数据库、信息检索和数据挖掘。在许多应用中，数据对象常常会被表示为欧氏向量。例如，在图像搜索应用中，图像会被自然映射为高维特征向量，其中每个像素表示一个维度。c-ANN中更小的c保证更好的查询质量。
现有的方法如LSH等...The seminal work.
![这里写图片描述](https://img-blog.csdn.net/20180510100230326?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA0NTI4MTY=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)

根据上述问题引出query-aware LSH函数，受...的激励，我们提出了..

本文主要贡献点包括：...

The rest of this paper组织如下：...
(感觉开始先描述清楚文章涉及的问题，最好举个小栗子能形象些；然后简单介绍与本文方法相似的最新前沿的方法；引出本文的方法基点以及介绍，贡献点；最后是文章脉络)。
1
2
3
4
5
6
7
8
9
10

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-森林，尤其在高维空间。
1

本文来源于QueryAware LocalitySensitive Hashing for Approximate Nearest Neighbor Search.