共查询到20条相似文献,搜索用时 140 毫秒
1.
本文首先阐明线性RaRb变换之间的关系,并提出了算法MRab,再引用标准线性RaRb变换,证明了RaRb变换与算法MRab求解方程组的能力是等价的.然后讨论MRab与算法ALT之间的关系,进而说明受ALT攻击的那些有限自动机包含 相似文献
2.
区域查询是数据仓库上支持联机分析处理(on-line analytical processing,简称OLAP)的重要操作.近几年,人们提出了一些支持区域查询和数据更新的Cube存储结构.然而这些存储结构的空间复杂性和时间复杂性都很高,难以在实际中使用.为此,提出了一种层次式Cube存储结构HDC(hierarchical data cube)及其上的相关算法.HDC上区域查询的代价和数据更新代价均为O(logdn),综合性能为O((logn)2d)(使用CqCu模型)或O(K(logn)d)(使用Cqnq+Cunu模型).理论分析与实验表明,HDC的区域查询代价、数据更新代价、空间代价以及综合性能都优于目前所有的Cube存储结构. 相似文献
3.
4.
5.
6.
7.
三维空间中的最短路问题 总被引:1,自引:0,他引:1
在包含一组相互分离凸多面体的三维空间中为任意两点寻找最短路的问题是NP问题.当凸多面体的个数k任意时,它为指数时间复杂度;而当k=1时,为O(n2)(n为凸多面体的顶点数).文章主要研究了k=2情形下的最短路问题,提出一个在O(n2)时间内解决该问题的算法.所得结果大大优于此情形下迄今为止最好的结果——O(n3 相似文献
8.
9.
个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2kn2m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k1-1)k222h+(k1+1)2h+nk2+mk1)的新算法,其中,k1为一个片断覆盖的最大SNP位点数(不大于n),k2为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k2).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值. 相似文献
10.
11.
The Logical Key Hierarchy (LKH) is the most widely used protocol in multicast group rekeying. LKH maintains a balanced tree
that provide uniform cost of O(log N) for compromise recovery, where N is group size. However, it does not distinguish the behavior of group members even though they may have different probabilities
of join or leave. When members have diverse changing probabilities, the gap between LKH and the optimal rekeying algorithm
will become bigger. The Probabilistic optimization of LKH (PLKH) scheme, optimized rekey cost by organizing LKH tree with
user rekey characteristic. In this paper, we concentrate on further reducing the rekey cost by organizing LKH tree with respect
to rekey probabilities of members using new join and leave operations. Simulation results show that our scheme performs 18
to 29% better than PLKH and 32 to 41% better than LKH. 相似文献
12.
The Swap Edges of a Multiple-Sources Routing Tree 总被引:1,自引:0,他引:1
Let T be a spanning tree of a graph G and S⊂V(G) be a set of sources. The routing cost of T is the total distance from all sources to all vertices. For an edge e of T, the swap edge of e is the edge f minimizing the routing cost of the tree formed by replacing e with f. Given an undirected graph G and a spanning tree T of G, we investigate the problem of finding the swap edge for every tree edge. In this paper, we propose an O(mlog n+n
2)-time algorithm for the case of two sources and an O(mn)-time algorithm for the case of more than two sources, where m and n are the numbers of edges and vertices of G, respectively. 相似文献
13.
相似连接算法在数据清理、数据集成和重复网页检测等领域有着广泛的应用.现有相似连接算法有两种类型:基于相似度阈值的相似连接和Top-k相似连接.Top-k连接算法非常适合于相似度阈值未知的应用场景,目前最为有效的Top-k相似连接算法是Xiao等人提出的Topk-join.为了解决Topk-join中存在的性能问题,提出了一种Top-k相似连接算法Opt-join,该算法将Token批处理技术集成在现有的事件驱动框架中,以降低前缀事件的处理代价;通过置换哈希查找与过滤操作的执行位置来降低哈希查找代价,并理论证明了该置换的正确性.实验结果表明:与Topk-join算法相比,Opt-join取得了1.28倍~3.09倍的性能提升.实验数据还显示:随着数据长度的增加或k值的增长,Opt-join的性能优势有不断增加的趋势. 相似文献
14.
We study two related network design problems with two cost functions. In the buy-at-bulk k-Steiner tree problem we are given a graph G(V,E) with a set of terminals T⊆V including a particular vertex s called the root, and an integer k≤|T|. There are two cost functions on the edges of G, a buy cost b:E→ℝ+ and a distance cost r:E→ℝ+. The goal is to find a subtree H of G rooted at s with at least k terminals so that the cost ∑
e∈H
b(e)+∑
t∈T−s
dist(t,s) is minimized, where dist(t,s) is the distance from t to s in H with respect to the r cost. We present an O(log 4
n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. The second and closely related one is bicriteria approximation algorithm for Shallow-light k-Steiner trees. In the shallow-light k-Steiner tree problem we are given a graph G with edge costs b(e) and distance costs r(e), and an integer k. Our goal is to find a minimum cost (under b-cost) k-Steiner tree such that the diameter under r-cost is at most some given bound D. We develop an (O(log n),O(log 3
n))-approximation algorithm for a relaxed version of Shallow-light k-Steiner tree where the solution has at least
terminals. Using this we obtain an (O(log 2
n),O(log 4
n))-approximation algorithm for the shallow-light k-Steiner tree and an O(log 4
n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. Our results are recently used to give the first polylogarithmic approximation algorithm for the non-uniform
multicommodity buy-at-bulk problem (Chekuri, C., et al. in Proceedings of 47th Annual IEEE Symposium on Foundations of Computer
Science (FOCS’06), pp. 677–686, 2006).
A preliminary version of this paper appeared in the Proceedings of 9th International Workshop on Approximation Algorithms
for Combinatorial Optimization Problems (APPROX) 2006, LNCS 4110, pp. 153–163, 2006.
M.T. Hajiaghayi supported in part by IPM under grant number CS1383-2-02.
M.R. Salavatipour supported by NSERC grant No. G121210990, and a faculty start-up grant from University of Alberta. 相似文献
15.
Lawrence T. Kou 《Acta Informatica》1990,27(4):369-380
Summary This paper studies the design and implementation of an approximation algorithm for the Steiner tree problem. Given any undirected distance graph G and a set of Steiner points S, the algorithm produces a Steiner tree with total weight on its edges no more than 2(1–1/L) times the total weight on the optimal Steiner tree, where L is the number of leaves in the optimal Steiner tree. Our implementation of the algorithm, in the worst case, makes it run in 0(¦E
g¦+¦V
g–S¦log¦V
g–S¦+¦S¦log ¦S¦) time for general graph G and in 0(¦S¦ log¦S¦+M log (M,¦V
g–S¦)) time for sparse graph G, where E
g is the set of edges in G, Vg is the set of vertices in G, M = min {¦E
g, (¦V
g–S¦–1)2/2} and (x,y) = min {i¦log(i)
y x/y}.The implementation is not likely to be improved significantly without the improvement of the shortest paths algorithm and the minimum spanning tree algorithm as the algorithm essentially composes of the computation of the multiple sources shortest paths of a graph with ¦V
g¦ vertices and ¦E
g¦ edges and the minimum spanning tree of a graph with ¦V
g–S¦ vertices and M edges. 相似文献
16.
In order to solve Toeplitz linear systems An(f)x=b generated by a nonnegative integrable function f, through use of the preconditioned conjugate gradient (PCG) method, several
authors have proposed An(g) as preconditioner in the case where g is a trigonometric polynomial [10, 14, 27, 12, 28]. In preceding works, we studied
the distribution and the extremal properties of the spectrum of the preconditioned matrix G=A
n
−1
(g) An(f). In this paper we prove that the union of the spectra of all the Gn is dense on the essential range of f/g, i.e.,ER(f/g) and we obtain asymptotic information about the rate of convergence of the smallest eigenvalue λ
l
n
of Gn to r (and of λ
n
n
to R). As a consequence of this second order result, it is possible to handle the case where f has zeros of any order θ,
through the PCG methods proposed in [10, 14]. This is a noteworthy extension since the techniques developed in [10, 14, 27,
12, 28] are shown to be effective only when f has zeros of even orders. The cost of this procedure is O(n1+c(θ) log n) arithmetic operations (ops) where the quantity c(θ) belongs to interval [0,2−1] and takes the maximum value 2−1 when f has a zero of odd order. Finally, for the special case of zeros of odd orders, we propose a further algorithm which
makes use of the PCG techniques proposed in [10, 14, 27, 12, 28] for theeven order case, reducing the cost to O(n long n) ops. 相似文献
17.
Dekel Tsur 《Information Processing Letters》2008,108(4):251-254
The guided tree edit distance problem is to find a minimum cost series of edit operations that transforms two input forests F and G into isomorphic forests F′ and G′ such that a third input forest H is included in F′ (and G′). The edit operations are relabeling a vertex and deleting a vertex. We show efficient algorithms for this problem that are faster than the previous algorithm for this problem of Peng and Ting [Z. Peng, H. Ting, Guided forest edit distance: Better structure comparisons by using domain-knowledge, in: Proc. 18th Symposium on Combinatorial Pattern Matching (CPM), 2007, pp. 28-39]. 相似文献
18.
Improving Markov Chain Monte Carlo Model Search for Data Mining 总被引:9,自引:0,他引:9
The motivation of this paper is the application of MCMC model scoring procedures to data mining problems, involving a large number of competing models and other relevant model choice aspects.To achieve this aim we analyze one of the most popular Markov Chain Monte Carlo methods for structural learning in graphical models, namely, the MC
3 algorithm proposed by D. Madigan and J. York (International Statistical Review, 63, 215–232, 1995). Our aim is to improve their algorithm to make it an effective and reliable tool in the field of data mining. In such context, typically highly dimensional in the number of variables, little can be known a priori and, therefore, a good model search algorithm is crucial.We present and describe in detail our implementation of the MC
3 algorithm, which provides an efficient general framework for computations with both Directed Acyclic Graphical (DAG) models and Undirected Decomposable Models (UDG). We believe that the possibility of commuting easily between the two classes of models constitutes an important asset in data mining, where an a priori knowledge of causal effects is usually difficult to establish.Furthermore, in order to improve the MC
3 method we propose provide several graphical monitors which can help extracting results and assessing the goodness of the Markov chain Monte Carlo approximation to the posterior distribution of interest.We apply our proposed methodology first to the well-known coronary heart disease dataset (D. Edwards &; T. Havránek, Biometrika, 72:2, 339–351, 1985). We then introduce a novel data mining application which concerns market basket analysis. 相似文献
19.
Ming-Syan Chen Hui-I Hsiao Philip S. Yu 《The VLDB Journal The International Journal on Very Large Data Bases》1997,6(2):121-131
In this paper, we explore an approach of interleaving a bushy execution tree with hash filters to improve the execution of
multi-join queries. Similar to semi-joins in distributed query processing, hash filters can be applied to eliminate non-matching
tuples from joining relations before the execution of a join, thus reducing the join cost. Note that hash filters built in
different execution stages of a bushy tree can have different costs and effects. The effect of hash filters is evaluat
ed first. Then, an efficient scheme to determine an effective sequence of hash filters for a bushy execution tree is developed,
where hash filters are built and applied based on the join sequence specified in the bushy tree so that not only is the reduction
effect optimized but also the cost associated is minimized. Various schemes using hash filters are implemented and evaluated
via simulation. It is experimentally shown that the application of hash filters is in general a very powerful means to improve
th
e execution of multi-join queries, and the improvement becomes more prominent as the number of relations in a query increases.
Edited by G. Gardarin. Received October 1994 / Accepted December 1995 相似文献
20.
Shai Simonson 《Theory of Computing Systems》1987,20(1):235-252
The Min Cut Linear Arrangement problem asks, for a given graphG and a positive integerk, if there exists a linear arrangement ofG's vertices so that any line separating consecutive vertices in the layout cuts at mostk of the edges. A variation of this problem insists that the arrangement be made on a (fixed-degree) tree instead of a line. We show that (1) this problem isNP-complete even whenG is planar; (2) it is easily solved whenG is a tree; and (3) there is a simple characterization for all graphs with cost 2 or less. Our main result is a linear-time algorithm to embed an outerplanar graphG into a spanning tree with cost at most maxdegree(G) + 1. This result is important because it extends to an approximation algorithm for the standard Min Cut Linear Arrangement Problem on outerplanar graphs.Supported in part by NSF Grant CCR-8710730. 相似文献