Frequent closed pattern discovery is one of the most important topics in the studies of the compact representation for data mining. In this paper, we consider the frequent closed pattern discovery problem for a class ...
详细信息
ISBN:
(纸本)3540281770
Frequent closed pattern discovery is one of the most important topics in the studies of the compact representation for data mining. In this paper, we consider the frequent closed pattern discovery problem for a class of structured data, called attribute trees (AT), which is a subclass of labeled ordered trees and can be also regarded as a fragment of description logic with functional roles only. We present an efficient algorithm for discovering all frequent closed patterns appearing in a given collection of attribute trees. By using a new enumeration method, called the prefix-preserving closure extension, which enable efficient depth-first search over all closed patterns without duplicates, we show that this algorithm works in polynomial time both in the total size of the input database and the number of output trees generated by the algorithm. To our knowledge, this is one of the first result for output-sensitive algorithms for frequent closed substructure disocvery from trees and graphs.
We consider the directed Steiner network problem, where given a weighted directed graph G and p pairs of vertices P = {(s(1), t(1)), . . . ,(s(p), t(p))}, one has to find the minimum weight subgraph H of G that contai...
详细信息
We consider the directed Steiner network problem, where given a weighted directed graph G and p pairs of vertices P = {(s(1), t(1)), . . . ,(s(p), t(p))}, one has to find the minimum weight subgraph H of G that contains path from s(i) to t(i) for all i. We search for the main cause of the complexity of the problem and introduce the notions of junction vertex and shared segment in an optimal solution. We study the parameterized complexity of the problem with respect to these parameters and achieve several parameterized hardness results. Also, we present two output-sensitive algorithms for the problem, which are much simpler and easier to implement than the previously best known one;and in addition, when the paths corresponding to the input pairs have few shared vertices or arcs in the optimal solution, these algorithms outperform the previous one.
We consider the problem of reporting the pairwise enclosures in a set of n axes-parallel rectangles in IR2, which is equivalent to reporting dominance pairs in a set of n points in IR4. Over a decade ago, Lee and Prep...
详细信息
We consider the problem of reporting the pairwise enclosures in a set of n axes-parallel rectangles in IR2, which is equivalent to reporting dominance pairs in a set of n points in IR4. Over a decade ago, Lee and Preparata(7) gave an O(nlog(2) n + k)-time and O(n)-space algorithm for these problems, where k is the number of reported pairs. Since that time, the question of whether there is a faster algorithm has remained an intriguing open problem. In this paper, we give an algorithm which uses O(n + k) space and runs in O(nlog nlog logn + klog logn) time. Thus, although our result is not a strict improvement over the Lee-Preparata algorithm for the full range of k, it is, nevertheless, the first result since Ref. (6) to make any progress on this long-standing open problem. Our algorithm is based on the divide-and-conquer paradigm. The heart of the algorithm is the solution to a red-blue dominance reporting problem (the ''merge'' step). We give a novel solution for this problem which is based on the iterative application of a sequence of non-trivial sweep routines. This solution technique should be of independent interest. We also present another algorithm whose bounds match the bounds given in Ref. (6), but which is simpler. Finally, we consider the special case where the rectangles have a small number, alpha, of different aspect ratios, which is often the case in practice. For this problem, we give an algorithm which runs in O(alpha nlogn + k) time and uses O(n) space.
暂无评论