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

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

韩希先;杨东华;李建中

【期刊名称】《计算机学报》 【年(卷),期】2010(033)010

【摘要】连接聚集操作是一种常用并且非常耗时的数据库操作.相对于准确查询,满足用户给定置信区间的近似结果由于其快得多的响应时间,更受用户的欢迎.作者分析发现现有的工作无法以既高效又满足给定的任意置信区间方式来处理近似连接聚集,因此提出了一种新的算法--(p,ε)-近似连接聚集查询(pε-AJA)来有效地返回满足任意置信区间的近似连接聚集结果.文章提出且预计算两个数据结构:连接随机样本 (JRS)和连接位置索引对表(JPIPT).利用JRS,pε-AJA向用户返回近似结果的快速响应.如果利用JRS得到的近似结果没有满足给定的置信区间,pε-AJA 利用JPIPT获得更多的随机连接元组.文中提出一种采样算法来获得JPIPT给定数量的样本,并且利用获得的JPIPT样本,该文提出的算法可通过对连接表的一遍顺序扫描获得连接元组.该文还提供了JPIPT和JRS有效的构建和维护算法.实验结果表明:pε-AJA可以获得相对于准确查询1～5个数量级的加速,并且可以有效地完成JPIPT和JRS的构建和维护操作. 【总页数】15页(1919-1933)

【关键词】pε-近似连接聚集;连接位置索引对表;连接随机样本;海量数据 【作者】韩希先;杨东华;李建中

【作者单位】哈尔滨工业大学计算机科学与技术学院,哈尔滨,150001;哈尔滨工业大学基础与交叉科学研究院高性能计算中心,哈尔滨,150001;哈尔滨工业大学计算机科学与技术学院,哈尔滨,150001