PD_Tree_一种映射空间上的高维数据索引结构.pdf

2011 12 12 小 型 微 型 计 算 机 系 统 年 月 第 期 Journal of Chinese Computer Systems Vol. 32 No． 12 2011 PD-Tree : 一种映射空间上的高维数据索引结构 1，2 1 1 ， ， 李仲生 李仁发 禹 亮 1 ( ， 4 10082) 湖南大学嵌入式系统与网络实验室 长沙 2 ( ， 422000) 邵阳学院信息工程系 湖南邵阳 E-mail :zsli666@ 163 ． com : ． - ， 摘 要 高效的数据过滤是减少距离函数计算次数的捷径 提出了一种高效处理高维数据的索引算法 在空间映射的基础上 ， ， 、 ， 选取信息蕴含丰富的一组维为主维 结合三角不等式完成数据过滤 实现分层聚类 分级索引 构成一种基于主维过滤的索引结 :PD-Tree． ． :PD-Tree 构 用方差覆盖权对主维的信息保持量做了定量分析 不同数据规模下的实验均显示 进一步减少了距离函数 ， CPU ， ． 的计算次数 降低了 开销 提高了检索速度 : ; ; ; ;PD-Tree 关键词 方差覆盖权 高维索引 主维 三角不等式 中图分类号:TP311 文献标识码:A 文章编号:1000-1220 (2011)12-247 1-06 PD-Tree :Novel High-dimensional Indexing Structure on a Mapping Space LI Zhong -sheng 1，2 ，LI Ren-fa1 ，YU Liang 1 1 (Embedded Systems ＆ Networking Laboratory ，H unan Univers ity ，Changsha 4 10082 ，China) 2 (Dep artment of Inf ormation Engineering and Electricity ，Shaoyang Univers ity ，Shaoyang 422000 ，China) Abstract :It is acted as the most effective method for low ing computation times of distance function to filter data space efficiently ． A novel filtering technique for multidimensional data is proposed here-on the basis of space mapping ，the dimension w ith the biggest combined-variance is selected as the principal dimension (PD)，and the unrelated data is filtered w ith it combining w ith the triangle in- equality ． The