一种支持非度量空间中近似查询的索引技术  

Index supporting approximate query in non-metric space

作　　者：彭敦陆[1] 徐文杰[1] 霍欢[1] 江平 

机构地区：[1]上海理工大学光电信息与计算机工程学院,上海200093 [2]上海宽文是风软件有限公司,上海200072

出　　处：《计算机应用研究》2014年第7期1965-1971,共7页Application Research of Computers

基　　金：上海浦东新区科技发展基金创新资金科技合作项目(PKJ2013-Z14);国家自然科学基金资助项目(61003031);上海市自然科学基金资助项目(10ZR1421100)

摘　　要：多媒体信息系统通常使用索引技术加快检索,现有索引技术绝大多数都是基于度量空间建立的,其中广泛应用度量空间的三角不等性。在非度量空间中,面向度量空间的索引技术难以快速而准确地完成检索任务。针对多媒体数据对象进行研究,发现其具有非度量空间的属性,在建立多媒体数据索引时,采用非度量空间中的计算方法使得所建索引更加有效。结合聚类和pivots技术,提出一种支持非度量空间中的对象索引结构——M+-tree。给出了M+-tree的建立、维护及采用M+-tree进行快速KNN检索的相关算法。实验表明,M+-tree在检索性能和检索效果上比现有的非度量空间的索引结构具有明显优势。Indexing techniques are often used to improve the performance of retrieving data in multimedia information systems.Currently,most of the indexing techniques are developed for metric space,in which the triangle inequality is widely employed.However,these techniques cannot efficiently and accurately retrieve data in the non-metric space,where the triangle inequality is not always satisfied. Data objects in multimedia information system have the properties of non-metric space. Therefore,exploiting non-metric technique for indexing these objects makes the retrieval more efficient and more accurate. This paper proposed an indexing structure for non-metric space,called M＋-tree,which combined the techniques of clustering with pivots. It presented the algorithms for building,maintaining and querying on M＋-tree as well. The results of experiments indicate that M＋-tree is superior to the indexing structures developed for non-metric spaces both at efficiency and accuracy.

关 键 词：索引结构 非度量空间 近似检索 树结构 聚类 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]