AKNN-Qalsh: PostgreSQL系统高维空间近似最近邻检索插件*

张楚涵，张家侨, 冯剑琳

(中山大学数据科学与计算机学院，广东 广州 510006)

最近邻检索是数据库研究的重要问题之一，即查找在数据库D中与查询对象距离最近的数据对象。在数据库中进行图片相似性搜索、文本相似性搜索、地理空间位置比较等查询，本质上都是要解决最近邻检索问题。

PostgreSQL作为业界内第一个吸纳KNN(K-nearest neighbor，K最近邻)技术的数据库系统[1]，为用户提供了KNN-Gist索引来解决最近邻检索问题，但KNN-Gist索引仅适用于如地理信息等低维数据。例如，基于KNN-Gist索引实现的图片相似性检索的插件ImgSmlr[2]，也只能利用低维的图片签名，通过图片的全局特征进行相似性检索，无法直接利用高维特征向量进行相似性检索，当需要避免图片尺度变化对图片相似性检索的影响时，ImgSmlr无法胜任基于尺度不变特征变换(SIFT)的检索[3]。此外，PostgreSQL还拥有开源的字符串相似性检索插件pg_trgm[4]，它通过测定字母数字文本基于三元模型匹配的相似性进行检索，适用于较小规模文本、字符串等数据。一般情况下，图片、视频、文本等信息的特征向量的维度较高，目前，PostgreSQL中还没有针对高维数据的最近邻检索的扩展。因此，我们希望为PostgreSQL数据库系统设计并实现一个高效的、支持大规模、高维度数据的最近邻检索插件。该插件可以作为一个最近邻检索模块，与图片、文本或视频等复杂数据对象的特征提取模块组合，在数据库中实现基于高维特征向量的图片、文本相似性检索。

现有的可以精确找到查询对象的最近邻的数据结构，如KNN-Gist所使用的树结构的检索性能会随着数据对象维度的升高而急剧下降。在向量维度大于10之后，其性能甚至会低于暴力地线性检索[5]。 而在很多实际应用场景中，往往不需要检索查询对象绝对精确的最近邻。这使得我们可以一定程度上通过降低检索精度来提高检索速度，将最近邻检索问题转化为近似最近邻检索问题再求解：若查询对象q与其精确最近邻o*的距离为r*，那么，c-近似最近邻检索就是要找出q的近似最近邻o，使得q与o的距离小于r*的c倍，其中c为近似比例，且c>1。

位置敏感哈希(Locality-Sensitive Hashing，简称LSH)机制[6]及其变体[7-10]是目前解决高维空间中近似最近邻检索问题最有效的手段。位置敏感哈希的基本思想是：如果两个高维特征向量的距离较小，那么，它们就会以较大的概率被哈希到同一个桶中。位置敏感哈希的一个新变体，QALSH机制[11-12]，是目前业界领先的、有理论保证的高维空间近似最近邻检索方法。

与KNN-Gist索引基于树结构的最近邻检索机制不同，QALSH机制通过解决一系列给定查询半径的近似最近邻检索问题来求解查询对象的近似最近邻：可以发现，c-近似最近邻问题的检索半径依赖于r*，而r*无法事先确定，因此，近似最近邻检索问题无法直接求解。需要将c-近似最近邻问题转化为一系列检索半径r确定的(依次取值1,c1,c2,c3,)近似最近邻检索问题，(r,c)-近似最近邻检索：对于给定的检索半径r和查询对象q返回一个数据对象使得q到该数据对象的距离小于或等于cr。

QALSH机制针对外存设计，能够更好地与数据库系统相结合。并且，QALSH机制查询引导的分桶策略和虚拟再哈希技术，使得我们可以在大数据集上进行任意检索半径r的(r,c)-近似最近邻检索。

本文所描述的近似最近邻检索插件AKNN-Qalsh就是基于QALSH机制设计并实现的。QALSH机制的检索性能基本不受数据维度的影响，这一性质使得AKNN-Qalsh为PostgreSQL提供了高效的针对高维空间的最近邻检索功能具有如下特点：

1) 支持大规模、高维数据对象的最近邻检索

2) 通用性：可以与图像、文本、视频等各种多媒体数据的特征提取模块相结合，解决多种数据对象的最近邻检索问题；

3) 检索速度快：检索速度远低于线性检索；

4) 检索精度高：检索精度在用户可接受范围内，且接近线性检索结果，有理论保证；

5) 检索效率稳定：其检索效率受数据维度影响极小；

6) 使用方便：用户通过直接调用相应的函数方法即可在数据库中实现数据预处理或近似最近邻检索。

1 AKNN-Qalsh的设计与实现

图1给出了利用AKNN-Qalsh插件进行近似最近邻检索的流程，包含预处理和查询两个阶段：在预处理阶段需要在PostgreSQL中构建关系表；在查询阶段，根据关系表中的信息检索查询对象的近似最近邻。

1.1 数据表

在PostgreSQL数据库中，数据集中的数据对象和查询对象分别存放在图2所示的data表和query表中，表中每一行由对象的id和其向量坐标(coordinate)构成。另外，需要在data表的id列上建立Hash索引，使得检索时能够在data表中能够快速地根据id值取得对应的向量坐标。

1.2 预处理阶段

1.2.1 参数表 QALSH机制需要预先根据数据集中数据对象的个数n、用户规定的近似比例c等参数，确定最近邻检索所需的哈希表个数m以及碰撞阈值l等参数，这些参数均需要保存在param表中以记录该数据集的信息。

图1 AKNN-Qalsh插件整体概述Fig.1 Overview of AKNN-Qalsh

图2 AKNN-Qalsh插件中的关系表Fig.2Tables of AKNN-Qalsh

表1 param表字段Table 1 Fields of paramTable

为了保证QALSH机制在检索阶段对哈希表的范围查询可以高效地完成，需要为每一个哈希表的哈希值的列利用B+树进行索引。PostgreSQL系统提供的B-Tree索引结构是根据B+树的一种变体，Blink-树来实现的[13]，恰好可以满足这一需求。因此，我们直接利用PostgreSQL提供的B-Tree索引为哈希表建立索引，使得AKNN-Qalsh与PostgreSQL系统更好地耦合。

值得注意的是，这种直观的哈希表结构在索引过程中将会暴露出缺陷。在实际应用场景下，数据集中数据对象的个数n值可能很大，直接对哈希表中的哈希值列建立B-Tree索引时得到的索引结构比较庞大，而庞大的索引结构将会导致非常可观的空间开销。并且，由于事先并未对哈希表中的数据对象根据其哈希值进行排序便建立索引，在数据库中，若对该列进行范围查询，则其索引指向的表元组是分散在堆文件不同页面中的，连续性很差。也就是说，通过范围查询获取满足条件的元组时，会发生堆文件页面的跳跃，引起随机I/O，也就增加了索引查询的时间开销。另外，由于PostgreSQL中B-Tree索引结构的一个索引元组指向一个索引页面或表元组。因此，一个叶子节点索引的数据对象非常有限。当利用B-Tree索引进行范围查询时，如果满足条件的数据对象较多时，需要读取的叶子节点也比较多，也会引起读取索引时的I/O增加，增加索引扫描的时间开销。为了解决上述的几个问题，可以设计一种新的哈希表结构。

对于索引时页面跳跃引起随机I/O的问题，通过事先对哈希表中的数据对象按照其哈希值进行排序来解决。而针对B-Tree索引结构庞大的问题，在利用QALSH机制进行最近邻检索时，并不需要粒度(即每个叶子节点中的一个索引元组索引的数据对象个数)为1的B-Tree索引结构。因此，可以通过调整B-Tree索引的粒度来控制B-Tree索引的大小。考虑预先对哈希表中的数据对象进行聚簇，设定每个簇中含有的数据对象个数为h，我们称其为簇的容量。每一个簇的代表哈希值为该簇中所有数据对象哈希值的最小值，再以簇为最小单位建立索引，索引的键即为簇的代表哈希值，索引的值即为簇中数据对象的id。

上述的聚簇策略，在降低树结构的深度的同时，也解决了满足范围查询条件的数据对象较多时，需要读取较多个叶子节点的问题：如果某次范围检索中满足条件的数据对象有2 000个，假设B-Tree索引的一个页面中可以存放100个索引元组，新的哈希索引结构只需要读取1个索引叶子页面即可取到所有满足条件的数据对象，而没有经过聚簇的哈希表结构则需要读取20个索引叶子页面。由此可见，新的哈希表结构可以减少索引结构的空间开销，更重要的是，可以显著提升索引效率。

1.3 查询阶段

图3 KNN检索中的半径更新与虚拟再哈希Fig.3 Radius update and Virtual Rehashing

图3为检索过程中，以某一哈希表为例的半径更新与虚拟再哈希的示例，其中阴影部分代表每轮检索的查询范围。

AKNN-Qalsh插件在实现基于B-Tree索引的范围查询时，利用了PostgreSQL系统提供的一系列索引操作方法，如index_beginscan等，而不是简单地通过其提供的SPI(server programming interface，即服务器编程接口)，直接利用SQL语句进行查询。做到了与PostgreSQL系统的紧密结合，从而进一步提升了检索效率。

1.4 增、删、改功能

为了更加贴合数据库扩展应用的需求，AKNN-Qalsh插件还支持增、删、改三个数据库基本操作。如实现向数据集和或查询集中增加对象的操作，需要将新的对象添加到相应数据表、计算其哈希值并更新哈希表。还需要注意param表中的参数的变化，如数据对象个数n增加等。同样地，删除、修改操作与插入操作类似，都需要更新PostgreSQL中相应的关系表。

1.5 用户接口

前文描述了AKNN-Qalsh插件在运行时生成的数据库表的结构、预处理部分和查询部分的实现、以及增删改三个基本操作的实现。我们希望用户在使用AKNN-Qalsh插件时，不需要理解或记忆这些实现细节。因此，我们为用户提供了方便的用户接口如表2所示。

表2 用户接口Table 2 The interface functions of AKNN-Qalsh

2 实 验

2.1 数据集

本文中将利用Mnist[注]http:∥yann.lecun.com/exdb/mnist、Sift和Gist[注]http:∥corpus-texmex.irisa.fr/、LabelMe[注]http:∥labelme.csail.mit.edu/Release3.0/、P53[注]http:∥archive.ics.uci.edu/ml/datasets/P53+Mutants五个数据集进行实验，数据集的信息以及其对应的查询集信息如表3所示，n记录了数据集中数据对象的个数，d表示数据对象的维度，查询集中查询对象的个数为qn。

2.2 性能评测指标

本文以运行时间和平均总体比率作为对比实验的评估度量，来评估该近似最近邻检索扩展程序的性能。两种度量方式的定义如下。

2.2.1 运行时间(running time) 运行时间记为检索一个查询对象q的k个近似最近邻所用的时间，对数据集和查询集的预处理时间不计入在内。本实验中统计了检索100个查询对象的k近似最近邻所用时间的平均值，并以此作为度量。

表3 数据集信息Table 3 The information of dataset

2.3 对比实验

由于目前PostgreSQL中还没有针对高维空间的近似最近邻检索方法，我们将本文所述的近似最近邻检索扩展程序与最基本的线性检索进行比较。线性检索计算查询对象与每个数据对象之间的距离，从而找到精确的最近邻，在实验中简记为Linear。

对于不同数据集，我们均将参数c设置为2.0，参数h统一设置为200。AKNN-Qalsh插件的检索时间开销与线性检索的时间开销、检索精度比较如图4、5所示。可以发现，AKNN-Qalsh插件的检索速度远高于线性检索方法，且其近似检索精度的损失在可接受范围内。面对大规模、高维度的数据集时，线性检索的时间开销非常大，利用线性检索在Gist数据集中获取一个查询对象的Top-100个最近邻需要近60 s的时间，而利用AKNN-Qalsh插件仅需要1 s。且其查询结果的平均总体比率大约为1.07。说明AKNN-Qalsh插件可以在短时间内获取查询对象的近似最近邻结果，还保证了较高的精确度。

图4 AKNN-Qalsh插件与线性检索的检索时间比较Fig.4 The search time of Linear and AKNN-Qalsh

图5 AKNN-Qalsh插件与线性检索的检索精度比较Fig.5 The overall ratio of Linear and AKNN-Qalsh

其实，不同的h值会影响AKNN-Qalsh插件的检索性能。当h值较小时，B-Tree索引的粒度相对较小时，B-Tree索引结构较庞大，最近邻检索的时间开销将会很高；h值过大时，B-Tree的索引粒度过大，起不到索引效果，检索精确度将降低。因此，我们需要为AKNN-Qalsh插件选择恰当的h值。上述对比实验中，针对不用的数据集，统一设定了簇的容量为200，是比较好的折中。

3 结 论

本文详述了PostgreSQL系统近似最近邻检索插件AKNN-Qalsh的设计与实现。该插件借助PostgreSQL数据库的B-Tree索引与Hash索引、以及统一的索引扫描接口，可以高效地支持近似最近邻检索。通过真实数据集上的密集实验，我们展示了插件检索准确率高、检索速度快的特点。