Cost analysis for dynamic update of vector space partitioning strategy index

doi:10.3778/j.issn.1002-8331.2009.18.005

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (18): 18-21.DOI: 10.3778/j.issn.1002-8331.2009.18.005

• 博士论坛 • Previous Articles Next Articles

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

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

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

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

通讯作者: 李博涵

Abstract

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

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

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

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,2. 向量空间划分类索引的动态更新代价分析[J]. 计算机工程与应用, 2009, 45(18): 18-21.

[1]	ZHAO Ji1，2, CHENG Cheng3. Improved QPSO algorithm based on search history [J]. Computer Engineering and Applications, 2017, 53(9): 41-46.
[2]	DONG Yushan, LI Chunjiang, XU Ying. Implementation and effects of loop-array-prefetching optimization in GCC [J]. Computer Engineering and Applications, 2016, 52(6): 19-25.
[3]	ZHANG Xiaorui1, LIU Jiamin2, LUO Yuegang3. Handling and comparing three-dimensional spaces based on application constraints [J]. Computer Engineering and Applications, 2015, 51(15): 231-235.
[4]	XU Hongbo1，2, YAO Nianmin2, HAN Qilong2, PAN Haiwei2. Index structure CB-tree supporting line query [J]. Computer Engineering and Applications, 2015, 51(11): 114-118.
[5]	CHEN Gang, QIAN Meng, LIU Jin. Trajectory outlier detection based on space partition [J]. Computer Engineering and Applications, 2014, 50(24): 127-132.
[6]	ZHANG Debin¹，CAO Lijun²，LIANG Yongxin¹，ZHANG Zhongping¹. X*tree index structure for k nearest neighbor queries [J]. Computer Engineering and Applications, 2011, 47(5): 123-125.
[7]	LI Jin，YU Jianqiao. Research on technology of reverse nearest neighbor query for spatial objects [J]. Computer Engineering and Applications, 2011, 47(33): 146-148.
[8]	ZHENG Jiabin，JIANG Xiajun. Storage and indexing of moving objects XML database [J]. Computer Engineering and Applications, 2011, 47(20): 138-143.
[9]	MOU Hai-ning. Blending of corners with controllable shape parameters [J]. Computer Engineering and Applications, 2010, 46(33): 158-159.
[10]	QIU Yong-hong^1,2,ZENG Yong-nian²,ZOU Bin². KDT tree：Multi-dimensional index structure for spatial data [J]. Computer Engineering and Applications, 2009, 45(8): 29-31.
[11]	SUN Jin-guang，WANG Shu-e. CKDB-Tree：Effective index structure in high-dimensional data spaces [J]. Computer Engineering and Applications, 2009, 45(30): 157-160.
[12]	MOU Hai-ning¹,ZHAO Guo-hui²,WANG Zhi-rui²,SU Zhi-xun². Blending of set operations of polyhedra by algebraic splines [J]. Computer Engineering and Applications, 2008, 44(22): 204-205.
[13]	SONG Xiao-yu,SUN Ye-ting,SUN Huan-liang. K-nearest neighbor queries over moving objects for dynamic workload [J]. Computer Engineering and Applications, 2007, 43(27): 152-155.
[14]	,,. Query Cost Optimization Model based on Remote Server Contention States Over the Internet [J]. Computer Engineering and Applications, 2006, 42(17期): 12-.

Cost analysis for dynamic update of vector space partitioning strategy index

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 14

Recommended Articles

Metrics