用于聚集值近似查询的基于密度的树索引结构  

A Density-based Tree Structure for Approximating Aggregate Queries

作　　者：许俭[1] 吴天轶[1] 王晨[1] 汪卫[1] 施伯乐[1] 

机构地区：[1]复旦大学计算机与信息技术系,上海200433

出　　处：《计算机科学》2005年第11期99-103,共5页Computer Science

基　　金：国家自然科学基金(69933010和60303008);国家863高科技项目(2002AA4Z3430和2002AA231041)

摘　　要：如何快速有效地对数据立方体上的聚集查询给出近似的回答,是数据挖掘和数据仓库研究领域中的核心问题之一。现有大多数聚集查询算法在同一个数据立方体上只能支持某种特定的而非多种类型的聚集查询。本文给出了一种新的框架AdenTS,即基于密度的自适应树结构,它可以回答同一数据立方体上的各类聚集查询,也提出了一些近似和启发式技术,改善了查询结果和精度。实验结果表明,这种方法在支持的查询种类和性能上是更好的。In many fields and applications, it is critical for users to make decisions through OLAP queries. How are accuracy and efficiency promoted while answering multiple aggregate queries, e.g. COUNT, SUM, AVG, MAX, MIN and MEDIAN？ It has been the urgent problem in the fields of OLAP and data summarization recently. There have been a few solutions such as MRA-Tree and GENHIST for it. However, they could only answer a certain aggregate query which was defined in a particular data cube with some limited applications. In this paper, we develop a novel framework ADenTS, e.g. Adaptive Density-based Tree Structure, to answer various types of aggregate queries within a single da- ta cube. We represent the whole cube by building a coherent tree structure. Furthermore, several techniques for approximation and heuristic approaches are proposed to improve the accuracy of query answering. The experimental results show that the method outperforms others in effectiveness and efficiency.

关 键 词：聚集查询 近似查询 密度 树结构 基于密度 索引结构 近似 数据立方体 集值 数据仓库 

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