SK-LSH：高效索引结构，优化近似最近邻搜索
155 浏览量
更新于2024-08-26
收藏 616KB PDF 举报
"SK-LSH：一种有效的索引结构，用于近似最近的邻居搜索"
在高维空间中的近似最近邻（Approximate Nearest Neighbor, ANN）搜索已经成为许多应用的基础范式，如图像识别、推荐系统和机器学习等领域。随着大数据量的增长，快速有效地寻找数据集中的近似最近邻变得至关重要。当前，局部敏感哈希（Locality Sensitive Hashing, LSH）被认为是最有前途的解决方案之一，因为它能够高效地处理高维数据并减少搜索复杂度。
然而，传统的LSH方法存在一个显著的问题：候选对象的访问需要大量的随机I/O操作。为了保证返回结果的质量，需要验证足够多的对象，这会消耗巨大的I/O成本，从而降低了搜索效率。针对这一问题，作者提出了一个新的方法——排序键-LSH（Sorting Keys-LSH, SK-LSH）。
SK-LSH的核心思想是通过局部排列候选对象来减少页面访问的数量。首先，他们定义了一个新的度量标准来评估“排序键”之间的距离。这些排序键是基于对象的特征生成的，并用于确定对象之间的相似性。通过精心设计的排序策略，候选对象可以按照其哈希值的某种顺序进行排列，使得相近的对象更有可能被安排在一起，从而减少了在验证阶段需要访问的页面数量。
在SK-LSH中，哈希表的构建和查询过程被优化，使得在查询时可以按顺序访问存储的候选对象，而不是随机访问。这种方法减少了对磁盘或内存的随机访问，提高了I/O效率。此外，SK-LSH还考虑了错误率的控制，确保在降低I/O成本的同时，仍然能提供高质量的近似最近邻搜索结果。
实验结果表明，与现有的LSH方法相比，SK-LSH在保持搜索精度的同时，显著降低了I/O开销，尤其是在处理大规模高维数据集时，性能优势更为明显。这种方法对于需要高效处理大规模数据的实时应用，如实时推荐系统和大规模图像搜索，具有重要的实用价值。
SK-LSH是一种创新的索引结构，它通过改进LSH的哈希碰撞策略和候选对象的排序方式，有效解决了传统LSH在高维度数据下的I/O效率问题。这种方法不仅提高了搜索效率，还兼顾了搜索质量，为高维空间的近似最近邻搜索提供了新的解决方案。
3.1 Locality Sensitive Hashing
To solve the c-ANN problem, Indyk and Motwani pro-
posed the idea of LSH [8], which is formally defined as fol-
lows.
Definition 1. (Locality Sensitive Hashing) Given a
distance R, an approximate ratio c and two probability val-
ues P
1
and P
2
, a hash function h : R
d
→ Z is called
(R, c, P
1
, P
2
)-sensitive if it satisfies the following condition-
s simultaneously for any two points p
1
, p
2
∈ D:
• If k p
1
, p
2
k≤ R, then P r[h(p
1
) = h(p
2
)] ≥ P
1
;
• If k p
1
, p
2
k≥ cR, then P r[h(p
1
) = h(p
2
)] ≤ P
2
;
To make sense, both c > 1 and P
1
≥ P
2
hold. In ad-
dition, a compound LSH function is denoted as G =
(h
1
, . . . , h
m
), where h
1
, . . . , h
m
are randomly selected LSH
functions. Specifically, for ∀p ∈ D, K = G(p) = (h
1
(p),
. . . , h
m
(p)) is defined as the compound hash key of point
p under G.
According to Definition 1, LSH ensures that a close pair
collides with each other with a high probability (P
1
) and a
far pair with a low probability (P
2
). This property of LSH
is also called distance-preserving.
The LSH function commonly used in Euclidean Space,
which was proposed by Datar [2], is shown as the following:
h(p) = b
a · p + bW
W
c (1)
Here, a is a random vector with each dimension indepen-
dently chosen from Guassian distribution and p is an ar-
bitrary point in D. b is a real number uniformly drawn
from the range [0,1]. W is also a real number represent-
ing the width of the LSH function. For two points p
1
, p
2
and an LSH function h, if k p
1
, p
2
k= r, the probability of
h(p
1
) = h(p
2
) can be computed as follows [2].
p(r, W ) = P r[h(p
1
) = h(p
2
)]
=
R
W
0
1
r
f
2
(
t
r
)(1 −
t
W
)dt
= 2norm(W/r) − 1 −
2
√
2π
r
W
(1 − e
−
W
2
2r
2
)
(2)
Here, f
2
(x) =
2
√
2π
e
−
x
2
2
and norm(·) represents the cumu-
lative distribution function of a random variable following
Gaussian Distribution. According to Equation 2, the proba-
bility p(r, W) decreases monotonically when r increases but
grows monotonically when W rises.
Due to the distance-preserving property of LSH, it is ra-
tional to use the hash values to estimate the distance be-
tween two points. Therefore, if two points have similar hash
values, it is believed that they are close to each other with
certain confidence. Based on this idea, several approaches
have been proposed for c-ANN [2, 4, 5, 12, 19]. However,
it is obvious that Equation 1 exhibits poor performance in
filtering irrelevant points, as many pairs, which are distant
from each other, may share the same hash value under a sin-
gle hash function as Equation 1. In other words, numerous
false positives may be returned. To remove the irrelevan-
t points (i.e. false positives), a compound LSH function
G = (h
1
, h
2
, . . . , h
m
) is employed so as to improve the dis-
tinguishing capacity. Note that each element of a compound
LSH function, h
i
, is randomly selected as defined in Equa-
tion 1. Only points sharing all the m hash values with the
query point are taken into account as candidate points, as
suggested by the basic LSH [2]. However, c-ANN search al-
gorithms should ensure that data points having similar com-
pound hash keys to the query point are taken into account as
candidates. Hence, a distance measure over compound hash
keys is required. In the following, we propose a novel mea-
sure to evaluate the distance between a pair of compound
hash keys.
3.2 Distance over Compound Hash Keys
Given a compound LSH function G and two points p
1
, p
2
∈ D, we have compound hash keys K
1
= G(p
1
) and K
2
=
G(p
2
), where both K
1
and K
2
are tuples containing m hash
values. Let k
1,i
(resp. k
2,i
) be the i-th element of K
1
(resp.
K
2
), that means k
1,i
= h
i
(p
1
) and k
2,i
= h
i
(p
2
).
Definition 2. (Prefix of a Compound Hash Key)
Given a point p ∈ D and its compound hash key K =
G(p) = (k
1
, k
2
, . . . , k
m
). The l-length prefix of K, de-
noted as pref (K, l), consisting of the first l elements of K
where 1 ≤ l ≤ m, is formally defined as follows.
pref(K, l) = (k
1
, k
2
, . . . , k
l
) (3)
Particularly, we denote pref(K, 0) as K
∅
, which is actually
an empty hash key.
Here, we are inspired by the prefix of a character string
and treat a compound hash key as a string of elements.
Therefore, its prefix is the substring constituted by its first
several elements. For example, for a compound hash key
K = (1, 2, 3, 4), pref (K, 3) = (1, 2, 3), pref(K, 2) = (1, 2)
and pref (K, 0) = K
∅
.
Definition 3. (Non-prefix Length of Compound Hash
Keys) Given two compound hash keys K
1
= (k
1,1
, k
1,2
, . . . , k
1,m
)
and K
2
= (k
2,1
, k
2,2
, . . . , k
2,m
), if pref(K
1
, l) = pref(K
2
, l)
and pref (K
1
, l + 1) 6= pref(K
2
, l + 1), where 0 ≤ l < m,
then the non-prefix length between K
1
and K
2
, denoted as
KL(K
1
, K
2
), is formally defined as follows:
KL(K
1
, K
2
) = m − l (4)
If pref(K
1
, m)=pref(K
2
, m), then KL(K
1
, K
2
) = 0.
A smaller non-prefix distance between two compound hash
keys indicates that they share a longer common prefix with
each other. For instance, given two compound hash keys
K
1
= (1, 2, 3, 4) and K
2
= (1, 2, 3, 5), KL(K
1
, K
2
) = 1 since
pref(K
1
, 3) = pref(K
2
, 3) and pref (K
1
, 4) 6= pref(K
2
, 4).
Definition 4. ((l + 1)-th Element Distance of Com-
pound Hash Keys) Given two compound hash keys K
1
=
(k
1,1
, k
1,2
, . . . , k
1,m
) and K
2
= (k
2,1
, k
2,2
, . . . , k
2,m
), if
KL(K
1
, K
2
) = m − l, where 0 ≤ l < m, then the (l + 1)-th
element distance between K
1
and K
2
is defined as the ab-
solute value of the distance between their (l + 1)-th elements
as follows:
KD(K
1
, K
2
) = |k
1,l+1
− k
2,l+1
| (5)
If l = m, we denote KD(K
1
, K
2
) as 0 by default.
Though the notion of non-prefix length can be used to
measure the distance between two compound hash keys, we
employ the (l + 1)-th element distance to further distinguish
two compound hash keys. Let us consider the following three
compound hash keys, K
1
= (1, 2, 3, 4), K
2
= (1, 2, 3, 5) and
747
剩余11页未读，继续阅读
2015-07-03 上传
2021-07-14 上传
2021-06-05 上传
2021-06-15 上传
2021-03-09 上传
2021-06-19 上传
2021-04-07 上传
2021-05-13 上传
2021-06-30 上传
weixin_38622777
- 粉丝: 5
- 资源: 938
我的内容管理
展开
最新资源
- StarModAPI: StarMade 模组开发的Java API工具包
- PHP疫情上报管理系统开发与数据库实现详解
- 中秋节特献：明月祝福Flash动画素材
- Java GUI界面RPi-kee_Pilot：RPi-kee专用控制工具
- 电脑端APK信息提取工具APK Messenger功能介绍
- 探索矩阵连乘算法在C++中的应用
- Airflow教程：入门到工作流程创建
- MIP在Matlab中实现黑白图像处理的开源解决方案
- 图像切割感知分组框架：Matlab中的PG-framework实现
- 计算机科学中的经典算法与应用场景解析
- MiniZinc 编译器：高效解决离散优化问题
- MATLAB工具用于测量静态接触角的开源代码解析
- Python网络服务器项目合作指南
- 使用Matlab实现基础水族馆鱼类跟踪的代码解析
- vagga：基于Rust的用户空间容器化开发工具
- PPAP: 多语言支持的PHP邮政地址解析器项目
