Global Convergence of a Class of Collinear Scaling Algorithms with Inexact Line Searches on Convex Functions

Ariyawansa [2] has presented a class of collinear scaling algorithms for unconstrained minimization. A certain family of algorithms contained in this class may be considered as an extension of quasi-Newton methods with the Broyden family [11] of approximants of the objective function Hessian. Byrd, Nocedal and Yuan [7] have shown that all members except the DFP [11] method of the Broyden convex family of quasi-Newton methods with Armijo [1] and Goldstein [12] line search termination criteria are globally and q-superlinearly convergent on uniformly convex functions. Extension of this result to the above class of collinear scaling algorithms of Ariyawansa [2] has been impossible because line search termination criteria for collinear scaling algorithms were not known until recently. Ariyawansa [4] has recently proposed such line search termination criteria. In this paper, we prove an analogue of the result of Byrd, Nocedal and Yuan [7] for the family of collinear scaling algorithms of Ariyawansa [2] with the line search termination criteria of Ariyawansa [4]. Received: May 8, 1996; revised January 27, 1999     

A Note on Decision versus Search for Graph Automorphism

We show that for any graphG,knontrivial automorphisms ofG—if as many exist—can be computed in time |G|^{O(log k)}with nonadaptive queries to GA, the decision problem for Graph Automorphism. As a consequence, we show that some problems related to GA are actually polynomial-time truth-table equivalent to GA. One of these results provides an answer to an open question of Lubiw [SIAM J. Comput.10(1981), 11–21].     

A Survey of Methods for Scaling Up Inductive Algorithms

One of the defining challenges for the KDD research community is to enable inductive learning algorithms to mine very large databases. This paper summarizes, categorizes, and compares existing work on scaling up inductive algorithms. We concentrate on algorithms that build decision trees and rule sets, in order to provide focus and specific details; the issues and techniques generalize to other types of data mining. We begin with a discussion of important issues related to scaling up. We highlight similarities among scaling techniques by categorizing them into three main approaches. For each approach, we then describe, compare, and contrast the different constituent techniques, drawing on specific examples from published papers. Finally, we use the preceding analysis to suggest how to proceed when dealing with a large problem, and where to focus future research.     

基于变异方法的禁忌搜索

1 TS简介禁忌搜索(Tabu Search或Taboo Search,简称 TS)技术是一种亚启发式(meta-heuristic)搜索技术,是局部邻城搜索的一种扩展。由Glover在1986年首次提出,进而形成一套完整算法,详见文[2,3]。所谓禁忌就是禁止重复前面的工作。为了避免局部邻域搜索中陷入局部最优的主要不足,禁忌搜索用一个禁忌表记录下己经到达过的局部最优点,在下一次的搜索中,利用禁忌表中的信息不再或有选择地搜索这些点,以此来跳出局部最优点。就好比人的短时记忆,走过的路不再重复或有选择地重复;同时“遗志”又使得这些禁止是弱禁止,即在一定的时间之后这些禁止将失效,最终达到全局优化之目的。该算法可简单地表示为:     

A Note on Linear Time Algorithms for Maximum Error Histograms

Histograms and Wavelet synopses provide useful tools in query optimization and approximate query answering. Traditional histogram construction algorithms, e.g., V-Optimal, use error measures which are the sums of a suitable function, e.g., square, of the error at each point. Although the best-known algorithms for solving these problems run in quadratic time, a sequence of results have given us a linear time approximation scheme for these algorithms. In recent years, there have been many emerging applications where we are interested in measuring the maximum (absolute or relative) error at a point. We show that this problem is fundamentally different from the other traditional {rm{non}}{hbox{-}}ell_infty error measures and provide an optimal algorithm that runs in linear time for a small number of buckets. We also present results which work for arbitrary weighted maximum error measures.     

A Note on Some Phase Differencing Algorithms for Disparity Estimation

Disparity can be estimated from the local phase differences between a pair of stereo images after Gabor filterings. In this paper, some phase differencing algorithms are discussed from the point of view of numerical computation. They are all categorised as certain types of Newton iterations, hence are restricted by the preconditions of Newton iterations. Furthermore, a numerical sensitivity analysis is made for phase computation near its singularity points without referring to any specific filtering method. It makes clear that the numerical instability has its roots in the singularities of the phase functions themselves rather than in their derivatives, therefore severe errors cannot be properly reduced by Newton iterations. Hence, the singularity problem must be carefully treated for any disparity estimation using phase differencing techniques. In the case of foveal vision, such as target detection or vergence control, the central parts of scenes are of interest. A shift-trials algorithm is proposed to contain the effects of singularities instead of relying on detection and removal of singularity neighbourhoods through local computation. This algorithm directly tackles the singularity problem by posing the local disparity estimations as a minimisation of the phase differences of the left and right views in terms of a global matching residual norm. By a direct search for solution, no numerical derivative is needed, phase singularity can be tolerated and robust results are thus produced.     

Termination Detection for Parallel Shortest Path Algorithms

Shortest path computation is required by a large number of applications such as VLSI, transportation, and communication networks. These applications, which are often very complex and have sparse networks, generally use parallel labeling shortest path algorithms. Such algorithms, when implemented on a distributed memory machine, require termination detection methods; these methods consist of some type of synchronization among all processors. Because global synchronization can be costly, it is assumed that the best termination detection methods synchronize as infrequently as possible. The frequency, however, can significantly impact the idle time of parallel labeling shortest path algorithms. In this paper we analyze the impact of this frequency on the performance, in particular the idle time, and identify when low versus high frequency detection is best. The analysis and results indicate that when the size of the subnetwork assigned to processor is small enough so that the computation time is less than or equal to the communication time within an iteration, high frequency termination detection methods should be used. Otherwise, low frequency methods should be used.     

A Note on Exact Algorithms for Vertex Ordering Problems on Graphs

In this note, we give a proof that several vertex ordering problems can be solved in O ^∗(2 ⁿ ) time and O ^∗(2 ⁿ ) space, or in O ^∗(4 ⁿ ) time and polynomial space. The algorithms generalize algorithms for the Travelling Salesman Problem by Held and Karp (J. Soc. Ind. Appl. Math. 10:196–210, 1962) and Gurevich and Shelah (SIAM J. Comput. 16:486–502, 1987). We survey a number of vertex ordering problems to which the results apply.     

Termination Criteria for DPO Transformations with Injective Matches

Reasoning about graph and model transformation systems is an important means to underpin model-driven software engineering, such as Model-Driven Architecture (MDA) and Model Integrated Computing (MIC). Termination criteria for graph and model transformation systems have become a focused area recently. This paper provides termination criteria for graph and model transformation systems with injective matches and finite input structure. It proposes a treatment for infinite sequences of rule applications, and takes attribute conditions, negative application conditions, and type constraints into account. The results are illustrated on case studies excerpted from real-world transformations, which show the termination properties of the frequently used "transitive closure" and "leaf collector" transformation idioms. An intuitive comparison with other approaches is also given.     

A Decentralized Method for Scaling Up Genome Similarity Search Services

As genome sequence databases grow in size, the accuracy and speed of sequence similarity detection become more important. There is an increasing number of methods being used for detecting sequence similarity. Meanwhile the demands for genome sequence search and alignment services are also increasing. It is a challenge to scale up the computer systems for hosting various methods and serving requests to these methods in a timely manner. Traditional clusters, which are used in most of scientific centers, can not cope with this challenge. This paper tackles this problem in a novel way, which treats the sequence search requests as content requests to both genome databases and similarity detection methods; therefore, scaling up the computer systems that serve these contents is a process of constructing content distribution network. The paper gives a decentralized method to dynamically construct content distribution networks for a variety of genome sequence similarity detection services. It also provides a scheduling algorithm for efficiently using content nodes. Our simulation study shows that scalability and high content node utilization can be achieved in such a system while the cost of achieving remains reasonable.     

A Library Hierarchy for Implementing Scalable Parallel Search Algorithms

This paper describes the design of the Abstract Library for Parallel Search (ALPS), a framework for implementing scalable, parallel algorithms based on tree search. ALPS is specifically designed to support data-intensive algorithms, in which large amounts of data are required to describe each node in the search tree. Implementing such algorithms in a scalable manner is challenging both because of data storage requirements and communication overhead. ALPS incorporates a number of new ideas to address this challenge. The paper also describes the design of two other libraries forming a hierarchy built on top of ALPS. The first is the Branch, Constrain, and Price Software (BiCePS) library, a framework that supports the implementation of parallel branch and bound algorithms in which the bounds are obtained by solving some sort of relaxation, usually Lagrangian. In this layer, the notion of global data objects associated with the variables and constraints is introduced. These global objects provide a connection between the various subproblems in the search tree, but they pose further difficulties for designing scalable algorithms. The other library is the BiCePS linear integer solver (BLIS), a concretization of BiCePS, in which linear programming is used to obtain bounds in each search tree node.     

搜索引擎结果聚类算法研究

随着Web文档数量的剧增,搜索引擎也暴露了许多问题,用户不得不在搜索引擎返回的大量文档摘要列表中查找。而对搜索引擎结果聚类能使用户在更高的主题层次上来查看搜索引擎返回的结果。该文提出了搜索引擎结果聚类的几个重要指标并给出了一个新的基于PAT—tree的搜索引擎结果聚类算法。     

A Note on the Expected Time for Finding Maxima by List Algorithms

Maxima in R ^d are found incrementally by maintaining a linked list and comparing new elements against the linked list. If the elements are independent and uniformly distributed in the unit square [0,1] ^d , then, regardless of how the list is manipulated by an adversary, the expected time is O(n log ^d-2 n) . This should be contrasted with the fact that the expected number of maxima grows as log ^d-1 n , so no adversary can force an expected complexity of n log ^d-1 n . Note that the expected complexity is O(n) for d=2 . Conversely, there are list-manipulating adversaries for which the given bound is attained. However, if we naively add maxima to the list without changing the order, then the expected number of element comparisons is n +o(n) for any . In the paper we also derive new tail bounds and moment inequalities for the number of maxima. Received January 7, 1997; revised June 20, 1997.     

Search Algorithms for Subdatatype-Based Multimedia Retrieval

Recently, researchers have mainly been interested only in the search for data content that are globally similar to the query and not in the search for inside data items. This paper presents an algorithm, called a generalized virtual node (GVN) algorithm, to search for data items where parts (subdatatype) are similar to the incoming query. We call this subdatatype-based multimedia retrieval. Each multimedia datatype, such as image and audio is represented in this paper as a k-dimensional signal in the spatio-temporal domain. A k-dimensional signal is transformed into characteristic features and these features are stored in a hierarchical multidimensional structure, called the k-tree. Each node on the k-tree contains partial content corresponding to the spatial and/or temporal positions in the data. The k-tree structure allows us to build a unified retrieval model for any types of multimedia data. It also eliminates unnecessary comparisons of cross-media querying. The experimental results of the use of the new GVN algorithm for subaudio and subimage retrievals show that it takes much less retrieval times than other earlier algorithms such as brute-force and the partial-matching algorithm, while the accuracy is acceptable.     

基于分割的字符串相似性查找算法

字符串相似性查找问题主要包括两方面,基于阈值的字符串相似性查找以及top-k字符串相似性查找。目前处理基于阈值的字符串相似性查找问题的算法多是基于过滤-验证框架的。基于该框架提出了PBsearch算法,算法在过滤阶段首次加入One-Off条件过滤掉大量的无效匹配,并在验证阶段提出了一种新的验证算法MultiThreshold算法,大大减少了计算编辑距离的次数。在top-k字符串相似性查找问题方面,提出了两种基于分割思想的算法,Pb-topk算法和PbCount-topk算法。其中,Pb-topk算法采用差值递增的策略,减少了需处理的字符串数目;PbCount-topk算法采用匹配数目划分的策略,进一步缩小了候选集的规模。最后,通过在3个真实数据集上的实验结果,验证了提出算法的高效性。     

Termination Criteria for Bounded Model Checking: Extensions and Comparison

Increasing attention has been paid recently to criteria that allow one to conclude that a structure models a linear-time property from the knowledge that no counterexamples exist up to a certain length. These termination criteria effectively turn Bounded Model Checking into a full-fledged verification technique and sometimes result in considerable time savings. In [M. Awedh and F. Somenzi. Proving more properties with bounded model checking. In R. Alur and D. Peled, editors, Sixteenth Conference on Computer Aided Verification (CAV'04), pages 96–108. Springer-Verlag, Berlin, July 2004. LNCS 3114] we presented a criterion based on the translation of the linear-time specification into a Büchi automaton. BMC can be terminated if no fair cycle is found up to a given length, and one can prove that no fair cycle exists beyond that length. The maximum length for which counterexamples are explicitly checked is called the termination length; it obviously depends on the model, the property, and the termination criterion. In this paper we improve the criterion of [M. Awedh and F. Somenzi. Proving more properties with bounded model checking. In R. Alur and D. Peled, editors, Sixteenth Conference on Computer Aided Verification (CAV'04), pages 96–108. Springer-Verlag, Berlin, July 2004. LNCS 3114] by adding a check that often substantially reduces termination length. Our previous work employed translation to a non-generalized Büchi automaton. Though a well-known technique converts a generalized automaton into that form by composing it with a counter, it has the undesirable effect of considerably lengthening the cycles in the graph to be searched. We propose several alternatives to that approach and compare them experimentally. The translation to automata can be accomplished in more than one way, and in this paper we contrast two of them: one based on the algorithms of [F. Somenzi and R. Bloem. Efficient Büchi automata from LTL formulae. In E. A. Emerson and A. P. Sistla, editors, Twelfth Conference on Computer Aided Verification (CAV'00), pages 248–263. Springer-Verlag, Berlin, July 2000. LNCS 1855], and one based on the notion of tight automaton of [E. Clarke, O. Grumberg, and K. Hamaguchi. Another look at LTL model checking. In D. L. Dill, editor, Sixth Conference on Computer Aided Verification (CAV'94), pages 415–427. Springer-Verlag, Berlin, 1994. LNCS 818]. The latter yields shorter counterexamples, but the former often leads to earlier termination. In addition, it can help in identifying safety properties, for which termination checks are much more efficient than for the general case. We finally present results on comparing techniques based on cycle detection to the technique of [V. Schuppan and A. Biere. Efficient reduction of finite state model checking to reachability analysis. Software Tools for Technology Transfer, 5(2–3):185–204, Mar. 2004], which converts liveness properties into safety properties by augmentation of the model.     

基于聚类算法的个性化搜索研究

搜索引擎的出现使得用户从信息爆炸性增长的互联网上获取所需的信息成为可能,个性化搜索引擎的研究使搜索结果尽可能满足不同用户的信息需求。文中提出了一种基于改进的DBSCAN算法的个性化搜索方法,在全文搜索包lucene与开源搜索引擎Nutch的基础上,实验证明该方法改善了聚类的结果,提高了用户搜索的准确率。