利用查询感知的局部敏感哈希提升高维空间近邻搜索准确性
需积分: 9 83 浏览量
更新于2024-09-09
收藏 1.14MB PDF 举报
Query-Aware Locality-Sensitive Hashing (QALSH) 是一种针对高维欧几里得空间中近似最近邻搜索（c-Approximate Nearest Neighbor, c-ANN）问题的知名索引方案。传统上，LSH函数是以一种查询无感知的方式构建的，即在接收到任何查询之前，数据对象会被划分到不同的桶中。这种预定义的桶划分可能导致一个问题：距离查询对象更近的数据可能被分配到不同的桶，这显然不利于提高查询效率和准确性。
然而，QALSH突破了这一限制，它引入了查询感知的特性。这意味着在处理查询时，会考虑到查询对象的具体位置信息和语义信息，从而动态调整桶的划分策略。这种方法旨在减少由于查询对象位置差异导致的“不理想”桶分配，提高精确匹配的可能性。相比于传统的查询无感知LSH，如外部内存中的C2LSH和LSB-Forest等，QALSH能够更好地适应实际应用场景，尤其是在处理空间和语义信息相结合的问题时。
QALSH的核心思想是构造一组针对特定查询敏感的哈希函数，这些函数在处理相同或相似距离范围内的数据时，使得相似对象有更高的概率落入同一个哈希桶。这通常通过设计多轮哈希和多个哈希函数来实现，每一轮哈希将数据点映射到更低维度的空间，同时保持局部敏感性。
为了实现QALSH，研究者们提出了一种混合策略，结合了局部敏感哈希和数据结构的优化，例如随机投影、多级索引等。这些技术能够有效地减小数据维度，降低存储开销，同时在查询阶段快速定位潜在的近似最近邻。通过这种方式，QALSH能够在保持空间效率的同时，显著提升查询性能，尤其是在大规模数据集和实时应用中。
总结来说，Query-Aware Locality-Sensitive Hashing是一种创新的索引技术，它通过考虑查询特征，提高了近似最近邻搜索的精度和效率。这对于地理位置服务、图像识别、推荐系统等领域具有重要意义，因为它能够更准确地识别出与查询对象相关度高的数据点，从而优化用户体验并降低计算复杂度。
where c > 1 and p
1
> p
2
. For ease of reference, p
1
and
p
2
are called positively-colliding probability and negatively-
colliding probability, respectively.
A query-oblivious LSH family is an LSH family H =
{h : R
d
→ Z} where each hash function h exploits query-
oblivious bucket partition, i.e., buckets in the hash table of
h are statically determined before any query arrives. Nor-
mally, for a query-oblivious LSH function h, two objects o
and q collide under h means h(o) = h(q), where h(o) identi-
fies the bucket of o. A typical query-oblivious LSH function
is formally defined as follows [2].
h
~a,b
(o) =
~a · ~o + b
w
, (1)
where ~o is a d-dimensional Euclidean vector representing
object o, ~a is a d-dimensional random vector with each en-
try drawn independently from standard normal distribution
N (0, 1). w is the pre-specified bucket width, and b is a real
number uniformly drawn from [0, w).
For two objects o
1
and o
2
, and a uniformly randomly cho-
sen hash function h
~a,b
, let s = ko
1
, o
2
k, and then their col-
lision probability is computed as follows [2]:
ξ(s) = P r
~a,b
[h
~a,b
(o
1
) = h
~a,b
(o
2
)]
=
R
w
0
1
s
f
2
(
t
s
)(1 −
t
w
) dt
(2)
where f
2
(x) =
2
√
2π
e
−
x
2
2
. For a fixed w, ξ(s) decreases
monotonically as s increases. With ξ
1
= ξ(r) and ξ
2
= ξ(cr),
the family of hash functions h
~a,b
is (r, cr, ξ
1
, ξ
2
)-sensitive.
Specifically, if we set r = 1 and cr = c, we have Lemma 1 as
follows [2] :
Lemma 1. The query-oblivious LSH family identified by
Equation 1 is (1, c, ξ
1
, ξ
2
)-sensitive, where ξ
1
= ξ(1) and
ξ
2
= ξ(c).
3. QUERY-AWARE LSH FAMILY
In this section we first introduce the concept of query-
aware LSH functions. Then we make a computational com-
parison of positively- and negatively-colliding probabilities
between query-oblivious and query-aware LSH families. Fi-
nally, we show that query-aware LSH family is able to sup-
port virtual rehashing in a simple and quick manner.
3.1 (1, c, p
1
, p
2
)-sensitive LSH Family
Constructing LSH functions in a query-aware manner con-
sists of two steps: random projection and query-aware bucket
partition. Formally, a query-aware hash function h
~a
(o) :
R
d
→ R maps a d-dimensional object ~o to a number along
the real line identified by a random vector ~a, whose entries
are drawn independently from N (0, 1). For a fixed ~a, the
corresponding hash function h
~a
(o) is defined as follows:
h
~a
(o) = ~a · ~o (3)
For all the data objects, their projections along the ran-
dom line ~a are computed in the pre-processing step. When
a query object q arrives, we obtain the query projection by
computing h
~a
(q). Then, we use the query as the “anchor”
to locate the anchor bucket with width w (defined by h
~a
(·)),
i.e., the interval [h
~a
(q) −
w
2
, h
~a
(q) +
w
2
]. If the projection
of an object o (i.e., h
~a
(o)), falls in the anchor bucket with
width w, i.e., |h
~a
(o) − h
~a
(q)| ≤
w
2
, we say o collides with q
under h
~a
.
We now show that the family of hash functions h
~a
(o) cou-
pled with query-aware bucket partition is locality-sensitive.
In this sense, each h
~a
(o) in the family is said to be a query-
aware LSH function. For objects o and q, let s = ko, qk.
Due to the stability of standard normal distribution N (0, 1),
we have that (~a · ~o − ~a · ~q) is distributed as sX, where
X is a random variable drawn from N (0, 1) [2]. Let ϕ(x)
be the probability density function (PDF) of N (0, 1), i.e.,
ϕ(x) =
1
√
2π
e
−
x
2
2
. The collision probability between o and
q under h
~a
is computed as follows:
p(s) = P r
~a
[|h
~a
(o) − h
~a
(q)| ≤
w
2
] = P r[|sX| ≤
w
2
]
= Pr[−
w
2s
≤ X ≤
w
2s
] =
R
w
2s
−
w
2s
ϕ(x) dx
(4)
Accordingly, we have Lemma 2 as follows:
Lemma 2. The query-aware hash family of all the hash
functions h
~a
(o) that are identified by Equation 3 and coupled
with query-aware bucket partition is (1, c, p
1
, p
2
)-sensitive,
where p
1
= p(1) and p
2
= p(c).
Proof. Referring to Equation 4 , a simple calculation
shows that p(s) = 1 − 2norm(−
w
2s
), where norm(x) =
R
x
−∞
ϕ(t) dt. Note that norm(x) is simply the cumulative
distribution function (CDF) of N (0, 1), which increases mono-
tonically as x increases. For a fixed w, norm(−
w
2s
) in-
creases monotonically as s increases, and hence p(s) de-
creases monotonically as s increases. Therefore, according
to Definition 1, the query-aware hash family identified by
Equation 3, is (1, c, p
1
, p
2
)-sensitive, where p
1
= p(1) and
p
2
= p(c), respectively.
3.2 Comparison of Colliding Probabilities
The effectiveness of an (r, cr, p
1
, p
2
)-sensitive hash family
depends on the difference between the positively-colliding
probability and negatively-colliding probability, i.e., (p
1
−
p
2
), since the difference measures the degree that positively-
colliding data objects of a query q can be discriminated
from negatively-colliding ones. We now show that the novel
query-aware hash family leads to larger (p
1
−p
2
) under typi-
cal settings of bucket width w. For query-aware LSH family,
from the proof of Lemma 2, we have p
1
= 1 − 2norm(−
w
2
)
and p
2
= 1 − 2norm(−
w
2c
). For query-oblivious LSH fam-
ily, we have ξ
1
= 1 − 2norm(−w) −
2
√
2πw
(1 − e
−(w
2
/2)
) and
ξ
2
= 1 − 2norm(−w/c) −
2
√
2πw/c
(1 − e
−(w
2
/2c
2
)
) [2].
Bucket width w is a critical parameter of an LSH function.
While E2LSH and LSB-Forest manually set w = 4.0, C2LSH
manually sets w = 1.0. For w in the range [0, 10], starting
from 0.5 and with a step of 0.5, we show the variations of the
colliding probabilities p
1
, p
2
, ξ
1
, and ξ
2
for two different c
values in Figure 3. We find that all the colliding probabilities
monotonically increase as w increases, and get very close to 1
as w gets close to 10. In addition, p
1
and p
2
are consistently
larger than ξ
1
and ξ
2
, respectively. Thus, we also show
the two differences (p
1
− p
2
) and (ξ
1
− ξ
2
) with respect to
w in Figure 4. We have two interesting observations: (1)
(p
1
−p
2
) is larger than (ξ
1
−ξ
2
) under typical bucket widths,
namely w = 4.0 and w = 1.0. (2) Both (p
1
− p
2
) and
(ξ
1
−ξ
2
) tend to have maximum values in the w range [0, 10].
Observation (1) indicates that our novel query-aware LSH
family can be used to improve the performance of query-
oblivious LSH schemes such as C2LSH by leveraging a larger
(p
1
− p
2
). Observation (2) inspires us to automatically set
3
剩余11页未读，继续阅读
2021-11-06 上传
2022-09-24 上传
237 浏览量
Trust-Aware Service Offloading for Video Surveillance in Edge Computing Enabled Internet of Vehicles
2023-05-23 上传
2023-03-25 上传
2023-06-13 上传
2024-10-26 上传
2023-04-29 上传
2023-03-28 上传
bccvictory
- 粉丝: 0
- 资源: 5
我的内容管理
展开
最新资源
- 前端协作项目：发布猜图游戏功能与待修复事项
- Spring框架REST服务开发实践指南
- ALU课设实现基础与高级运算功能
- 深入了解STK：C++音频信号处理综合工具套件
- 华中科技大学电信学院软件无线电实验资料汇总
- CGSN数据解析与集成验证工具集：Python和Shell脚本
- Java实现的远程视频会议系统开发教程
- Change-OEM: 用Java修改Windows OEM信息与Logo
- cmnd：文本到远程API的桥接平台开发
- 解决BIOS刷写错误28：PRR.exe的应用与效果
- 深度学习对抗攻击库：adversarial_robustness_toolbox 1.10.0
- Win7系统CP2102驱动下载与安装指南
- 深入理解Java中的函数式编程技巧
- GY-906 MLX90614ESF传感器模块温度采集应用资料
- Adversarial Robustness Toolbox 1.15.1 工具包安装教程
- GNU Radio的供应商中立SDR开发包：gr-sdr介绍
