FCSR—Tree：一种面向节点分裂优化的多维索引技术

李焕军

摘 要 本文對经典多维索引技术SR-Tree在节点溢出时使用的分裂方法进行了优化，针对其容易导致节点分裂后的新节点中存在着大量的互相重叠区域的问题，提出了一种新的基于空间划分的索引技术FCSR-Tree，并对溢出节点采用效率更高的分裂算法——用聚类技术进行“一分为四”的划分，把重叠区域的对象划分到一个节点中去，从而降低了分裂后节点的重叠现象，减少了kNN检索时的多路查找。并在真实数据集上的实验中验证了FCSR-Tree的查询效率。

【关键词】多维索引 特征选择 聚类 kNN检索

1 引言

多维索引作为对多维复杂内容的检索效率进行优化的一种关键技术和重要手段，其广阔的应用前景为学术界和产业界所公认，一直是研究热点。SR-Tree是一种经典的多维索引技术，自被提出以来，在空间数据库、多媒体、地理信息系统等领域的内容检索中得到广泛应用。

SR-Tree是受SS-Tree和R*-Tree技术的启发而设计出来的一种多维索引技术。但是与同为空间索引的SS-Tree与R*-tree技术类似，SR-Tree也继承了基于数据划分的多维索引的缺点：在将大量对象插入到节点的过程中，其节点溢出时使用的分裂处理方法容易导致节点分裂后的新节点中存在着大量的互相重叠区域，导致了对象检索时的多路查找，降低了检索效率。

本文针对SR-Tree技术的上述问题进行优化，提出了一种新的基于空间划分的索引技术FCSR-Tree，并借鉴了基于空间进行划分的多维索引技术Quad-Tree[8]的“一分为四”理念，对溢出节点设计了基于聚类技术的效率更高的分裂处理算法，把重叠区域的对象划分到一个节点中去，从而降低了分裂后节点的重叠现象，减少了检索时的多路查找，提升了总体效率。

2 FCSR-Tree的数据结构

FCSR-Tree的索引节点的数据结构与SR-Tree类似，SR-Tree的结构如图1所示。它采用最小包围圆形（N维球体）与最小包围矩形（N维方体）的公共部分来表示节点的区域，同时具有了SS-Tree与R*-tree的优势：既有了较小的半径，可以将数据对象分配到较小直径的区域；也具有较小的容积，能够将数据对象分配到有较小的空间容量的区域中。从而能够在多维空间中一定程度的避免区域重叠。

在大量对象插入的过程中，节点之间的严重重叠是不可避免的，从而导致了对象检索时的多路查找。当待插入的多维数据对象大量增加时，会导致索引的中间节点的广度增大的同时，索引节点之间的重叠区域也会相应增大。此时，若FCSR-Tree仍然采用SR-Tree的查询算法，查找时需要访问所有的涉及重叠区域的索引树分枝，但是由于索引分支数量的增加，会导致检索性能急剧下降。

图2是索引节点分裂方式的差异的一个示意图。从中可以看出，一个节点按照左图的方式进行分裂后，分裂得到的两个新节点是不存在重叠区域的，这意味着在对这部分数据进行检索时，不存在会导致额外I/O开销的多路查找。而该节点若按照右图所示的方式进行分裂，分裂后得到的两个节点之间存在这一个重叠区域部分，当数据对象的特征向量维度较高时，这种索引节点之间的重叠区域面积增长的更快，使得检索时的要搜索更多的分枝数，增加了多路查找，降低了查询的处理效率。

3 FCSR-Tree节点的分裂处理方法

为了解决上一节中提到的索引节点分裂导致查询效率受损的问题，本文在实现FCSR-Tree时，借鉴多维索引技术Quad-Tree的“一分为四”理念，对拟分裂的节点中的数据采用k-Means聚类技术进行数据划分，并根据聚类划分的结果对节点进行分裂处理。接下来，首先对传统的节点分裂方法进行剖析，然后再介绍FCSR-Tree的节点分裂处理策略。

3.1 传统分裂方法的分析

假设M是索引节点中对象上限，m是节点中对象的下限。根据大量的实验研究表明，较大的m值可以保证节点存储空间的利用率，但是会限制节点分裂的合理性。m的值取M的20-40%时，通常能保证较好的查询效率与插入效率。此时既能保持很好节点利用率，也可以充分的利用了节点空间利用率。

在传统处理方式中，当需向一个已包含M个对象的节点N中插入一个新对象时，先不进行分裂，而是在索引树中同层的其他节点中进行动态调整，选取N节点中的一部分对象重新插入，以推迟节点的分裂，这样使得节点的最小包围圆形（N维球体）或最小包围矩形（N维方体）区域间重叠较小，获得较高的节点存贮利用率，有时还可以避免节点的分裂。反之，则分裂节点N。

此时需将M+1个对象分裂到两个节点N和N'中。选择原N节点中两个最大的点作为新节点的中心，然后将剩余点分配到距离最近的中心的节点中。从而实现两个节点中心的数据的方差最小化。

当数据维度较高时，溢出节点分裂之后的二个新节点之间容易产生类似于图2所示的重叠区域，将导致对该区域检索时需要进行多路查找，严重影响检索效率。根据分裂后的二部分节点的划分面积和/周长/重叠面积最小的准则，基于穷举的思想，罗列出各种一分为二符合要求组合，并从中选取面积和最小的组合，作为分裂策略。但是该算法复杂度太高，达到了2M-1，而且随着节点数的增加，耗费的时间将会呈指数上升。即使在此过程中采用近似优化，在数据量和数据维度较高是，效率仍不够理想。

3.2 FCSR-Tree节点的“一分为四”分裂策略

本文在FCSR-Tree中提出一种新分裂算法，即将节点“一分为四”，使得节点分裂后的新节点数目达到四个。同时选取m/M之比为20%到30%之间，在保证了下限时，还可以根据实际的聚类划分，使分裂后的每个节点中的对象数量具有了一定的适应性。通过上述分裂处理形成四个节点，一方面可以使得节点的重叠区域划分在一个节点中，减少了数据对象检索时的多路查找；另一方面可以使节点的容量增加，即分裂后的节点可以可插入的数据对象比“一分为二”的分裂存储多一倍的条目；最后它缩小了分裂后节点的覆盖面积，降低了数据区域发生重叠的概率。

在對待分裂的索引节点中的数据进行聚类划分时，本文选取了k-means算法，过将K-means中的k设置为4，最终将数据分为四组，每组数据放入分裂后的一个节点中。FCSR-Tree的索引节点分裂流程如下：

（1）节点数目达到M+1或者M+2时，先判断节点是否是第一次溢出，如是则调用重新插入算法，推迟节点的分裂。反之，则分裂节点N。

（2）重新插入之后再次发生节点的溢出，则节点需要分裂。从节点中的M+1或者M+2个数据对象任意选择四个对象的中心作为初始聚类中心。

（3）根据每个聚类对象的均值（中心对象），计算每个对象与四个中心对象的距离；并根据最小距离重新对相应对象进行较均衡划分；

（4）重新计算每个（有变化）聚类的均值（中心对象）；

（5）迭代第（3）至（4）步直至新的均值与原均值相等或小于指定阈值；

（6）得到四个数量较均衡的簇，其中的数据划分到分裂后的四个索引节点中。

总的来说，FCSR-Tree节点的“一分为四”分裂处理算法的核心流程可以用下述伪代码来描述。

算法：FCSR-Tree索引节点分裂算法

输入：需要进行分裂的叶子节点对象A

输出：分裂之后的叶子节点Bi（i=1，2，3，4）

1. for k=1，…n，

2. 令C（K）为从节点A中随机选取的一个点；

3. while叶子节点Bi中有变化发生 do

4. 应用k-Means技术形成聚类；

5. for k=1，….，n do；

6. Bi={X属于A|A（Ck，x）≤A（Cj，x） 且

对所有j=1…..k，j≠k}；

7. end；

8. 计算新的聚类中心；

9. for k=1，….，n do

10. Ck=Bi内数据对象的均值向量；

11. end；

12. end；

对于索引的中间节点，节点分裂算法在节点数目达到M+1或者M+2时开始分裂。中间节点分裂之后把在聚类中心区域附近的叶子节点划分在一起，有利于使距离上相近的叶子节点成一个新的中间节点。这样分裂后的中间节点可以更好的进行KNN检索与范围查询。

对于叶子节点，它的节点分裂算法是先判断是否先进行重新插入操作，然后再进行叶子节点的分裂。叶子节点分裂之后，将在聚类中心区域附近的数据对象划分在一起，使其距离上相近的对象聚类成一个新的节点。这样分裂后的叶子节点也便于更好的进行kNN检索与范围查询。总的来说，叶子节点的分裂处理与中间节点略有不同，叶子节点在对象数溢出（即对象数量为M+1）时即开始进行分裂处理。

4 基于FCSR-Tree的kNN检索

对于基于FCSR-Tree的kNN检索，本文采用深度优先的策略进行处理优化，具体说明如下：

（1）首先假定查询点p的最近邻距离为无穷大，记作Nearest，在遍历FCSR-Tree的向子树搜索过程中，对每个没有被访问过的新的非叶子节点，将他们按照最小包围矩形（N维方体）排序，把结果保存在活动分枝列表（ Active Branch List，ABL）中；

（2）采用SR-Tree的传统剪枝规则，对ABL进行修剪，删除不必要的分枝；

（3）不停的对ABL 中每个节点（包括孩子），递归调用此算法，直到ABL为空；

（4）对于叶子节点，由于存储的是数据对象信息，计算出其中每个对象到查询对象p的距离，并更新Nearest。

为了进一步优化，对于kNN检索，我们可以从上述检索算法上进行优化扩展，即找出k个距离查询点p最近的对象，具体的方法和上述一样，只是需要增加以下二个方面：需要一个缓冲器，用来存放当前k个最近邻，并且要把其中的记录按距离进行排序；对FCSR-Tree各个子树的修剪，要根据当前最近邻缓冲器中最大距离进行。

5 实验结果与分析

5.1 实验环境和设置

在本文的实验中，采用64位操作系统CentOS6.4，内存为16 GB，处理器为2.4GHz的Intel Xeon E5645，磁盘为2TB。实验中，基于从微软Bing图像检索引擎中获取的大规模多媒体数据集MSRA-MM 2.0，对FCSR-Tree与SR-Tree的kNN检索效率进行比较分析。实验中所用的特征向量数据是从MSRA-MM 2.0图像数据级中抽取的64维HSV颜色直方图数据。数据总量为100万，从中随机挑选出k（k=20， 50， 100）个多维特征向量作为查询集。在实验中，FCSR-Tree和SR-Tree的索引节点的页面大小均设置为8KB。

5.2 数据量对kNN检索性能的影响分析

在此实验中，将分析数据量的大小对基于FCSR-Tree和SR-Tree索引的kNN检索的平均响应时间的影响。在实验中，数据量为20万，40万，100万，k固定为100。实验结果如图3所示。

从图3中可以看到，在执行100NN查询时，基于本文提出的FCSR-Tree的查询的响应时间一直是低SR-Tree的，而且随着数据量的增加，在查询相应时间段增幅上，FCSR-Tree也是由于SR-Tree。主要原因是：

（1）在大规模多维数据集上，采用了基于聚类的“一分为四”节点分裂处理策略的FCSR-Tree所构建的索引树中的重叠区域要比SR-Tree少。相应的，由此引起的多路查找和性能损耗也少；

（2）在进行kNN检索时，基于FCSR-Tree的检索过程中，采用了基于近邻队列的优化扩展，进一步提升了检索效率。

5.3 k值对kNN检索性能的影响分析

在此实验中，将分析k的取值对基于FCSR-Tree和SR-Tree索引的kNN检索的平均响应时间的影响。在实验中，数据量100万，k的取值为20，50，100。实验结果如图4所示。

从图4可以看出，尽管随着k值的增加，SR-Tree的查询响应时间变化不大，而FCSR-Tree的查询响应时间变化相对明显，但在各种场景下，FCSR-Tree的检索性能均优于SR-Tree。考虑到SR-Tree和FCSR-Tree在数据结构上的相似性，除了构建索引时两种技术的节点分裂处理方式的区别导致的树形结构和数据重叠区域的差异外，这主要是由于FCSR-Tree还额外引入了一个缓冲队列来对近邻对象进行剪枝优化。

6 结语

传统多维索引技术的节点分裂处理方法通常容易促使分裂后的新节点中形成大量互相重叠的区域，从而导致对象检索时产生多路查找，检索效率受损。本文提出并实现了FCSR-Tree索引，采用聚类技术对多维数据空间进行“一分为四”的节点划分和分裂处理。FCSR-Tree具有节点分裂效率高、分裂后的重叠区域小等优点。大规模真实数据集上的实验验证了FCSR-Tree的效率。

参考文献

[1]N.Katayama，S.Satoh.The SR-tree：An Index Structure for High-Dimensional Nearest Neighbor Queries[C].Proc. SIGMOD，1997.

[2]张翀，唐九阳，戴长华，肖卫东.一种适用于点和区间混合型维度数据集的多维索引[J].国防科技大学学报，2009，31（03）.

[3]B.Siddhartha，B.Hrishikesh；D. Sourav，K.Goran.Intelligent Analysis of Multimedia Information[M].IGI Global，2016.

[4]羅晓华，郑扣根，潘云鹤.基于SR-Tree的三维无级比例尺GIS空间对象综合技术[J].计算机学报，2005，28（06）.

[5]D.White，R.Jain.Similarity Indexing with the SS-tree [C].Proc.ICDE，1996.

[6]Y.Manolopoulos，A.Nanopoulos，A. Papadopoulos，Y.Theodoridis.R-Trees：Theory and Applications[M]. Springer，2006.

[7]X.Wu，V.Kumar.The Top the Algorithms in Data Mining [M].CRC Press，2009.

[8]H.Samet.Foundations of Multidimensional and Metric Data Structures[M].Morgan Kaufmann，2006.

＼