摘要
一般来说,外存访问的数据文件中针对多属性的区域查询有两个改进其效率的方向。一个是在其上建立索引,另一个是在物理层按照某种规律重新安排记录。探讨如何通过第二种方法来提高范围查询的效率,即通过多维聚簇的方式得到数据文件中更好的记录的存储顺序。首先,细致分析了该问题,并针对该问题构造了一个数学模型,然后通过引入光谱算法(SA)的思想为解决该NP难问题提供了一种多项式时间内的近似解。最后通过实验来验证了该方法在矩形区域查询和单维范围查询方面的有效性。
Generally there are two directions to improve the query performance of range queries on multiple attributes in a static data file. One is to devise an index, and the other is to rearrange records in physical layer. In this paper, we took the second way to give a better data file organization, which we call multidimensional clustering. First we analyzed the problem, and constructed a mathematical model for this it, and then based on the idea of Spectrum Algorithm （SA）, we devised a polynomial method to heuristically solve this NP-hard problem. And the experiment results show that the spectrum algorithm is an effective record reorganization method for range queries.
出处
《计算机科学》
CSCD
北大核心
2009年第6期133-137,共5页
Computer Science
基金
国家自然科学基金(60673135
60373081)重点项目(60736020)
教育部新世纪优秀人才支持计划(NCET-04-0805)
广东省自然科学基金(7003721)资助
关键词
高维聚簇
数据重组
范围查询
光谱算法
Multidimensional clustering, Data reorganization, Range query,Spectrum algorithm
