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

• 博士论坛 • 上一篇    下一篇

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

李博涵1,郝忠孝1,2   

  1. 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-han1,HAO Zhong-xiao1,2   

  1. 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

摘要: 代价分析是借助代价模型预测和评估空间索引结构的一种有效方法。针对索引的空间划分和数据划分这两种策略,在已有的索引结构基础上建立了向量空间划分类型索引的代价模型,该模型可实现查询以及动态更新的性能评价。以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