A new efficient algorithm for polynomial interpolation

A new backward stable algorithm (Algorithm 2) for polynomial interpolation based on the Lagrange and the Newton interpolation forms is proposed. It is shown that the Aitken algorithm and the scheme of the divided differences can be significantly less accurate than the proposed unconditionally stable Algorithm 2. Numerical examples that illustrate the advantage of a new algorithm are also given.     

The indexing for one-dimensional proportionally-scaled strings

Related problems of scaled matching and indexing, which aim to determine all positions in a text T that a pattern P occurs in its scaled form, are considered important because of their applications to computer vision. However, previous results only focus on enlarged patterns, and do not allow shrunk patterns since they may disappear. In this paper, we give the definition and an efficient indexing algorithm for proportionally-scaled patterns that can be visually enlarged or shrunk. The proposed indexing algorithm takes O(|T|) time in its preprocessing phase, and achieves time in its answering phase, where |T|, |P|, Up, and m denote the length of T, the length of P, the number of reported positions, and the length of T under run-length representation, respectively.     

An efficient algorithm for matching multiple patterns

An efficient algorithm for performing multiple pattern match in a string is described. The match algorithm combines the concept of deterministic finite state automata (DFSA) and the Boyer-Moore algorithm to achieve better performance. Experimental results indicate that in the average case, the algorithm is able to perform pattern match operations sublinearly, i.e. it does not need to inspect every character of the string to perform pattern match operations. The analysis shows that the number of characters to be inspected decreases as the length of patterns increases, and increases slightly as the total number of patterns increases. To match an eight-character pattern in an English string using the algorithm, only about 17% of all characters of the strong and 33% of all characters of the string, when the number of patterns is seven, are inspected. In an actual testing, the algorithm running on SUN 3/160 takes only 3.7 s to search seven eight-character patterns in a 1.4-Mbyte English text file     

Efficient indexing algorithms for one-dimensional discretely-scaled strings

The discretely-scaled string indexing problem asks one to preprocess a given text string T, so that for a queried pattern P, the matched positions in T that P appears with some discrete scale can be reported efficiently. For solving this problem, Wang et al. first show that with an O(|T|log|T|)-time preprocessing on T, all matched positions can be reported in O(|P|+Ud) time, where |T|, |P|, and Ud denote the length of T, the length of P, and the number of matched positions for discretely-scaled P in T, respectively. In this paper, for fixed alphabets we propose the first-known optimal indexing algorithm that takes O(|T|) and O(|P|+Ud) time in its preprocessing and query phases, respectively. For integer and unbounded alphabets, our new algorithm can also be extended to obtain the best-known results.     

一种新的多层频繁模式挖掘算法

在多层频繁模式挖掘时,结合映射和并发技术,改进经典的FP-growth算法,提出了多层映射频繁模式增长算法(ML-MFP_Growth).首先对事务数据库中的项目编码预处理,随后对编码数据库的每一列进行映射,构造各层映射频繁模式树(MFP-Tree),最后并发挖掘各层MFP-Tree,得到所有频繁模式.实验表明,ML_MFP_Growth算法比传统多层频繁模式挖掘算法性能有所提高.     

A generic and efficient framework for flash-aware spatial indexing

Spatial indexing on flash-based Solid State Drives (SSDs) has become a core aspect in spatial database applications, and has been carried out by flash-aware spatial indices. Although there are some flash-aware spatial indices proposed in the literature, they do not exploit all the benefits of SSDs, leading to loss of efficiency and durability. In this article, we propose eFIND, a new generic and efficient framework for flash-aware spatial indexing. eFIND takes into account the intrinsic characteristics of SSDs by employing (i) a write buffer to avoid expensive random writes, (ii) a flushing algorithm that smartly picks modifications to be flushed in batch to the SSD, (iii) a read buffer to decrease the overhead of random reads, (iv) a temporal control to avoid interleaved reads and writes, and (v) a log-structured approach to provide data durability. Performance tests showed the efficiency of eFIND. Compared to the state of the art, eFIND improved the construction of spatial indices from 43% to 77%, and the spatial query processing from 4% to 23%.     

An efficient algorithm for mining top-rank-k frequent patterns

Mining top-rank-k frequent patterns is a popular data mining task, which consists of discovering the patterns in a transaction database that belong to the k first ranks in terms of support. Although, several algorithms have been proposed for this task, it remains computationally expensive. To address this issue, this paper proposes a novel algorithm named BTK. It relies on a novel tree structure named TB-tree to store crucial information about frequent patterns. Moreover, BTK employs a new B-list structure to store information about patterns, and relies on subsume indexes to reduce the search space and speed up the discovery of top-rank-k frequent patterns. BTK also uses an early pruning strategy and an effective threshold raising mechanism. Additionally, BTK introduces two efficient procedures for respectively generating subsume indexes and intersecting B-lists. Extensive experiments were conducted on several datasets to evaluate the efficiency of the proposed algorithm. Results show that BTK is highly efficient and competitive.     

Analysis of a new algorithm for one-dimensional minimization

Davidon has recently introduced a new approach to optimization using the idea of nonlinear scaling. In this paper we study the algorithm that results when applying his ideas to the one-dimensional case. We show that the algorithm is locally convergent withQ-order equal 2 and compare it with the method of cubic interpolation.     

An efficient algorithm for mining frequent inter-transaction patterns

In this paper, we propose an efficient method for mining all frequent inter-transaction patterns. The method consists of two phases. First, we devise two data structures: a dat-list, which stores the item information used to find frequent inter-transaction patterns; and an ITP-tree, which stores the discovered frequent inter-transaction patterns. In the second phase, we apply an algorithm, called ITP-Miner (Inter-Transaction Patterns Miner), to mine all frequent inter-transaction patterns. By using the ITP-tree, the algorithm requires only one database scan and can localize joining, pruning, and support counting to a small number of dat-lists. The experiment results show that the ITP-Miner algorithm outperforms the FITI (First Intra Then Inter) algorithm by one order of magnitude.     

Color indexing for efficient image retrieval

Content based image retrieval is an active area of research. Many approaches have been proposed to retrieve images based on matching of some features derived from the image content. Color is an important feature of image content. The problem with many traditional matching-based retrieval methods is that the search time for retrieving similar images for a given query image increases linearly with the size of the image database. We present an efficient color indexing scheme for similarity-based retrieval which has a search time that increases logarithmically with the database size.In our approach, the color features are extracted automatically using a color clustering algorithm. Then the cluster centroids are used as representatives of the images in 3-dimensional color space and are indexed using a spatial indexing method that usesR-tree. The worst case search time complexity of this approach isOn _q log(N^* n_avg)), whereN is the number of images in the database, andn _q andn _avg are the number of colors in the query image and the average number of colors per image in the database respectively. We present the experimental results for the proposed approach on two databases consisting of 337 Trademark images and 200 Flag images.     

A fast pivot-based indexing algorithm for metric spaces

This work focus on fast nearest neighbor (NN) search algorithms that can work in any metric space (not just the Euclidean distance) and where the distance computation is very time consuming. One of the most well known methods in this field is the AESA algorithm, used as baseline for performance measurement for over twenty years. The AESA works in two steps that repeats: first it searches a promising candidate to NN and computes its distance (approximation step), next it eliminates all the unsuitable NN candidates in view of the new information acquired in the previous calculation (elimination step).This work introduces the PiAESA algorithm. This algorithm improves the performance of the AESA algorithm by splitting the approximation criterion: on the first iterations, when there is not enough information to find good NN candidates, it uses a list of pivots (objects in the database) to obtain a cheap approximation of the distance function. Once a good approximation is obtained it switches to the AESA usual behavior. As the pivot list is built in preprocessing time, the run time of PiAESA is almost the same than the AESA one.In this work, we report experiments comparing with some competing methods. Our empirical results show that this new approach obtains a significant reduction of distance computations with no execution time penalty.     

An efficient algorithm for mining periodic high-utility sequential patterns

A periodic high-utility sequential pattern (PHUSP) is a pattern that not only yields a high-utility (e.g. high profit) but also appears regularly in a sequence database. Finding PHUSPs is useful for several applications such as market basket analysis, where it can reveal recurring and profitable customer behavior. Although discovering PHUSPs is desirable, it is computationally difficult. To discover PHUSPs efficiently, this paper proposes a structure for periodic high-utility sequential pattern mining (PHUSPM) named PUSP. Furthermore, to reduce the search space and speed up PHUSPM, a pruning strategy is developed. This results in an efficient algorithm called periodic high-utility sequential pattern optimal miner (PUSOM). An experimental evaluation was performed on both synthetic and real-life datasets to compare the performance of PUSOM with state-of-the-art PHUSPM algorithms in terms of execution time, memory usage and scalability. Experimental results show that the PUSOM algorithm can efficiently discover the complete set of PHUSPs. Moreover, it outperforms the other four algorithms as the former can prune many unpromising patterns using its designed structure and pruning strategy.     

A generic algorithm for one-dimensional homotopic compaction

One-dimensional homotopic compaction problems model the task of VLSI layout compaction with automatic jog insertion. They have the following form: given a routable layout, find a layout of minimum width reachable by a continuous motion of layout components that displaces each rigid component horizontally and preserves routability. We define a configuration space for this problem, and prove that if routability is characterized bycut conditions, then the set of reachable configurations is a closed, convex polyhedron. We also present a polynomial-time algorithm that finds the constraints defining this polyhedron and solves them to produce an optimal configuration. A homotopic router can recover the compacted layout from this configuration. We illustrate our strategy in thesketch model of VLSI layout, where it yields a compaction algorithm with worst-case running timeO(N ⁴) on input of sizeN.     

A generic algorithm for one-dimensional homotopic compaction

One-dimensional homotopic compaction problems model the task of VLSI layout compaction with automatic jog insertion. They have the following form: given a routable layout, find a layout of minimum width reachable by a continuous motion of layout components that displaces each rigid component horizontally and preserves routability. We define a configuration space for this problem, and prove that if routability is characterized bycut conditions, then the set of reachable configurations is a closed, convex polyhedron. We also present a polynomial-time algorithm that finds the constraints defining this polyhedron and solves them to produce an optimal configuration. A homotopic router can recover the compacted layout from this configuration. We illustrate our strategy in thesketch model of VLSI layout, where it yields a compaction algorithm with worst-case running timeO(N ⁴) on input of sizeN.This paper is based on a thesis submitted in May of 1986 in partial fulfillment of the requirements for the degree of Master of Science in the Department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. The work described herein was supported in part by a Graduate Fellowship from the Office of Naval Research, in part by the Defense Advanced Research Projects Agency under Contract N00014-80-C-0622, and in part by a Mathematical Sciences Postdoctoral Research Fellowship from the National Science Foundation, Grant DMS-8705835.     

A nonmonotone scaled conjugate gradient algorithm for large-scale unconstrained optimization

This paper proposes a nonmonotone scaled conjugate gradient algorithm for solving large-scale unconstrained optimization problems, which combines the idea of scaled memoryless Broyden–Fletcher–Goldfarb–Shanno preconditioned conjugate gradient method with the nonmonotone technique. An attractive property of the proposed method is that the search direction always provides sufficient descent step at each iteration. This property is independent of the line search used. Under appropriate assumptions, the method is proven to possess global convergence for nonconvex smooth functions, and R-linear convergence for strongly convex functions. Preliminary numerical results and related comparisons show the efficiency of the proposed method in practical computation.     

A new real time disk-scheduling method based on GSR algorithm

Disk scheduling has an important role in QOS guarantee of soft real-time environments such as video-on-demand and multimedia servers. Since now, some disk-scheduling algorithms have been proposed to schedule real-time disk requests. One of the most recent algorithms is global seek-optimizing real-time (GSR) that schedules the disk requests with different ready times by a global regrouping scheme. In the present paper, we propose a real-time disk-scheduling algorithm based on GSR that is called IGSR (improved GSR). IGSR creates the scan-groups of the requests and tries to find a good feasible schedule by optimized grouping with considering another chance for tasks that miss their deadlines at initial grouping. With regard to the admission policy of tasks, two different version of proposed method are presented: the first one has been designed for the case that all the disk requests available simultaneously and second one has been designed for the case that requests are admitted dynamically (GSR does not support the second one). It means that in the second case, the request queue may change when a task is running but in the first one it does not change. Simulation results showed IGSR outperformed GSR and some other related works in terms of maximum supportable streams, number of missed deadlines, and disk throughput.     

eXploratory K-Means: A new simple and efficient algorithm for gene clustering

In this paper, a novel gene expression clustering method known as eXploratory K-Means (XK-Means) is proposed. The method is based on the integration of the K-Means framework, and an exploratory mechanism to prevent premature convergence of the clustering process. Experimental results reveal that the performance of XK-Means in grouping gene expressions, measured in terms of speed, error and stability, is superior to existing methods that are based on evolutionary algorithm. In addition, the complexity of the proposed method is lower and the method can be easily implemented in practice.     

A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space

We present here a new and efficient algorithm for planning collision-free motion of a line segment (a rod or a ladder) in two-dimensional space amidst polygonal obstacles. The algorithm uses a different approach than those used in previous motion-planning techniques, namely, it calculates the boundary of the (three-dimensional) space of free positions of the ladder, and then uses this boundary for determining the existence of required motions, and plans such motions whenever possible. The algorithm runs in timeO(K logn) =O(n ² logn) wheren is the number of obstacle corners and whereK is the total number of pairs of obstacle walls or corners of distance less than or equal to the length of the ladder. The algorithm has thus the same complexity as the best previously known algorithm of Leven and Sharir [5], but if the obstacles are not too cluttered together it will run much more efficiently. The algorithm also serves as an initial demonstration of the viability of the technique it uses, which we expect to be useful in obtaining efficient motion-planning algorithms for other more complex robot systems.Work on this paper has been supported in part by a grant from the Joint Ramot-Israeli Ministry of Industry Foundation.