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

Cost analysis for dynamic update of vector space partitioning strategy index

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

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.