ScanChunk:一种在数据方体中寻找密集区域的有效算法  

SCANCHUNK:AN EFFICIENT ALGORITHM FOR HUNTING DENSE REGIONS IN DATA CUBE

作　　者：周波[1] 

机构地区：[1]浙江大学计算机科学与工程系,杭州310027

出　　处：《计算机学报》1999年第6期620-626,共7页Chinese Journal of Computers

摘　　要：为实现ＭＯＬＡＰ和ＲＯＬＡＰ的有机融合，达到较好的存储效率和操作效率，提出了一种基于密集区域的新的数据方体组织结构．给出了确定数据方体中密集区域的明确定义，分析了现有相关算法的可行性．在此基础上，提出了一种在数据方体中寻找密集区域的算法ＳｃａｎＣｈｕｎｋ，同时分析了算法的计算精度和复杂度，并进行了详细的实验．结果表明。MOLAP and ROLAP are two main approaches of building OLAP system. MOLAP is good for query performance but suffers from storage inefficiency when the data cube is sparse. ROLAP can be built on mature RDBMS technology but its performance is not as competitive. The paper presents a new structure of data cube based on the dense regions. Following the new structure, the MOLAP and ROLAP approaches can be integrated to obtain both high query performance and space efficiency. The core of building the new structure lies in hunting dense regions from raw data. The dense region hunting problem is defined as an optimization problem in this paper. An efficient algorithm named ScanChunk has been developed. The accuracy and complexity of algorithm ScanChunk have been analyzed and extensive performance studies have been performed. The experimental results clearly show that ScanChunk is efficient and effective in locating dense region in large database.

关 键 词：联机数据分布 数据方体 ScanChunk 数据库 算法 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]