度量空间中支撑点的选取方法及装置

摘要

本发明公开了一种度量空间中支撑点的选取方法及装置，该方法包括：根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点，将该目标数据集中除作为支撑点的数据之外的其他数据作为待计算数据，计算该待计算数据与最后一次选出的支撑点的距离，并通过算出的距离与预先存储的距离值的比较结果确定最小距离值，选取该最小距离值中数值最大的最小距离值对应的数据，并将选出的数据作为支撑点，由于度量空间的周边点可以作为较优的支撑点，故通过只与最近选出的预置数目的支撑点进行计算可以快速的且准确的选出度量空间的周边点，提高度量空间数据管理分析的性能，同时提高了建立索引的效率。

权利要求

1.一种度量空间中支撑点的选取方法，其特征在于，包括：根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点；

将所述目标数据集中除作为支撑点的数据之外的其他数据作为待计算数据；

计算所述待计算数据与最后一次选出的支撑点的距离，并通过算出的距离与预先存储的距离值的比较结果确定最小距离值；

选取所述最小距离值中数值最大的最小距离值对应的数据，并将选出的数据作为支撑点；

所述根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点之前，还包括：为所述目标数据集中每一数据设置队列，其中所述队列中最多存储距离的数量为最近选出的支撑点的个数，所述最近选出的支撑点的个数为1或2；

所述计算所述待计算数据与最后一次选出的支撑点的距离，并通过算出的距离与预先存储的距离值的比较结果确定最小距离值，具体包括：设置选出的所述待计算数据为第m个数据；

计算所述第m个数据与最后一次选出的支撑点的距离；

将算出的距离与所述第m个数据对应的队列中存储的距离进行比较，选出数值最小的距离作为所述第m个数据对应的最小距离值。

2.根据权利要求1所述的方法，其特征在于，所述根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点，具体包括：在所述目标数据集中选取预置位置上的数据作为参考数据；

将所述目标数据集中距离所述参考数据最远的数据作为所述支撑点。

3.根据权利要求1所述的方法，其特征在于，所述根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点，具体包括：从所述目标数据集中选出第n个数据；

分别计算所述第n个数据与所述目标数据集中除所述第n个数据之外的数据的距离的n个方差值；

选取所述n个方差值中的最大方差值；

提取所述最大方差值对应的数据，并将所述提取的数据作为所述支撑点。

4.一种度量空间中数据支撑点的选取装置，其特征在于，所述装置包括：选取模块，用于根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点；

所述选取模块，还用于将所述目标数据集中除作为支撑点的数据之外的其他数据作为待计算数据；

计算模块，用于计算所述待计算数据与最后一次选出的支撑点的距离，并通过算出的距离与预先存储的距离值的比较结果确定最小距离值；

所述选取模块，还用于选取所述最小距离值中数值最大的最小距离值对应的数据，并将选出的数据作为支撑点；

设置模块，用于为所述目标数据集中每一数据设置队列，其中所述队列中最多存储距离的数量为最近选出的支撑点的个数，所述最近选出的支撑点的个数为1或2；

所述计算模块包括：

设置子模块，用于设置选出的所述待计算数据为第m个数据；

运算子模块，用于计算所述第m个数据与最后一次选出的支撑点的距离；

选取子模块，用于将算出的距离与所述第m个数据对应的队列中存储的距离进行比较，选出数值最小的距离作为所述第m个数据对应的最小距离值。

5.根据权利要求4所述的装置，其特征在于，所述选取模块，还用于在所述目标数据集中选取预置位置上的数据作为参考数据；

所述选取模块，还用于将所述目标数据集中距离所述参考数据最远的数据作为所述支撑点。

6.根据权利要求4所述的装置，其特征在于，所述选取模块包括：选择子模块，用于从所述目标数据集中选出第n个数据；

计算子模块，用于分别计算所述第n个数据与所述目标数据集中除所述第n个数据之外的数据的距离的n个方差值；

所述选择子模块，还用于选取所述n个方差值中的最大方差值；

提取子模块，用于提取所述最大方差值对应的数据，并将提取的数据作为所述支撑点。

说明书

度量空间中支撑点的选取方法及装置

技术领域

[0001] 本发明属于计算机技术领域，尤其涉及一种度量空间中支撑点的选取方法及装置。

背景技术

[0002] 度量空间(Metric space)是一种覆盖范围很广的数据类型的抽象。度量空间最大的优势在于其高度的普遍适用性，用户只需提供距离函数就可以进行数据相似性搜索。然而，数据被抽象成度量空间中的点，虽然提高了通用性，但同时也损失了坐标信息，唯一可用的信息就是距离值。由于没有坐标，许多数学工具不能直接使用。一般方法是先找出一些支撑点(Pivot)，然后将数据到该支撑点的距离作为坐标。因此，选出的支撑点的好坏对于度量空间数据管理分析的性能发挥着关键性的影响。

[0003] 现有技术中，在度量空间索引领域，一般认为好的支撑点往往是数据拐角的点。最远优先遍历(Farthest First Traversal，FFT)是一种聚类方法，即FFT算法为一种寻找数据中周边点的方法，具有线性的时间复杂度和空间复杂度，是使用最广泛的支撑点选取算法之一。虽然FFT算法能够在线性的时间内选出数据周边及拐角的点，但是研究中发现最优的支撑点往往不是拐角的点，而是稍微偏离拐角的点，因而FFT算法往往很难选出最优的支撑点。如果想选出稍微偏离拐角的最优的支撑点，那么FFT算法就需要选出更多的点，这将大大增加支撑点选择的个数，致使FFT算法的时间复杂度退化成接近O(n2)。由于时间复杂度用于表示执行算法所需要的计算工作量，时间复杂度的大小可以衡量一个算法的优与劣。

[0004] 一般地，较优的支撑点是位于度量空间的周边的点，使用现有技术中的FFT算法无法准确且快速的选出周边的点，从而影响度量空间数据管理分析的性能。

发明内容

[0005] 本发明提供一种度量空间中支撑点的选取方法及装置，旨在解决因较优的支撑点是位于度量空间的周边的点，故现有技术中的FFT算法无法准确且快速的选出周边的点，从而影响度量空间数据管理分析的性能。

[0006] 本发明提供的一种度量空间中支撑点的选取方法，包括：根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点；将所述目标数据集中除作为支撑点的数据之外的其他数据作为待计算数据；计算所述待计算数据与最后一次选出的支撑点的距离，并通过算出的距离与预先存储的距离值的比较结果确定最小距离值；选取所述最小距离值中数值最大的最小距离值对应的数据，并将选出的数据作为支撑点。

[0007] 本发明提供的一种度量空间中支撑点的选取装置，包括：选取模块，用于根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点；所述选取模块，还用于将所述目标数据集中除作为支撑点的数据之外的其他数据作为待计算数据；计算模块，用于计算所述待计算数据与最后一次选出的支撑点的距离，并通过算出的距离与预先存储的距离值的比较结果确定最小距离值；所述选取模块，还用于选取所述最小距离值中数值最大的最小距离值对应的数据，并将选出的数据作为支撑点。

[0008] 本发明提供的度量空间中支撑点的选取方法及装置，根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点，将所述目标数据集中除作为支撑点的数据之外的其他数据作为待计算数据，计算所述待计算数据与最后一次选出的支撑点的距离，并通过算出的距离与预先存储的距离值的比较结果确定最小距离值，选取所述最小距离值中数值最大的最小距离值对应的数据，并将选出的数据作为支撑点，由于度量空间的周边点可以作为较优的支撑点，故通过只与最近选出的预置数目的支撑点进行计算可以快速的且准确的选出度量空间的周边点，提高度量空间数据管理分析的性能，同时提高了建立索引的效率。

附图说明

[0009] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例。

[0010] 图1是本发明第一实施例提供的度量空间中支撑点的选取方法的实现流程示意图；

[0011] 图2是本发明第二实施例提供的度量空间中支撑点的选取方法的实现流程示意图；

[0012] 图3是本发明第三实施例提供的度量空间中支撑点的选取装置的结构示意图；

[0013] 图4是本发明第四实施例提供的度量空间中支撑点的选取装置的结构示意图；

[0014] 图5是UV数据上FFT算法和RFT选点准确率比较结果示意图；

[0015] 图6是Image数据上FFT算法和RFT选点准确率比较结果示意图。

具体实施方式

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

[0017] 需要说明的是，本技术领域中大多数据集满足度量空间的性质，在本发明实施例中的目标数据集也满足度量空间的性质。

[0018] 请参阅图1，图1为本发明第一实施例提供的度量空间中支撑点的选取方法的实现流程示意图，可应用于所有运行程序的终端中，图1所示的度量空间中支撑点的选取方法，主要包括以下步骤：

[0019] S101、根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点。

[0020] 度量空间在数学中是指一个集合，并且该集合中的任意元素之间的距离是可定义的。该预置规则是预先定义的选取数据的规则，该预置规则可以为任意选取的数据，也可以是该目标数据集中选取的一个相较于其他数据距离最远的数据。然后将该选出的数据作为支撑点。

[0021] S102、将该目标数据集中除作为支撑点的数据之外的其他数据作为待计算数据。

[0022] 在实际应用中，在目标数据集中，待计算数据是除了作为支撑点的数据之外的其他数据。

[0023] S103、计算该待计算数据与最后一次选出的支撑点的距离，并通过算出的距离与预先存储的距离值的比较结果确定最小距离值。

[0024] 该待计算数据为多个，此时每一个待计算数据均需要算出与最后一次选出的支撑点之间的距离，待计算数据的个数和算出的距离的个数相同。其中该待计算数据的个数等于该目标数据集中未作为支撑点的数据的个数。

[0025] S104、选取该最小距离值中数值最大的最小距离值对应的数据，并将选出的数据对应于该度量空间的点作为支撑点。

[0026] 在步骤S103之后，从得到的最小距离值中选取数值最大的最小距离值。

[0027] 在步骤S104之后，返回到步骤S102-步骤S104，继续在该目标数据集中未作为支撑点的数据计算支撑点。

[0028] 本发明实施例中，根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点，将该目标数据集中除作为支撑点的数据之外的其他数据作为待计算数据，计算该待计算数据与最后一次选出的支撑点的距离，并通过算出的距离与预先存储的距离值的比较结果确定最小距离值，选取该最小距离值中数值最大的最小距离值对应的数据，并将选出的数据作为支撑点，由于度量空间的周边点可以作为较优的支撑点，故通过只与最近选出的预置数目的支撑点进行计算可以快速的且准确的选出度量空间的周边点，提高度量空间数据管理分析的性能，同时提高了建立索引的效率。

[0029] 请参阅图2，图2为本发明第二实施例提供的度量空间中支撑点的选取方法的实现流程示意图，可应用于所有运行程序的终端中，主要包括以下步骤：

[0030] S201、为目标数据集中每一数据设置队列。

[0031] 其中该队列中最多存储距离的数量为最近选出的支撑点的个数，该最近选出的支撑点的个数为1或2。即，队列最多存储1或2个距离值。需要说明的是，在初始状态下，数据对应的队列为空，即队列未存储任何距离值。

[0032] 队列是一种特殊的线性表，特殊之处在于队列只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，在队列中，插入操作的端称为队尾，删除操作的端称为队头。队列中没有元素时，称为空队列；队列的数据元素又称为队列元素。在队列中，插入一个队列元素称为入队，从队列中删除一个队列元素成为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出(FIFO—first in first out)线性表。

[0033] 在本发明实施例中，队列也具有上述的先进先出的特性，故当队列存储的数量超出最大存储量时，删除最先入队的距离值，然后再将新的距离值入队。

[0034] S202、根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点。

[0035] 可选地，根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点具体为：

[0036] 在该目标数据集中选取预置位置上的数据作为参考数据；

[0037] 将该目标数据集中距离该参考数据最远的数据作为该支撑点。

[0038] 该预置位置上的数据可以是位于目标数据集中第一位的数据，也可以是位于目标数据集中末位的数据，还是可以是从目标数据集中任一位置的数据。然后选出距离该参考数据最远的数据作为支撑点，其中该作为支撑点的最远的数据为该目标数据集中的一个数据。

[0039] 可选地，根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点，具体还可以为：

[0040] 从该目标数据集中选出第n个数据；

[0041] 分别计算该第n个数据与该目标数据集中除该第n个数据之外的数据位于该度量空间中点的距离的n个方差值；

[0042] 选取该n个方差值中的最大方差值；

[0043] 提取该最大方差值对应的数据，并将提取的数据作为该支撑点。

[0044] 从该目标数据集中任意选出第n个数据。该提取的数据为该最大方差值对应的数据。

[0045] S203、将该目标数据集中除作为支撑点的数据之外的其他数据作为待计算数据。

[0046] 在实际应用中，在目标数据集中，待计算数据是除了作为支撑点的数据之外的其他数据。

[0047] S204、计算该待计算数据与最后一次选出的支撑点的距离，并通过算出的距离与预先存储的距离值的比较结果确定最小距离值。

[0048] 可选地，计算该待计算数据与最后一次选出的支撑点的距离，并通过算出的距离与预先存储的距离值的比较结果确定最小距离值具体为：

[0049] 设置选出的该待计算数据为第m个数据；

[0050] 计算该第m个数据与最后一次选出的支撑点的距离；

[0051] 将算出的距离与该第m个数据对应的队列中存储的距离进行比较，选出数值最小的距离作为该第m个数据对应的最小距离值。

[0052] 如果第m个数据对应的队列中未存储有距离，则算出的距离就作为最小距离值。

[0053] 在实际应用中，在度量空间中数据到支撑点距离的计算方法可以有多种，即不同的数据类型通过不同的距离函数来算出距离，该距离函数在满足度量空间的条件的基础上。度量空间可定义为一个二元组(S，d)，其中S是有限非空的数据集合，而d是定义在S上的具有如下三个性质的距离函数：

[0054] 正定性：对于任意x,y∈S,d(x,y)>＝0，并且

[0055] 对称性：对于任意x,y∈S,d(x,y)＝d(y,x)；

[0056] 三角不等性：对于任意x,y,z∈S,d(x,y)+d(y,z)>＝d(x,z)。

[0057] 下面给出三种数据类型以及三种数据类型对应的距离函数：

[0058] 第一种数据类型为：向量(Vector)数据类型，该Vector数据的距离函数为欧几里德距离

[0059] 第二种数据类型为：图片(Image)数据类型，该Image数据的距离函数为L族距离(线性组合)，Image数据是经由特征提取后的数据，由三个特征集组成，表示图片的结构、纹理和颜色。每个特征集可以看成是一个向量，举例说明，结构特征集的大小是3，纹理特征集大小为48，颜色特征集大小为15，故而一张图片可以表示为一个66维的向量。每个特征集都有一个距离函数，纹理和结构使用L2距离，颜色使用L1距离。Image数据间的距离是每个特征集距离的一个线性组合。其中，L族距离公式如下：

[0060]

[0061] 第三种数据类型为：基因数据类型，该基因数据使用的距离函数为全局比对(Global alignment)。

[0062] S205、选取该最小距离值中数值最大的最小距离值对应的数据，并将选出的数据作为支撑点。

[0063] 在步骤S104之后，返回到步骤S102-步骤S104，继续在该目标数据集中未作为支撑点的数据计算支撑点。

[0064] 在步骤S205之后，返回到步骤S203-步骤S205，继续在该目标数据集中未作为支撑点的数据计算支撑点。

[0065] 举例说明，选取该最小距离值中数值最大的最小距离值对应的数据具体为：

[0066] 初始状态下，即在步骤S201之前，预先设置一个参考数值，其中该参考数值<0。当在步骤S204中第一次得到一个数据的最小距离值a时，该最小距离值a与该参考数值进行比较，由于距离值均是大于0的数值，则该最小距离值a>参考数值，然后将该参考数值更新为最小距离值的数值，这样在步骤S204中下一次再得到另外一个数据的最小距离值b时，最小距离值b与更新后的参考数值进行比较，以此类推，就相当于从所有得到的最小距离值中选出一个数值最大的最小距离值，具体的实施方式后面通过应用场景来说明，此处不再赘述。

[0067] 下面以一个实际的应用场景对上述描述进行说明，具体参见如下：

[0068] 假设目标数据集data中有data0、data1、data2、data3四个数据，该四个数据分别对应的队列queue为queue0、queue1、queue2、queue3，queue最多存储的数量为1或2；令最后一次选出的支撑点为lastpoint；参考数值为maxdis＝-1。

[0069] 步骤1、根据预置规则在data中选取一个数据data0，并将data0作为支撑点，并加入到结果集中；

[0070] 步骤2、令最后一次加入结果集的支撑点作为lastpoint；

[0071] 步骤3、将非支撑点的数据作为待计算数据；

[0072] 步骤4、当待计算数据为data1时，计算data1到lastpoint的距离dis1，此时最后一次加入结果集的lastpoint＝data0；

[0073] 步骤5、此时data1对应的queue1中为空，即queue1未存储有距离值，则dis1作为最小距离值mindis；

[0074] 步骤6、将mindis与maxdis进行比较，其中mindis＝dis1>0，maxdis＝-1

[0075] 步骤7、判断queue1中存储的距离值是否超出最多存储的数量，若未超过，则将dis1入队queue1中，若超过，则queue1队首出队，并将dis1入队queue1中；

[0076] 需要说明的是，在步骤5中，若queue1不为空，则mindis为queue1中最小值，dis1和queue1中最小值进行比较，若dis1mindis，则mindis的值不变，此时步骤6还需执行mindis与maxdis比较，但是这里的mindis的值不等于dis1，而是mindis为queue1中的最小值，然后按照上述步骤7的描述执行dis1入队queue1的操作。

[0077] 上述步骤4-步骤7是小循环，就是计算完data1之后，按照上述步骤3-步骤7描述的计算方法来计算data2，即遍历整个目标数据集。

[0078] 然后循环上述步骤4到步骤7的过程来计算data2，具体如下：

[0079] 步骤4、当待计算数据为data2时，计算data2到lastpoint的距离dis2，由于除了data0，没有其他的支撑点，故lastpoint＝data0；

[0080] 步骤5、此时data2对应的queue2中为空，即queue2未存储有距离值，则dis2作为最小距离值mindis，即mindis＝dis2；

[0081] 步骤6、将mindis与maxdis进行比较，由于在计算data1时，maxdis＝dis1，所以比较的是dis1和dis2的数值，假定dis1

[0082] 步骤7、判断queue2中存储的距离值是否超出最多存储的数量，若未超过，则将dis2入队queue2中，若超出，则queue2队首出队，将dis2入队queue2中；

[0083] 需要说明的是，步骤6中，如假定dis1>dis2，则maxdis>mindis，则maxdis的值不变，maxdis＝dis1，那么此时nextpoint＝data1，然后还需执行上述步骤7的过程，即dis2入队queue2的过程。

[0084] 然后循环上述步骤4到步骤7的过程来计算data3，具体如下：

[0085] 步骤4、当待计算数据为data3时，计算data3到lastpoint的距离dis3，由于除了data0，没有其他的支撑点，故lastpoint＝data0；

[0086] 步骤5、此时data3对应的queue3中为空，即queue3未存储有距离值，则dis3作为最小距离值mindis，即mindis＝dis3；

[0087] 步骤6、将mindis与maxdis进行比较，由于在计算data2时，maxdis＝dis2或maxdis＝dis1，故比较的是dis2和dis3的数值，或者比较的是dis1和dis3的数值，然后从中选取数值最大的作为maxdis，然后数值最大的距离作为nextpoint，也就是说，nextpoint可能为data1、data2、data3三个中的任一个；

[0088] 步骤7、判断queue3中存储的距离值是否超出最多存储的数量，若未超过，则将dis3入队queue3中，若超出，则queue3队首出队，将dis3入队queue3中；

[0089] 当目标数据集data中所有未作为支撑点的数据都遍历之后，执行下面的步骤：

[0090] 步骤8、将nextpoint加入到结果集中，其中结果集中的数据为支撑点，若nextpoint＝data3，则将data3作为支撑点，加入到结果集中，此时结果集包括data0和data3。

[0091] 然后步骤3到步骤8描述的计算方法为大循环，当选出一个支撑点之后，再次回到步骤3，将没有作为支撑点的数据作为待计算数据，执行步骤4-步骤7的小循环遍历data中所有未作为支撑点的数据，最后执行步骤8再次选出支撑点。需要说明的是，第二次遍历data中所有未作为支撑点的数据时，lastpoint可能会改变，例如，上述最后步骤8完成后，最后一次加入到结果集中的数据为data3，那么第二次遍历data中所有未作为支撑点的数据来计算支撑点的方法中lastpoint＝data3，以此类推，遍历第三次、第四次…，此处不做赘述。

[0092] 在实际应用中，可以预置最大支撑点的个数，即一个目标数据集中选取的支撑点的个数等于预置最大支撑点的个数，其中该预置最大支撑点的个数为大于0的整数。

[0093] 需要说明的是，当预置最大支撑点的个数为1时，结果集中的支撑点为上述步骤1选出的支撑点data0，不进行上述的步骤2-步骤8。

[0094] 下面提供上述描述的整个选取支撑点算法运行在终端中的程序，如下：输入：数据集data，

[0095] 距离函数metric，

[0096] 最多选支撑点的个数pointNum

[0097] 输出：结果集resultSet

[0098]

[0099]

[0100] 继续执行步骤4到17；

[0101] 其中，maxdis＝-1，为上述步骤S205中所描述的预置的参考数值。

[0102] 需要说明的是，小循环是从步骤5到步骤12，大循环是从步骤4到步骤17，其中步骤1中recentsize是本实施例的步骤S201中所描述的最近选出的支撑点的个数，即recentsize＝1或2。

[0103] 需要说明的是，若recentsize>2，则选出的支撑点中既有度量空间的周边点又有度量空间的内部点，但是内部点不是较优的支撑点，故recentsize只能等于1或2。

[0104] 本发明实施例中，为目标数据集中每一数据设置队列，根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点，将该目标数据集中除作为支撑点的数据之外的其他数据作为待计算数据，计算该待计算数据与最后一次选出的支撑点的距离，并通过算出的距离与预先存储的距离值的比较结果确定最小距离值，选取该最小距离值中数值最大的最小距离值对应的数据，并将选出的数据作为支撑点，由于度量空间的周边点可以作为较优的支撑点，故通过只与最近选出的预置数目的支撑点进行计算可以快速的且准确的选出度量空间的周边点，提高度量空间数据管理分析的性能，同时提高了建立索引的效率。

[0105] 请参阅图3，图3是本发明第三实施例提供的度量空间中支撑点的选取装置的结构示意图，为了便于说明，仅示出了与本发明实施例相关的部分。图3示例的度量空间中支撑点的选取装置可以是前述图1和图2所示实施例提供的度量空间中支撑点的选取方法的执行主体。图3示例的度量空间中支撑点的选取装置，主要包括：选取模块301和计算模块302。以上各功能模块详细说明如下：

[0106] 选取模块301，用于根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点；

[0107] 选取模块301，还用于将该目标数据集中除作为支撑点的数据之外的其他数据作为待计算数据；

[0108] 计算模块302，用于计算该待计算数据与最后一次选出的支撑点的距离，并通过算出的距离与预先存储的距离值的比较结果确定最小距离值；

[0109] 选取模块301，还用于选取该最小距离值中数值最大的最小距离值对应的数据，并将选出的数据作为支撑点。

[0110] 该预置规则是预先定义的选取数据的规则，该预置规则可以为任意选取的数据，也可以是该目标数据集中选取的一个相较于其他数据距离最远的数据。然后将该选出的数据作为支撑点。该待计算数据为多个，此时每一个待计算数据均需要算出与最后一次选出的支撑点之间的距离，待计算数据的个数和算出的距离的个数相同。其中该待计算数据的个数等于该目标数据集中未作为支撑点的数据的个数。

[0111] 本实施例未尽之细节，请参阅前述图1所示实施例的描述，此处不再赘述。

[0112] 需要说明的是，以上图3示例的度量空间中支撑点的选取装置的实施方式中，各功能模块的划分仅是举例说明，实际应用中可以根据需要，例如相应硬件的配置要求或者软件的实现的便利考虑，而将上述功能分配由不同的功能模块完成，即将图像处理装置的内部结构划分成不同的功能模块，以完成以上描述的全部或者部分功能。而且，实际应用中，本实施例中的相应的功能模块可以是由相应的硬件实现，也可以由相应的硬件执行相应的软件完成。本说明书提供的各个实施例都可应用上述描述原则，以下不再赘述。

[0113] 本发明实施例中，选取模块301根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点，然后将该目标数据集中除作为支撑点的数据之外的其他数据作为待计算数据，计算模块302计算该待计算数据与最后一次选出的支撑点的距离，并通过算出的距离与预先存储的距离值的比较结果确定最小距离值，选取模块301选取该最小距离值中数值最大的最小距离值对应的数据，并将选出的数据作为支撑点，由于度量空间的周边点可以作为较优的支撑点，故通过只与最近选出的预置数目的支撑点进行计算可以快速的且准确的选出度量空间的周边点，提高度量空间数据管理分析的性能，同时提高了建立索引的效率。

[0114] 请参阅图4，图4为本发明第四实施例提供的度量空间中支撑点的选取装置的结构示意图，为了便于说明，仅示出了与本发明实施例相关的部分。图4示例的度量空间中支撑点的选取装置可以是前述图1和图2所示实施例提供的度量空间中支撑点的选取方法的执行主体。图4示例的度量空间中支撑点的选取装置，主要包括：设置模块401、选取模块402和计算模块403。以上各功能模块详细说明如下：

[0115] 设置模块401，用于为目标数据集中每一数据设置队列。

[0116] 其中该队列中最多存储距离的数量为该最近选出的支撑点的个数，该最近选出的支撑点的个数为1或2，即该队列中最多存储距离的数量为1或2。

[0117] 队列是一种特殊的线性表，特殊之处在于队列只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，在队列中，插入操作的端称为队尾，删除操作的端称为队头。队列中没有元素时，称为空队列；队列的数据元素又称为队列元素。在队列中，插入一个队列元素称为入队，从队列中删除一个队列元素成为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出(FIFO—first in first out)线性表。

[0118] 在本发明实施例中，队列也具有上述的先进先出的特性，故当队列存储的数量超出最大存储量时，删除最先入队的距离值，然后再将新的距离值入队。

[0119] 选取模块402，用于根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点。

[0120] 可选地，选取模块402，还用于在该目标数据集中选取预置位置上的数据作为参考数据；

[0121] 选取模块402，还用于将该目标数据集中距离该参考数据最远的数据作为该支撑点。

[0122] 该预置位置上的数据可以是位于目标数据集中第一位的数据，也可以是位于目标数据集中末位的数据，还是可以是从目标数据集中任一位置的数据。然后选出距离该参考数据最远的数据作为支撑点，其中该作为支撑点的最远的数据为该目标数据集中的一个数据。

[0123] 可选地，选取模块402包括：选择子模块4021、计算子模块4022和提取子模块4023。

[0124] 选择子模块4021，用于从该目标数据集中选出第n个数据；

[0125] 计算子模块4022，用于分别计算该第n个数据与该目标数据集中除该第n个数据之外的数据的距离的n个方差值；

[0126] 选择子模块4021，用于选取该n个方差值中的最大方差值；

[0127] 提取子模块4023，用于提取该最大方差值对应的数据，并将提取的数据作为该支撑点。

[0128] 选择子模块4021从该目标数据集中任意选出第n个数据。提取子模块4033提取的数据为该最大方差值对应的数据。

[0129] 选取模块402，还用于将该目标数据集中除作为支撑点的数据之外的其他数据作为待计算数据。

[0130] 在实际应用中，在目标数据集中，待计算数据是除了作为支撑点的数据之外的其他数据。

[0131] 计算模块403，用于计算该待计算数据与最后一次选出的支撑点的距离，并通过算出的距离与预先存储的距离值的比较结果确定最小距离值。

[0132] 可选地，计算模块403包括：设置子模块4031、运算子模块4032和选取子模块4033；

[0133] 设置子模块4031，用于设置选出的该待计算数据为第m个数据；

[0134] 运算子模块4032，用于计算该第m个数据与最后一次选出的支撑点的距离；

[0135] 选取子模块4033，用于将算出的距离与该第m个数据对应的队列中存储的距离进行比较，选出数值最小的距离作为该第m个数据对应的最小距离值。

[0136] 如果第m个数据对应的队列中未存储有距离，则选取子模块4033算出的距离就作为最小距离值。

[0137] 本实施例未尽之细节，请参阅前述图1和图2所示实施例的描述，此处不再赘述。

[0138] 本发明实施例中，设置模块401为目标数据集中每一数据设置队列，选取模块402根据预置规则在目标数据集中选取一个数据，并将选出的数据作为支撑点，将该目标数据集中除作为支撑点的数据之外的其他数据作为待计算数据，计算模块403计算该待计算数据与最后一次选出的支撑点的距离，并通过算出的距离与预先存储的距离值的比较结果确定最小距离值，由于度量空间的周边点可以作为较优的支撑点，故通过只与最近选出的预置数目的支撑点进行计算可以快速的且准确的选出度量空间的周边点，提高度量空间数据管理分析的性能，同时提高了建立索引的效率。

[0139] 下面提供仿真的实验结果，来证明本发明实施例所描述的方法比现有的FFT算法更加优越，共从两个方面来证明，一个是选最优支撑点的速度，另外一个是选取较优支撑点(度量空间的周边点)的准确率。

[0140] 第一方面，选取最优支撑点的速度比较：

[0141] 由于本发明实施例所描述的选取支撑点的方法和FFT算法的时间复杂度是相同的，算法的执行时间也受到代码实现、机器状况等因素影响，故不以运行时间来比较两者的速度，而是以选出最优支撑点时所进行的选择次数为标准来衡量选点速度。在其他条件都相同的情况下，若选点次数越多，则表示速度越慢。

[0142] 选取Vector和Image数据类型上进行了测试。如表2所示，数据为UV(Uniform Vector)上2维数据，选取查询半径0.03到0.07上的结果，对应的值为选出最优支撑点时所进行的支撑点的选择次数，或者说是选出最优支撑点时所选出的总点数。值越小，表示速度越快。为了方便书写，本发明实施例所描述的选取支撑点的方法简写成：近期最远遍历(RFT，Recent Farthest Traversal)算法，当recentSize＝1时，RFT为RFT1；当recentSize＝2时，RFT为RFT2。

[0143]

[0144] 从1000个数据中选出最优支撑点，最多需要1000次选取。从表2可以看出，FFT算法平均需要628次才能选出最优的支撑点，这时接近O(n2)的时间复杂度了。而RFT2平均只需28.8次就能完成同样的工作。RFT1比RFT2稍微慢一些，平均需要65.4次，但也远比FFT算法快得多。半径0.03和半径0.05上结果相同是因为两个半径上最优支撑点相同。Image类型也和UV类型结论类似，此处不再赘述。

[0145] 第二方面，选取较优支撑点(度量空间的周边点)的准确率：

[0146] 首先选取性能最优的前m个支撑点组合，该m个支撑点构成一个集合P。从FFT或RFT选出的支撑点中取前n个，该n个支撑点构成一个集合Q。那么，准确率h可定义为如下表达式：

[0147]

[0148] 因为集合P的大小决定于m，集合Q的大小等于n(FFT或RFT选出的支撑点不会重复)，当m和n变化时，准确率也随着变化，针对不同的侧重点，固定m和n，使得两种算法具有可比性。在固定m的情况下，逐渐增大n，则准确率h将趋近于1。当数据维度增大时，在数据量不变的情况下，因为数据分布变得更加稀疏，所以我们适当地增大了n的取值，使得结果更加直观。准确率h越高，表示算法选出的优异支撑点越多，从而得到高搜索性能的可能性越大。

[0149] 我们在Vector、Image二种数据类型上进行了测试。图5为UV数据上FFT算法和RFT选点准确率比较结果示意图。图5中横轴表示查询半径，使用了0.01～0.10间隔为0.01的十个半径；纵轴表示准确率。m取为100，n取为40。

[0150] 从图5中可以看出，FFT算法的准确率平稳在10％左右；RFT2的准确率不小于70％，且最高能达到92％；RFT1的准确率在30％～40％间波动。需要注意的是，图5中曲线的波动是因为在不同半径上，最优的前m个支撑点组合是不一样的，即集合P的大小是不一样的。看图5时，要在相同的半径上比较FFT算法和RFT，这样才具有可比性。我们给出多个半径的比较，是为了表达RFT比FFT算法优越是普遍情况，不是个例。

[0151] 图6为Image数据上FFT算法和RFT选点准确率比较结果示意图，其中查询半径为0.01～0.06，m取为100，n取为60，虽然RFT的准确率不像Vector数据类型上那么高，但相对FFT来说，依然高出了四倍到五倍。

[0152] 以上实验结果均说明了，本发明实施例中所描述的选取支撑点的方法无论从速率还是准确率都优于现有技术中FFT算法。

[0153] 在本申请所提供的多个实施例中，应该理解到，所揭露的系统、装置和方法，可以通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的，例如，所述模块的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个模块或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信链接可以是通过一些接口，装置或模块的间接耦合或通信链接，可以是电性，机械或其它的形式。

[0154] 所述作为分离部件说明的模块可以是或者也可以不是物理上分开的，作为模块显示的部件可以是或者也可以不是物理模块，即可以位于一个地方，或者也可以分布到多个网络模块上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。

[0155] 另外，在本发明各个实施例中的各功能模块可以集成在一个处理模块中，也可以是各个模块单独物理存在，也可以两个或两个以上模块集成在一个模块中。上述集成的模块既可以采用硬件的形式实现，也可以采用软件功能模块的形式实现。

[0156] 所述集成的模块如果以软件功能模块的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁碟或者光盘等各种可以存储程序代码的介质。

[0157] 需要说明的是，对于前述的各方法实施例，为了简便描述，故将其都表述为一系列的动作组合，但是本领域技术人员应该知悉，本发明并不受所描述的动作顺序的限制，因为依据本发明，某些步骤可以采用其它顺序或者同时进行。其次，本领域技术人员也应该知悉，说明书中所描述的实施例均属于优选实施例，所涉及的动作和模块并不一定都是本发明所必须的。

[0158] 在上述实施例中，对各个实施例的描述都各有侧重，某个实施例中没有详述的部分，可以参见其它实施例的相关描述。

[0159] 以上为对本发明所提供的度量空间中支撑点的选取方法及装置的描述，对于本领域的技术人员，依据本发明实施例的思想，在具体实施方式及应用范围上均会有改变之处，综上，本说明书内容不应理解为对本发明的限制。