In pattern mining and association rule mining, there is a variety of algorithms for mining frequent closed itemsets (FCIs) and frequent generators (FGs), whereas a smaller part further involves the precedence relation...
详细信息
In pattern mining and association rule mining, there is a variety of algorithms for mining frequent closed itemsets (FCIs) and frequent generators (FGs), whereas a smaller part further involves the precedence relation between FCIs. The interplay of these three constructs and their joint computation have been studied within the formal concept analysis (FCA) field yet none of the proposed algorithms is scalable. In frequent pattern mining, at least one suite of efficient algorithms has been designed that exploits basically the same ideas and follows the same overall computational schema. Based on an in-depth analysis of the aforementioned interplay that is rooted in a fundamental duality from hypergraph theory, we propose a new schema that should enable for a more parsimonious computation. We exemplify the new schema in the design of Snow-Touch, a concrete FCI/FG/precedence miner that reuses an existing algorithm, Charm, for mining FCIs, and completes it with two original methods for mining FGs and precedence, respectively. The performance of Snow-Touch and of its closest competitor, Charm-L, were experimentally compared using a large variety of datasets. The outcome of the experimental study suggests that our method outperforms Charm-L on dense data while on sparse one the trend is reversed. Furthermore, we demonstrate the usefulness of our method and the new schema through an application to the analysis of a genome dataset. The initial results reported here confirm the capacity of the method to focus on significant associations.
Delaunay triangulation is always used to construct TIN, and is also widely applied in manifold fields, for it can avoid long and skinny triangles resulting in a nice looking map. A wide variety of algorithms have been...
详细信息
ISBN:
(纸本)9780819469113
Delaunay triangulation is always used to construct TIN, and is also widely applied in manifold fields, for it can avoid long and skinny triangles resulting in a nice looking map. A wide variety of algorithms have been proposed to construct delaunay triangulation, such as divide-and-conquer, incremental insertion, trangulation growth, and so on. The compound algorithm is also researched to construct delaunay triangulation, and prevalently it is mainly based on divide-and-conquer and incremental insertion algorithms. This paper simply reviews and assesses sweepline and divide-and-conquer algorithms, based on which a new compound algorithm is provided after studying the sweepline algorithm seriously. To start with, this new compound algorithm divides a set of points into several grid tiles with different dividing methods by divide-and-conquer algorithm, and then constructs subnet in each grid tile by sweepline algorithm. Finally these subnets are recursively merged into a whole delaunay triangulation with a simplified efficient LOP algorithm. Because topological structure is important to temporal and spatial efficiency of this algorithm, we only store data about vertex and triangle, thus edge is impliedly expressed by two adjacent triangles. In order to fit two subnets merging better, we optimize some data structure of sweepline algorithm. For instance, frontline and baseline of triangulation are integrated into one line, and four pointers point to where maximum and minimum of x axis and y axis are in this outline. The test shows that this new compound algorithm has better efficiency, stability and robustness than divide-and-conquer and sweepline algorithms. Especially if we find the right dividing method reply to different circumstance, its superiority is remarkable.
Today, there are more mature and relative perfect means of how to learn structures or parameters from completed data and learn parameters of fixed structure from uncompleted data. But it is a more difficult thing that...
详细信息
ISBN:
(纸本)081946452X
Today, there are more mature and relative perfect means of how to learn structures or parameters from completed data and learn parameters of fixed structure from uncompleted data. But it is a more difficult thing that learning structures of Bayesian Networks from uncompleted data. A compound learning algorithm is proposed;it combines the EM algorithm, Monte Carlo sampling algorithm and evolution algorithm together, uses EM algorithm to learn parameters of networks in uncompleted data, then samples the best network, converts the uncompleted data to completed data, and then evolves the structure using evolution algorithm. This algorithm could get over the defect of EM algorithm that frequently gains local maximum. Because data processing is based on posterior networks structures, structures of Bayesian Networks is optimizing and optimizing with evolution computing, the reliability of complementary data is higher. Learning rate is high and performance of this algorithm is good.
We present efficient parallel matrix multiplication algorithms for linear arrays with reconfigurable pipelined bus systems (LARPBS). Such systems are able to support a large volume of parallel communication of various...
详细信息
We present efficient parallel matrix multiplication algorithms for linear arrays with reconfigurable pipelined bus systems (LARPBS). Such systems are able to support a large volume of parallel communication of various patterns in constant time. An LARPBS can also be reconfigured into many independent subsystems and, thus, is able to support parallel implementations of divide-and-conquer computations like Strassen's algorithm. The main contributions of the paper are as follows: We develop five matrix multiplication algorithms with varying degrees of parallelism on the LARPBS computing model;namely, MM1, MM2, MM3, and compound algorithms C-1(epsilon) and C-2(delta). algorithm C-1(epsilon) has adjustable time complexity in sublinear level. algorithm C-2(delta) implies that it is feasible to achieve sublogarithmic time using o(N-3) processors for matrix multiplication on a realistic system. algorithms MM3, C-1(epsilon), and C-2(delta) all have o(N-3) cost and, hence, are very processor efficient. algorithms MM1, MM3,and C-1(epsilon) are general-purpose matrix multiplication algorithms, where the array elements are in any ring. algorithms MM2 and C-2(delta) are applicable to array elements that are integers of bounded magnitude, or floating-point values of bounded precision and magnitude, or Boolean values. Extension of algorithms MM2 and C-2(delta) to unbounded integers and reals are also discussed.
暂无评论