基于SQL的度量空间数据相似度查询方法及装置

摘要

本发明提供一种基于SQL的度量空间数据相似度查询方法及装置，通过对数据集进行分区处理，每个分区中包含数据对象和参考点；根据参考点确定分区内每个数据对象与参考点之间的第一距离；根据第一距离，确定每个数据对象的索引结构。根据查询请求中的查询对象确定查询对象与每个分区内参考点之间的第二距离，并根据第二距离和预设距离阈值，确定查询对象在每个所述分区内的查询范围；在数据对象的索引结构内确定与每个所述分区内的查询范围对应的目标数据对象。本发明可基于SQL技术的数据库来实现度量空间数据相似度查询，以提高对该RDBMS数据库相似度查询的适用性和性能。

说明书

技术领域

本发明涉及数据处理技术领域，尤其涉及一种基于SQL的度量空间数据相似度查询方法及装置。

背景技术

相似度查询是通过给定数据集R、查询对象q、相似度函数和用户指定阈值θ，从而在数据集R中找出与查询对象q的距离小于等于用户指定阈值θ的所有数据对象r，即认为数据对象r与查询对象q相似。相似度查询的应用可遍及各个领域，包括人脸识别、指纹识别、空间位置查询、文本纠错、模式识别(如DNA或蛋白质序列)等。而随着数据集中数据量的快速增长及数据类型呈现出的多样性发展趋势，目前相似度查询针对的对象从早期的欧几里得空间的维度数据、文本空间的字符串数据，延伸到目前比较通用的不限于某个数据类型的度量空间数据，度量空间下的数据集中任意元素之间的距离是可定义的。

由于关系数据库管理系统(Relational Database Management System，简称RDBMS)可以提供统一的结构化查询语言(Structured Query Language，简称SQL)技术，还可结合其他查询条件过滤数据，同时数据库本身支持数据更新，所以利用RDBMS进行度量空间数据相似度查询可大大提高查询的性能。但是，现有的度量空间数据相似度查询方法通常是针对特定的应用领域建立新型的索引结构，并基于构建的索引结构进行相似度查询。但是这些新型的索引结构与RDBMS中支持的索引结构类型不匹配，即RDBMS中的索引结构无法识别这些新型索引的格式，因此也就无法借助RDBMS强大的数据管理功能实现度量空间数据的相似度查询，导致查询效率低。

因此，亟需一种对基于SQL技术的数据库，如RDBMS来实现度量空间数据相似度查询的方法，以提高对该RDBMS数据库相似度查询的适用性和性能。

发明内容

本发明提供一种基于SQL的度量空间数据相似度查询方法及装置，以解决现有技术中度量空间数据相似度查询方法构建的索引结构与RDBMS中支持的索引结构类型不匹配的问题，以实现基于SQL技术的数据库来实现度量空间数据相似度查询的方法，以提高对该RDBMS数据库相似度查询的适用性和性能。

本发明第一个方面提供一种基于SQL的度量空间数据相似度查询方法，包括：

对数据集进行分区处理，得到多个分区；其中，每个分区中包含：数据对象，参考点；

根据所述参考点，确定分区内每个数据对象与参考点之间的第一距离；

根据所述第一距离，确定每个数据对象的索引结构；

接收用户的查询请求，所述查询请求中包括查询对象、查询对象与目标数据对象之间的预设距离阈值；

确定所述查询对象与每个分区内参考点之间的第二距离，并根据所述第二距离、所述预设距离阈值，确定查询对象在每个所述分区内的查询范围；

在每个分区的所述查询范围内，根据所述查询范围内的数据对象的索引结构，确定与所述查询对象对应的目标数据对象。

在本发明一实施例中，上述对数据集进行分区处理，得到多个分区，包括：

在数据集中，确定每个数据对象与每个参考点之间的距离；

将每个参考点对应的与其距离最小的数据对象划分为一个分区，得到与考点数目相匹配的多个分区。

在本发明一实施例中，上述根据所述第一距离，确定每个数据对象的索引结构，包括：

根据所述第一距离的大小关系，确定数据对象的排序规则；

根据所述第一距离、所述排序规则，确定每个数据对象的索引结构。

在本发明一实施例中，上述根据所述第二距离、所述预设距离阈值，确定查询对象在每个所述分区内的查询范围，包括：

根据所述第二距离与所述预设距离阈值之和，确定所述查询范围的上限值；

根据所述第二距离与所述预设距离阈值之差，确定所述查询范围的下限值。

在本发明一实施例中，上述确定所述查询对象与每个分区内参考点之间的第二距离之后，还包括：根据所述查询对象与每个分区内参考点之间的第二距离，获取所述第二距离的最小值；

相应的，所述根据所述第二距离与所述预设距离阈值之和，确定所述查询范围的上限值，包括：

根据所述第二距离的最小值与所述预设距离阈值之和，确定所述查询范围的上限值。

本发明另一个方面提供一种基于SQL的度量空间数据相似度查询装置，包括：分区模块、第一确定模块、构建模块、接收模块、第二确定模块、查询模块；

其中，所述分区模块，用于对数据集进行分区处理，得到多个分区；其中，每个分区中包含：数据对象，参考点；

所述第一确定模块，用于根据所述参考点，确定分区内每个数据对象与参考点之间的第一距离；

所述构建模块，用于根据所述第一距离，确定每个数据对象的索引结构；

所述接收模块，用于接收用户的查询请求，所述查询请求中包括查询对象、查询对象与目标数据对象之间的预设距离阈值；

所述第二确定模块，用于确定所述查询对象与每个分区内参考点之间的第二距离，并根据所述第二距离、所述预设距离阈值，确定查询对象在每个所述分区内的查询范围；

所述查询模块，用于在每个分区的所述查询范围内，根据所述查询范围内的数据对象的索引结构，确定与所述查询对象对应的目标数据对象。

在本发明一实施例中，上述分区模块包括：第一确定单元、划分单元；

其中，所述第一确定单元，用于在数据集中，确定每个数据对象与每个参考点之间的距离；

所述划分单元，用于将每个参考点对应的与其距离最小的数据对象划分为一个分区，得到与考点数目相匹配的多个分区。

在本发明一实施例中，上述构建模块包括：第二确定单元、第三确定单元；

其中，所述第二确定单元，用于根据所述第一距离的大小关系，确定数据对象的排序规则；

所述第三确定单元，用于根据所述第一距离、所述排序规则，确定每个数据对象的索引结构。

在本发明一实施例中，上述第二确定模块包括：第四确定单元、第五确定单元；

其中，所述第四确定单元，用于根据所述第二距离与所述预设距离阈值之和，确定所述查询范围的上限值；

所述第五确定单元，用于根据所述第二距离与所述预设距离阈值之差，确定所述查询范围的下限值。

在本发明一实施例中，上述第二确定模块还包括：获取单元；

所述获取单元，用于根据所述查询对象与每个分区内参考点之间的第二距离，获取所述第二距离的最小值；

相应的，所述第四确定单元，还用于根据所述第二距离的最小值与所述预设距离阈值之和，确定所述查询范围的上限值。

由上述技术方案可知，本发明提供的基于SQL的度量空间数据相似度查询方法及装置，通过对数据集进行分区处理，得到多个分区，每个分区中包含：数据对象，参考点；根据所述参考点，确定分区内每个数据对象与参考点之间的第一距离；根据所述第一距离，确定每个数据对象的索引结构；接收用户的查询请求，所述查询请求中包括查询对象、查询对象与目标数据对象之间的预设距离阈值；确定所述查询对象与每个分区内参考点之间的第二距离，并根据所述第二距离、所述预设距离阈值，确定查询对象在每个所述分区内的查询范围；在每个分区的所述查询范围内，根据所述查询范围内的数据对象的索引结构，确定与所述查询对象对应的目标数据对象。本发明可基于SQL技术的数据库来实现度量空间数据相似度查询，以提高对该RDBMS数据库相似度查询的适用性和性能。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为本发明一实施例提供的基于SQL的度量空间数据相似度查询方法的流程示意图；

图2为本发明一实施例中数据集分区的示意图；

图3为本发明另一实施例提供的基于SQL的度量空间数据相似度查询方法的流程示意图；

图4为本发明又一实施例提供的基于SQL的度量空间数据相似度查询方法的流程示意图；

图5为本发明一实施例提供的基于SQL的度量空间数据相似度查询装置的结构示意图；

图6为本发明另一实施例提供的基于SQL的度量空间数据相似度查询装置的结构示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

实施例一

本实施例提供一种基于SQL的度量空间数据相似度查询方法，如图1所示，该方法可以包括：

步骤101，对数据集进行分区处理，得到多个分区；其中，每个分区中包含：数据对象，参考点；

由于度量空间下的数据类型多样化且数据量巨大，为提高查询效率可以采用对数据库中的所有数据进行划分的预处理方法，将数据分为多个分区。度量空间下的所有数据构成数据集，对数据集进行划分后的每个分区包含用于识别该分区的分区序号，每个分区中还包含至少一个参考点和至少一个数据对象。

具体的，如图2所示，可以在数据集中任意选取多个对象作为参考点，将数据空间划分为与参考点个数相同的多个不相交的分区，其中，参考点可以用p_i表示，其中i为用于标识每个分区的分区序号，i＝1，2，3，4，5。每个分区中的数据对象的确定方式可以有多种方式，举例来说，可以根据数据集中除参考点外剩余的数据对象数量，将数据对象按数量平均划分给多个参考点；也可以根据数据对象到参考点的距离，将到参考点的距离在预设范围内的数据对象划分给每一个参考点。

步骤102，根据参考点，确定分区内每个数据对象与参考点之间的第一距离；

由于数据集中数据对象的类型具有多样性，每个数据对象都具有其原始属性，可以将数据对象添加一个新的属性值，用于在之后的相似度查询中标识数据对象。具体的，可以在每一个分区中，根据参考点，确定每一个数据对象到参考点之间的距离，即第一距离。第一距离可以用于标识每个数据对象，具体的，第一距离包括数据对象所在分区的分区序号信息、数据对象到数据对象所在分区的参考点之间的距离信息。

举例来说，在数据集中获取一个数据对象r，无论该数据对象r的原始属性为字符串数据、图像数据或是其他任意一种类型，为该数据对象r添加一个新的属性值，属性值为该数据对象r到其所在分区i内的参考点p_i的距离，即第一距离。则第一距离可以表示为：<i,|r,p_i|>。

步骤103，根据第一距离，确定每个数据对象的索引结构；

在确定每个数据对象的第一距离之后，可以以第一距离作为数据对象的属性值来构建索引结构,具体的索引结构可以采用B+树索引。

步骤104，接收用户的查询请求，查询请求中包括查询对象、查询对象与目标数据对象之间的预设距离阈值；

本实施例提供的基于SQL的度量空间数据相似度查询方法，为用户提供一种用户自定义函数作为查询接口，即用户在发送查询请求时，只需要提交SQL语句即可。SQL语句中需要包括数据集名称、查询对象、查询对象与目标数据对象之间的预设距离阈值，以在数据集中找出与查询对象的距离小于等于预设距离阈值的所有数据对象，即认为数据对象与查询对象相似。

步骤105，确定查询对象与每个分区内参考点之间的第二距离，并根据第二距离、预设距离阈值，确定查询对象在每个分区内的查询范围；

由于每个数据对象被转化为以第一距离来表示的数据，因此如果需要利用SQL语句实现相似度查询，需要将查询对象也对应转化为以查询对象与每个分区内参考点之间的距离来表示的数据。

具体的，由于查询对象是用户给定的，每个分区内的参考点也是确定的，因此可以确定查询对象与每个分区内参考点之间的距离，即第二距离。根据分区的不同，查询对象到不同分区内参考点之间的距离也不同。

将查询对象转化为以第二距离来表示的数据之后，需要根据第二距离、预设距离阈值，确定查询对象在每个分区内的查询范围。

具体的，由于确定数据对象与查询对象相似的必要条件为：数据对象到查询对象的距离小于等于预设距离阈值，该必要条件可以用公式一表示：

公式一：|p_i,q|-θ≤|p_i,r|≤|p_i,q|+θ；

其中，p_i为参考点；i为分区序号；q为查询对象；θ为预设距离阈值；r为数据对象。

在确定查询对象q到不同分区i内参考点p_i之间的第二距离|p_i,q|后，根据公式一可以确定在不同分区i内|p_i,r|应该满足的范围区间，而|p_i,r|表示的含义为分区i内数据对象到参考点p_i的距离，由此可以确定查询对象在每个分区内的查询范围。

举例来说，若确定在分区1中|p₁,q|为10，则可以确定查询对象在分区1内的查询范围为[10-θ，10+θ]；若在分区2中|p₂,q|为15，则可以确定询对象在分区2内的查询范围为[15-θ，15+θ]，以此方式可以获取多个查询范围。

步骤106，在每个分区的查询范围内，根据查询范围内的数据对象的索引结构，确定与查询对象对应的目标数据对象。

由于索引结构是根据第一距离构建的，第一距离用于表示分区内数据对象到参考点的距离，而查询范围也是表示分区内数据对象到参考点的距离的区间范围，因此在确定每个分区的查询范围后，在索引结构中以查询范围为查询条件，可以查询出每个分区中到参考点的距离满足查询范围的数据对象，将每个分区中查询出的数据对象取并集获取目标数据对象。

本实施例提供的基于SQL的度量空间数据相似度查询方法，通过对数据集进行分区处理，得到多个分区，每个分区中包含：数据对象，参考点；根据参考点，确定分区内每个数据对象与参考点之间的第一距离；根据第一距离，确定每个数据对象的索引结构；接收用户的查询请求，查询请求中包括查询对象、查询对象与目标数据对象之间的预设距离阈值；确定查询对象与每个分区内参考点之间的第二距离，并根据第二距离、预设距离阈值，确定查询对象在每个分区内的查询范围；在每个分区的查询范围内，根据查询范围内的数据对象的索引结构，确定与查询对象对应的目标数据对象。本实施例可基于SQL技术的数据库来实现度量空间数据相似度查询，以提高对该RDBMS数据库相似度查询的适用性和性能。

实施例二

本实施例提供一种基于SQL的度量空间数据相似度查询方法，如图3所示，该方法可以包括：

步骤201，在数据集中，确定多个参考点；

在数据集中确定参考点的方式可以有多种，举例来说，可以根据数据集中除参考点外剩余的数据对象数量，将数据对象按数量平均划分给多个参考点；也可以根据数据对象到参考点的距离，将到参考点的距离在预设范围内的数据对象划分给每一个参考点。

由于参考点和数据对象的分布不规则，参考点的选取结果影响着每一分区内的数据对象的数量及每个数据对象到参考点的距离。因此，参考点选择的优劣直接影响到相似度查询的性能。

因此，本实施例中在数据集中确定多个参考点，可以包括：

给定一个查询集，查询集中每个查询对象是已知的，因此，查询对象与数据集中的每个数据对象的距离是可以获知的。同时，一个理想的参考点选取条件可以包括以下两方面：(1)距离该点最近的查询对象的数量应尽量多；(2)每个查询对象到该点的距离总和应尽量小。

根据以上两个选取条件，在查询集和数据集共同构成的数据集合中，根据公式二获取每一个数据对象的参考值score(r)，并根据参考值的大小，选择参考值score(r)最大的多个数据对象作为多个参考点。

公式二：

其中，score(r)为数据对象的参考值；为距离该数据对象最近的查询对象的数量；为距离该数据对象最近的查询对象的数量的最大值，且其中r为数据对象，R为数据集，Q为查询集；为距离该数据对象最近的查询对象的数量的最小值，且其中r为数据对象，R为数据集，Q为查询集；AVG(r)为每个查询对象到该数据对象的距离总和的平均值，且其中，q为查询对象，为距离该数据对象最近的查询对象构成的集合，r为数据对象，为距离该数据对象最近的查询对象的数量；AVG_max为每个查询对象到该数据对象的距离总和的平均值的最大值，且AVG_max＝max_r∈(R∪Q)AVG(r)，其中r为数据对象，R为数据集，Q为查询集；AVG_min每个查询对象到该数据对象的距离总和的平均值的最小值，且AVG_min＝min_r∈(R∪Q)AVG(r)，其中r为数据对象，R为数据集，Q为查询集。

步骤202，确定每个数据对象与每个参考点之间的距离；

为了对每个数据进行划分，在确定参考点之后，需要确定数据集中每个数据对象与每个参考点之间的距离。

步骤203，将每个参考点对应的与其距离最小的数据对象划分为一个分区，得到与参考点数目相匹配的多个分区，其中，每个分区中包含：数据对象，参考点；

确定数据集中每个数据对象与每个参考点之间的距离之后，将每个参考点对应的与其距离最小的数据对象划分为一个分区。即比较每个数据对象与不同参考点之间的距离的大小关系，确定与每个数据对象距离最近的参考点，将每个数据对象划入与其距离最小的参考点所在的分区。

举例来说，已知数据集中共有M个参考点p₁、p₂……p_M，数据对象x到参考点p₁的距离为1，且数据对象x到其他参考点p₂……p_M的距离均大于1；而数据对象y到参考点p₂的距离为1，且数据对象x到其他参考点p₁、p₃……p_M的距离均大于1，则将数据对象x与参考点p₁划入同一个分区，将数据对象y与参考点p₂划入同一个分区。根据此方法得到与参考点数目相匹配的多个分区，其中，每个分区中包含至少一个数据对象和至少一个参考点。

通过将数据集中的数据对象进行分区，并为每一个分区设置一个参考点，实现了对数据对象的分区处理，提高相似度查询的效率。

步骤204，根据参考点，确定分区内每个数据对象与参考点之间的第一距离；

由于数据集中数据对象的类型具有多样性，每个数据对象都具有其原始属性，可以将数据对象添加一个新的属性值，用于在之后的相似度查询中标识数据对象。具体的，可以在每一个分区中，根据参考点，确定每一个数据对象到参考点之间的距离，即第一距离。第一距离可以用于标识每个数据对象，具体的，第一距离包括数据对象所在分区的分区序号信息、数据对象到数据对象所在分区的参考点之间的距离信息。

举例来说，在数据集中获取一个数据对象r，无论该数据对象r的原始属性为字符串数据、图像数据或是其他任意一种类型，为该数据对象r添加一个新的属性值，属性值为该数据对象r到其所在分区i内的参考点p_i的距离，即第一距离。则第一距离可以表示为：<i,|r,p_i|>。

通过对数据对象增加一个新的属性值：第一距离，使得将度量空间下的各种类型的数据对象格式统一化，提高更新和维护数据对象的效率和便捷性，同时使其适用于基于SQL技术的数据库。

步骤205，根据第一距离的大小关系，确定数据对象的排序规则；

由于第一距离可以表示为：<i,|r,p_i|>，其中i为分区序号，|r,p_i|为，数据对象r到其所在分区i内的参考点p_i的距离。将第一距离简化表示为：<i_i,d_i>，因此任意给出两个数据对象的第一距离<i₁,d₁>和<i₂,d₂>，可以确定数据对象的排序规则为：

当i₁>i₂，或i₁＝i₂且d₁>d₂时，<i₁,d₁>><i₂,d₂>；

当i₁＝i₂且d₁＝d₂时，<i₁,d₁>＝<i₂,d₂>；

否则，<i₁,d₁><<i₂,d₂>。

步骤206，根据第一距离、排序规则，确定每个数据对象的索引结构；

当确定了所有数据对象的第一距离后，根据排序规则可以将所有数据对象的第一距离按照分区序号的大小和数据对象到其所在分区内的参考点的距离大小进行排序，进而可以根据第一距离和排序规则确定每个数据对象的索引结构。具体的，索引结构可以按照分区序号的大小顺序和数据对象到其所在分区内的参考点的距离大小进行升序排序或降序排序。同时，索引结构中每个分区中的数据对象的第一距离的范围是连续的且形成一个范围区间。因此采用本实施例中的索引结构，当在一个分区中查询对应的数据对象的第一距离时，能够有针对性的访问指定分区对应的索引页，而不会访问到剩余索引页中其他分区的第一距离数值，避免了不必要的数据传输和处理器冗余计算量，提高相似度查询的效率和准确性。

通过根据数据对象的第一距离，确定每个数据对象的索引结构，使得索引的表示方式与数据对象的原始属性无关，因此提高了数据库中数据对象存储的紧凑性。同时由于索引的表示方式为具体的数值，使得索引的更新和维护更加便捷，在使用索引扫描时加快相似度查询处理速度，整体提高相似度查询的性能。

步骤207，接收用户的查询请求，查询请求中包括查询对象、查询对象与目标数据对象之间的预设距离阈值；

本实施例提供的基于SQL的度量空间数据相似度查询方法，为用户提供一种用户自定义函数作为查询接口，即用户在发送查询请求时，只需要提交SQL语句即可。SQL语句中需要包括数据集名称、查询对象、查询对象与目标数据对象之间的预设距离阈值，以在数据集中找出与查询对象的距离小于等于预设距离阈值的所有数据对象，即认为数据对象与查询对象相似。

步骤208，确定查询对象与每个分区内参考点之间的第二距离，并根据第二距离、预设距离阈值，确定查询对象在每个分区内的查询范围；

由于每个数据对象被转化为以第一距离来表示的数据，因此如果需要利用SQL语句实现相似度查询，需要将查询对象也对应转化为以查询对象与每个分区内参考点之间的距离来表示的数据。

具体的，由于查询对象是用户给定的，每个分区内的参考点也是确定的，因此可以确定查询对象与每个分区内参考点之间的距离，即第二距离。根据分区的不同，查询对象到不同分区内参考点之间的距离也不同。

将查询对象转化为以第二距离来表示的数据之后，需要根据第二距离、预设距离阈值，确定查询对象在每个分区内的查询范围。

可选的，根据第二距离、预设距离阈值，确定查询对象在每个分区内的查询范围，具体包括：

根据第二距离与预设距离阈值之和，确定查询范围的上限值；同时，根据第二距离与预设距离阈值之差，确定查询范围的下限值。

具体的，由于确定数据对象与查询对象相似的必要条件为：数据对象到查询对象的距离小于等于预设距离阈值，该必要条件可以用公式一表示：

公式一：|p_i,q|-θ≤|p_i,r|≤|p_i,q|+θ；

其中，p_i为参考点；i为分区序号；q为查询对象；θ为预设距离阈值；r为数据对象。

在确定查询对象q到不同分区i内参考点p_i之间的第二距离|p_i,q|后，根据公式一可以确定在不同分区i内|p_i,r|应该满足的范围区间，而|p_i,r|表示的含义为分区i内数据对象到参考点p_i的距离，由此可以确定查询对象在每个分区内的查询范围。

举例来说，若确定在分区1中|p₁,q|为10，则可以确定查询对象在分区1内的查询范围为[10-θ，10+θ]；若在分区2中|p₂,q|为15，则可以确定询对象在分区2内的查询范围为[15-θ，15+θ]，以此方式可以获取多个查询范围。

步骤209，在每个分区的查询范围内，根据查询范围内的数据对象的索引结构，确定与查询对象对应的目标数据对象。

由于索引结构是根据第一距离构建的，第一距离用于表示分区内数据对象到参考点的距离，而查询范围也是表示分区内数据对象到参考点的距离的区间范围，因此在确定每个分区的查询范围后，在索引结构中以查询范围为查询条件，可以查询出每个分区中到参考点的距离满足查询范围的数据对象，将每个分区中查询出的数据对象取并集获取目标数据对象。

本实施例提供的基于SQL的度量空间数据相似度查询方法，通过对数据集进行分区处理，得到多个分区，每个分区中包含：数据对象，参考点；根据参考点，确定分区内每个数据对象与参考点之间的第一距离；根据第一距离，确定每个数据对象的索引结构；接收用户的查询请求，查询请求中包括查询对象、查询对象与目标数据对象之间的预设距离阈值；确定查询对象与每个分区内参考点之间的第二距离，并根据第二距离、预设距离阈值，确定查询对象在每个分区内的查询范围；在每个分区的查询范围内，根据查询范围内的数据对象的索引结构，确定与查询对象对应的目标数据对象。本实施例可基于SQL技术的数据库来实现度量空间数据相似度查询，以提高对该RDBMS数据库相似度查询的适用性和性能。

实施例三

本实施例提供一种基于SQL的度量空间数据相似度查询方法，如图4所示，该方法可以包括：

步骤301，对数据集进行分区处理，得到多个分区；其中，每个分区中包含：数据对象，参考点；

由于度量空间下的数据类型多样化且数据量巨大，为提高查询效率可以采用对数据库中的所有数据进行划分的预处理方法，将数据分为多个分区。度量空间下的所有数据构成数据集，对数据集进行划分后的每个分区包含用于识别该分区的分区序号，每个分区中还包含至少一个参考点和至少一个数据对象。

具体的，如图2所示，可以在数据集中任意选取多个对象作为参考点，将数据空间划分为与参考点个数相同的多个不相交的分区，其中，参考点可以用p_i表示，其中i为用于标识每个分区的分区序号，i＝1，2，3，4，5。每个分区中的数据对象的确定方式可以有多种方式，举例来说，可以根据数据集中除参考点外剩余的数据对象数量，将数据对象按数量平均划分给多个参考点；也可以根据数据对象到参考点的距离，将到参考点的距离在预设范围内的数据对象划分给每一个参考点。

步骤302，根据参考点，确定分区内每个数据对象与参考点之间的第一距离；

由于数据集中数据对象的类型具有多样性，每个数据对象都具有其原始属性，可以将数据对象添加一个新的属性值，用于在之后的相似度查询中标识数据对象。具体的，可以在每一个分区中，根据参考点，确定每一个数据对象到参考点之间的距离，即第一距离。第一距离可以用于标识每个数据对象，具体的，第一距离包括数据对象所在分区的分区序号信息、数据对象到数据对象所在分区的参考点之间的距离信息。

举例来说，在数据集中获取一个数据对象r，无论该数据对象r的原始属性为字符串数据、图像数据或是其他任意一种类型，为该数据对象r添加一个新的属性值，属性值为该数据对象r到其所在分区i内的参考点p_i的距离，即第一距离。则第一距离可以表示为：<i,|r,p_i|>。

步骤303，根据第一距离，确定每个数据对象的索引结构；

在确定每个数据对象的第一距离之后，可以以第一距离作为数据对象的属性值来构建索引结构，具体的索引结构可以采用B+树索引。

步骤304，接收用户的查询请求，查询请求中包括查询对象、查询对象与目标数据对象之间的预设距离阈值；

本实施例提供的基于SQL的度量空间数据相似度查询方法，为用户提供一种用户自定义函数作为查询接口，即用户在发送查询请求时，只需要提交SQL语句即可。SQL语句中需要包括数据集名称、查询对象、查询对象与目标数据对象之间的预设距离阈值，以在数据集中找出与查询对象的距离小于等于预设距离阈值的所有数据对象，即认为数据对象与查询对象相似。

进一步的，用户发送的查询请求中还可以包括相似度函数,相似度函数用于对目标数据对象进行处理过滤，返回最终的结果集。

步骤305，确定查询对象与每个分区内参考点之间的第二距离；

由于每个数据对象被转化为以第一距离来表示的数据，因此如果需要利用SQL语句实现相似度查询，需要将查询对象也对应转化为以查询对象与每个分区内参考点之间的距离来表示的数据。

具体的，由于查询对象是用户给定的，每个分区内的参考点也是确定的，因此可以确定查询对象与每个分区内参考点之间的距离，即第二距离。根据分区的不同，查询对象到不同分区内参考点之间的距离也不同。

步骤306，根据查询对象与每个分区内参考点之间的第二距离，获取第二距离的最小值；

根据查询对象到不同分区内参考点之间的第二距离，确定多个第二距离的最小值，即查询对象与距离其最近的参考点之间的距离。

具体来说，若p_i为参考点；i为分区序号；q为查询对象；r为数据对象；可以确定查询对象q到不同分区i内参考点p_i之间的第二距离|p_i,q|，在多个第二距离|p_i,q|中获取最小值|p_q,q|，其中p_q为多个参考点p_i中距离查询对象q最近的参考点。

步骤307，根据第二距离的最小值与预设距离阈值之和，确定查询范围的上限值，根据第二距离与预设距离阈值之差，确定查询范围的下限值；

由于确定数据对象与查询对象相似的必要条件为：数据对象到查询对象的距离小于等于预设距离阈值，该必要条件可以用公式一表示：

公式一：|p_i,q|-θ≤|p_i,r|≤|p_i,q|+θ；

其中，p_i为参考点；i为分区序号；q为查询对象；θ为预设距离阈值；r为数据对象。

举例来说，若确定在分区1中|p₁,q|为10，则可以确定查询对象在分区1内的查询范围为[10-θ，10+θ]；若在分区2中|p₂,q|为15，则可以确定询对象在分区2内的查询范围为[15-θ，15+θ]。

在确定查询对象q到不同分区i内参考点p_i之间的第二距离|p_i,q|的最小值|p_q,q|后，可以将公式一优化为公式二：

公式二：|p_i,q|-θ≤|p_i,r|≤|p_q,q|+θ；

通过公式二可以确定在不同分区i内|p_i,r|应该满足的范围区间，其中，|p_q,q|为查询对象q与距离其最近的参考点p_q之间的距离。举例来说，若确定|p_q,q|为5,分区1中|p₁,q|为10，则可以确定查询对象在分区1内的查询范围为[10-θ，5+θ]；若在分区2中|p₂,q|为15，则可以确定询对象在分区2内的查询范围为[15-θ，5+θ]，以此方式可以获取多个查询范围。

由于|p_q,q|≤|p_i,q|，可见公式二相对于公式一能够得到一个更精准的查询范围上限值，同时保持查询范围下限值不变。由此确定查询对象在每个分区内的查询范围更加精准，提高对数据对象的过滤效果，提高相似度查询的效率和性能，同时显著降低CPU和I/O开销。

由于根据查询请求可以获取查询对象在每个分区内的查询范围，因此查询范围的数量与分区的数量相同。在当数据集数量巨大或维度数很大时，可能出现选取出成千上万个参考点的情况，这是就会导致获取的查询范围的数量剧增。而每一个查询条件都会触发一次索引上的索引扫描，然后逐步进行每一次扫描，并将每次索引扫描产生的目标数据对象合并才能获取候选集。这就造成了数据库在进行相似度查询是产生很高的开销，同时，当查询范围的数量超过一个阈值时，查询引擎会采用顺序扫描而不是索引扫描，顺序扫描的查询处理时间与数据集的记录数呈线性增长关系，当数据集数量巨大或维度数很大时，会导致查询处理时间较长，时效性差。

因此，为了解决上述问题，可以首先在数据集中生成母表R，母表R中存储有分区序号、每个分区内的所有数据对象的第一距离的范围区间；

相应的，在确定查询对象在每个分区内的查询范围之后，可以在数据库中构建一个临时表S，该表中存储着分区序号、与分区序号对应的查询对象的查询范围；

将临时表S与母表R进行连接查询，进一步缩小临时表S中的查询对象在每个分区内的查询范围，以提高相似度查询的效率。

步骤308，在每个分区的查询范围内，根据查询范围内的数据对象的索引结构，确定与查询对象对应的目标数据对象。

由于索引结构是根据第一距离构建的，第一距离用于表示分区内数据对象到参考点的距离，而查询范围也是表示分区内数据对象到参考点的距离的区间范围，因此在确定每个分区的查询范围后，在索引结构中以查询范围为查询条件，可以查询出每个分区中到参考点的距离满足查询范围的数据对象，将每个分区中查询出的数据对象取并集获取目标数据对象。

进一步的，获取目标数据对象后，可以根据查询请求中的相似度函数对目标数据对象进行处理过滤，获取最终的结果集。通过利用相似度函数对目标数据对象进行处理，进一步提高相似度查询的准确度，提高相似度查询的性能。

本实施例提供的基于SQL的度量空间数据相似度查询方法，通过对数据集进行分区处理，得到多个分区，每个分区中包含：数据对象，参考点；根据参考点，确定分区内每个数据对象与参考点之间的第一距离；根据第一距离，确定每个数据对象的索引结构；接收用户的查询请求，查询请求中包括查询对象、查询对象与目标数据对象之间的预设距离阈值；确定查询对象与每个分区内参考点之间的第二距离，并根据第二距离、预设距离阈值，确定查询对象在每个分区内的查询范围；在每个分区的查询范围内，根据查询范围内的数据对象的索引结构，确定与查询对象对应的目标数据对象。本实施例可基于SQL技术的数据库来实现度量空间数据相似度查询，以提高对该RDBMS数据库相似度查询的适用性和性能。

实施例四

本实施例提供一种基于SQL的度量空间数据相似度查询装置，如图5所示，该装置可以包括：分区模块41、第一确定模块42、构建模块43、接收模块44、第二确定模块45、查询模块46；

其中，分区模块41，用于对数据集进行分区处理，得到多个分区；其中，每个分区中包含：数据对象，参考点；

第一确定模块42，用于根据参考点，确定分区内每个数据对象与参考点之间的第一距离；

构建模块43，用于根据第一距离，确定每个数据对象的索引结构；

接收模块44，用于接收用户的查询请求，查询请求中包括查询对象、查询对象与目标数据对象之间的预设距离阈值；

第二确定模块45，用于确定查询对象与每个分区内参考点之间的第二距离，并根据第二距离、预设距离阈值，确定查询对象在每个分区内的查询范围；

查询模块46，用于在每个分区的查询范围内，根据查询范围内的数据对象的索引结构，确定与查询对象对应的目标数据对象。

关于本实施例中的装置，其中各个模块执行操作的具体方式已经在有关该方法的实施例中进行了详细描述，此处将不做详细阐述说明。

本实施例提供的基于SQL的度量空间数据相似度查询装置，通过对数据集进行分区处理，得到多个分区，每个分区中包含：数据对象，参考点；根据参考点，确定分区内每个数据对象与参考点之间的第一距离；根据第一距离，确定每个数据对象的索引结构；接收用户的查询请求，查询请求中包括查询对象、查询对象与目标数据对象之间的预设距离阈值；确定查询对象与每个分区内参考点之间的第二距离，并根据第二距离、预设距离阈值，确定查询对象在每个分区内的查询范围；在每个分区的查询范围内，根据查询范围内的数据对象的索引结构，确定与查询对象对应的目标数据对象。本实施例可基于SQL技术的数据库来实现度量空间数据相似度查询，以提高对该RDBMS数据库相似度查询的适用性和性能。

实施例五

本实施例提供一种基于SQL的度量空间数据相似度查询装置，如图6所示，该装置可以包括：分区模块51、第一确定模块52、构建模块53、接收模块54、第二确定模块55、查询模块56；

其中，分区模块51，用于对数据集进行分区处理，得到多个分区；其中，每个分区中包含：数据对象，参考点；

第一确定模块52，用于根据参考点，确定分区内每个数据对象与参考点之间的第一距离；

构建模块53，用于根据第一距离，确定每个数据对象的索引结构；

接收模块54，用于接收用户的查询请求，查询请求中包括查询对象、查询对象与目标数据对象之间的预设距离阈值；

第二确定模块55，用于确定查询对象与每个分区内参考点之间的第二距离，并根据第二距离、预设距离阈值，确定查询对象在每个分区内的查询范围；

查询模块56，用于在每个分区的查询范围内，根据查询范围内的数据对象的索引结构，确定与查询对象对应的目标数据对象。

可选的，分区模块51可以包括：第一确定单元511、划分单元512；

其中，第一确定单元511，用于在数据集中，确定每个数据对象与每个参考点之间的距离；

划分单元512，用于将每个参考点对应的与其距离最小的数据对象划分为一个分区，得到与参考点数目相匹配的多个分区。

进一步的，构建模块53可以包括：第二确定单元531、第三确定单元532；

其中，第二确定单元531，用于根据第一距离的大小关系，确定数据对象的排序规则；

第三确定单元532，用于根据第一距离、排序规则，确定每个数据对象的索引结构。

更进一步的，第二确定模块55包括：第四确定单元551、第五确定单元552；

其中，第四确定单元551，用于根据第二距离与预设距离阈值之和，确定查询范围的上限值；

第五确定单元552，用于根据第二距离与预设距离阈值之差，确定查询范围的下限值。

优选的，第二确定模块55还可以包括：获取单元553，用于根据查询对象与每个分区内参考点之间的第二距离，获取第二距离的最小值；

相应的，第四确定单元551，还用于根据第二距离的最小值与预设距离阈值之和，确定查询范围的上限值。

关于本实施例中的装置，其中各个模块执行操作的具体方式已经在有关该方法的实施例中进行了详细描述，此处将不做详细阐述说明。

本实施例提供的基于SQL的度量空间数据相似度查询装置，通过对数据集进行分区处理，得到多个分区，每个分区中包含：数据对象，参考点；根据参考点，确定分区内每个数据对象与参考点之间的第一距离；根据第一距离，确定每个数据对象的索引结构；接收用户的查询请求，查询请求中包括查询对象、查询对象与目标数据对象之间的预设距离阈值；确定查询对象与每个分区内参考点之间的第二距离，并根据第二距离、预设距离阈值，确定查询对象在每个分区内的查询范围；在每个分区的查询范围内，根据查询范围内的数据对象的索引结构，确定与查询对象对应的目标数据对象。本实施例可基于SQL技术的数据库来实现度量空间数据相似度查询，以提高对该RDBMS数据库相似度查询的适用性和性能。

本领域普通技术人员可以理解：实现上述方法实施例的全部或部分步骤可以通过程序指令相关的硬件来完成，前述的程序可以存储于一计算机可读取存储介质中，该程序在执行时，执行包括上述方法实施例的步骤；而前述的存储介质包括：ROM、RAM、磁碟或者光盘等各种可以存储程序代码的介质。

最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。