A new algorithm for generating hilbert curves

A new algorithm is described which generates the co-ordinates of the tth point along a Hilbert curve, given the value of the parameter t. The algorithm is expressed in the concurrent programming language occam.     

A New Method for Generating Conic Sections

This paper presents a difference method for computing vertices of the polygon inscribed in a conic section.It can be applied to computer graphic package or to plotter to generate conic sections.This metho is simpler and more efficient than traditional ones,and its form remains invariant under homogeneous affine transformations.The stability of the metho and its relationship with its matrix counterpart are also discussed.     

A new algorithm for shortest paths among obstacles in the plane

We introduce a new algorithm for computing Euclidean shortest paths in the plane in the presence of polygonal obstacles. In particular, for a given start points, we build a planar subdivision (ashortest path map) that supports efficient queries for shortest paths froms to any destination pointt. The worst-case time complexity of our algorithm isO(kn log² n), wheren is the number of vertices describing the polygonal obstacles, andk is a parameter we call the illumination depth of the obstacle space. Our algorithm usesO(n) space, avoiding the possibly quadratic space complexity of methods that rely on visibility graphs. The quantityk is frequently significantly smaller thann, especially in some of the cases in which the visibility graph has quadratic size. In particular,k is bounded above by the number of different obstacles that touch any shortest path froms.Partially supported by NSF Grants IRI-8710858 and ECSE-8857642 and by a grant from Hughes Research Laboratories, Malibu, CA.     

The symbolic OBDD scheme for generating mechanical assembly sequences

Assembly sequence planning is one of typical combinatorial optimization problems, where the size of parts involved is a significant and often prohibitive difficulty. The compact storage and efficient evaluation of feasible assembly sequences is one crucial concern. Ordered binary decision diagram (OBDD) is a canonical form to represent and manipulate the Boolean functions efficiently, and appears to give improved results for large-scale combinatorial optimization problems. In this paper, assembly knowledge models of liaison graph and translation function are formulated by OBDDs, and OBDD-based representation of assembly sequences is proposed. A novel OBDD-based procedure was presented to generate all geometrically feasible assembly sequences from the OBDDs of liaison graph and translation relation. This procedure can be used conveniently on the computer and all the feasible sequences can be derived. The great advantage of OBDD-based scheme is that the storage space of OBDD-based representation of feasible assembly sequences does not increase with the part count of assembly dramatically so quickly as that of AND/OR graph does. We developed the prototype tool for generating assembly sequence using Visual C++ and CUDD package, and undertake some experimental tests. It was shown that the OBDD scheme generated feasible assembly sequences correctly and completely.     

An efficient implementation algorithm for generating de Bruijn sequences

A nonsingular feedback shift register will generate pairwise disconnecting cycles. To get a de Bruijn cycle, we put a different mark on the states that are on the different cycle. This could help us find adjacent cycles easily and join them together. We modify the marks of the states that on the joined cycles to the same mark. At the same time, the feedback function is modified accordingly. Then a full cycle is obtained when the marks of all the states on different cycles are modified to the same mark. At the same time, the feedback function that could generate the de Bruijn sequences is also obtained.     

生成de Bruijn序列的加元算法

提出一种加元算法,通过对给定的一个m+1元的de Buijn序列添加一元来产生m+2元de Bruijn序列。实现的方法是通过由一个m+1元de Bruijn序列找出它的Look-up表标签,并由该Look-up表标签产生多个m+1元Look-up表标签,然后合成这些Look-up表标签产生一个m+2元Look-up表标签,再由它产生m+2元de Bruijn序列。     

改进的混沌序列产生方法

为了得到具有良好随机性的二值序列,在已有方法的基础上,介绍了一种改进的混沌二值序列产生方法,该方法以混沌动力学模型为基础,利用非线性的方法产生混沌二值序列,实验表明产生的二值序列具有较好的随机性和初值敏感性,同时通过非线性的比较过程提高了算法的安全性.作为应用,还给出了该二值序列在图像加密中的应用.实验表明,该方法具有较好的效率和安全性.     

A new fusion strategy for web metasearch

In this paper, we present two new list fusion strategies for the collection fusion problem in web metasearch. The new approaches fall in the category of isolated methods since they consider as input the lists obtained by different search engines only, plus a fuzzy degree of relevance in one of the methods. In the latter case, we employ a recently proposed approach for the representation of fuzzy preferences, namely, RL-preference relations. A remarkable contribution of the approaches is that the result of the fusion is an ordered list of indistinguishable groups of documents. This kind of output represents a good compromise between understandability and accuracy of the result. We have illustrated the performance of the method by means of several experiments and a comparison with other web metasearchers.     

A new control strategy for IKN-type coolers

This paper presents a new system for the optimized control of IKN-type cement coolers based on adaptive predictive methodology. The new system introduces the concepts of ’layer on grate’ and ’thickness of slope’, which allow a decoupled multivariable control of the layer of clinker over the grate, and the flow rate of the cooler fans, solving a fundamental control problem for this type of process and maximizing the heat transfer from the cooling process to the kiln. The experimental results obtained in the Gador mill of Holcim, in Almeria (Spain), are analyzed.     

Efficient processing of shortest path queries in evolving graph sequences

In many applications, information is best represented as graphs. In a dynamic world, information changes and so the graphs representing the information evolve with time. We propose that historical graph-structured data be maintained for analytical processing. We call a historical evolving graph sequence an EGS. We observe that in many applications, graphs of an EGS are large and numerous, and they often exhibit much redundancy among them. We study the problem of efficient shortest path query processing on an EGS and put forward a solution framework called FVF. Two algorithms, namely, FVF-F and FVF-H, are proposed. While the FVF-F algorithm works on a sequence of flat graph clusters, the FVF-H algorithm works on a hierarchy of such clusters. Through extensive experiments on both real and synthetic datasets, we show that our FVF framework is highly efficient in shortest query processing on EGSs. Comparing FVF-F and FVF-H, the latter gives a larger speedup, is more flexible in terms of memory requirements, and is far less sensitive to parameter values.     

A novel randomized iterative strategy for aligning multiple protein sequences.

The rigorous alignment of multiple protein sequences becomes impractical even with a modest number of sequences, since computer memory and time requirements increase as the product of the lengths of the sequences. We have devised a strategy to approach such an optimal alignment, which modifies the intensive computer storage and time requirements of dynamic programming. Our algorithm randomly divides a group of unaligned sequences into two subgroups, between which an optimal alignment is then obtained by a Needleman-Wunsch style of algorithm. Our algorithm uses a matrix with dimensions corresponding to the lengths of the two aligned sequence subgroups. The pairwise alignment process is repeated using different random divisions of the whole group into two subgroups. Compared with the rigorous approach of solving the n-dimensional lattice by dynamic programming, our iterative algorithm results in alignments that match or are close to the optimal solution, on a limited set of test problems. We have implemented this algorithm in a computer program that runs on the IBM PC class of machines, together with a user-friendly environment for interactively selecting sequences or groups of sequences to be aligned either simultaneously or progressively.     

de Bruijn序列间的映射及升级算法

通过由n级de Bruijn序列找出n+1级de Bruijn序列的look-up表标签,并由相应的look-up表求出n+1级de Bruijn序列,从而建立起n级de Bruijn序列到n+1级de Bruijn序列的映射,发现de Bruijn序列间的一种内在联系,导出一类任意元de Bruijn序列的升级算法。     

de Bruijn序列间的映射及降级算法

通过由一个n级de Bruijn序列找出它的LOOK-UP表标签,并由该LOOK-UP表标签经修正找出n-1级LOOK-UP表标签,再由它计算出n-1级de Bruijn序列,从而建立起n级de Bruijn序列到n-1级de Bruijn序列的映射,发现de Bruijn序列间的一种内在联系,导出一类任意元de Bruijn序列的降级算法。     

A new approach for generating efficient sample from market basket data

Classical data mining algorithms require expensive passes over the entire database to generate frequent items and hence to generate association rules. With the increase in the size of database, it is becoming very difficult to handle large amount of data for computation. One of the solutions to this problem is to generate sample from the database that acts as representative of the entire database for finding association rules in such a way that the distance of the sample from the complete database is minimal. Choosing correct sample that could represent data is not an easy task. Many algorithms have been proposed in the past. Some of them are computationally fast while others give better accuracy. In this paper, we present an algorithm for generating a sample from the database that can replace the entire database for generating association rules and is aimed at keeping a balance between accuracy and speed. The algorithm that is proposed takes into account the average number of small, medium and large 1-itemset in the database and average weight of the transactions to define threshold condition for the transactions. Set of transactions that satisfy the threshold condition is chosen as the representative for the entire database. The effectiveness of the proposed algorithm has been tested over several runs of database generated by IBM synthetic data generator. A vivid comparative performance evaluation of the proposed technique with the existing sampling techniques for comparing the accuracy and speed has also been carried out.     

Studies on the distribution of the shortest linear recurring sequences

The distribution of the shortest linear recurrence (SLR) sequences in the Z/(p) field and over the Z/(p^e) ring is studied. It is found that the length of the shortest linear recurrent (SLRL) is always equal to n/2, if n is even and n/2 + 1 if n is odd in the Z/(p) field, respectively. On the other hand, over the Z/(p^e) ring, the number of sequences with length n can also be calculated. The recurring distribution regulation of the shortest linear recurring sequences is also found. To solve the problem of calculating the SLRL, a new simple representation of the Berlekamp-Massey algorithm is developed as well.