检索结果-南通市图书馆

PAA:海量数据上一种有效的近似聚集查询算法

在线全文

学校读者我要写书评

暂无评论

计算机研究与发展 2014年第1期51卷 41-53页

作者：韩希先李建中高宏哈尔滨工业大学计算机科学与技术学院哈尔滨150001

聚集查询是一种常用但是耗时的数据库操作.相对于准确查询,以少得多的响应时间向用户返回满足置信区间的近似结果通常是一种更好的选择.现有的近似查询方法无法在海量数据上高效地处理满足任意精度的近似聚集查询.提出一种新的算法PAA(p... 详细信息

聚集查询是一种常用但是耗时的数据库操作.相对于准确查询,以少得多的响应时间向用户返回满足置信区间的近似结果通常是一种更好的选择.现有的近似查询方法无法在海量数据上高效地处理满足任意精度的近似聚集查询.提出一种新的算法PAA(partition-based approximate aggregation)来有效处理满足任意置信区间的近似聚集.维属性的数据空间被划分为同样大小的空间区域,每个分片维护着维属性落入对应空间区域的元组.PAA算法维护表的随机样本RS,其执行包括两个阶段.在阶段1,如果利用预构建的随机样本RS不能返回满足用户要求的近似结果,那么在阶段2,PAA算法从与查询区域相交的空间区域对应的分片集合IPS中获得更多的随机元组.PAA算法的特色在于:1)如何在不知道IPS包含的每个分片满足谓词的元组数量情况下,从IPS中获得需要的随机元组;2)如何有效减少阶段2中的随机I/O费用.实验表明,相对于现有方法,PAA算法可以获得两个数量级的加速比.

关键词：海量数据 PAA算法近似聚集划分随机样本

在线全文

学校读者我要写书评

暂无评论

时间依赖代价函数下的最优路径查询问题研究

计算机学报 2012年第11期35卷 2247-2264页

作者：杨雅君高宏李建中哈尔滨工业大学计算机科学与技术学院哈尔滨150001

作者研究了时间依赖图下,具有时间限制的费用代价最优路径的查询问题.目前有关时间依赖图上的最短路径查询的研究工作解决的是最短旅行时间问题(TDSP),这些工作都利用了以下性质:到达某个顶点的最早时刻可以通过到达其邻居的最早时刻计... 详细信息

作者研究了时间依赖图下,具有时间限制的费用代价最优路径的查询问题.目前有关时间依赖图上的最短路径查询的研究工作解决的是最短旅行时间问题(TDSP),这些工作都利用了以下性质:到达某个顶点的最早时刻可以通过到达其邻居的最早时刻计算得出.然而,在计算具有时间限制的费用代价最优路径时,该性质并不成立.因此,目前解决TDSP问题的方法均不能解决文中面对的问题.对此作者提出一个新的算法用于计算时间依赖图模型上的满足时间限制的费用代价最优路径.该算法适用于有向图和无向图.作者证明了算法的时间复杂度和空间复杂度分别为O(knlogn+mk2logk)和O((n+m)k).最后,作者通过真实数据集上的实验,验证了该算法的有效性.

关键词：时间依赖图代价函数最优路径

在线全文

学校读者我要写书评

暂无评论

多维代价图模型上最优路径查询问题的研究

计算机学报 2012年第10期35卷 2147-2158页

作者：杨雅君高宏李建中哈尔滨工业大学计算机科学与工程学院哈尔滨150001

近年来,图数据模型被广泛地用于刻画现实世界中各种各样的实体间的复杂关系.最短路径查询是图研究领域中一类非常重要的查询并有着广泛的应用.然而,目前大多数关于最短路径的查询都是定义在单代价(权重)图模型下的.现实世界中,基于单一... 详细信息

近年来,图数据模型被广泛地用于刻画现实世界中各种各样的实体间的复杂关系.最短路径查询是图研究领域中一类非常重要的查询并有着广泛的应用.然而,目前大多数关于最短路径的查询都是定义在单代价(权重)图模型下的.现实世界中,基于单一代价所选择的最短路径并不明智,比如路程最短的路径需要花费极高的费用.该文中,作者介绍了多维代价图模型的概念,并给出了多维代价图模型下基于函数的最优路径的定义.现有的计算最短路径的方法都利用了最短路径的子路径最优的性质:最短路径上的任意两点间的子路径是这两点的最短路径.因此,在计算最短路径的过程中,对访问过的每个顶点,只需保留起点到该点的最短路径即可.不幸的是,多维代价图模型下,当评分函数是非线性的时候,子路径最优的性质并不成立.因此,目前的方法均不能应用于多维代价图模型下基于函数的最优路径查询问题.该文给出了一个best-first search分支界限法并给出3种优化策略.进一步,给出了一个顶点过滤算法,该算法能从图中过滤掉大部分不属于最优路径的顶点.最后,用真实数据集上的实验验证了算法的有效性.

关键词：多维代价图最短路径目标函数路径查询

DBCC-Join:一种新的高速缓存敏感的磁盘连接算法

在线全文

学校读者我要写书评

暂无评论

计算机学报 2010年第8期33卷 1500-1511页

作者：韩希先杨东华李建中哈尔滨工业大学计算机科学与技术学院哈尔滨150001 哈尔滨工业大学基础与交叉科学研究院高性能计算中心哈尔滨150001

随着CPU和内存的性能差距越来越大,系统设计者在CPU寄存器和内存之间插入高速缓存来弥补这个差距.高速缓存的数据存取速度远高于内存,所以数据库操作要获得更好的性能就必须考虑充分利用高速缓存.基于磁盘的连接操作是一种常用并且耗时... 详细信息

随着CPU和内存的性能差距越来越大,系统设计者在CPU寄存器和内存之间插入高速缓存来弥补这个差距.高速缓存的数据存取速度远高于内存,所以数据库操作要获得更好的性能就必须考虑充分利用高速缓存.基于磁盘的连接操作是一种常用并且耗时的数据库查询操作,可是大多数传统的连接算法在设计时都没有考虑高速缓存的使用,从而使得这些连接算法无法充分利用CPU的能力.文中分析了传统的连接算法在高速缓存利用方面的问题,并且提出了一种新的可以充分利用高速缓存的磁盘连接算法DBCC-Join.连接位置索引对表JPIPT是用到的数据结构,说明了每个连接结果元组在各自表中的位置索引对.DBCC-Join的执行包括两个阶段:JPIPT构建阶段和结果输出阶段.JPIPT构建阶段对列存储化的连接属性执行高速缓存敏感的算法来构建连接位置索引对表.利用获得的JPIPT,结果输出阶段只需要对数据表执行一遍顺序扫描就可以获得结果.该文是第一篇提出利用高速缓存的磁盘连接算法的文章.实验表明,和传统磁盘连接算法相比,DBCC-Join算法可以获得一个数量级的加速比.

关键词： DBCC-Join JPIPT构建阶段结果输出阶段缓存敏感算法

在线全文

学校读者我要写书评

暂无评论

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

计算机学报 2010年第10期33卷 1919-1933页

作者：韩希先杨东华李建中哈尔滨工业大学计算机科学与技术学院哈尔滨150001 哈尔滨工业大学基础与交叉科学研究院高性能计算中心哈尔滨150001

连接聚集操作是一种常用并且非常耗时的数据库操作.相对于准确查询,满足用户给定置信区间的近似结果由于其快得多的响应时间,更受用户的欢迎.作者分析发现现有的工作无法以既高效又满足给定的任意置信区间方式来处理近似连接聚集,因此... 详细信息

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

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

TKEP:海量数据上一种有效的Top-K查询处理算法

在线全文

学校读者我要写书评

暂无评论

计算机学报 2010年第8期33卷 1405-1417页

作者：韩希先杨东华李建中哈尔滨工业大学计算机科学与技术学院哈尔滨150001 哈尔滨工业大学基础与交叉科学研究院高性能计算中心哈尔滨150001

在许多应用领域中,top-k查询是一种十分重要的操作,它根据给定的评分函数在潜在的巨大的数据空间中返回k个最重要的对象.不同于传统的TA算法,NRA算法只需要顺序读就可以处理top-k查询,从而适合于随机读受限或不可能的场合.文中详细地分... 详细信息

在许多应用领域中,top-k查询是一种十分重要的操作,它根据给定的评分函数在潜在的巨大的数据空间中返回k个最重要的对象.不同于传统的TA算法,NRA算法只需要顺序读就可以处理top-k查询,从而适合于随机读受限或不可能的场合.文中详细地分析了NRA算法的执行行为,确定了增长阶段和收缩阶段中每个文件需要扫描的元组个数.文中发现在海量数据环境中,NRA在增长阶段需要维护大量的候选元组,严重影响了算法的执行效率.所以,文中提出一种新的海量数据上的top-k查询算法TKEP,该算法在查询的增长阶段就执行早剪切,从而大大减少增长阶段需要维护的候选元组.文中给出了早剪切操作的数学分析,确定了早剪切操作的理论和实际剪切效果.据作者所知,该文是第一篇提出在top-k查询的增长阶段执行早剪切的文章.实验结果表明,和传统的NRA相比,TKEP在增长阶段维护的元组数量减少3个数量级,需要的内存量减少1个数量级,TKEP算法获得1个数量级的加速比.

关键词：海量数据 top-k 早剪切 TKEP

在线全文

学校读者我要写书评

暂无评论

RM树:一种支持字符串相似性操作的索引

计算机学报 2011年第11期34卷 2142-2154页

作者：王金宝高宏李建中杨东华哈尔滨工业大学计算机科学与技术学院哈尔滨150001 哈尔滨工业大学基础与交叉科学研究院高性能计算中心哈尔滨150001

字符串相似性操作在很多领域中被广泛应用,如数据清洁、信息集成等.现有研究工作主要为基于q-Gram和倒排索引的内存方法,在处理大量数据时具有以下缺点:内存消耗大、更新效率低、支持操作类型有限.现有的外存索引Bed树无法将相似的字符... 详细信息

字符串相似性操作在很多领域中被广泛应用,如数据清洁、信息集成等.现有研究工作主要为基于q-Gram和倒排索引的内存方法,在处理大量数据时具有以下缺点:内存消耗大、更新效率低、支持操作类型有限.现有的外存索引Bed树无法将相似的字符串聚类,在查询处理过程中导致了较大的I/O代价.该文设计了支持多种字符串相似性操作的RM树索引,消除了现有内存方法的缺点,并通过字符串聚类的方法提高了相似性操作的效率.该文通过大量实验结果证明了RM树的有效性.

关键词：字符串相似性索引查询处理连接处理

基于MPI的二维泊松方程差分并行实现与测试

在线全文

学校读者我要写书评

暂无评论

哈尔滨商业大学学报（自然科学版） 2011年第6期27卷 854-856,861页

作者：苑野杨东华哈尔滨工业大学基础与交叉科学研究院哈尔滨150080

消息传递是一种广泛应用于集群环境下的并行编程模型.针对简单二维Poisson方程的第一边值问题的典型差分格式,在MPI并行环境下,使用五点差分离散和雅可比迭代法实现了此类方程的并行求解.实际测试表明此类方程在一定问题规模下,其并行... 详细信息

消息传递是一种广泛应用于集群环境下的并行编程模型.针对简单二维Poisson方程的第一边值问题的典型差分格式,在MPI并行环境下,使用五点差分离散和雅可比迭代法实现了此类方程的并行求解.实际测试表明此类方程在一定问题规模下,其并行算法具有很好的加速比和并行效率.

关键词： Poisson方程消息传递接口有限差分加速比并行效率

在线全文

学校读者我要写书评

暂无评论

云计算系统中查询处理及优化技术研究综述

智能计算机与应用 2013年第4期3卷 51-54页

作者：王金宝高宏哈尔滨工业大学计算机科学与技术学院哈尔滨150001

云计算系统中的查询及优化技术是近年来倍受关注的热点研究领域,综合了并行计算、分布式计算和查询处理及优化技术等方面的研究成果,具有广阔的应用前景。云计算系统中的查询和优化是一项基础而重要的操作,被研究者们所广泛关注,也涌现... 详细信息

云计算系统中的查询及优化技术是近年来倍受关注的热点研究领域,综合了并行计算、分布式计算和查询处理及优化技术等方面的研究成果,具有广阔的应用前景。云计算系统中的查询和优化是一项基础而重要的操作,被研究者们所广泛关注,也涌现出了很多研究工作。总结了近年来云计算系统中的查询处理和查询优化方向的研究工作,讨论了现有工作的内容和需要进一步研究的方向,并提供了广泛的参考文献。

关键词：云计算查询处理查询优化