一个基于Semijoin的并行join算法SBABJ

本文在并行ｊｏｉｎ法ＡＢＪ＾＋的基础上提出一个基于Ｓｅｍｉｊｏｉｎ的改进算法ＳＢＡＢＪ。我们在多台Ｓｕｎ工作站是实现了该算法，并对ＡＢＪ＾＋和ＳＢＡＢＪ＾＋进行了能测试。算法分析和实验结果表明了并行ｊｏｉｎ算法ＳＢＡＢＪ＾＋优于ＡＢＪ＾＋算法。     

并行数据库上的进行CMD—Join算法

并行数据库在多处理机之间的分布方法对并行数据 算法的性能影响很大，如果在设计并行数据操作算法时充分利用数据分布方法的特点，可以得到十分有效的并行算法。本研究如何充分利用数据分布方法的特点，设计并行数据操作算法的问题，提出了基ＣＭＤ多维数据分布方法的并行ＣＭＤ－Ｊｏｉｎ算法，理论分析和实验结果表明，并行ＣＭＤ－Ｊｏｉｎ算法的效率高于其它并行Ｊｏｉｎ算法。     

并行数据库复杂关系查询优化的一种方法

查询优化不仅是顺序数据库系统的重要组成部分，也是并行数据库的重要组成部分，而多个Ｊｏｉｎ操作的复杂关系数据库的查询经又是目前研究的 主要课题。     

并行数据库的改进Hash划分方法及并行Join算法

文中提出了Ｈａｓｈ划分的改进方法－－ＩＨ划分,ＩＨ划分为结点扩充时数据的重新划分提供了方便,在论述ＩＨ划分的基础上,给出了基于该数据划人垢并行Ｊｏｉｎ算法,利用已有数据分布,文中提出的并行Ｊｏｉｎ算法提高算法的效率。最后,从理论上对以上并行算法的计算复杂性进行了分析。     

并行数据库系统PARO的物理设计方法与实现

物理设计方法是并行数据库系统研究和实现中的一个核心问题，本文介绍我们在一个并行数据库原型系统中采用的数据库物理设计方法，描述其数据划分，并行Ｂ树索引结构和几种复杂并行数据组织形式。     

并行数据操作算法和查询优化技术

本文是并行数据库的查询处理并行化技术和物理设计方法”一文的续篇，继续综述并行数据库系统的另外两个重要研究领域：并行数据操作算法和并行数据库查询优化技术．最后，作为并行数据库系统研究与进展情况综述的结尾，本文将探讨并行数据库系统今后的研究方向和问题．     

关系数据库系统并行化方法

提出一种新的并行数据库系统的实现模型，称为“半重写变换”模型。基于该模型提出了一种并行数据库系统的结构。这一结构由多个ＤＢＭＳ Ｉｎｓｔａｎｃｅｓ和并行查询服务器（ＰＱＳ）组成。文中首先描述了“半重写变换”模型，然后描述了基于这个模型实现的一个并行查询原型系统ＰａｒａＢａｓｅ，最后给出基于Ｗｉｓｏｎｓｉｎ Ｂｅｎｃｈｍａｒｋ的一组性能测试结果。     

基于工作站机群结构的并行数据库连接算法的实现

本文心细介绍了基于无共享并行结构的并行嵌套环连接（ＰＮＬＪ）算法的实现,旨在探索并行数据库系统的实现技术。     

并行数据库的研究

本文回顾了并行数据库的发展史和研究现状，并以与分布式数据库（ＤＤＢ）对比的方式，着重介绍并行数据库（ＰＤＢ）的硬件结构、并行数据库管理系统（ＰＤＢＭＳ）的参考模型以及并行数据库中的ｊｏｉｎ运算。     

并行数据库PDBMS的设计与实现

文章介绍了并行数据库管理系统ＰＤＢＭＳ的设计与实现方法,探讨了并行数据库系统设计和实现中的一些关键技术。     

阵列众核结构上的一种多层分区Hash连接算法

连接是数据查询处理中最耗时、使用最频繁的操作之一,对提高连接操作的速率具有重要意义。阵列众核处理器是一类重要的众核处理器,具有强大的并行能力,可用来加速并行计算。基于阵列众核处理器的结构,设计和优化了一种高效的多层分区Hash连接算法。该算法通过多层划分的策略大大降低了主存访问次数,通过分区重排方法有效消除了数据倾斜的影响,获得了很高的性能。在异构融合阵列众核处理器DFMC(Deeply-Fused Many Core)原型系统上的实验结果表明,DFMC上多层分区Hash连接算法的性能是CPU-GPU耦合结构上最快的连接算法的8.0倍,表明利用阵列众核处理器加速数据查询应用具有优势。     

基于DSVM的并行Hash连接算法及其性能评价

提出了一个基于分布式共享虚拟存储器技术的并行Ｈａｓｈ连接算法,然后设计了一个并行连接算法的测试评价基准,并评价和分析了该算法在均匀情况下３个不同负载的性能比较和Ｚｉｐｆ顺斜数据分布情况下两种度策略的算法性能。同时与其它并行连接算法进行性能比较与分析。     

基于哈希的B+树结构的频繁模式挖掘

提出了一种基干改进的B 树结构及一种新的数据挖掘算法，HB-Minc，该算法通过构造哈希函数，获得B 树的关键字，并在B 树的叶子结点上构建链表结构，记录卡H关关键字的项集及频数，这样在无需产生巨大的候选项集的情况下，挖掘出频繁模式，且具有较高的时间效率。     

抗数据偏斜的高效并行join运算算法研究

通过分析ABJ 算法和Hybrid hash join算法,并对两个算法进行了结合和改进,提出了一种能克服各种数据偏斜的并行二元连接运算算法,可在不同的数据偏斜情况下启动不同的模块,克服数据偏斜造成的负载不平衡现象。     

抗数据偏斜的高效并行join运算算法研究

通过分析ABJ＋算法和Hybrid hash join算法,并对两个算法进行了结合和改进,提出了一种能克服各种数据偏斜的并行二元连接运算算法,可在不同的数据偏斜情况下启动不同的模块,克服数据偏斜造成的负载不平衡现象。     

Spatial join processing using corner transformation

Spatial join finds pairs of spatial objects having a specific spatial relationship in spatial database systems. Since spatial join is a fairly expensive operation, we need an efficient algorithm taking advantage of the characteristics of available spatial access methods. In this paper, we propose a spatial join algorithm using corner transformation and show its excellence through experiments. To the extent of authors' knowledge, the spatial join processing using corner transformation is new. In corner transformation, two regions in one file joined with two adjacent regions in the other file share a large common area. The proposed algorithm utilizes this property in order to reduce the number of disk accesses for spatial join. Experimental results show that the performance of the algorithm is generally better than that of the R*-tree based algorithm proposed by Brinkhoff et al. (1993. 1994). This is a strong indication that corner transformation is a promising category of spatial access methods and that spatial operations can be performed better in the transform space than in the original space. This reverses the common belief that transformation will adversely effect the clustering. We also briefly mention that the join algorithm based on corner transformation has a nice property of being amenable to parallel processing. We believe that our result will provide a new insight towards transformation-based processing of spatial operations     

一种避免数据偏斜的动态Hash连接方法

本文提出了一种新的动态Hash连接方法──DHJ（dynamichash　join），以解决并行数据库连接操作中的数据偏斜现象.为避免目前某些算法提出的预处理中隐含的高额费用，该方法在划分阶段通过增添附加桶的方法来平衡输出，然后依据计算确认哪些附加桶被映射到处理器上并确定处理器分配，在最后阶段完成连接.本文最后给出了该算法的性能分析.     

Parallel Algorithms for Discovery of Association Rules

Discovery of association rules is an important data mining task. Several parallel and sequential algorithms have been proposed in the literature to solve this problem. Almost all of these algorithms make repeated passes over the database to determine the set of frequent itemsets (a subset of database items), thus incurring high I/O overhead. In the parallel case, most algorithms perform a sum-reduction at the end of each pass to construct the global counts, also incurring high synchronization cost. In this paper we describe new parallel association mining algorithms. The algorithms use novel itemset clustering techniques to approximate the set of potentially maximal frequent itemsets. Once this set has been identified, the algorithms make use of efficient traversal techniques to generate the frequent itemsets contained in each cluster. We propose two clustering schemes based on equivalence classes and maximal hypergraph cliques, and study two lattice traversal techniques based on bottom-up and hybrid search. We use a vertical database layout to cluster related transactions together. The database is also selectively replicated so that the portion of the database needed for the computation of associations is local to each processor. After the initial set-up phase, the algorithms do not need any further communication or synchronization. The algorithms minimize I/O overheads by scanning the local database portion only twice. Once in the set-up phase, and once when processing the itemset clusters. Unlike previous parallel approaches, the algorithms use simple intersection operations to compute frequent itemsets and do not have to maintain or search complex hash structures. Our experimental testbed is a 32-processor DEC Alpha cluster inter-connected by the Memory Channel network. We present results on the performance of our algorithms on various databases, and compare it against a well known parallel algorithm. The best new algorithm outperforms it by an order of magnitude.     

A survey of alternative designs for a search engine storage structure

Three information retrieval storage structures are considered to determine their suitability for a World Wide Web search engine: The Wolverhampton Web Library — The Next Generation. The structures are an inverted file, signature file and Pat tree. A number of implementations are considered for each structure. For the index of an inverted file a sorted array, B-tree, B+-tree, trie and hash table are considered. For the signature file vertical and horizontal partitioning schemes are considered and for the Pat tree a tree and array implementation are considered. A theoretical comparison of the structures is done on seven criteria that include: response time, support for results ranking, search techniques, file maintenance, efficient use of disk space (including the use of compression), scalability and extensibility. The comparison reveals that an inverted file is the most suitable structure, unlike the signature file and Pat tree, which encounter problems with very large corpora.