Exploiting partial order with Quicksort

The widely known Quicksort algorithm does not attempt to actively take advantage of partial order in sorting data. A simple change can be made to the Quicksort strategy to give a bestcase performance of n, for ordered data, with a smooth transition to O(n log n) for random data. This algorithm (Transort) matches the performance of Sedgewick's claimed best implementation of Quicksort for random data.     

A new external sorting algorithm with no additional disk space

This paper is concerned with an external sorting algorithm with no additional disk space. The proposed algorithm is a hybrid one that uses Quicksort and special merging process in two distinct phases. The algorithm excels in sorting a huge file, which is many times larger than the available memory of the computer. This algorithm creates no extra backup file for manipulating huge records. For this, the algorithm saves huge disk space, which is needed to hold the large file. Also our algorithm switches to special merging process after the first phase that uses Quicksort. This reduces the time complexity and makes the algorithm faster.     

Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism

Data compression can be used to simultaneously reduce memory, communication and computation requirements of string comparison. In this paper we address the problem of computing the length of the longest common subsequence (LCS) between run-length-encoded (RLE) strings. We exploit RLE both to reduce the complexity of LCS computation from O(M×N) to O(mN+Mn−mn), where M and N are the lengths of the original strings and m and n the number of runs in their RLE representation, and to improve the inherent parallelism of the proposed algorithm, so that it may execute in O(m+n) steps on a systolic array of M+N units.We also discuss the application of the proposed algorithm to the related problem of edit distance (ED) computation.     

Efficient out-of-core sorting algorithms for the Parallel Disks Model

In this paper,¹ we present efficient algorithms for sorting on the Parallel Disks Model (PDM). Numerous asymptotically optimal algorithms have been proposed in the literature. However, many of these merge based algorithms have large underlying constants in the time bounds, because they suffer from the lack of read parallelism on the PDM. The irregular consumption of the runs during the merge affects the read parallelism and contributes to the increased sorting time. In this paper, we first introduce a novel idea called the dirty sequence accumulation that improves the read parallelism. Next, we show analytically that this idea can reduce the number of parallel I/O’s required to sort the input close to the lower bound of . We verify experimentally our dirty sequence idea with the standard R-Way merge and show that our idea can reduce the number of parallel I/Os to sort on the PDM significantly.     

A faster algorithm for matching a set of patterns with variable length don't cares

We present a simple and faster solution to the problem of matching a set of patterns with variable length don't cares. Given an alphabet Σ, a pattern p is a word p₁@p₂?@pm, where pi is a string over Σ called a keyword and @∉Σ is a symbol called a variable length don't care (VLDC) symbol. Pattern p matches a text t if t=u₀p₁u₁…um−1pmum for some u₀,…,um∈Σ^∗. The problem addressed in this paper is: given a set of patterns P and a text t, determine whether one of the patterns of P matches t.Kucherov and Rusinowitch (1997) [9] presented an algorithm that solves the problem in time O((|t|+|P|)log|P|), where |P| is the total length of keywords in every pattern of P. We give a new algorithm based on Aho-Corasick automaton. It uses the solutions of Dynamic Marked Ancestor Problem of Chan et al. (2007) [5]. The algorithm takes O((|t|+‖P‖)logκ/loglogκ) time, where ‖P‖ is the total number of keywords in every pattern of P, and κ is the number of distinct keywords in P. The algorithm is faster and simpler than the previous approach.     

An efficient external sorting with minimal space requirement

An efficient external sorting algorithm with minimal space requirement is presented in this article. The average number of passes over the data is approximately 1 +Ln(N + 1)/4B, whereN is the number of records in the file to be sorted, andB is the buffer size. The external storage requirement is only the file itself, no additional disk space is required. The internal storage requirement is four buffers: two for input, and two for output. The buffer size can be adjusted to the available memory space. A stack of size log₂ N is also required.This work was partially supported by a fellowship and grant from Western Michigan University.     

Edit distance for a run-length-encoded string and an uncompressed string

We propose a new algorithm for computing the edit distance of an uncompressed string against a run-length-encoded string. For an uncompressed string of length n and a compressed string with M runs, the algorithm computes their edit distance in time O(Mn). This result directly implies an O(min{mN,Mn}) time algorithm for strings of lengths m and n with M and N runs, respectively. It improves the previous best known time bound O(mN+Mn).     

A parallel version of cook and Kim's algorithm for presorted lists

The Cook and Kim algorithm is a well known method for sorting presorted lists. This paper presents observations based on an implementation of the algorithm on a single processor. An extension of the algorithm to a tightly coupled multiprocessor will also be presented. The performance of the parallel version of the algorithm on presorted lists will be compared to that of a heavily used parallel sort algorithm for tightly coupled multiprocessors, Parallel Quicksort.     

Waiting time and complexity for matching patterns with automata

The paper shows how to compute exactly expectations, standard deviations, and cumulative probabilities of the searching times of string-matching algorithms based on the use of automata. This is derived from a methodology based on viewing the underlying Markov chains as exponential families and applying recent results on them.     

Stability criteria for control systems with many non-linear elements

Liapunov functions are used to develop frequency domain criteria for a class of multinonlinear systems in which the non-linear characteristics are restricted in both sector and slope. These criteria are shown to be superior to the multivariable Popov criteria for several particular examples.     

Constrained differential evolution with multiobjective sorting mutation operators for constrained optimization

Differential evolution (DE) is a simple and powerful evolutionary algorithm for global optimization. DE with constraint handling techniques, named constrained differential evolution (CDE), can be used to solve constrained optimization problems (COPs). In existing CDEs, the parents are randomly selected from the current population to produce trial vectors. However, individuals with fitness and diversity information should have more chances to be selected. This study proposes a new CDE framework that uses nondominated sorting mutation operator based on fitness and diversity information, named MS-CDE. In MS-CDE, firstly, the fitness of each individual in the population is calculated according to the current population situation. Secondly, individuals in the current population are ranked according to their fitness and diversity contribution. Lastly, parents in the mutation operators are selected in proportion to their rankings based on fitness and diversity. Thus, promising individuals with better fitness and diversity are more likely to be selected as parents. The MS-CDE framework can be applied to most CDE variants. In this study, the framework is applied to two popular representative CDE variants, (μ + λ)-CDE and ECHT-DE. Experiment results on 24 benchmark functions from CEC’2006 and 18 benchmark functions from CEC’2010 show that the proposed framework is an effective approach to enhance the performance of CDE algorithms.     

Parallel sorting with cooperating heaps in a linear array of processors

A parallel sorting algorithm using cooperating heaps in a linear array of processors is presented. It can sort a sequence whose length is much larger than the number of processors. Because the output begins one step after all the items have been input, sorting n items requires 2n + 1 steps. Two independent modifications of the algorithm are possible; one tries to reduce the number of processors used, and the other can sort more items on the same array.     

Exploiting early sorting and early partitioning for decision support query processing

Decision support queries typically involve several joins, a grouping with aggregation, and/or sorting of the result tuples. We propose two new classes of query evaluation algorithms that can be used to speed up the execution of such queries. The algorithms are based on (1) early sorting and (2) early partitioning– or a combination of both. The idea is to push the sorting and/or the partitioning to the leaves, i.e., the base relations, of the query evaluation plans (QEPs) and thereby avoid sorting or partitioning large intermediate results generated by the joins. Both early sorting and early partitioning are used in combination with hash-based algorithms for evaluating the join(s) and the grouping. To enable early sorting, the sort order generated at an early stage of the QEP is retained through an arbitrary number of so-called order-preserving hash joins. To make early partitioning applicable to a large class of decision support queries, we generalize the so-called hash teams proposed by Graefe et al. [GBC98]. Hash teams allow to perform several hash-based operations (join and grouping) on the same attribute in one pass without repartitioning intermediate results. Our generalization consists of indirectly partitioning the input data. Indirect partitioning means partitioning the input data on an attribute that is not directly needed for the next hash-based operation, and it involves the construction of bitmaps to approximate the partitioning for the attribute that is needed in the next hash-based operation. Our performance experiments show that such QEPs based on early sorting, early partitioning, or both in combination perform significantly better than conventional strategies for many common classes of decision support queries. Received April 4, 2000 / Accepted June 23, 2000     

Stabilized finite elements with equal order of interpolation for soil dynamics problems

Summary The accurate prediction of the behaviour of geostructures is based on the strong coupling between the pore fluid and the solid skeleton. If the relative acceleration of the fluid phase to the skeleton is neglected, the equations describing the problem can be written in terms of skeleton displacements (or velocities) and pore pressures. This mixed problem is similar to others found in solid and fluid dynamics. In the limit case of zero permeability and incompressibility of the fluid phase, the restrictions on the shape functions used to approximate displacements and pressures imposed by Babuska-Brezzi conditions or the Zienkiewicz-Taylor patch test hold. As a consequence, it is not possible to use directly elements with the same order of interpolation for the field variables. This paper proposes two alternative methods allowing us to circumvent the BB restrictions in the incompressibility limit, making it possible to use elements with the same order of interpolation. The first consists on introducing the divergence of the momentum equation of the mixture as an stabilization term, the second is a generalization of the two step-projection method introduced by Chorin for fluid dynamics problems.     

A filtering algorithm for k-mismatch with don't cares

We present a filtering based algorithm for the k-mismatch pattern matching problem with don't cares. Given a text t of length n and a pattern p of length m with don't care symbols in either p or t (but not both), and a bound k, our algorithm finds all the places that the pattern matches the text with at most k mismatches. The algorithm is deterministic and runs in Θ(nm1/3k1/3log2/3m) time.     

Partitioning and searching dictionary for correction of optically read Devanagari character strings

Abstract. This paper describes a method for the correction of optically read Devanagari character strings using a Hindi word dictionary. The word dictionary is partitioned in order to reduce the search space besides preventing forced matching to an incorrect word. The dictionary partitioning strategy takes into account the underlying OCR process. The dictionary words at the top level have been divided into two partitions, namely: a short-words partition and the remaining words partition. The short-word partition is sub-partitioned using the envelope information of the words. The envelope consists of the number of top, lower, core modifiers along with the number of core charactersp. Devanagari characters are written in three strips. Most of the characters referred to as core characters are written in the middle strip. The remaining words are further partitioned using tags. A tag is a string of fixed length associated with each partition. The correction process uses a distance matrix for a assigning penalty for a mismatch. The distance matrix is based on the information about errors that the classification process is known to make and the confidence figure that the classification process associates with its output. An improvement of approximately 20% in recognition performance is obtained. For a short word, 590 words are searched on average from 14 sub-partitions of the short-words partition before an exact match is found. The average number of partitions and the average number of words increase to 20 and 1585, respectively, when an exact match is not found. For tag-based partitions, on an average, 100 words from 30 partitions are compared when either an exact match is found or a word within the preset threshold distance is found. If an exact match or a match within a preset threshold is not found, the average number of partitions becomes 75 and 450 words on an average are compared. To the best of our knowledge this is the first work on the use of a Hindi word dictionary for OCR post-processing. Received August 6, 2001 / Accepted August 22, 2001     

一种基于listwise的在线学习书目排序检索算法

高效检索是数字图书馆的核心业务之一,其中排序是高效信息检索的核心问题。给定一系列的书目列表,利用排序模型生成目标书目的排序列表。将学习排序算法应用于信息检索领域时,常用方法是通过最小化pairwise损失函数值来优化排序模型。然而,已有结论表明,pairwise损失值最小化不一定能得到listwise算法的最佳排序性能。并且将在线学习排序算法与listwise算法相结合也非常困难。提出了一种基于listwise的在线学习排序算法,旨在保证listwise算法性能优势的前提下,实现在线学习排序算法,从而降低检索复杂度。首先解决将在线学习排序算法与listwise算法相结合的问题;然后通过最小化基于预测列表和真实列表定义的损失函数来优化排序模型;最后提出基于online-listwise算法的自适应学习率。实验结果表明,所提出算法具有较好的检索性能和检索速度。     

Spike sorting based on radial basis function network with overlap decomposition

Spike sorting is the essential step in analyzing recording spike signals for studying information processing mechanisms within the nervous system. Overlapping is one of the most serious problems in the spike sorting for multi-channel recordings. In this paper, a modified radial basis function (RBF) network is proposed to decompose the overlapping signals and separate spikes within the same RBF network. A modified radial basis function based on the Gaussian function is employed in the method to improve the accuracy of overlap decomposition. In addition, the improved constructing algorithm reduces the calculation cost by taking advantage of the symmetry of the RBF network. The performance of the presented method is tested at various signal-to-noise ratio levels based on simulated data coming from the University of Leicester and Wave-clus software. Experiment results show that our method successfully solves the fully overlapping problem and has higher accuracy comparing with the Gaussian function.