QQ客服 官方微博 反馈留言

	MX-tree: A double hierarchical metric index with overlap reduction
	Jin, Shichao ; Kim, Okhee ; Feng, Wenya
	2013
英文摘要	Large multimedia repositories often call for a highly efficient index supported by external memories, in order to fast retrieve the desired information. The M-tree, one of the metric trees, is a well-tested and dynamic index structure for similarity search in metric spaces where various distance measures can be applied. Nevertheless, its performance is undermined dramatically by the number of paths it has to traverse, which consequently increases CPU and I/O costs both. In this paper, an analysis has been performed to demonstrate the gravity of this issue. As a result, we propose a novel index structure called the MX-tree. It introduces the super node, which is inspired by the X-tree in the spatial search area, and the MX-tree fully extends the super node to metric spaces. Besides, a new node split method is presented in the MX-tree to meet the need of the low cost of index construction. This proposed method uses only O(n 2) runtime to split the overfull node without tuning any parameter while the search performance of the whole index is still guaranteed compared to the node split policy with O(n 2) in the M-tree. In addition, an internal index is proposed in the MX-tree to seamlessly handle the CPU costs in the extended leaf nodes due to the introduction of the super node. Compared to other former improvements of the M-tree, the MX-tree retains all the merits of the M-tree without any post-processing steps or losing the applicability. To survey the proposed index, we conduct extensive experiments, and experimental evaluations illustrate the efficiency of the MX-tree with regard to both CPU and I/O costs. ? 2013 Springer-Verlag Berlin Heidelberg.; EI; 0
语种	英语
DOI标识	10.1007/978-3-642-39640-3-42
内容类型	其他
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/325788]
专题	软件与微电子学院
推荐引用方式 GB/T 7714	Jin, Shichao,Kim, Okhee,Feng, Wenya. MX-tree: A double hierarchical metric index with overlap reduction. 2013-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。