We introduce a complexity measure r for the class F of read-once formulas over the basis {AND,OR,NOT, XOR, MUX} and show that for any Boolean formula F in the class F, r(F) is a lower bound on the quantum query complexity of the Boolean function that F represents. We also show that for any Boolean function f represented by a formula in F, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f. Thus, the paper gives further evidence for the conjecture that there is an only quadratic gap for all functions.

Sensor networks have promising applications such as battlefield surveillance, biological detection, and emergency navigation, etc. Crucial problems in sensor networks are energy-efficiency and collision avoidance in wireless communication. To deal with the problems, we consider a self-stabilizing solution to the construction of k disjoint sense-sleep trees, where range adjustment and the use of GPS are allowed. Each root is determined by its identifier and is distinguished by its color, the identification of a tree. Using a dominating k-partition rule, each non-root node first determines a color irrelevant to the root. Then, the non-root node determines a parent node that is equally colored with minimal distance. If there is no appropriate parent, the range is extended or shrunk until the nearest parent is determined. Finally, we perform a simulation.

A graph is an interval graph if and only if each vertex in the graph can be associated with an interval on the real line such that any two vertices are adjacent in the graph exactly when the corresponding intervals have a nonempty intersection. A number of interesting applications for interval graphs have been found in the literature. In order to find structural features common to structural data which can be represented by intervals, this paper proposes new interval graph structured patterns, called linear interval graph patterns, and a polynomial time algorithm for finding a minimally generalized linear interval graph pattern explaining a given finite set of interval graphs.

Embedded zero-tree coding in wavelet domain has drawn a lot of attention for image compression applications. Among noteworthy zero-tree algorithms is the set partitioning in hierarchical trees (SPIHT) algorithm. For images with textures, high frequency wavelet coefficients are likely to become significant after a few scan passes of SPIHT, and therefore the coding results are often insufficient. It is desirable that the low frequency and high frequency components of an image are coded using different strategies. In this paper, we propose a hybrid algorithm using the SPIHT and EBC (embedded block coding) to code low frequency and high frequency wavelet coefficients, respectively; the intermediate coding results of low frequency coefficients are used to facilitate the coding operation of high frequency coefficients. Experimental results show that the coding performance can be significantly improved by the hybrid SPIHT-EBC algorithm.

Lin-Kernighan (LK) is the most powerful local search for the Traveling Salesman Problem (TSP). The choice of data structure for tour representation plays a vital role in LK's performance. Binary trees are asymptotically the best tour representation but they perform empirically best only for TSPs with one million or more cities due to a large overhead. Arrays and two-level trees are used for smaller TSPs. This paper proposes a new three-level tree data structure for tour representation. Although this structure is asymptotically not better than the binary tree structure, it performs empirically better than the conventional structures for TSPs having from a thousand to three million cities.

The support vector machines (SVMs) are one of the most effective classification techniques in several knowledge discovery and data mining applications. However, a SVM requires the user to set the form of its kernel function and parameters in the function, both of which directly affect to the performance of the classifier. This paper proposes a novel method, named a kernel-tree, the function of which is composed of multiple kernels in the form of a tree structure. The optimal kernel tree structure and its parameters is determined by genetic programming (GP). To perform a fine setting of kernel parameters, the gradient descent method is used. To evaluate the proposed method, benchmark datasets from UCI and dataset of text classification are applied. The result indicates that the method can find a better optimal solution than the grid search and the gradient search.

There is an increasing requirement for supporting complex multidimensional queries in Peer-to-Peer systems. In the centralized spatial database world, R-Trees and its variant structures are widely accepted due to their capabilities to manage complex multidimensional queries. In this paper, we propose a new multidimensional indexing structure for P2P systems, called Distributed Hilbert R-Trees (DHR-Trees), in which peers organize themselves into an overlay network, dynamically maintain routing tables with region information and collaboratively execute complex multidimensional queries, such as range query and k-nearest neighbors query, efficiently. DHR-Trees has similar topology to the P-Trees P2P system. The peers' routing tables are enhanced with spatial region information, which allow multidimensional query predicates to be adapted into P2P systems with minor modification. The structure design and two major multidimensional query algorithms are presented. Our experimental results demonstrate that it performs well on range queries and k-nearest neighbors queries with multidimensional data set.

Set Partitioning in Hierarchical Trees (SPIHT) is a highly efficient technique for compressing Discrete Wavelet Transform (DWT) decomposed images. Though its compression efficiency is a little less famous than Embedded Block Coding with Optimized Truncation (EBCOT) adopted by JPEG2000, SPIHT has a straight forward coding procedure and requires no tables. These make SPIHT a more appropriate algorithm for lower cost hardware implementation. In this paper, a modified SPIHT algorithm is presented. The modifications include a simplification of coefficient scanning process, a 1-D addressing method instead of the original 2-D arrangement of wavelet coefficients, and a fixed memory allocation for the data lists instead of a dynamic allocation approach required in the original SPIHT. Although the distortion is slightly increased, it facilitates an extremely fast throughput and easier hardware implementation. The VLSI implementation demonstrates that the proposed design can encode a CIF (352288) 4:2:0 image sequence with at least 30 frames per second at 100-MHz working frequency.

Rebuilding an index is an essential step for database recovery. Fast recovery of the index is a necessary condition for fast database recovery. The B+-Tree is the most popular index structure in database systems. In this paper, we present a fast B+-Tree rebuilding algorithm called Max-PL. The main idea of Max-PL is that at first it constructs a B+-Tree index structure using the pre-stored max keys of the leaf nodes, and then inserts the keys and data pointers into the index. The algorithm employs a pipelining mechanism for reading the data records and inserting the keys into the index. It also exploits parallelisms in several phases to boost the overall performance. We analyze the time complexity and space requirement of the algorithm, and perform the experimental study to compare its performance to other B+-Trees rebuilding algorithms; Sequential Insertion and Batch-Construction. The results show that our algorithm runs on average at least 670% faster than Sequential Insertion and 200% faster than Batch-Construction.

Constraint-based software specifications enable run-time monitoring to detect probable risk events and ensure the desired system behavior. SpecTRM-RL is a well-developed constraint-based specification method for computer-controlled systems. However, it is desirable to express constraints in familiar visual models. To provide better visualization and popularity, we developed methods to represent all the SpecTRM-RL constraint types in UML. We have also extended SpecTRM's constraints by adding relational and global constraints, and then expressed them in OCL. Safety verification of these specifications is also proposed. We developed a systematic way to construct fault trees for safety analysis based on UML diagrams. Due to the generality of UML as well as the defensive manner of constraints and fault tree analysis, our approach can be adapted for both general applications and safety-critical applications.

In this paper, we consider a data mining problem for semi-structured data. Modeling semi-structured data as labeled ordered trees, we present an efficient algorithm for discovering frequent substructures from a large collection of semi-structured data. By extending the enumeration technique developed by Bayardo (SIGMOD'98) for discovering long itemsets, our algorithm scales almost linearly in the total size of maximal tree patterns contained in an input collection depending mildly on the size of the longest pattern. We also developed several pruning techniques that significantly speed-up the search. Experiments on Web data show that our algorithm runs efficiently on real-life datasets combined with proposed pruning techniques in the wide range of parameters.

The traditional way of approaching device-level placement problems for analog layout is to explore a huge search space of absolute placement representations, where cells are allowed to illegally overlap during their moves. This paper presents a novel exploration technique for analog placement, operating on a subset of tree representations of the layout, where the typical presence of an arbitrary number of symmetry groups of devices is directly taken into account during the search of the solution space. The efficiency of the novel approach is due to the use of red-black interval trees, data structures employed to support operations on dynamic sets of intervals.

Consider an undirected graph G=(V,E) with n (=|V|) vertices and m (=|E|) edges. It is well-known that the problem of computing the sequence Nn-1,Nn,...,Nm is #P-complete (see e.g.,[3]), where Ni denotes the number of connected spanning subgraphs with i (n-1!im) edges in G. In this paper, by proving new inequalities on the sequence Nn-1,Nn,...,Nm, we show an interesting and stronger property that the sequence γn-1,γn,...,γm, where γi denotes the average number of spanning trees in the connected spanning subgraphs with i edges, is a convex sequence as well as a monotonically increasing sequence, although this property does not hold for the sequence Nn-1,Nn,...,Nm.

In this paper, a novel approach to speaker recognition is proposed. The approach makes use of adaptive boosting (AdaBoost) and classifiers such as Multilayer Perceptrons (MLP) and C4.5 Decision Trees for closed set, text-dependent speaker recognition. The performance of the systems is assessed using a subset of utterances drawn from the YOHO speaker verification corpus. Experiments show that significant improvement in accuracy can be achieved with the application of adaptive boosting techniques. Results also reveal that an accuracy of 98.8% for speaker identification may be achieved using the adaptively boosted C4.5 system.

A plane drawing of a graph is called a floorplan if every face (including the outer face) is a rectangle. A based floorplan is a floorplan with a designated base line segment on the outer face. In this paper we give a simple algorithm to generate all based floorplans with at most n faces. The algorithm uses O(n) space and generates such floorplans in O(1) time per floorplan without duplications. The algorithm does not output entire floorplans but the difference from the previous floorplan. By modifying the algorithm we can generate without duplications all based floorplans having exactly n faces in O(1) time per floorplan. Also we can generate without duplications all (non-based) floorplans having exactly n faces in O(n) time per floorplan.

Layout design for analog circuits has historically been a time consuming, error-prone, manual task. Its complexity results not so much from the number of devices, as from the complex interactions among devices or with the operating environment, and also from continuous-valued performance specifications. This paper addresses the problem of device-level placement for analog layout in a non-traditional way. Different from the classic approaches--exploring a huge search space with a combinatorial optimization technique, where the cells are represented by means of absolute coordinates, being allowed to illegally overlap during their moves in the chip plane--this paper advocates the use of non-slicing topological representations, like (symmetric-feasible) sequence-pairs, ordered- and binary- trees. Extensive tests, processing industrial analog designs, have shown that using skillfully the symmetry constraints (very typical to analog circuits) to remodel the solution space of the encoding systems, the topological representation techniques can achieve a better computation speed than the traditional approaches, while obtaining a similar high quality of the designs.

We propose a two-level hierarchical method for dependability evaluation of distributed systems with replicated programs and data files. Since Markov modeling is limited only to each component in this method, state explosion can be circumvented successfully. Simulation results show that the method can accomplish evaluation even for large systems for which Markov modeling is not feasible.

Given a graph G, a designated vertex r and a natural number k, we wish to find k "independent" spanning trees of G rooted at r, that is, k spanning trees such that, for any vertex v, the k paths connecting r and v in the k trees are internally disjoint in G. In this paper we give a linear-time algorithm to find k independent spanning trees in a k-connected maximal planar graph rooted at any designated vertex.

Using decision trees to fill the missing values in data has been shown experimentally to be useful in some domains. However, this is not the general case. In other domains, using decision trees for imputing missing attribute values does not outperform other methods. Trying to identify the reasons behind the success or failure of the various methods for filling missing values on different domains can be useful for deciding the technique to be used when learning concepts from a new domain with missing values. This paper presents a technique by which to approach to previous goal and presents the results of applying the technique on predicting the success or failure of a method that uses decision trees to fill the missing values in an ordered manner. Results are encouraging because the obtained decision tree is simple and it can even provide hints for further improvement on the use of decision trees to impute missing attribute values.

We address the problem of computing various types of expressive tests for decision trees and regression trees. Using expressive tests is promising, because it may improve the prediction accuracy of trees, and it may also provide us some hints on scientific discovery. The drawback is that computing an optimal test could be costly. We present a unified framework to approach this problem, and we revisit the design of efficient algorithms for computing important special cases. We also prove that it is intractable to compute an optimal conjunction or disjunction.