海量数据上的近似连接聚集操作  

Approximate Join Aggregate on Massive Data

作　　者：韩希先[1] 杨东华[2] 李建中[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001 [2]哈尔滨工业大学基础与交叉科学研究院高性能计算中心,哈尔滨150001

出　　处：《计算机学报》2010年第10期1919-1933,共15页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(2006CB303005);国家自然科学基金(60903016;60533110;60773063);新世纪优秀人才支持计划(NCET-05-0333);黑龙江省教育厅科学技术研究项目(11531276);NSFC-RGC of China(60831160525)资助~~

摘　　要：连接聚集操作是一种常用并且非常耗时的数据库操作.相对于准确查询,满足用户给定置信区间的近似结果由于其快得多的响应时间,更受用户的欢迎.作者分析发现现有的工作无法以既高效又满足给定的任意置信区间方式来处理近似连接聚集,因此提出了一种新的算法——(p,ε)-近似连接聚集查询(pε-AJA)来有效地返回满足任意置信区间的近似连接聚集结果.文章提出且预计算两个数据结构:连接随机样本(JRS)和连接位置索引对表(JPIPT).利用JRS,pε-AJA向用户返回近似结果的快速响应.如果利用JRS得到的近似结果没有满足给定的置信区间,pε-AJA利用JPIPT获得更多的随机连接元组.文中提出一种采样算法来获得JPIPT给定数量的样本,并且利用获得的JPIPT样本,该文提出的算法可通过对连接表的一遍顺序扫描获得连接元组.该文还提供了JPIPT和JRS有效的构建和维护算法.实验结果表明:pε-AJA可以获得相对于准确查询1～5个数量级的加速,并且可以有效地完成JPIPT和JRS的构建和维护操作.Join aggregate is a commonly used but time-consuming operation in database. Compa- ring to exact queries, approximate results satisfying user-specified confidence intervals are more attractive for their much faster responses. None of the previous work can process approximate join aggregate with both high efficiency and an arbitrarily specified confidence interval. This pa- per proposes a novel algorithm, （p,e） Approximate Join Aggregate （pe-AJA）, which is able to return approximate results for arbitrary confidence interval efficiently. Two data structures, join random sample （JRS） and join positional index pair table （JPIPT）, are presented and pre-compu- ted in ρε-AJA, ρε-AJA first makes use of JRS to make a quick response of approximate results to users. If the approximate results from JRS do not satisfy the given confidence interval, JPIPT is exploited to obtain more random join tuples. A sampling algorithm is provided to sample JPIPT tuples of specified size. Algorithms are also presented to retrieve join tuples by sampled JPIPT tuples in one pass sequential scan. The construction and maintenance of JPIPT and JRS are pro- vided in this paper. The experimental results show that ρε-AJA obtains approximate results for arbitrary confidence intervals with a speedup by 1 to 5 orders of magnitude compared to exact queries and the update operations for JPIPT and JRS are efficient.

关 键 词：pε-近似连接聚集 连接位置索引对表 连接随机样本 海量数据 

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