| MC-Tree: Dynamic Index Structure for Partially Clustered Multi-Dimensional Database |
| |
| 作者姓名： | 靳晓明 王丽坤 陆玉昌 石纯一 |
| |
| 作者单位： | State Key Laboratory of Intelligent Technology and Systems，Department of Computer Science and Technology，Tsinghua University，Beijing 100084，China，State Key Laboratory of Intelligent Technology and Systems，Department of Computer Science and Technology，Tsinghua University，Beijing 100084，China，State Key Laboratory of Intelligent Technology and Systems，Department of Computer Science and Technology，Tsinghua University，Beijing 100084，China，State Key Laboratory of Intelligent Technology and Systems，Department of Computer Science and Technology，Tsinghua University，Beijing 100084，China |
| |
| 基金项目： | Supported by the Chinese National Key FundamentalResearch Program(No.G1998030414)，the National Natural Science Foundation of China (No.79990580)，the“985” Program of Tsinghua University |
| |
| 摘 要： | Index structure that enables efficient similarity queries in high-dimensional space is crucial for many applications. This paper discusses the indexing problem in dataset composed of partially clustered data, which exists in many applications. Current index methods are inefficient with partially clustered datasets. The dynamic and adaptive index structure presented here, called a multi-cluster tree (MC-tree), consists of a set of height-balanced trees for indexing. This index structure improves the querying efficiency in three ways: 1) Most bounding regions achieve uniform distributions, which results in fewer splits and less overlap compared with a single indexing tree. 2) The clusters in the dataset are dynamically detected when the index is updated. 3) The query process does not involve a sequential scan. The MC-tree was shown to be better than hierarchical and cluster-based indexes for the partially clustered datasets.
|
MC-Tree: Dynamic Index Structure for Partially Clustered Multi-Dimensional Database |
| |
| JIN Xiaoming WANG Likun,LU Yuchang,SHI Chunyi
State Key Laboratory of Intelligent Technology and Systems.MC-Tree: Dynamic Index Structure for Partially Clustered Multi-Dimensional Database[J].Tsinghua Science and Technology,2003,8(2). |
| |
| Authors: | JIN Xiaoming WANG Likun LU Yuchang SHI Chunyi
State Key Laboratory of Intelligent Technology and Systems |
| |
| Institution: | JIN Xiaoming WANG Likun,LU Yuchang,SHI Chunyi
State Key Laboratory of Intelligent Technology and Systems. Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China |
| |
| Abstract: | Index structure that enables efficient similarity queries in high-dimensional space is crucial for many applications. This paper discusses the indexing problem in dataset composed of partially clustered data, which exists in many applications. Current index methods are inefficient with partially clustered datasets. The dynamic and adaptive index structure presented here, called a multi-cluster tree (MC-tree), consists of a set of height-balanced trees for indexing. This index structure improves the querying efficiency in three ways: 1) Most bounding regions achieve uniform distributions, which results in fewer splits and less overlap compared with a single indexing tree. 2) The clusters in the dataset are dynamically detected when the index is updated. 3) The query process does not involve a sequential scan. The MC-tree was shown to be better than hierarchical and cluster-based indexes for the partially clustered datasets. |
| |
| Keywords: | MC-tree multi-dimensional index similarity query partially clustered dataset |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
