The set-set LCS problem

An efficient algorithm is presented that solves a generalization of the Longest Common Subsequence problem, in which both of the input strings consists of sets of symbols which may be permuted.     

The set LCS problem

An efficient algorithm is presented that solves a generalization of the Longest Common Subsequence problem, in which one of the two input strings contains sets of symbols which may be permuted. This problem arises from a music application.     

A fast and practical bit-vector algorithm for the Longest Common Subsequence problem

This paper presents a new practical bit-vector algorithm for solving the well-known Longest Common Subsequence (LCS) problem. Given two strings of length m and n, nm, we present an algorithm which determines the length p of an LCS in O(nm/w) time and O(m/w) space, where w is the number of bits in a machine word. This algorithm can be thought of as column-wise “parallelization” of the classical dynamic programming approach. Our algorithm is very efficient in practice, where computing the length of an LCS of two strings can be done in linear time and constant (additional/working) space by assuming that mw.     

The constrained longest common subsequence problem

This paper considers a constrained version of longest common subsequence problem for two strings. Given strings S₁, S₂ and P, the constrained longest common subsequence problem for S₁ and S₂ with respect to P is to find a longest common subsequence lcs of S₁ and S₂ such that P is a subsequence of this lcs. An O(rn²m²) time algorithm based upon the dynamic programming technique is proposed for this new problem, where n, m and r are lengths of S₁, S₂ and P, respectively.     

Using multiple indexes for efficient subsequence matching in time-series databases

A time-series database is a set of data sequences, each of which is a list of changing values of an object in a given period of time. Subsequence matching is an operation that searches for such data subsequences whose changing patterns are similar to a query sequence in a time-series database. This paper addresses a performance issue of time-series subsequence matching. First, we quantitatively examine the performance degradation caused by the window size effect, and then show that the performance of subsequence matching with a single index is not satisfactory in real applications. We claim that index interpolation is a fairly effective tool to solve this problem. Index interpolation performs subsequence matching by selecting the most appropriate one from multiple indexes built on windows of their distinct sizes. For index interpolation, we need to decide the sizes of windows for multiple indexes to be built. In this paper, we solve the problem of selecting optimal window sizes from the perspective of physical database design. Given a set of pairs 〈length, frequency〉 of query sequences to be performed in a target application and a set of window sizes for building multiple indexes, we devise a formula that estimates the overall cost of all the subsequence matchings performed in a target application. By using this formula, we propose an algorithm that determines the optimal window sizes for maximizing the performance of entire subsequence matchings. We formally prove the optimality as well as the effectiveness of the algorithm. Finally, we show the superiority of our approach by performing extensive experiments with a real-life stock data set and a large volume of synthetic data sets.     

Quantum Algorithms for Weighing Matrices and Quadratic Residues

Abstract. In this article we investigate how we can employ the structure of combinatorial objects like Hadamard matrices and weighing matrices to devise new quantum algorithms. We show how the properties of a weighing matrix can be used to construct a problem for which the quantum query complexity is significantly lower than the classical one. It is pointed out that this scheme captures both Bernstein and Vazirani's inner-product protocol, as well as Grover's search algorithm. In the second part of the article we consider Paley's construction of Hadamard matrices, which relies on the properties of quadratic characters over finite fields. We design a query problem that uses the Legendre symbol χ (which indicates if an element of a finite field F _q is a quadratic residue or not). It is shown how for a shifted Legendre function f _s (i)=χ(i+s) , the unknown s ∈ F _q can be obtained exactly with only two quantum calls to f _s . This is in sharp contrast with the observation that any classical, probabilistic procedure requires more than log q + log ((1-ɛ )/2) queries to solve the same problem.     

A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs

The Arc-Preserving Subsequence (APS) problem appears in the comparison of RNA structures in computational biology. Given two arc-annotated sequences of length n and m<n, APS asks if the shorter sequence can be obtained from the longer one by deleting certain elements along with their incident arcs. It is known that APS with pairwise nested arcs can be solved in O(mn) time. We give an algorithm running in O(m²+n) time in the worst case, actually it is even faster in particular if the shorter sequence has many arcs. The result may serve as a building block for improved APS algorithms in the general case.     

Efficient moving average transform-based subsequence matching algorithms in time-series databases

Moving average transform is very useful in finding the trend of time-series data by reducing the effect of noise, and has been used in many areas such as econometrics. Previous subsequence matching methods with moving average transform, however, are problematic in that, since they must build multiple indexes in supporting transform of arbitrary order, they incur index overhead both in storage space and in update maintenance. To solve this problem, we propose a single-index approach to subsequence matching that supports moving average transform of arbitrary order in time-series databases. Using the single-index approach, we can reduce both the storage space and the index maintenance overhead. In explaining the single-index approach, we first introduce the notion of poly-order moving average transform by generalizing the original definition of moving average transform. We then formally prove the correctness of poly-order transform-based subsequence matching. We also propose two subsequence matching methods based on poly-order transform that efficiently support moving average transform of arbitrary order. Experimental results for real stock data show that, compared with the sequential scan, our methods improve average performance significantly, by a factor of 22.6-33.6. Also, compared with cases in which an index is built for every moving average order, our methods reduce storage space and maintenance effort significantly while incurring only marginal performance degradation. Our approach entails the additional advantage of being generalized to support many other transforms in addition to moving average transform. Therefore, we believe that our approach will be widely used in many transform-based subsequence matching methods.     

The longest almost-increasing subsequence

Given a sequence of n elements, we introduce the notion of an almost-increasing subsequence as the longest subsequence that can be converted to an increasing subsequence by possibly adding a value, that is at most a fixed constant, to each of the elements. We show how to optimally construct such subsequence in time, where k is the length of the output subsequence.     

分布式视频服务器的动态数据分配算法

针对分布式视频点播系统,提出了三种改进的动态数据分配算法：DRR(Dynamic Round Robin video data allocation),DBWP(Dynamic Bandwidth Weighted Partition video data allocation),DPB(Dynamic Popularity Based video data allocation)。仿真结果表明：分别与RR,BWP,PB算法相比,DRR,DBWP和DPB算法具有较好的环境适应性,特别是在视频对象访问频率及视频服务器带宽差异较大、环境扰动增强的情况下,DBWP和DPB算法可明显降低分布式视频服务器的视频对象访问响应时间。     

The longest common subsequence problem revisited

This paper re-examines, in a unified framework, two classic approaches to the problem of finding a longest common subsequence (LCS) of two strings, and proposes faster implementations for both. Letl be the length of an LCS between two strings of lengthm andn m, respectively, and let s be the alphabet size. The first revised strategy follows the paradigm of a previousO(ln) time algorithm by Hirschberg. The new version can be implemented in timeO(lm · min logs, logm, log(2n/m)), which is profitable when the input strings differ considerably in size (a looser bound for both versions isO(mn)). The second strategy improves on the Hunt-Szymanski algorithm. This latter takes timeO((r +n) logn), wherermn is the total number of matches between the two input strings. Such a performance is quite good (O(n logn)) whenrn, but it degrades to (mn logn) in the worst case. On the other hand the variation presented here is never worse than linear-time in the productmn. The exact time bound derived for this second algorithm isO(m logn +d log(2mn/d)), whered r is the number ofdominant matches (elsewhere referred to asminimal candidates) between the two strings. Both algorithms require anO(n logs) preprocessing that is nearly standard for the LCS problem, and they make use of simple and handy auxiliary data structures.     

Algorithms for the boundary selection problem

User-oriented clustering schemes enable the classification of documents based upon the user's perception of the similarity between documents, rather than on some similarity function presumed by the designer to represent the user's criteria. In an earlier paper it was shown that such a classification scheme can be developed in two stages. The first stage involves the accumulation of relevance judgements provided by users,vis-à-vis past query instances, into a suitable structure. The second stage consists of cluster identification. When the structure chosen, in the first stage, for the accumulation of corelevance characteristics of documents is a straight line, the second stage can be formulated as a function optimization problem termed the Boundary Selection Problem (BSP). A branch-and-bound algorithm with a good bounding function is developed for the BSP. Although significant pruning is achieved due to the bounding function, the complexity is still high for a problem of a large size. For such a problem a heuristic that divides it into a number of subproblems, each being solved by a branch-and-bound approach, is developed. Then the overall problem is mapped to an integer knapsack problem and solved by the use of dynamic programming. The tradeoff between accuracy and complexity can be controlled, giving the user a preference of one over the other. Assuming that the heuristic which divides the overall problem introduces no errors and is given sufficient time, the branch and bound with dynamic programming (BBDP) approach will converge to the optimal solution. Two other heuristic approaches, one with the application of a polynomial dynamic programming algorithm and the other which works in a greedy way, are also proposed for the BSP and an experimental comparison of all these approaches is provided. Experimental results indicate that all proposed algorithms show better performance compared with the existing algorithm.     

Algorithms for Fuzzy Segmentation

Fuzzy segmentation is an effective way of segmenting out objects in pictures containing both random noise and shading. This is illustrated both on mathematically created pictures and on some obtained from medical imaging. A theory of fuzzy segmentation is presented. To perform fuzzy segmentation, a ‘connectedness map’ needs to be produced. It is demonstrated that greedy algorithms for creating such a connectedness map are faster than the previously used dynamic programming technique. Once the connectedness map is created, segmentation is completed by a simple thresholding of the connectedness map. This approach is efficacious in instances where simple thresholding of the original picture fails. Received: 22 October 1998?Received in revised form: 22 November 1998?Accepted: 2 December 1998     

最大子长方体问题的动态规划算法

动态规划程序设计策略对许多实际应用问题的解决是灵活和有效的。首先对一类最大子长方体问题进行了分析,并给出了该类问题的动态规划解法,最后对所给算法的复杂度进行了分析和讨论。实验结果验证了所提出方法的有效性。     

动态规划法中返求最优可靠度分配的实用算法

本文简单介绍动态规划法应用,并着重对动态规划法中返求最优可靠度分配的算法进行研究,提出了一种比较简单实用的实现算法,该方法的优点在于：简单实用,易于编程和实现,解决参数化编程求解问题。     

Solving single-product economic lot-sizing problem with non-increasing setup cost,constant capacity and convex inventory cost in O(N log N) time

This paper considers an economic lot sizing model with constant capacity, non-increasing setup cost, and convex inventory cost function. Algorithms with computational time of O(N×TD_N)have been developed for solving the model, where N is the number of planning periods and TD_N is the total demand. This study partially characterizes the optimal planning structure of the model. A new efficient algorithm with computational time of O(N log N) has also been developed based on the partial optimal structure. Moreover, computational study demonstrates that the new algorithm is efficient.     

Algorithms for solving the single-sink fixed-charge transportation problem

The single-sink fixed-charge transportation problem is an important subproblem of the fixed-charge transportation problem. Just a few methods have been proposed in the literature to solve this problem. In this paper, solution approaches based on dynamic programming and implicit enumeration are revisited. It is shown how the problem size as well as the search space of a recently published dynamic programming method can be reduced by exploiting reduced cost information. Additionally, a further implicit enumeration approach relying on solution concepts for the binary knapsack problem is introduced. The performance of the various solution methods is compared in a series of computational experiments.