Some Notes on Generalized Cyclotomic Sequences of Length pq

We review the constructions of two main kinds of generalized cyclotomic binary sequences with length pq (the product with two distinct primes). One is the White-generalized cyclotomic sequences, the other is the Ding-Helleseth(DH, for short)-generalized cyclotomic sequences. We present some new pseudo-random properties of DH-generalized cyclotomic sequences using the theory of character sums instead of the theory of cyclotomy, which is a conventional method for investigating generalized cyclotomic sequences.     

Composite Distance Transformation for Indexing and k-Nearest-Neighbor Searching in High-Dimensional Spaces

Due to the famous dimensionality curse problem, search in a high-dimensional space is considered as a ＂hard＂ problem. In this paper, a novel composite distance transformation method, which is called CDT, is proposed to support a fast κ-nearest-neighbor （κ-NN） search in high-dimensional spaces. In CDT, all （n） data points are first grouped into some clusters by a κ-Means clustering algorithm. Then a composite distance key of each data point is computed. Finally, these index keys of such n data points are inserted by a partition-based B^＋-tree. Thus, given a query point, its κ-NN search in high-dimensional spaces is transformed into the search in the single dimensional space with the aid of CDT index. Extensive performance studies are conducted to evaluate the effectiveness and efficiency of the proposed scheme. Our results show that this method outperforms the state-of-the-art high-dimensional search techniques, such as the X-Tree, VA-file, iDistance and NB-Tree.     

Continually Answering Constraint <Emphasis Type="Italic">k</Emphasis>-<Emphasis Type="Italic">NN</Emphasis> Queries in Unstructured P2P Systems

We consider the problem of efficiently computing distributed geographical k-NN queries in an unstructured peer-to-peer （P2P） system, in which each peer is managed by an individual organization and can only communicate with its logical neighboring peers. Such queries are based on local filter query statistics, and require as less communication cost as possible which makes it more difficult than the existing distributed k-NN queries. Especially, we hope to reduce candidate peers and degrade communication cost. In this paper, we propose an efficient pruning technique to minimize the number of candidate peers to be processed to answer the k-NN queries. Our approach is especially suitable for continuous k-NN queries when updating peers, including changing ranges of peers, dynamically leaving or joining peers, and updating data in a peer. In addition, simulation results show that the proposed approach outperforms the existing Minimum Bounding Rectangle （MBR）-based query approaches, especially for continuous queries.     

Linear complexity and autocorrelation values of a polyphase generalized cyclotomic sequence of length pq

A construction of a family of generalized polyphase cyclotomic sequences of length pq is presented in terms of the generalized cyclotomic classes modulo pq. Their linear complexity and corresponding minimal polynomials are deduced. Some upper bounds on periodic and aperiodic autocorrelation values of resulting sequences are also estimated by using certain exponential sums.     

Edge-Oriented Spatial Interpolation for Error Concealment of Consecutive Blocks

This paper proposes a low-complexity spatial-domain error concealment （EC） algorithm for recovering consecutive blocks error in still images or intra-coded （I） frames of video sequences. The proposed algorithm works with the following steps. Firstly the Sobel operator is performed on the top and bottom adjacent pixels to detect the most probable edge direction of current block area. After that one-dimensional （1-D） matching is used on the available block boundaries. Displacement between edge direction candidate and most probable edge direction is taken into consideration as an important factor to improve stability of 1-D boundary matching. Then the corrupted pixels are recovered by linear weighting interpolation along the estimated edge direction. Finally the interpolated values are merged to get last recovered picture. Simulation results demonstrate that the proposed algorithms obtain good subjective quality and higher PSNR than the methods in literatures for most images.     

Sequences related to Legendre/Jacobi sequences

Two families of binary sequences are constructed from dth order cyclotomic generator and from dth order generalized cyclotomic generator with respect to two distinct primes respectively. By using estimates of certain exponential sums over rings or fields, the upper bounds of both the well-distribution measure and the order k (at least for small k) correlation measure of the resulting binary sequences are evaluated, and some lower bounds on the linear complexity profile of d-ary cyclotomic sequences and d-ary generalized cyclotomic sequences are presented. Our results indicate that such binary sequences possess “very good” local pseudo-randomness.     

Multi-Dimensional Scheduling for Real-Time Tasks on Heterogeneous Clusters

Multiple performance requirements need to be guaranteed in some real-time applications such as multimedia data processing and real-time signal processing in addition to timing constraints.Unfortunately,most conventional scheduling algorithms only take one or two dimensions of them into account.Motivated by this fact,this paper investigates the problem of providing multiple performance guarantees including timeliness,QoS,throughput,QoS fairness and load balancing for a set of independent tasks by dynamic ...     

Predicting RNA Secondary Structure Using Profile Stochastic Context-Free Grammars and Phylogenic Analysis

Stochastic context-free grammars （SCFGs） have been applied to predicting RNA secondary structure. The prediction of RNA secondary structure can be facilitated by incorporating with comparative sequence analysis. However, most of existing SCFG-based methods lack explicit phylogenic analysis of homologous RNA sequences, which is probably the reason why these methods are not ideal in practical application. Hence, we present a new SCFG-based method by integrating phylogenic analysis with the newly defined profile SCFG. The method can be summarized as： 1） we define a new profile SCFG, M, to depict consensus secondary structure of multiple RNA sequence alignment; 2） we introduce two distinct hidden Markov models, λ and λ＇, to perform phylogenic analysis of homologous RNA sequences. Here, λ＇ is for non-structural regions of the sequence and λ＇ is for structural regions of the sequence; 3） we merge λ and λ＇ into M to devise a combined model for prediction of RNA secondary structure. We tested our method on data sets constructed from the Rfam database. The sensitivity and specificity of our method are more accurate than those of the predictions by Pfold.     

Symbolic Algorithmic Analysis of Rectangular Hybrid Systems

This paper investigates symbolic algorithmic analysis of rectangular hybrid systems.To deal with the symbolic reachability problem,a restricted constraint system called hybrid zone is formalized for the representation and manipulation of rectangular automata state-spaces.Hybrid zones are proved to be closed over symbolic reachability operations of rectangular hybrid systems.They are also applied to model-checking procedures for verifying some important classes of timed computation tree logic formulas.To ...     

Parallel Algorithm Core: A Novel IPSec Algorithm Engine for Both Exploiting Parallelism and Improving Scalability

To deal with the challenges of both computation-complexity and algorithm-scalability posed to the design of an IPSec engine, we develop PAC （parallel algorithm core）, called PAC, employed in an IPSec engine, which can meet requirements of both exploiting parallelism existing in IPSec packets and offering scalability in both the scales and types of cryptographic algorithms. With three kinds of parallelism and two kinds of transparency defined, a novel hierarchy of the specifically-designed parallel structure for PAC is presented, followed by corresponding mechanisms. With a simulation, the scalability of PAC is examined. For the purpose of performance evaluation, a Quasi Birth-and-Death （QBD） process is then established to model a simplified version of the proposed PAC. Performance evaluation of PAC in terms of two representative measures, throughput and mean packet waiting time, is numerically investigated. A comparison study is done on a simulation basis. Conclusions are finally drawn for providing a helpful guideline for both the design and implementation of our proposal.     

On the linear span of the p -ary cascaded GMW sequences

In this paper, a recursion is derived to compute the linear span of the p-ary cascaded GMW sequences. It is the first time to determine the linear span of the p-ary cascaded GMW sequence without any restriction on the parameters completely. Whereas, the known result on the p-ary cascaded GMW sequence with the specific parameters in the literature could be viewed as a special case of the new result. Supported by the National Natural Science Foundation of China (Grant No. 60302015), the Foundation for the Author of National Excellent Doctoral Dissertation of China (Grant No. 200341), and Sichuan Youth Science Foundation (Grant No. 04ZQ026-048)     

Autocorrelation Values of New Generalized Cyclotomic Sequences of Order Two and Length pq

Pseudo-random sequences are used extensively for their high speed and security level and less errors. As a branch, the cyclotomic sequences and the generalized ones are studied widely because of their simple mathematical structures and excellent pseudo-random properties. In 1998, Ding and Helleseth introduced a new generalized cyclotomy which includes the classical cyclotomy as a special case. In this paper, based on the generalized cyclotomy, new generalized cyclotomic sequences with order two and length pq are constructed. An equivalent definition of the sequences is deduced so that the autocorrelation values of these sequences can be determined conveniently. The construction contributes to the understanding of the periodic autocorrelation structure of cyclotomically-constructed binary sequences, and the autocorrelation function takes on only a few values.     

The linear complexity of new generalized cyclotomic binary sequences of order four

Whiteman generalized cyclotomic sequences are proven to exhibit a number of good randomness properties. In this paper we determine the linear complexity of some newly generalized cyclotomic sequences, of order four with period pq which are defined by Ding and Helleseth. The results show that all of these sequences have high linear complexity.     

Trace representation of some generalized cyclotomic sequences of length pq

This paper contributes to trace representation of some generalized cyclotomic sequences of length which are defined by Ding and Helleseth. From the relations between these sequences and the Legendre sequence, we firstly confirm the defining pairs of these sequences of arbitrary order. Then, we obtain their trace representation, from which we give their linear complexity using Key’s method. It can be seen that Bai et al.’s conclusion is a special case of our result when the order is two. Finally, an example is given to illustrate the validity of our result.     

Non-ambiguity of blind watermarking: a revisit with analytical resolution

Resistance to ambiguity attack is an important requirement for a secure digital rights management (DRM) system. In this paper,we revisit the non-ambiguity of a blind watermarking based on the compu-tational indistinguishability between pseudo random sequence generator (PRSG) sequence ensemble and truly random sequence ensemble. Ambiguity attacker on a watermarking scheme,which uses a PRSG sequence as watermark,is viewed as an attacker who tries to attack a noisy PRSG sequence. We propose and prove the security theorem for binary noisy PRSG sequence and security theorem for gen-eral noisy PRSG sequence. It is shown that with the proper choice of the detection threshold Th = an1/2 (a is a normalized detection threshold; n is the length of a PRSG sequence) and n 1.39×m/a2 (m is the key length),the success probability of an ambiguity attack and the missed detection probability can both be made negligibly small thus non-ambiguity and robustness can be achieved simultaneously for both practical quantization-based and blind spread spectrum (SS) watermarking schemes. These analytical resolutions may be used in designing practical non-invertible watermarking schemes and measuring the non-ambiguity of the schemes.     

大线性复杂度三值自相关的二元三阶分圆序列的构造

对于一类周期为素数p,p≡1(mod 3)的二元三阶分圆序列提出了一种构造方法,确保其少自相关值及大线性复杂度。利用分圆的知识计算其自相关值,并进一步考虑序列的自相关值为三值时,素数p应满足的条件。此时p应满足p=a²+12,a为整数。当p满足此形式时,序列的线性复杂度为p-1,否则为2(p-1)/3。通过计算机实验,找出了满足所给形式的p,并能生成对应的序列集,验证了序列的自相关性及线性复杂度。新序列的线性复杂度和已有的三元三阶分圆序列的相同;和二元偶数阶分圆序列的相比,大部分相同或较优(已有的有些情况为(p-1)/2、(p+1)/2或1+(p-1)/6)。所提出的构造方法可推广至其他少自相关值、大线性复杂度的奇数阶分圆序列集的构造上。大奇数阶分圆序列的平衡性也会提高,能被较好地应用于密码与通信系统中。     

阶数为2的pq周期广义割圆序列的自相关值

给出了关于阶数为2的pq周期广义割圆序列自相关值的几个猜想,这类序列是由Ding和Helleseth构造的,大量的实验结果验证了猜想的正确性,但没有找到理论证明的方法。结果表明这类序列的自相关值为5-, 4-或3-值,序列具有“好”的自相关性质,而且这类序列也具有大的线性复杂度,可以作为流密码中的密钥流序列或作为随机数发生器。     

On the 2<Superscript>m</Superscript>-variable symmetric Boolean functions with maximum algebraic immunity

The properties of the 2m-variable symmetric Boolean functions with maximum al- gebraic immunity are studied in this paper. Their value vectors, algebraic normal forms, and algebraic degrees and weights are all obtained. At last, some necessary conditions for a symmetric Boolean function on even number variables to have maximum algebraic immunity are introduced.     

Adaptive Indexing of Moving Objects with Highly Variable Update Frequencies

In recent years, management of moving objects has emerged as an active topic of spatial access methods. Various data structures （indexes） have been proposed to handle queries of moving points, for example, the well-known B^x-tree uses a novel mapping mechanism to reduce the index update costs. However, almost all the existing indexes for predictive queries are not applicable in certain circumstances when the update frequencies of moving objects become highly variable and when the system needs to balance the performance of updates and queries. In this paper, we introduce two kinds of novel indexes, named B^y-tree and αB^y-tree. By associating a prediction life period with every moving object, the proposed indexes are applicable in the environments with highly variable update frequencies. In addition, the αB^y-tree can balance the performance of updates and queries depending on a balance parameter. Experimental results show that the B^y-tree and αB^y-tree outperform the B^x-tree in various conditions.     

Generating Combinations by Three Basic Operations

We investigate the problem of listing combinations using a special class of operations, prefix shifts. Combinations are represented as bitstrings of O＇s and l＇s, and prefix shifts are the operations of rotating some prefix of a bitstring by one position to left or right. We give a negative answer to an open problem asked by F. Ruskey and A. Williams （Generating combinations by prefix shifts, In Proc. llth Annual International Computing and Combinatorics Conference 2005, LNCS 3595, Springer, 2005, pp.570-576）, that is whether we can generate combinations by only using three very basic prefix shifts on bitstrings, which are transposition of the first two bits and the rotation of the entire bitstring by one position in either direction （i.e., applying the permutations σ2, σn and σn^-1 to the indices of the bitstrings）.