Background and objective Integrating data from multiple sources is a crucial and challenging problem. Even though there exist numerous algorithms for record linkage or deduplication, they suffer from either large time...
详细信息
Background and objective Integrating data from multiple sources is a crucial and challenging problem. Even though there exist numerous algorithms for record linkage or deduplication, they suffer from either large time needs or restrictions on the number of datasets that they can integrate. In this paper we report efficient sequential and parallel algorithms for record linkage which handle any number of datasets and outperform previous algorithms. Methods Our algorithms employ hierarchical clustering algorithms as the basis. A key idea that we use is radix sorting on certain attributes to eliminate identical records before any further processing. Another novel idea is to form a graph that links similar records and find the connected components. Results Our sequential and parallel algorithms have been tested on a real dataset of 1083878 records and synthetic datasets ranging in size from 50000 to 9000000 records. Our sequential algorithm runs at least two times faster, for any dataset, than the previous best-known algorithm, the two-phase algorithm using faster computation of the edit distance (TPA (FCED)). The speedups obtained by our parallel algorithm are almost linear. For example, we get a speedup of 7.5 with 8 cores (residing in a single node), 14.1 with 16 cores (residing in two nodes), and 26.4 with 32 cores (residing in four nodes). Conclusions We have compared the performance of our sequential algorithm with TPA (FCED) and found that our algorithm outperforms the previous one. The accuracy is the same as that of this previous best-known algorithm.
A localized microcomputer network PLEXUS, (developed at I.I.T., Bombay) for studies on parallel algorithms, has been briefly presented. For the solution of linear algebraic equations on the PLEXUS, this paper implemen...
详细信息
A localized microcomputer network PLEXUS, (developed at I.I.T., Bombay) for studies on parallel algorithms, has been briefly presented. For the solution of linear algebraic equations on the PLEXUS, this paper implements two methods: 1) Jacobi method, used in sequential computers; and 2) Purely Asynchronous method, specifically designed for multiprocessors and computer networks. This implementation illustrates that the second method is more advantageous than the first method on the PLEXUS in regard to the execution time and the rate of convergence. Further, the performance of these two methods has been predicted in terms of: 1) the execution times for the evaluation and communication sections; and 2) the processor utilization.
The problem of mathematical modeling of the spread of contamination from point sources in the air has been considered. An approach that uses the idea of splitting and organization of computation with explicit differen...
详细信息
An interval graph is one in which each vertex in the graph can be associated with an interval in the real line such that 2 vertices are adjacent in the graph if and only if the 2 corresponding intervals intersect. Th...
详细信息
An interval graph is one in which each vertex in the graph can be associated with an interval in the real line such that 2 vertices are adjacent in the graph if and only if the 2 corresponding intervals intersect. The collection of intervals is called an interval representation of the graph. Interval graphs occur naturally in many applications in various fields, and recognizing interval graphs is an important problem. An interval graph recognition algorithm is presented that also builds an interval representation for interval graphs. The algorithm is relatively simple. More importantly, it yields directly a simple and elegant parallel algorithm for the same problem. In the only other previous algorithm for the same problem, parallel implementation of certain steps is complicated. The new algorithm begins as the previous algorithm does, transitively orienting the complement of the given graph. The remaining steps, however, are much simpler, and their parallel implementation is straightforward.
In this paper we focus on the problem of designing very fast parallel algorithms for the convex hull and the vector maxima problems in three dimensions that are output-size sensitive. Our algorithms achieve O(log log(...
详细信息
In this paper we focus on the problem of designing very fast parallel algorithms for the convex hull and the vector maxima problems in three dimensions that are output-size sensitive. Our algorithms achieve O(log log(2) n log h) parallel time and optimal O(n log h) work with high probability in the CRCW PRAM where n and h are the input and output size, respectively. These bounds are independent of the input distribution and are faster than the previously known algorithms. We also present an optimal speed-up (with respect to the input size only) sublogarithmic time algorithm that uses superlinear number of processors for vector maxima in three dimensions. (C) 2003 Elsevier Science (USA). All rights reserved.
We describe the parallel algorithms for studying the structural features of the anomalies in the gravity and magnetic fields of the lithosphere, which are based on the height transformations of the data. The algorithm...
详细信息
We describe the parallel algorithms for studying the structural features of the anomalies in the gravity and magnetic fields of the lithosphere, which are based on the height transformations of the data. The algorithms are numerically implemented on the Uran supercomputer. The suggested computer technology is used for constructing the maps of the regional and local anomalies of the magnetic and gravity fields for the northeastern sector of Europe within an area confined between 48A degrees-62A degrees E and 60A degrees-68A degrees N.
作者：
STPICZYNSKI, PInstitute of Mathematics
Numerical Analysis Department Marie Curie-Sk?odowska University Pl. Marii Curie-Sk?odowskiej 1 20-031 Lublin Poland
In the paper we present an error analysis of two parallel algorithms for solving linear recurrence systems. We prove that the computed solution is the exact solution of the problem with slightly perturbed input data.
In the paper we present an error analysis of two parallel algorithms for solving linear recurrence systems. We prove that the computed solution is the exact solution of the problem with slightly perturbed input data.
The abstract problem of using P failure-prone processors to cooperatively update all locations of an iV-element shared array is called Write-AU. Solutions to Write-All can be used iteratively to construct efficient si...
详细信息
The abstract problem of using P failure-prone processors to cooperatively update all locations of an iV-element shared array is called Write-AU. Solutions to Write-All can be used iteratively to construct efficient simulations of PRAM algorithms on failureprone PRAMS. Such use of Write-All in simulations is abstracted in terms of the iterative Write-All problem. The efficiency of the algorithmic solutions for Write-Aii and iterative Write-All is measured in terms of work complexity where all processing steps taken by the processors are counted. This paper considers determinitic solutions for the WriteA1I and iterative Write-All problems in the fail-stop synchronous CRCW PRAM model where memory access concurrency needs to be controlled. A deterministic algorithm of Kanellakis, Michailidis, and Shvartsman [16] efficiently solves the Write-All problem in this model, while controlling read and write memory access concurrency. However it was not shown how the number of processor failures / affects the work efficiency of the algorithm. The results herein give a new analysis of the algorithm [16] that obtain failure-sensitive work bounds, while retaining the known memory access concurrency bounds. Specifically, the new result expresses the work bound as a function of N, P and f. Another contribution in this paper is the new failure-sensitive analysis for iterative Write-All with controlled memory access concurrency. This result yields tighter bounds on work (vs. [16]) for simulations of PRAM algorithms on fail-stop PRAMS.
The problem of finding a sublogarithmic time optimal parallel algorithm for 3-colouring rooted forests has been open for long. We settle this problem by obtaining an O ((log log n) log*(log* n)) time optimal parallel ...
详细信息
The problem of finding a sublogarithmic time optimal parallel algorithm for 3-colouring rooted forests has been open for long. We settle this problem by obtaining an O ((log log n) log*(log* n)) time optimal parallel algorithm on a TOLERANT Concurrent Read Concurrent Write (CRCW) parallel Random Access Machine (PRAM). Furthermore, we show that if f(n) is the running time of the best known algorithm for 3-colouring a rooted forest on a COMMON or TOLERANT CRCW PRAM, a fractional independent set of the rooted forest can be found in O(f(n)) time with the same number of processors, on the same model. Using these results, it is shown that decomposable top-down algebraic computation a,nd, hence, depth computation (ranking), 2-colouring and prefix summation on rooted forests can be done in O (log n) optimal time on a TOLERANT CRCW PRAM. These algorithms have been obtained by proving a result of independent interest, one concerning the self-simulation property of TOLERANT: an N-processor TOLERANT CRCW PRAM that uses an address space of size O (N) only, can be simulated on an n-processor TOLERANT PRAM in O (N/n) time, with no asymptotic increase in space or cost, when n = O (N/log log N).
The parallel complexity of template matching has been well studied. In this paper we present more work-efficient algorithms than the existing ones. Our algorithms are based on FFT primitives. We consider the following...
详细信息
The parallel complexity of template matching has been well studied. In this paper we present more work-efficient algorithms than the existing ones. Our algorithms are based on FFT primitives. We consider the following models of computing: PRAM and the hypercube.
暂无评论