向量空间划分类索引的动态更新代价分析

doi:10.3778/j.issn.1002-8331.2009.18.005

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (18): 18-21.DOI: 10.3778/j.issn.1002-8331.2009.18.005

向量空间划分类索引的动态更新代价分析

李博涵¹,郝忠孝^1,2

1.哈尔滨理工大学计算机科学与技术学院，哈尔滨 150080
2.哈尔滨工业大学计算机科学与技术学院，哈尔滨 150001

收稿日期:2009-02-27 修回日期:2009-04-03 出版日期:2009-06-21 发布日期:2009-06-21
通讯作者: 李博涵

Cost analysis for dynamic update of vector space partitioning strategy index

LI Bo-han¹,HAO Zhong-xiao^1,2

1.College of Computer Science and Technology，Harbin University of Science and Technology，Harbin 150080，China
2.College of Computer Science and Technology，Harbin Institute of Technology，Harbin 150001，China

Received:2009-02-27 Revised:2009-04-03 Online:2009-06-21 Published:2009-06-21
Contact: LI Bo-han

摘要/Abstract

摘要： 代价分析是借助代价模型预测和评估空间索引结构的一种有效方法。针对索引的空间划分和数据划分这两种策略，在已有的索引结构基础上建立了向量空间划分类型索引的代价模型，该模型可实现查询以及动态更新的性能评价。以KDB-树系为评估对象，从结点存取次数（NA）值推导计算出页面存取次数（PA）的估计值，并在标准数据分布上对估计值的相关误差率进行了验证。结果表明代价模型的平均相关误差率较低，不超过12%。代价分析的结果有助于对索引结构的动态更新代价的预估和查询的优化。

关键词: 代价模型, 空间划分, 索引结构, KDB-树系

Abstract: Cost analysis can predict and estimate the spatial index structure with the cost model.According to two main index partition strategy named space partition and data partition，the efficient cost model is presented to estimate the query and dynamic update of the vector space partitioning strategy index.The new cost model deduces and calculates the estimated value of page access from the number of node access based on the KDB-tree family.The experiment result indicates that the average relative error ratio of estimated value is less than 12% on the typical uniform data distribution.The result of cost analysis contributes to the performance prediction of dynamic update in index and the optimization in query.

Key words: cost model, space partition, index structure, KDB-tree family

李博涵¹,郝忠孝^1,2. 向量空间划分类索引的动态更新代价分析[J]. 计算机工程与应用, 2009, 45(18): 18-21.

LI Bo-han¹,HAO Zhong-xiao^1,2. Cost analysis for dynamic update of vector space partitioning strategy index[J]. Computer Engineering and Applications, 2009, 45(18): 18-21.

[1]	郑星星，谢明鸿，张亚运. 基于空间划分和线性规划的快速碰撞检测算法[J]. 计算机工程与应用, 2017, 53(23): 236-240.
[2]	董钰山，李春江，徐颖. GCC编译器中循环数组预取优化的实现及效果[J]. 计算机工程与应用, 2016, 52(6): 19-25.
[3]	张晓蕊1，刘嘉敏2，罗跃纲3. 基于应用约束的三维空间的处理和比较[J]. 计算机工程与应用, 2015, 51(15): 231-235.
[4]	徐红波1，2，姚念民2，韩启龙2，潘海为2. 支持线段查询索引结构CB树[J]. 计算机工程与应用, 2015, 51(11): 114-118.
[5]	陈刚，钱猛，刘金. 基于划分的高效异常轨迹检测[J]. 计算机工程与应用, 2014, 50(24): 127-132.
[6]	章德斌¹，曹丽君²，梁永欣¹，张忠平¹. 支持k近邻查询的X*树索引结构[J]. 计算机工程与应用, 2011, 47(5): 123-125.
[7]	陈磊1，牛秦洲2. FCM迭代增强与划分混合聚类算法[J]. 计算机工程与应用, 2011, 47(34): 158-160.
[8]	李进，余建桥. 空间对象的反最近邻查询处理技术研究[J]. 计算机工程与应用, 2011, 47(33): 146-148.
[9]	曹旻，杨彩霞. FMM算法中问题规模与空间划分的关系分析[J]. 计算机工程与应用, 2011, 47(25): 39-43.
[10]	郑家彬，蒋夏军. 移动对象XML数据库的存储与索引[J]. 计算机工程与应用, 2011, 47(20): 138-143.
[11]	田建磊，刘旭敏，关永. 一种保特征的隐式曲面算法[J]. 计算机工程与应用, 2011, 47(1): 208-210.
[12]	邱永红^1,2,曾永年²,邹滨². KDT树：一种多维空间数据索引结构[J]. 计算机工程与应用, 2009, 45(8): 29-31.
[13]	孙劲光，王淑娥. CKDB-Tree：一种有效的高维动态索引结构[J]. 计算机工程与应用, 2009, 45(30): 157-160.
[14]	孙劲光¹，王淑娥¹，陈虹². 压缩金字塔树：有效的高维数据索引结构[J]. 计算机工程与应用, 2009, 45(22): 114-116.
[15]	苏锦旗¹，薛惠锋¹，吴慧欣². 基于熵度量的空间邻域离群点查找[J]. 计算机工程与应用, 2009, 45(21): 41-43.

向量空间划分类索引的动态更新代价分析

Cost analysis for dynamic update of vector space partitioning strategy index

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics