李焕军

摘 要 本文對经典多维索引技术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]的“一分为四”理念，对溢出节点设计了基于聚类技术的效率更高的分裂处理算法，把重叠区域的对象划分到一个节点中去，从而降低了分裂后节点的重叠现象，减少了检索时的多路查找，提升了总体效率。……