The discovery of frequent itemsets is a very computational and I/O intensive task, and beyond a certain database size, it is crucial to leverage and the combined computational power of multiple processors for fast res...
详细信息
ISBN:
(纸本)0780378652
The discovery of frequent itemsets is a very computational and I/O intensive task, and beyond a certain database size, it is crucial to leverage and the combined computational power of multiple processors for fast response and scalability. In this paper we present new scalable algorithm for maximal frequent itemset mining. It decomposes the search space by prefix-based equivalence classes, distributes work among the processors and selectively duplicates databases in such a way that each processor can compute the maximal frequent itemsets independently. It utilizes multiple level backtrack pruning strategy, along with vertical database format, counting frequency by simple tid-list intersection operation. These techniques eliminate the need for synchronization, drastically cutting down the communication cost. The analysis and experimental results demonstrate that our approach is well scalable in speedup and sizeup.
The rigid graph needs to be decomposed to solve the multi-equilibrium problem of the multi-agent formation control based on navigation function method. In this paper, a theorem and a scalable algorithm based on the He...
详细信息
The rigid graph needs to be decomposed to solve the multi-equilibrium problem of the multi-agent formation control based on navigation function method. In this paper, a theorem and a scalable algorithm based on the Henneberg sequence of graphs are proposed for the decomposition of minimally rigid graph. The theorem demonstrates that if graphG(V,E) is a minimally rigid graph, then it can be decomposed asG=G(t)?G(c), whereG(t)is a spanning tree ofGandG(c)contains the remaining edges and their vertices. Moreover, the scalable algorithm is given to constructG(t)= (V-t,E-t) andG(c)= (V-c,E-c), and assign the edges inE(c)ton-- 2 distinct vertices in a scalable way via communication. Furthermore, a lemma is given to show when the number of vertices is less than eight, any edge can be chosen as the initialized edge, and the scalable algorithm mentioned above is always feasible. Finally, the effectiveness of the scalable algorithm is verified by numerical simulation.
Multiple moving objects, partially occluded objects, or even a single object moving against the background gives rise to discontinuities in the optical flow field in corresponding image sequences. While uniform global...
详细信息
Multiple moving objects, partially occluded objects, or even a single object moving against the background gives rise to discontinuities in the optical flow field in corresponding image sequences. While uniform global regularization based moderately fast techniques cannot provide accurate estimates of the discontinuous flow field, statistical optimization based accurate techniques suffer from excessive solution time. A 'weighted anisotropic' smoothness based numerically robust algorithm is proposed that can generate discontinuous optical flow field with high speed and linear computational complexity. Weighted sum of the first-order spatial derivatives of the flow field is used for regularization. Less regularization is performed where strong gradient information is available. The flow field at any point is interpolated more from those at neighboring points along the weaker intensity gradient-component. Such intensity gradient weighted regularization leads to Euler-Lagrange equations with strong anisotropies coupled with discontinuities in their coefficients. A robust multilevel iterative technique, that recursively generates coarse-level problems based on intensity gradient weighted smoothing weights, is employed to estimate discontinuous optical flow field. Experimental results are presented to demonstrate the efficacy of the proposed technique.
It is hard to implement the ADI method in an efficient way on distributed-memory parallel computers. We propose "P-scheme" which parallelizes a tridiagonal linear system of equations for the ADI method, but ...
详细信息
It is hard to implement the ADI method in an efficient way on distributed-memory parallel computers. We propose "P-scheme" which parallelizes a tridiagonal linear system of equations for the ADI method, but its effectiveness is limited to the cases where the problem size is large enough mainly because of the communication cost of the propagation phase of the scheme. In order to overcome this difficulty, we propose an improved version of the P-scheme with "message vectorization" which aggregates several communication messages into one and alleviates the communication cost. Also we evaluate the effectiveness of message vectorization for the ADI method and show that the improved version of the P-scheme works well even for smaller problems and linear and super-linear speedups can be achieved for 8194 x 8194 and 16,386 x 16,386 problems, respectively. (C) 2004 Elsevier B.V. All rights reserved.
Advances in IT infrastructure have enabled the generation and storage of very large data sets describing complex systems continuously in time. These can derive from both simulations and measurements. Analysis of such ...
详细信息
Advances in IT infrastructure have enabled the generation and storage of very large data sets describing complex systems continuously in time. These can derive from both simulations and measurements. Analysis of such data requires the availability of scalable algorithms. In this contribution, we propose a scalable algorithm that partitions instantaneous observations (snapshots) of a complex system into kinetically distinct sets (termed basins). To do so, we use a combination of ordering snapshots employing the method's only essential parameter, i.e., a definition of pairwise distance, and annotating the resultant sequence, the so-called progress index, in different ways. Specifically, we propose a combination of cut-based and structural annotations with the former responsible for the kinetic grouping and the latter for diagnostics and interpretation. The method is applied to an illustrative test case, and the scaling of an approximate version is demonstrated to be O (N log N) with N being the number of snapshots. Two real-world data sets from river hydrology measurements and protein folding simulations are then used to highlight the utility of the method in finding basins for complex systems. Both limitations and benefits of the approach are discussed along with routes for future research. (C) 2013 Elsevier B.V. All rights reserved.
Frequent Pattern Tree (FP-Tree) is a compact data structure of representing frequent itemsets. The construction of FP-Tree is very important prior to frequent patterns mining. However, there have been too limited effo...
详细信息
Frequent Pattern Tree (FP-Tree) is a compact data structure of representing frequent itemsets. The construction of FP-Tree is very important prior to frequent patterns mining. However, there have been too limited efforts specifically focused on constructing FP-Tree data structure beyond from its original database. In typical FP-Tree construction, besides the prior knowledge on support threshold, it also requires two database scans;first to build and sort the frequent patterns and second to build its prefix paths. Thus, twice database scanning is a key and major limitation in completing the construction of FP-Tree. Therefore, this paper suggests scalable Trie Transformation Technique algorithm (T3A) to convert our predefined tree data structure, Disorder Support Trie Itemset (DOSTrieIT) into FP-Tree. Experiment results through two UCI benchmark datasets show that the proposed T3A generates FP-Tree up to 3 magnitudes faster than that the benchmarked FP-Growth.
This paper proposes anew metaheuristic optimization algorithm named Battlefield Optimization algorithm (BfOA). As the name implies, it is inspired by the simulation of a battlefield, where two opposing squads battle e...
详细信息
This paper proposes anew metaheuristic optimization algorithm named Battlefield Optimization algorithm (BfOA). As the name implies, it is inspired by the simulation of a battlefield, where two opposing squads battle each other. The squad with the stronger position defends its position and the weaker squad attacks using Supit Urang formation (an Indonesian traditional battle formation). Each squad is led by a commander. The commander leads three types of soldiers (cavaliers, special forces, and builders). Before the battle started, in the first phase each squad employs airplanes to scan the best position to begin the battle. The airplanes' movements are highly explorative. In the second phase, the defending squad's movement is highly exploitative, while the attacking squad is in the mid-explorative movement. The proposed algorithm is examined using twentythree benchmark functions and compared with one classic and five newer algorithms. To further examine the capability of the algorithm, CEC 2021 Single Objective Bound Constrained Numerical Optimization benchmark functions are used. Then the algorithm is tested in a real-world engineering optimization problem by solving the Three-Bar Truss problem.
Signal reconstruction problem (SRP) is an important optimization problem where the objective is to identify a solution to an underdetermined system of linear equations that is closest to a given prior. It has a substa...
详细信息
Signal reconstruction problem (SRP) is an important optimization problem where the objective is to identify a solution to an underdetermined system of linear equations that is closest to a given prior. It has a substantial number of applications in diverse areas including network traffic engineering, medical image reconstruction, acoustics, astronomy and many more. Most common approaches for SRP do not scale to large problem sizes. In this paper, we propose multiple optimization steps, developing scalable algorithms for the problem. We first propose a dual formulation of the problem and develop the Direct algorithm that is significantly more efficient than the state of the art. Second, we show how adapting database techniques developed for scalable similarity joins provides a significant speedup over Direct, scaling our proposal up to large-scale settings. Third, we describe a number of practical techniques that allow our algorithm to scale to settings of size in the order of a million by a billion. We also adapt our proposal to identify the top-k components of the solved system of linear equations. Finally, we consider the dynamic setting where the inputs to the linear system change and propose efficient algorithms inspired by the database techniques of materialization and reuse. Extensive experiments on real-world and synthetic data confirm the efficiency, effectiveness and scalability of our proposal.
We develop an optimal algorithm for the numerical solution of semi-coercive variational inequalities by combining dual-primal FETI algorithms with recent results for bound and equality constrained quadratic programmin...
详细信息
We develop an optimal algorithm for the numerical solution of semi-coercive variational inequalities by combining dual-primal FETI algorithms with recent results for bound and equality constrained quadratic programming problems. The discretized version of the model problem, obtained by using the FETI-DP methodology, is reduced by the duality theory of convex optimization to a quadratic programming problem with bound and equality constraints, which is solved by a new algorithm with a known rate of convergence given in terms of the spectral condition number of the quadratic problem. We present convergence bounds that guarantee the scalability of the algorithm. These results are confirmed by numerical experiments. (c) 2006 Elsevier B.V. All rights reserved.
Motion estimation is an indispensable stage of motion pictures encoding used in all common video coding standards, such as MPEG-2 [3] or AVC [4]. At the same time it is the most complex operation both in software and ...
详细信息
ISBN:
(纸本)9781424445936
Motion estimation is an indispensable stage of motion pictures encoding used in all common video coding standards, such as MPEG-2 [3] or AVC [4]. At the same time it is the most complex operation both in software and hardware implementation of an encoder that makes the choice of the appropriate motion estimation algorithm crucial in terms of increasing the entire coding process efficiency. This should be taken into consideration especially ill case of real time processing. In this paper, a novel scalable multi-level algorithm for motion estimation is proposed. It is a fast motion estimation algorithm, using the block-matching mechanism, provided the motion vectors accuracy equal 1/4 of the sampling period. Proposed algorithm is modular and scalable. First feature enables structure scalability, second provides mechanism to control of clock cycles number spend for motion estimation process. As a result the global clock-rate required for real-time processing can be adjusted.
暂无评论