An outlier is an observation that deviates so much front other observations as to arouse suspicion that it was generated by a different mechanism. Outlier detection has many applications, such as data cleaning, fraud ...
详细信息
ISBN:
(纸本)0769522785
An outlier is an observation that deviates so much front other observations as to arouse suspicion that it was generated by a different mechanism. Outlier detection has many applications, such as data cleaning, fraud detection and network intrusion. The existence of outliers can indicate individuals or groups that exhibit a behavior that is very different from most of the individuals of the dataset. In this paper we design two parallel algorithms, the first one is for finding out distance-based outliers based on nested loops along with randomization and the use of a pruning rule. The second parallel algorithin is for detecting density-based local outliers. In both cases data parallelism is used. We show that both algorithms reach near linear speedup. Our algorithms are tested on four real-world datasets coining front the Machine Learning Database Repository at the UCI.
We describe the parallelization of an efficient algorithm for balanced truncation that allows to reduce models with state-space dimension up to 0 (105). The major computational task in this approach is the solution of...
详细信息
ISBN:
(纸本)3540290672
We describe the parallelization of an efficient algorithm for balanced truncation that allows to reduce models with state-space dimension up to 0 (105). The major computational task in this approach is the solution of two largescale sparse Lyapunov equations, performed via a coupled LR-ADI iteration with (super-)linear convergence. Experimental results on a cluster of Intel Xeon processors illustrate the efficacy of our parallel model reduction algorithm.
The index-permutation graph (IPG) model is a natural extension of the Cayley graph model, and super-IPGs form an efficient class of IPGs that contain a wide variety of networks as subclasses. In this paper, we derive ...
详细信息
ISBN:
(纸本)0769512577;0769512585
The index-permutation graph (IPG) model is a natural extension of the Cayley graph model, and super-IPGs form an efficient class of IPGs that contain a wide variety of networks as subclasses. In this paper, we derive a number of efficient algorithms and embeddings for super-IPGs, proving their versatility. We show that a multitude of important networks can also be emulated in super-IPGs with optimal slowdown. Also, the intercluster diameter, average intercluster distance, and bisection bandwidth of suitably constructed super-IPGs are optimal within small constant factors. Finally, we show that when parallel computers, built as multiple chip-multiprocessors (MCMP), are based on super-IPGs, they can significantly outperform those based on hypercubes, k-ary n-cubes, and other networks in carrying out communication-intensive tasks.
We propose parallel algorithms for detecting collisions among 3-D objects in real-time. First, a basic algorithm of serial version is described. It can detect potential collisions among multiple objects with arbitrary...
详细信息
ISBN:
(纸本)078032904X
We propose parallel algorithms for detecting collisions among 3-D objects in real-time. First, a basic algorithm of serial version is described. It can detect potential collisions among multiple objects with arbitrary motion (translation and rotation) in three-dimensional (3-D) space. The algorithm can be used without modification for both convex and concave objects represented as polyhedra. This algorithm is efficient, simple to implement, and does not require any memory intensive auxiliary data structure to be precomputed and updated. Then, two parallel algorithms are proposed for MIMD multi-processors having a shared-memory;one uses a static and the other uses a dynamic method for proper load balancing. Experimental results demonstrate the performance of the proposed collision detection methods.
parallel algorithms are developed for the numerical solution of second-order hyperbolic partial differential equations using (M, K) Padé approximants with M ≠ K. A linear one-dimensional wave equation is solved ...
详细信息
We consider the problem of finding the kth highest element in a totally ordered set of n elements (SELECT), and partitioning a totally ordered set into the top k and bottom n-k elements (PARTITION) using pairwise comp...
详细信息
ISBN:
(纸本)9781450341325
We consider the problem of finding the kth highest element in a totally ordered set of n elements (SELECT), and partitioning a totally ordered set into the top k and bottom n-k elements (PARTITION) using pairwise comparisons. Motivated by settings like peer grading or crowdsourcing, where multiple rounds of interaction are costly and queried comparisons may be inconsistent with the ground truth, we evaluate algorithms based both on their total runtime and the number of interactive rounds in three comparison models: noiseless (where the comparisons are correct), erasure (where comparisons are erased with probability 1-gamma), and noisy (where comparisons are correct with probability 1/2 + gamma/2 and incorrect otherwise). We provide numerous matching upper and lower bounds in all three models. Even our results in the noiseless model, which is quite well-studied in the TCS literature on parallel algorithms, are novel.
One of the many ways of solving free-boundary problems is, when possible, to put them (perhaps after suitable transformations) in the framework of variational or quasi-variational inequalities. It then remains to solv...
详细信息
Power-List, ParList and PList data structures are efficient tools for functional descriptions of parallel programs that are divide & conquer in nature. The goal of this work is to develop three parallel variants f...
详细信息
ISBN:
(纸本)3540440496
Power-List, ParList and PList data structures are efficient tools for functional descriptions of parallel programs that are divide & conquer in nature. The goal of this work is to develop three parallel variants for Fast Fourier Transformation using these theories. The variants are implied by the degree of the polynomial, which can be a power of two, a prime number, or a product of prime factors. The last variant includes the first two, and represents a general and efficient parallel algorithm for Fast Fourier Transformation. This general algorithm has a very good time complexity, and can be mapped on a recursive interconnection network.
In this paper, we design massively parallel algorithms for sparse matrix multiplication, as well as more general join-aggregate queries, where the join hypergraph is a tree with arbitrary output attributes. For each c...
详细信息
ISBN:
(纸本)9781450371087
In this paper, we design massively parallel algorithms for sparse matrix multiplication, as well as more general join-aggregate queries, where the join hypergraph is a tree with arbitrary output attributes. For each case, we obtain asymptotic improvement over existing algorithms. In particular, our matrix multiplication algorithm is shown to be optimal in the semiring model.
暂无评论