The complete Voronoi map of a binary image with black and white pixels is a matrix of the same size such that each element is the closest black pixel of the corresponding pixel. The complete Voronoi map visualizes the...
详细信息
ISBN:
(纸本)9781538610428
The complete Voronoi map of a binary image with black and white pixels is a matrix of the same size such that each element is the closest black pixel of the corresponding pixel. The complete Voronoi map visualizes the influence region of each black pixel. However, each region may not be connected due to exclave pixels. The connected Voronoi map is a modification of the complete Voronoi map so that all regions are connected. The Euclidean distance map of a binary image is a matrix, in which each element is the distance to the closest black pixel. It has many applications of image processing such as dilation, erosion, blurring effects, skeletonization and matching. The main contribution of this paper is to present simple and fast parallel algorithms for computing the complete/connected Voronoi maps and the Euclidean distance map and implement them in the GPU. Our parallel algorithm first computes the mixed Voronoi map, which is a mixture of the complete and connected Voronoi maps, and then converts it into the complete/connected Voronoi by exposing/hiding all exclave pixels. After that, the complete Voronoi map is converted into the Euclidean distance map by computing the distance to the closest black pixel for every pixel in an obvious way. The experimental results on GeForce GTX 1080 GPU show that the computing time for these conversions is relatively small. The throughput of our GPU implementation for computing the Euclidean distance maps of 2K x 2K binary images is up to 2.08 times larger than the previously published best GPU implementation, and up to 172 times larger than CPU implementation using Intel Core i7-4790.
We are interested in the fringe analysis of synchronized parallel insertion algorithms on 2-3 trees, namely the algorithm of W. Paul, U. Vishkin and H. Wagener (PVW). This algorithm inserts k keys into a tree of size ...
详细信息
ISBN:
(纸本)354065142X
We are interested in the fringe analysis of synchronized parallel insertion algorithms on 2-3 trees, namely the algorithm of W. Paul, U. Vishkin and H. Wagener (PVW). This algorithm inserts k keys into a tree of size n with parallel time O(log n + log K). Fringe analysis studies the distribution of the bottom subtrees and it is still an open problem for parallel algorithms on search trees. To tackle this problem we introduce a new kind of algorithms whose two extreme cases seems to upper and lower bounds the performance of the PVW algorithm. We extend the fringe analysis to parallel algorithms and we get a rich mathematical structure giving new interpretations even in the sequential case. The process of insertions is modeled by a Markov chain and the coefficients of the transition matrix are related with the expected local behavior of our algorithm. Finally we show that this matrix has a power expansion over (n+1)(-1) where the coefficients are the binomial transform of the expected local behavior. This expansion shows that the parallel case can be approximated by iterating the sequential case.
Frequent itemset mining is a classic problem in data mining. It is a non-supervised process which concerns in finding frequent patterns (or itemsets) hidden in large volumes of data in order to produce compact summari...
详细信息
ISBN:
(纸本)0769520464
Frequent itemset mining is a classic problem in data mining. It is a non-supervised process which concerns in finding frequent patterns (or itemsets) hidden in large volumes of data in order to produce compact summaries or models of the database. These models are typically used to generate association rules, but recently they have also been used in far reaching domains like e-commerce and bio-informatics. Because databases are increasing in terms of both dimension (number of attributes) and size (number of records), one of the main issues in a frequent itemset mining algorithm is the ability to analyze very large databases. Sequential algorithms do not have this ability, especially in terms of run-time performance, for such very large databases. Therefore, we must rely on high performance parallel and distributed computing. We present new parallel algorithms for frequent itemset mining. Their efficiency is proven through a series of experiments on different parallel environments, that range from shared-memory multiprocessors machines to a set of SMP clusters connected together through a high speed network. We also briefly discuss an application of our algorithms to the analysis of large databases collected by a Brazilian web portal.
Novel and fast parallel algorithms for the DHT-based real-valued discrete Gabor expansion (DGE) and discrete Gabor transform (DGT) are presented based on filterbanks. An analysis filterbank is designed for the DHT-bas...
详细信息
ISBN:
(纸本)9781424453092
Novel and fast parallel algorithms for the DHT-based real-valued discrete Gabor expansion (DGE) and discrete Gabor transform (DGT) are presented based on filterbanks. An analysis filterbank is designed for the DHT-based real-valued DGT and a synthesis filterbank is designed for the DHT-based real-valued DGE. The parallel channel in each of the two filterbanks has a unified structure and can apply the fast DHT (discrete Hartley transform) to reduce its computational load. The computational complexity of each parallel channel is very low and is independent of the oversampling rate. The computational complexity of the proposed parallel algorithms is analyzed and compared with that of the existing major parallel algorithms for the DGT and DGE. The results indicate that the proposed parallel algorithms are attractive for real time signal processing.
In a cellular network, the base stations are not necessarily uniformly distributed, and their corresponding cell sizes are not necessarily the same. For example, a cell in a well-populated city cell is usually smaller...
详细信息
ISBN:
(纸本)0769517609
In a cellular network, the base stations are not necessarily uniformly distributed, and their corresponding cell sizes are not necessarily the same. For example, a cell in a well-populated city cell is usually smaller than a cell in a rural area. To study a cellular network with non-uniform cell sizes, one approach is to use a virtual cellular network with a uniform cell size such that each virtual cell contains at most one base station. This paper has proposed parallel algorithms for meshes with multiple broadcasting to construct virtual mesh and honeycomb cellular networks for non-uniformly distributed base stations. The constructed virtual cellular networks are optimal in the sense that their corresponding uniform cell sizes reach the largest possible. The algorithms run in O(logn) time on a mesh with multiple broadcasting of size nxn to construct optimal virtual mesh and honeycomb cellular networks for n non-uniformly distributed base stations. Furthermore, those algorithms are time-optimal.
In this paper, We proposed a new parallel algorithm for computing path expression, named parallel Cascade Semijoin (PCSJ). Moreover, a new scheduling strategy called right-deep zigzag tree is designed to further impro...
详细信息
ISBN:
(纸本)0769509967;0769509975
In this paper, We proposed a new parallel algorithm for computing path expression, named parallel Cascade Semijoin (PCSJ). Moreover, a new scheduling strategy called right-deep zigzag tree is designed to further improve the performance of the PCSJ algorithm. The experiments have been implemented in a NOW distributed and parallel environment. The results show that the PCSJ algorithm out-performs the other two parallel algorithms (the parallel version of forward pointer chasing algorithm (PFPC) and the index splitting parallel algorithm (IndexSplit)) when computing path expressions with restrictive predicates and that the right-deep zigzag tree scheduling strategy has the better performance that the right-deep tree scheduling strategy.
The multidimensional assignment problem (MAP) is a combinatorial optimization problem arising in diverse applications such as computer vision and motion tracking. In the MAP, the objective is to match tuples of object...
详细信息
The multidimensional assignment problem (MAP) is a combinatorial optimization problem arising in diverse applications such as computer vision and motion tracking. In the MAP, the objective is to match tuples of objects with minimum total cost. Randomized parallel algorithms are proposed to solve MAPs appearing in multi-sensor multi-target applications. A parallel construction heuristic is described, together with some variations, as well as a parallel local search heuristic. Experimental results using the proposed algorithms are discussed. (C) 2003 IMACS. Published by Elsevier B.V. All rights reserved.
In this paper we present new parallel versions of sequential Goertzel and Reinsch algorithms for calculating trigonometric sums. The new algorithms use a recently introduced, very efficient BLAS-based algorithm for so...
详细信息
ISBN:
(纸本)0769517315
In this paper we present new parallel versions of sequential Goertzel and Reinsch algorithms for calculating trigonometric sums. The new algorithms use a recently introduced, very efficient BLAS-based algorithm for solving linear recurrence systems with constant coefficients. To achieve their portability across different shared-memory parallel architectures, the algorithms have been implemented in Fortran 77 and OpenMP. We also present experimental results performed on a two processor Pentium III computer running under Linux operating system with Atlas as an efficient implementation of BLAS. The new algorithms are up to 60-90% faster than the equivalent sequential Goertzel and Reinsch algorithms, even on one processor.
This paper presents new parallel algorithms for generating Euclidean minimum spanning trees and spatial clustering hierarchies (known as HDBSCAN*). Our approach is based on generating a well-separated pair decompositi...
详细信息
ISBN:
(纸本)9781450383431
This paper presents new parallel algorithms for generating Euclidean minimum spanning trees and spatial clustering hierarchies (known as HDBSCAN*). Our approach is based on generating a well-separated pair decomposition followed by using Kruskal's minimum spanning tree algorithm and bichromatic closest pair computations. We introduce a new notion of well-separation to reduce the work and space of our algorithm for HDBSCAN*. We also give a new parallel divide-and-conquer algorithm for computing the dendrogram and reachability plots, which are used in visualizing clusters of different scale that arise for both EMST and HDBSCAN*. We show that our algorithms are theoretically efficient: they have work (number of operations) matching their sequential counterparts, and polylogarithmic depth (parallel time). We implement our algorithms and propose a memory optimization that requires only a subset of well-separated pairs to be computed and materialized, leading to savings in both space (up to 10x) and time (up to 8x). Our experiments on large real-world and synthetic data sets using a 48-core machine show that our fastest algorithms outperform the best serial algorithms for the problems by 11.13-55.89x, and existing parallel algorithms by at least an order of magnitude.
In this paper, we develop parallel algorithms for pricing a class of multidimensional financial derivatives employing binomial lattice approach. We describe the algorithms, explain their complexities, and study their ...
详细信息
ISBN:
(纸本)0769516807
In this paper, we develop parallel algorithms for pricing a class of multidimensional financial derivatives employing binomial lattice approach. We describe the algorithms, explain their complexities, and study their performance. The limitations posed by the problem size on the recursive algorithm and the solution to overcome this problem by the iterative algorithm are explained through the experimental results using MPL We first present analytical results for the number of computations and communications for both the algorithms. Since the number of nodes in a recombining lattice grows linearly with the problem size, it is feasible to price long-dated options using a recombining lattice. We have extended our algorithm to handle derivatives with many underlying assets and shown that the multi-asset derivatives offer a better problem for parallel computation. This is very important for finance industry since long-dated derivatives with many underlying assets are common in practice.
暂无评论