Late join algorithms for distributed interactive applications

Distributed interactive applications such as shared whiteboards and multiplayer games often support dynamic groups where users may join and leave at any time. A participant joining an ongoing session has missed the data that have previously been exchanged by the other session members. It is therefore necessary to initialize the application instance of the latecomer with the current state. In this paper, we propose a late join algorithm for distributed interactive applications that provides such an initialization of applications. The algorithm is scalable and robust and can be easily adapted to the needs of different applications by means of late join policies. The behavior of the late join algorithm and the impact of design alternatives are investigated in detail by means of an extensive simulation study. This study also shows that an improper handling of the late join problem can cause very high application and network load.     

Parallel join for IBGF partitioned relational databases

This study is concerned with a parallel join operation where the subject relations are partitioned according to an interpolation based grid file (IBGF) scheme. The partitioned relations and directories are distributed over a set of independently accessible external storage units, together with the partitioning control data. The join algorithms executed by a mesh type parallel computing system allow handling of uniform as well as nonuniformly partitioned relations. Each processor locates and retrieves the data partitions it is to join at each step of the join process, in synchronisation with other processors. The approach is found to be feasible as the speedup and efficiency results found by simulation are consistent with theoretical bounds. The algorithms are tuned to join-key distributions, so that effective load balancing is achieved during the actual join. © 1997 John Wiley & Sons, Ltd.     

The join algorithms on a shared-memory multiprocessor databasemachine

The authors develop and present a large set of parallel algorithms for implementing the join operation on a shared-memory multiprocessor database machine. The development of these algorithms follows a structured approach. The major steps involved in the processing of the join operation by the machine are first identified. Then, alternative join algorithms are constructed by concatenating the different ways of performing these steps. A study of the performance of the proposed algorithms is presented. This study shows, among other things, that for a given hardware configuration there is not just one overall best performing join algorithm, but rather different algorithms score the best performance, depending on the characteristics of the data participating in the join operation     

Parallel algorithms for arrangements

We give the first efficient parallel algorithms for solving the arrangement problem. We give a deterministic algorithm for the CREW PRAM which runs in nearly optimal bounds ofO (logn log^* n) time andn ²/logn processors. We generalize this to obtain anO (logn log^* n)-time algorithm usingn ^d /logn processors for solving the problem ind dimensions. We also give a randomized algorithm for the EREW PRAM that constructs an arrangement ofn lines on-line, in which each insertion is done in optimalO (logn) time usingn/logn processors. Our algorithms develop new parallel data structures and new methods for traversing an arrangement.This work was supported by the National Science Foundation, under Grants CCR-8657562 and CCR-8858799, NSF/DARPA under Grant CCR-8907960, and Digital Equipment Corporation. A preliminary version of this paper appeared at the Second Annual ACM Symposium on Parallel Algorithms and Architectures [3].     

GPU-based efficient join algorithms on Hadoop

The Journal of Supercomputing - The growing data have brought tremendous pressure for query processing and storage, so there are many studies that focus on using GPU to accelerate join operation,...     

Parallel algorithms for a hypercomplex discrete fourier transform

Methods for the parallel computation of a multidimensional hypercomplex discrete Fourier transform (HDFT) are considered. The basic idea consists in the application of the properties of the hypercomplex algebra in which this transform is performed. Additional possibilities for increasing the efficiency of the algorithm are provided by the natural parallelism of the multidimensional Cooley-Tukey scheme. Marat Vyacheslavovich Aliev. Born 1978. Graduated from the Adygeya State University in 2000. Received candidate’s degree in physics and mathematics in 2004. Presently he is a senior lecturer at the Department of Applied Mathematics and Information Technologies, Adygeya State University. Scientific interests: image processing, fractals, fast algorithms of discrete transforms, and finite-dimensional algebras. Author of 14 publications, including 7 papers. Member of the Russian Association of Pattern Recognition and Image Analysis. Aleksandr Mikhailovich Belov. Born 1980. Graduated from the Samara State Aerospace University in 2002. In the same year, he entered postgraduate courses with the specialty 05.13.18: mathematical modeling, numerical methods, and program complexes. Presently he is a postgraduate student at the Department of Geoinformatics, Samara State Aerospace University, and a trainee at the Laboratory of Mathematical Methods of Image Processing, Image Processing Systems Institute, Russian Academy of Sciences. Scientific interests: discrete orthogonal transforms, fast algorithms of discrete orthogonal transforms, and theory of canonical systems of calculus. Author of 13 publications, including 5 papers. Member of the Russian Association of Pattern Recognition and Image Analysis. Aleksei Vladimirovich Ershov. Born 1983. In 2000, he graduated from the Samara Lyceum of Economics and entered the Faculty of Mechanics and Mathematics, Samara State University, to specialize in the field of Organization and Technology of Information Security. In 2001, he started his training within an additional educational program and was qualified as a translator in the field of professional communication. Presently he is a fifth-year student at Samara State University. The title of his diploma work is “Control of the Flows of Confidential Information.” He is an active participant in the translation of the monograph Principia Mathematica, Cambridge University Press, 1927, by A. Whitehead and B. Russell. Author of four publications, including two papers. Marina Aleksandrovna Chicheva. Born 1964. Graduated from the Kuibyshev Aviation Institute (now Samara State Aerospace University) in 1987. Received candidate’s degree in Engineering in 1998. Presently she is a senior researcher at the Image Processing Systems Institute, Russian Academy of Sciences. Scientific interests: image processing, compression, and fast algorithms of discrete transforms. Author of more than 50 publications, including 18 papers and 1 monograph. Member of the Russian Association of Pattern Recognition and Image Analysis.     

Parallel algorithms for line generation

A new, parallel approach for generating Bresenham-type lines is developed. Coordinate pairs which approximate straight lines on a square grid are derived from line equations. These pairs serve as a basis for the development of four new parallel algorithms. One of the algorithms uses the fact that straight time generation is equivalent to a vector prefix sums calculation. The algorithms execute on a binary tree of processors. Each node in the tree performs a simple calculation that involves only additions and shifts. All four algorithms have time complexityO(log₂ n) wheren in the form 2 ^m denotes the number of points generated andn-1 is the number of processors in the tree. This compares toO(n) for Bresenham's algorithm executed on a sequential processor. Pipelining can be used to achieve a constant time per line generation as long as line length is less thann.     

Parallel algorithms for tree traversals

Three commonly used traversal methods for binary trees (forsets) are pre-order, in-order and post-order. It is well known that sequential algorithms for these traversals takes order O(N) time where N is the total number of nodes. This paper establishes a one-to-one correspondence between the set of nodes that possess right sibling and the set of leaf nodes for any forest. For the case of pre-order traversal, this result is shown to provide an alternate characterization that leads to a simple and elegant parallel algorithm of time complexity O(log N) with or without read-conflicts on an N processor SIMD shared memory model, where N is the total number of nodes in a forest.     

Parallel algorithms for corner stitching

Corner stitching is the underlying data structure that is used to represent rectangular objects in interactive VLSI layout editing systems such as Magic and Tailor. In this paper we develop efficient algorithms for basic corner stitching operations under the message-passing paradigm. These algorithms were implemented using C and PVM on a distributed network composed of SUN workstations. Experimental results show that significant speed-ups were obtained. © 1998 John Wiley & Sons, Ltd.     

Using a hash-based method with transaction trimming for miningassociation rules

We examine the issue of mining association rules among items in a large database of sales transactions. Mining association rules means that, given a database of sales transactions, to discover all associations among items such that the presence of some items in a transaction will imply the presence of other items in the same transaction. The mining of association rules can be mapped into the problem of discovering large itemsets where a large itemset is a group of items that appear in a sufficient number of transactions. The problem of discovering large itemsets can be solved by constructing a candidate set of itemsets first, and then, identifying, within this candidate set, these itemsets that meet the large itemset requirement. Generally, this is done iteratively for each large k-itemset in increasing order of k, where a large k-itemset is a large itemset with k items. To determine large itemsets from a huge number of candidate sets in early iterations is usually the dominating factor for the overall data mining performance. To address this issue, we develop an effective algorithm for the candidate set generation. It is a hash-based algorithm and is especially effective for the generation of a candidate set for large 2-itemsets. Explicitly, the number of candidate 2-itemsets generated by the proposed algorithm is, in orders of magnitude, smaller than that by previous methods, thus resolving the performance bottleneck. Note that the generation of smaller candidate sets enables us to effectively trim the transaction database size at a much earlier stage of the iterations, thereby reducing the computational cost for later iterations significantly. The advantage of the proposed algorithm also provides us the opportunity of reducing the amount of disk I/O required. An extensive simulation study is conducted to evaluate performance of the proposed algorithm     

New plane-sweep algorithms for distance-based join queries in spatial databases

Efficient and effective processing of the distance-based join query (DJQ) is of great importance in spatial databases due to the wide area of applications that may address such queries (mapping, urban planning, transportation planning, resource management, etc.). The most representative and studied DJQs are the K Closest Pairs Query (KCPQ) and εDistance Join Query (εDJQ). These spatial queries involve two spatial data sets and a distance function to measure the degree of closeness, along with a given number of pairs in the final result (K) or a distance threshold (ε). In this paper, we propose four new plane-sweep-based algorithms for KCPQs and their extensions for εDJQs in the context of spatial databases, without the use of an index for any of the two disk-resident data sets (since, building and using indexes is not always in favor of processing performance). They employ a combination of plane-sweep algorithms and space partitioning techniques to join the data sets. Finally, we present results of an extensive experimental study, that compares the efficiency and effectiveness of the proposed algorithms for KCPQs and εDJQs. This performance study, conducted on medium and big spatial data sets (real and synthetic) validates that the proposed plane-sweep-based algorithms are very promising in terms of both efficient and effective measures, when neither inputs are indexed. Moreover, the best of the new algorithms is experimentally compared to the best algorithm that is based on the R-tree (a widely accepted access method), for KCPQs and εDJQs, using the same data sets. This comparison shows that the new algorithms outperform R-tree based algorithms, in most cases.     

Hash-based and index-based join algorithms for cube and ringconnected multicomputers

The authors compare the performance of two join algorithms on both cube and ring interconnections for message-based multicomputers, and investigate the effects that the number of processors and the type of interconnection scheme have on the performance. First, the parallel hybrid-hash join algorithm and the parallel join-index join algorithm for both the cube and ring connected multicomputers are presented. The performance of these algorithms is then compared through analytical cost modeling. The result shows that the join-index join algorithm gives good performance only when the join selectivity is very small, and the hybrid-hash join algorithm performs consistently well under most situations. It is shown that the cube topology yields better execution time than the same algorithm on the ring topology. Furthermore, increasing the number of processors has a more significant improvement on the execution time of the cube than for the ring configuration. The applicability of join indexes on the parallel database algorithms is also discussed     

Parallel branch-and-bound algorithms

In this paper a parallel algorithm for branch-and-bound problems is sketched. It is designed to run on MIMD machines and exploits coarse grain parallelism. Due to the irregular and unpredictable behavior of branch-and-bound algorithms, it is hard to obtain a good load-balance. Another design issue is the minimization of the communication overhead. Our algorithm overcomes these problems by a dynamic load-balancing strategy and a dynamic way to decide when communication is really useful. After first sketching a general parallel algorithm for branch-and-bound problems, we concentrate on a particular instance of a branch-and-bound problem: the so-called knapsack problem. The performance of the algorithm for this problem is measured with a simulator for a multiprocessor system.     

Parallel algorithms for algebraic Riccati equations

The matrix sign function is the basis of a parallel algorithm for solving the generalized algebraic Riccati equation. Three forms of the algorithm were implemented and tested on a distributed memory hypercube multiprocessor. Performance results indicate that the method is an excellent means of solving large-scale problems on a parallel computer.     

Parallel algorithms for certain matrix computations

The complexity of performing matrix computations, such as solving a linear system, inverting a nonsingular matrix or computing its rank, has received a lot of attention by both the theory and the scientific computing communities. In this paper we address some “nonclassical” matrix problems that find extensive applications, notably in control theory. More precisely, we study the matrix equations AX + XA^T = C and AX − XB = C, the “inverse” of the eigenvalue problem (called pole assignment), and the problem of testing whether the matrix [B AB … Aⁿ⁻¹ B] has full row rank. For these problems we show two kinds of PRAM algorithms: on one side very fast, i.e. polylog time, algorithms and on the other side almost linear time and processor efficient algorithms. In the latter case, the algorithms rely on basic matrix computations that can be performed efficiently also on realistic machine models.     

Parallel multilevel algorithms for hypergraph partitioning

In this paper, we present parallel multilevel algorithms for the hypergraph partitioning problem. In particular, we describe for parallel coarsening, parallel greedy k-way refinement and parallel multi-phase refinement. Using an asymptotic theoretical performance model, we derive the isoefficiency function for our algorithms and hence show that they are technically scalable when the maximum vertex and hyperedge degrees are small. We conduct experiments on hypergraphs from six different application domains to investigate the empirical scalability of our algorithms both in terms of runtime and partition quality. Our findings confirm that the quality of partition produced by our algorithms is stable as the number of processors is increased while being competitive with those produced by a state-of-the-art serial multilevel partitioning tool. We also validate our theoretical performance model through an isoefficiency study. Finally, we evaluate the impact of introducing parallel multi-phase refinement into our parallel multilevel algorithm in terms of the trade off between improved partition quality and higher runtime cost.