Similarity Search（相似度搜索）

首先，我们要知道，什么是Similarity Search（相似度搜索）？

相似度搜索指的是，给定一个数据集 D 和查询数据（query）q ，找到数据集 D 中，与 q 相似的对象（object）o ( o ∈ D )

主要的相似度搜索有2种类：

1. Range Search（范围搜索）：dist (o, q) ≤ τ （这里的 τ 是一个预设的阈值）
   

2. Nearest Neighbor Search（邻近搜索）：最经典的就是大家都很熟悉的KNN，在 D 中寻找与 q 最接近 (相似) 的 k 个对象 o

以上两种方法之间其实可以互相转换。

用于度量距离 (Distance) / 相似度 (Similarity) 的函数有很多种，一般来说比较常见的是：欧氏距离 (Eucliden Distance)，Jaccard 系数，Jaccard 距离，内积 (inner product) 等。我们要注意一般，我们认为距离越近，相似度越高。

以上就是相似度搜索（Similarity Seacrh）的基本思想，而所谓的高维相似度搜索（High Dimensional Similarity Search），指的是应用于大数据的相似度搜索。我们之前已经说过，大数据的“大”也体现在数据的复杂度上，诸如图像，视频，音频，文档等数据，它们都有很多的特征（Features），这就使得数据的维度变得很高，传统的相似度搜索显得很乏力，因此发展出高维相似度搜索（High Dimensional Similarity Search）。

*相似度搜索也是信息检索 (Information Retrieval) 的基础处理

Low Dimensional Similarity Search（低维相似度搜索）

一维空间：
数据都是数字，只需要使用二分法搜索（Binary Search），二叉搜索树（Binary Search Tree），B+ Tree等方法，就能进行有效的搜索。
这些方法的背后都秉持一个基本的思想（Essential Idea）就是排序（Sorting）。一旦对objects进行了排序，就可降低时间和空间复杂度（Time & Space Complexity）

二维空间：
在二维空间中，无法再使用二分法进行搜索，因为此时数据已经没有顺序。此时，常用的方法是 Voronoi Diagram 。下图为采用两种不同距离度量的 Voronoi Diagram：

在图中，黑色的点代表数据点（data point）。每个点占据一块区域，每个区域内的点都是到该数据点最近的点。所有区域被data points之间的bisector（二等分线、平分面）划分。所以在进行搜索时，只需要知道query落在哪个区域。

但是计算Voronoi Diagram的复杂度是个问题，一般为

其中d为维度数

度量空间（Metric Space）
所谓的度量空间（Metric Space），也就是距离空间。在这个空间中，距离函数满足以下条件：

1. Dist (x, x) = 0
2. Dist (x, y) = Dist (y, x)
3. Dist (x, q) ≤ Dist (x, y) + Dist (y, q) - Triangle inequality（三角不等式）

三角不等式可以帮助我们裁剪掉多余的结果，这里介绍一个采用了三角不等式的基础算法：Orchard’s Algorithm：

1. 对Dataset中的每一个data points x (x ∈ D)，我们为其建立一个列表，这个列表中，以到其的距离升序排列了数据集中其他所有data points
2. 给定一个查询数据（query）q，随机选择一个data point x作为初始的候选点p（p = x），计算 Dist (p, q)
3. 遍历候选点p在Step 1中为其建立的列表，并依次计算列表中点到q的距离。一旦发现某个点y比p更接近q（query），那么就把点y作为新的候选点p（p = y）
4. 重复以上步骤，直到 Dist (p, y) > 2 * Dist (p, q)，停止，当前的p就是q的最近邻点

牢牢记住：p是当前的候选点，y是该候选点的列表中，我们正在访问的点

这里的终止条件就是运用了三角不等式：

Dist (p, y) > 2 * Dist (p, q)
Dist (p, y) ≤ Dist (p, q) + Dist (y, q)

所以：
2 * Dist (p, q) < Dist (p, q) + Dist (y, q)

即：
Dist (p, q) < Dist (y, q)

因为每个data point p的列表都是根据到p的距离升序排列，所以剩下所有大于y的值，我们就全部不需要再进行计算了。

但是，以上的所有方法，均无法适用于高维空间！！

High Dimensional Similarity Search（高维相似度搜索）

Curse of Dimensionality（维度诅咒）

之所以上述的方法无法应用于高维空间，正是因为维度诅咒。这一概念我们常见于ML中，这里我们不再具体赘述，只是看一些具体的例子。

我们考虑一个二维平面内的环（ring）

此时，该环的流通量为：

单若是在高维空间中，我们把维度设为100，则

若我们假设点均匀分布，那么，在维度为100时，99.997%的点都会落在“环” （hyperspherical shell - 超球壳）上，此时我们假想一个刚好位于超球体中心的query，此时query和几乎所有的data points的距离都相同，无法使用三角不等式。此时没有线性解决方案可以找到最近邻居查询的确切结果，因此，我们放宽条件。这也就是近似最近邻居搜索（ANNS）。

对于近似最近邻居搜索（ANNS），我们允许返回的data points不是query的最近邻点，我们只需要使得成功率（success rate = num of success / num of queries）达到要求即可，也就是有一定的容错性。但问题依旧存在， 那就是难以保障成功率。

为了解决这个问题，进一步放宽条件，这就有了c-近似最近邻居搜索（c-ANNS）。此时，我们把“邻近”的条件放宽：

即，只要data point与query的距离小于等于 cr 都算作正确答案（o^*为true NN）。这样就可以使用 局部敏感哈希（Locality Sensitive Hashing，LSH） 来保证成功率，至于具体如何保障，我会在之后详细介绍。

Locality Sensitive Hashing（LSH, 局部敏感哈希）

Hashing

主要分为两个步骤：

1. Index Phase：将数据（data）/对象（object）映射为值（values/hash key）
   - 相同的data会得到相同的hash key
   - 不同的data我们希望会有不同的hash key（因为hash function本身的问题，总可能会有不同的data拥有相同的hash key，但至少我们要保证不同的data用大概率会有不同的hash key）

2. Retrieval Phase：当我们要进行查询时，计算query data的hash key（h(q)）。之后在哈希图（hash map）中搜索该hash key，这样就能知道，数据库中是否有相同的数据。

主要的优点在于成本很低

• Space Cost：O(n) （为每个object创建hash key并存储，所以对n个object，要存储n个hash key）
• Time Cost：O(1) （主要指的是检索时间，是恒定时间）

Hashing具有以上有点，且很简单，但却无法应用于最近邻居搜索（Nearest Neighbor Search）。这是因为 即使object之间很接近，也会生成完全不同的hash keys，而 在最近邻居搜索中，我们要找的不是完全相同的数据，而是最接近的数据，这就导致难以得到结果。

Locality Sensitive

配合Locality Sensitive（局部敏感），就有可能将 LSH 用于最近邻居搜索（Nearest Neighbor Search）。我们依旧从Index和Retrieval两个阶段来看变化。

1. Index Phase：让哈希函数（Hash Function）具有容错性
   - 让相似的数据（高概率）有同样的hash key
   - 让不相似的数据（高概率）有不同的hash key
2. Retrieval Phase：计算query data的hash key，获取所有与query有相同hash key的的data（与query相似的data）作为候选（candidates）。然后从候选中选取与query最接近（nearest）的一个。

此时，成本为：

• Space Cost：O(n)
• Time Cost：O(1) + O(|candidate size|) << O(n)

以上就是LSH的基本思想，但仍不是全部，因为到目前为止，还留有一些问题没有解决，接下来，会进行全面的介绍。

LSH Functions

要完成LSH，首先，我们需要有一个合适的LSH Function，以使得 相似的数据（高概率）有同样的hash key，不相似的数据（高概率）有不同的hash key

这里给出正式定义：
给定data points o₁，o₂；
距离 r₁（相似界限），r₂（不相似界限），因此r₁ < r₂
概率 p₁（希望p₁要高），p₂（希望p₂要小），因此 p₁ > p₂

LSH Fcuntion（h(·)）要满足：

• 如果Dist(o₁，o₂) ≤ r₁ ，即o ₁，o₂ 相似，则：

• 如果Dist(o₁，o₂) ＞ r₁ ，即o ₁，o₂ 不相似，则：

根据给定的距离（distance）/相似度（similarity）度量函数的不同，LSH Function（h(·)）也会有所不同，我们主要介绍一下三种度量函数所对应的LSH Function：

• Jaccard similarity（jaccard相似系数）
• Angular distance（角距离）
• Euclidean distance（欧氏距离）

MinHash（LSH Function for Jaccard Similarity）

先介绍一下Jaccard Similarity，将每一个object看做一个集合（set），那么object A和object B的Jaccard Similarity为：

基于Jaccard Similarity的LSH Function具体操作为，将数据集中的所有object取并集

随机生成所有元素的全局顺序。此时，让 h(S) 为符合全局顺序的S中的最小元素（minimal member），可看做是第一个元素。

比如，S = {b, c, e, h, i}，全局顺序为反字典序（inversed
alphabet order），此时，重排列之后的 S = {i, h, e, c, b}，因此h(S) = i

现在，我们来计算两个object有相同hash key的概率 Pr[h(S₁) = h(S₂)]。S₁ U S₂ 中的每一个元素 e （e ∈ S₁ U S₂）在重排列之后都用同等的机会成为S₁ U S₂ 中的第一个元素。那么：

e ∈ S₁ ∩ S₂ 当且仅当 h(S₁) = h(S₂)
e ∉ S₁ ∩ S₂ 当且仅当 h(S₁) ≠ h(S₂)

所以

即，对象S₁ 和S₂ 有相同hash key的概率就等于他们的Jaccard Similarity。对于相似的object，它们的Jaccard Similarity会比较高，因此会有高概率有相同的hash key，完全符合我们对LSH Function的要求。

SimHash（LSH Function for Angular Distance）

每一个object都看作一个d维的向量（d dimensional vector），用 θ(x, y) 表示x和y之间的角度，随机生成一个法向量（normal vector）a，a中的每一个元素都服从标准正态分布 a_i ~ N(0, 1)。
此时，h(x, a) = sgn(a^Tx)

因此这个LSH Function的值只有1和-1，以显示x落在a的哪一边。

现在，我们来计算两个object有相同hash key的概率 Pr[h(S₁) = h(S₂)]。我们根据之前定义的LSH Fucntion可以知道，当且仅当o₁和o₂在a的两边时，h(o₁) ≠ h(o₂)。

根据图可以知道，只有当a位于蓝色范围内时，才会使得o₁和o₂在a的两边，因此：

对于相似的object，它们的向量之间的角度θ会很小，因此拥有相同hash key的概率很高，符合要求。

p-stable LSH （LSH Function for Euclidea distance）

同样，每一个object都看作一个d维的向量（d dimensional vector），对象x和y之间的距离即为

随机生成一个法向量（normal vector）a，a中的每一个元素都服从标准正态分布 a_i ~ N(0, 1)。标准正态分布是2-stable的，即若a_i ~ N(0, 1)，那么 a^Tx = Σa_i x_i ~ N(0, ||x||₂²)。
此时，LSH Function为：

a, b 为超参数，b服从均匀分布（b~U(0, 1)），w是用户定义的参数
（ **f(·)**是正态变量绝对值的PDF ）

这里直接理解公式会比较困难，所以主要还是通过图来进行一个直观的理解：

图中的每个点就是一个data point，向量a上的 × 就是每个data point在其上的投影（projection），即为 a^Tx + b，蓝色虚线则为使用floor和w计算出的bucket，当两个data points的投影落在同一个bucket中时，它们有相同的hash key。因此，越接近（相似）的data points，会有更高的几率被投射在同一个bucket中

Comparasion

我们现在已经有了3个Hash Function，但仍然存在一个不可忽视的问题，那就是这些函数的曲线还是太平滑，当两个object过于接近时，我们很难分辨它们，我们还是用来看一下，图中两个蓝色的object十分接近，因此p₁和p₂也极其接近

我们希望及时两个object很接近时仍能将二者分别，也就是说

即使 r₁ 和 r₂ 之差不大，p₁ 和 p₂ 仍能有较大的区分度

同时，我们也希望能够控制这种剧烈的变化在哪里出现，比如，让r₁接近Dist(o^*, q)。

但是仅靠单一的SLH Function是难以实现的，因此，我们需要对LSH Function进行组合，组成新的Super Hush Function。

AND-OR Composition（与或组合）

回顾一下单一LSH Function：

现在，我们用

表示o₁ 和o₂两个对象有相同hash key（匹配）的概率。

现在我们考虑两个场景：

• 使用AND（与）运算，把k个hash function组合起来。因为是与运算，所以两个points都符合所有k个hash function，才能算作匹配
• 使用OR（或）运算，把l个hash function组合起来。因为是与运算，所以只要两个points有一个hash function符合，就算作匹配（换言之，只有这两个points所有l个hash function都不符合，才能匹配失败）

因此，o₁ 和o₂两个对象有相同hash key的概率分别为：


接下来看一个具体的例子，以minHash为例，将k，l都设为5，可以得到以下结果：

对于AND Composition，两个object不相似时，它们匹配的概率几乎等于0；对于OR Composition，两个object相似时，它们匹配的概率逼近1.但是前者对于部分相似的两个object，概率不够高，后者对于不相似的object，概率不够低。所以，单用AND或者OR进行组合，依然不够。

所以，需要组合AND和OR进行使用：

1. 现在，我们用h_i,j 表示Hash Function。（i ∈ {1, 2, …, l}, j ∈ {1, 2, …, k}），很明显，i是表示OR运算，j表示AND运算。

2. 我们先进行AND运算。定义一个Super Hash，H_i(o):
   H_i(o) = [ h_i,1(o), h_i,2(o), …, h_i,k(o) ]
   H_i(o) 是一个用AND运算连接的k个Hash Function的Super Hash，所以，只有 ∀ j ∈ {1, 2, …, k}， h_i,j(o₁) = h_i,j(o₂)，才有 H_i(o₁) = H_i(o₂)

3. 再进行OR运算，我们假设一个query q以及任意data point o。只有满足 ∃ i ∈ {1, 2, …, l}，H_i(o) = H_i(q)，o才是q的最近邻点（Nearest Neighbor）候选。

o是q的最近邻点（Nearest Neighbor）候选的概率为：

使用这种方法的效果是很明显的，我们设 k = 20，l = 15：

可以看到，当q和o极其不相似时（0.2），结果无限接近与0（0.02），而当二者相似时，结果无限接近1。同时，在相邻的结果之间，差距也很明显。
同时我们可以调整k和l来调整效果：

此时将k设为17，l设为46。该曲线表明，当o和q的Jaccard相似度低于0.7时，o成为q的最邻近候选点的概率几乎等于0，当o和q的Jaccard相似度高于0.8时，o成为q的最邻近候选点的概率逼近1。

而当我们把k和l都设置的很小时，整体的效果就比较差：

所以这实际上还是存储空间（storage space），运算时间和运算效果之间的权衡，当k和l，尤其是后者很大时，我们需要耗费更多的存储空间（因为要创建l个Hash Table），也需要更多时间进行检索，但是效果会更好具体表现在假阳性（False Positive）和假阴性（False Negative）会降低。

图中的绿色部分表示False Negative（not returned data with dist(o,q) < r₁），红色部分表示False Positive（returned data with dist(o,q) > r₂）。这两种情况False Negative更难以接受

The Framework of NNS using LSH（使用LSH进行最近邻搜索的基本框架）

• Preprocessing：生成LSH函数，需要 k * l 个Hash Functions
  - minHash
  - simHash
  - p-stable
• Index：对每个data object o，计算 H_i(o) （i ∈ {1, 2, …, l}）（每个object o有l个Super Hash）。然后用 H_i(o) 作为键（key）以 o 或者 o 的ID作为值建立Hash Table，因此一共会有 l 个Hash Table
• Query：为query q计算 H_i(q) （i ∈ {1, 2, …, l}）。只要 o 的 l 个Super Hash中有一个 H_i(o) = H_i(q)，就将o加入候选集合。最后计算所有候选object与q的实际距离，返回最近的那个。

至此我们已经介绍完LSH的基本思想。现在，来看看它还存在的一些问题：

1. 首先因为每个Super Hash是由k个hash function用AND运算组合出来的，所以，只要 h_i,j(o₁) ≠ h_i,j(o₂)，那么 H_i(o₁) ≠ H_i(o₂)。比如 k = 5时，q = 1 1 1 1 1，o = 1 1 1 1 0，我们可以看到，其实o和q是很相似的，但是o却没有机会成为q的候选点
2. 无法自适应距离的分布

Multi-Probe LSH

回忆一下p-stable LSH，我们说当object o的投影和q落在同一个bucket时，它们算作“相似”。我们也能很轻易地得到一个结论：q的最近邻点若没有落在q所在的bucket中是，大概率落在了它两旁的bucket。

所以，不仅要看q落入的bucket，也要看它旁边的两个bucket。但是这样也会存在一些问题，那就是我们需要查看的bucket从原来的的1个变为了3^k个，而且我们要明白，两边的bucket它们的重要性并不相同。

通过概率决定探测顺序

该算法的优点在于：

• 需要更小的l
• 对于不幸（没落在q的bucket）的点有更强的鲁棒性

C2LSH

这一算法相较于Multi-Probe LSH直观的多，简单的来说就是一个不断放宽条件的过程。它的核心思想就是Counting Collision，Collision的数量越大，两个points就越接近。

这个算法中有三个比较关键的参数：

• alpha_m：collisions数量的阈值
• beta_n：候选点（candidates）的最小数量
• offset：唯有两个points值之差小于等于offset，才算一个collision

具体看一个例子：
我们设alpha_m = 8，beta_10，offset=0

一开始，offset = 0，可以看到q和o₁只有2个collision，没有达到alpha_m = 8的要求，因此o₁ 不能成为q的候选点。我们假设对于其他o_i也一样，因此第一轮，q的候选点数量为0，没有达到beta_10的要求。

这时候，我们放宽条件，offset += 1 = 1

这时，可以看到q和o₁有6个collision，没有达到alpha_m = 8的要求，因此o₁ 不能成为q的候选点，但条件已经宽松很多，可以预见，有一些点已经有资格成为q的候选点。我们假设这时候候选点的数量仍未达到beta_10的要求。

这时候，我们再次放宽条件，offset += 1 = 2

可以看到q和o₁有8个collision，达到alpha_m = 8的要求，因此o₁ 成为q的候选点。

我们就是这么通过挑选合适的offset，以找到满足alpha_m和beta_n约束的结果。

以下为伪代码：

以下贴出一个我根据伪代码，在pyspark下写出的naive solution，以及使用二分法选择offset的改进型

def count_collision(row, query_hashes, offset, alpha_m):
    """ Using this function to count collision """
    counter = 0
    for i in range(len(query_hashes)):
        sub = row[1][i] - query_hashes[i]
        if -1 * offset <= sub <= offset:
            counter += 1

    if counter >= alpha_m:
        return row


# do not change the heading of the function
def c2lsh(data_hashes, query_hashes, alpha_m, beta_n):
    offset = 0
    while True:
        filtered = data_hashes.filter(lambda row: count_collision(row, query_hashes, offset, alpha_m)).keys()

        if filtered.countApprox(timeout=50) < beta_n:
            offset += 1
        else:
            break

    return filtered

import math

"""
    Updated
    Pass: all Test
"""


def count_collision(row, query_hashes, offset, alpha_m):
    """ Using this function to count collision """
    counter = 0
    for i in range(len(query_hashes)):
        sub = row[1][i] - query_hashes[i]
        if -1 * offset <= sub <= offset:
            counter += 1

    if counter >= alpha_m:
        return row


# do not change the heading of the function
def c2lsh(data_hashes, query_hashes, alpha_m, beta_n):
    # Step 1: Find the range of offset
    max_values = data_hashes.map(lambda x: max(x[1]))
    max_value = int(max_values.max())
    min_values = data_hashes.map(lambda x: min(x[1]))
    min_value = int(min_values.min())

    min_query = min(query_hashes)
    max_query = max(query_hashes)

    a = abs(min_query - max_value)
    b = abs(min_query - min_value)
    c = abs(max_query - max_value)
    d = abs(max_query - min_value)

    p = int(max([a, b, c, d]))

    r = list(range(p + 1))
    high = p
    low = 0

    # Step 2: Define iteration times
    num = p * 2
    if num == 0:
        # p = 0 means that offset is 0
        iteration = 1
    else:
        iteration = int(math.log(num, 2))
    result = []

    for _ in range(iteration):
        """ Using binary search to find the appropriate offset and candidate IDs """
        # Initialising offset
        mid = (high + low) // 2
        offset = r[mid]

        # Counting collision
        filtered = data_hashes.filter(lambda row: count_collision(row, query_hashes, offset, alpha_m)).keys()
        result_num = filtered.count()

        if result_num == beta_n:
            """ The best solution """
            return filtered
        elif result_num > beta_n:
            """ The offset may be too large """
            if len(result) == 0:
                result.append((result_num, filtered))
                print(result)
            else:
                if result_num < result[0][0]:
                    result.clear()
                    result.append((result_num, filtered))
                    print(result)
            high = mid - 1
        else:
            """ The offset is not large enough """
            low = mid + 1

    return result[0][1]

Product Quantization（积量化）

我们首先回顾一下高维空间中进行最近邻搜索（NNS）的方法，主要是对数据库中的所有对象 o ∈ D（D为数据库）进行线性扫描，分别计算它们和查询数据（Query）q的距离（一般为欧几里得距离）：

这一方法的时间复杂度和空间复杂度都为O(nd)，n表示D中的Data Point数量，d表示数据的维度。

我们可以清楚地看到，这一方法在DBMS和分布式系统中会有比较大的问题。在DBMS中，这一方法需要从磁盘存储（Disk）中多次读取数据进行计算，类似的在分布式系统中，需要从多个节点读取数据，因此网络传输量会很大，同样IO开销也会很大。因此，我们自然会想要对计算量进行压缩（Compression）。

为了进行压缩，首先采用的方法是向量量化（Vector Quantization）。这一方法主要用于压缩数据点/数据向量的表现规模。它的主要思想是，我们为每一个数据点/数据向量 o 找一个代表（representative），记作QZ(o)，它也是一个向量。 同时，我们要控制代表QZ(o)的数量，我们用k表示QZ(o)的总数，这也意味一个QZ(o)会代表数据库中的多个数据向量。 此时，我们不再存储数据向量o，而是存储它的代表QZ(o)的ID，如此一来原本用d个数字表示的数据向量，现在变为用1个数字表示的代表ID。这样一来，我们不再计算Dist(o, q)，而是计算Dist(QZ(o), q)，总共只需要计算k次距离，大大压缩了计算量。

当然，这样地提升，建立在我们挑选的代表QZ(o)足够的好。现在，我们来看如何选择代表QZ(o)。指派代表本质上是一个分区问题或者说聚类问题，我们要把有n个对象的数据集分割为k个聚类（Cluster）代表QZ(o)就是o所在Cluster的Center。这样一来，如何衡量代表的好坏就很明显了，与一般的聚类问题一样，我们只需要关注两个指标：

1. 类内方差足够小：同类足够相似
   
2. 类间方差足够大：不同类之间足够有区分度

换言之，我们想要最小化：E [( d(QZ(o), q) - d(o, q) )²]。同时，根据三角不等式，我们可以知道：E [( d(QZ(o), q) - d(o, q) )²] ≤ E[d(QZ(o) , q)²]

聚类算法想必大家都已经在ML中有所学习了，所以这里不再做介绍，在这里，我们默认使用的聚类算法为K-means（K均值聚类）。在进行聚类之后，我们创建一个Codebook W，用来记录所有聚类的中心（Center），即W = {c₁, c₂, , c₃, …, c_k}，这时数据库中的所有对象/数据向量o都被分配给距它最近的c_i

现在我们来看如何进行查询，在这个问题中也就是给定一个查询数据（Query）q，我们怎么去找距它最近的数据点/数据向量。

1. 首先找到距离q最近的代表QZ(q)（即c₁, c₂, , c₃, …, c_k）
2. 因为我们知道，每个QZ(q)代表多个数据库中的对象o，所以我们要找到这些与QZ(q)相关联的对象（可以用哈希表，键为c_i，值为与其关联的o的列表），把它们放在一个候选集合（Candidate Set）C中
3. 计算q与所有o ∈ C的距离，选择最近的结果

可以看到该方法可以大幅压缩计算量，但是它也存在一定的局限性。我们想用该方法取得高准确率的结果时，就需要一个比较大的k值（代表QZ(o)的总数）。但是一旦k的值很大，K-Mean Cluster算法运行代价就会比较高，而且我们在计算QZ(q)时的计算量也会比较大。

为了避免这个问题，我们采用Product Quantization（积量化）

积量化的基本思想是对数据向量进行维度分割（Partition the dimension），在维度上将向量分割为m个子向量（Subvector）。比如，一个数据向量 α = (1, 2, 3, 4, 5, 6, 7, 8) 共有8个维度，现在，我们将它分割为 m = 2 个子向量，即被分为 α₁ = (1, 2, 3, 4)，α₂ = (5, 6, 7, 8)。这里再给一个比较直观的例子：

然后，我们对每一个分块用k个Codewords来表示。这里我们对每个分块用4个Codeword表示，实际上就是将原8维数据向量分割为两个4维向量，然后再这两个四维空间中做4均值聚类，每个四维空间得到4个centers（从0到3）：

然后，从中选择最近的c_i,j作为代表，因为每个分块有4个Codeword，且技术从0开始，因此用2bits二进制数表示时，从00开始：

我们在计算Query q和数据点a（编码为t）的距离时，要根据t重构向量p，再进行计算

所以整体查询的流程如下所示：

计算每个数据向量和q的距离，再选距离最小的一个。

整体的流程如下：

最后

以上就是迅速花生为你收集整理的Big Data Management笔记03：High Dimensional Similarity SearchSimilarity Search（相似度搜索）Low Dimensional Similarity Search（低维相似度搜索）High Dimensional Similarity Search（高维相似度搜索）的全部内容，希望文章能够帮你解决Big Data Management笔记03：High Dimensional Similarity SearchSimilarity Search（相似度搜索）Low Dimensional Similarity Search（低维相似度搜索）High Dimensional Similarity Search（高维相似度搜索）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。