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

• 作者: 李建中 杨东华 韩希先
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: pε-近似连接聚集 连接位置索引对表 连接随机样本 海量数据
• 年，卷（期）: 2010,（10）
• 页码范围: 1919-1933
• 分类号: TP311
• 字数: 11298字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2010.01919

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李建中	哈尔滨工业大学计算机科学与技术学院	237	6003	33.0	72.0
2	杨东华	哈尔滨工业大学基础与交叉科学研究院高性能计算中心	11	167	7.0	11.0
3	韩希先	哈尔滨工业大学计算机科学与技术学院	11	159	6.0	11.0