Partial indexing for nonuniform data distributions in relationalDBMS's

It is well known that the effectiveness of relational database systems is greatly dependent on the efficiency of the data access strategies. For this reason, much work has been devoted to the development of new access techniques, supported by adequate access structures such as the B⁺trees. The effectiveness of the B ⁺tree also depends on the data distribution characteristics; in particular, poor performance results when the data show strong key value distribution unbalancing. The aim of this paper is to present the partial index: a new access structure that is useful in such cases of unbalancing, as an alternative to the B⁺tree unclustered indexes. The access structures are built in the physical design phase, and at execution (or compilation) time, the optimizer chooses the most efficient access path. Thus, integration of the partial indexing technique in the design and in the optimization process are also described     

Sort vs. hash revisited

Efficient algorithms for processing large volumes of data are very important both for relational and new object-oriented database systems. Many query-processing operations can be implemented using sort- or hash-based algorithms, e.g. intersections, joins, and duplicate elimination. In the early relational database systems, only sort-based algorithms were employed. In the last decade, hash-based algorithms have gained acceptance and popularity, and are often considered generally superior to sort-based algorithms such as merge-join. In this article, we compare the concepts behind sort- and hash-based query-processing algorithms and conclude that (1) many dualities exist between the two types of algorithms, (2) their costs differ mostly by percentages rather than by factors, (3) several special cases exist that favor one or the other choice, and (4) there is a strong reason why both hash- and sort-based algorithms should be available in a query-processing system. Our conclusions are supported by experiments performed using the Volcano query execution engine     

Evaluation of a parallel branch-and-bound algorithm on a class ofmultiprocessors

We propose and evaluate a parallel “decomposite best-first” search branch-and-bound algorithm (dbs) for MIN-based multiprocessor systems. We start with a new probabilistic model to estimate the number of evaluated nodes for a serial best-first search branch-and-bound algorithm. This analysis is used in predicting the parallel algorithm speed-up. The proposed algorithm initially decomposes a problem into N subproblems, where N is the number of processors available in a multiprocessor. Afterwards, each processor executes the serial best-first search to find a local feasible solution. Local solutions are broadcasted through the network to compute the final solution. A conflict-free mapping scheme, known as the step-by-step spread, is used for subproblem distribution on the MIN. A speedup expression for the parallel algorithm is then derived using the serial best-first search node evaluation model. Our analysis considers both computation and communication overheads for providing realistic speed-up. Communication modeling is also extended for the parallel global best-first search technique. All the analytical results are validated via simulation. For large systems, when communication overhead is taken into consideration, it is observed that the parallel decomposite best-first search algorithm provides better speed-up compared to other reported schemes     

Unstructured tree search on SIMD parallel computers

We present new methods for load balancing of unstructured tree computations on large-scale SIMD machines, and analyze the scalability of these and other existing schemes. An efficient formulation of tree search on an SIMD machine consists of two major components: a triggering mechanism, which determines when the search space redistribution must occur to balance the search space over processors, and a scheme to redistribute the search space. We have devised a new redistribution mechanism and a new triggering mechanism. Either of these can be used in conjunction with triggering and redistribution mechanisms developed by other researchers. We analyze the scalability of these mechanisms and verify the results experimentally. The analysis and experiments show that our new load-balancing methods are highly scalable on SIMD architectures. Their scalability is shown to he no worse than that of the best load-balancing schemes on MIMD architectures. We verify our theoretical results by implementing the 15-puzzle problem on a CM-2 SIMD parallel computer     

Comments on “Can backpropagation error surface not have localminima?”

in the above paper Yu (IEEE Trans. Neural Networks, vol.3, no.6, p.1019-21 (1992)) claims to prove that local minima do not exist in the error surface of backpropagation networks being trained on data with t distinct input patterns when the network is capable of exactly representing arbitrary mappings on t input patterns. The commenter points out that the proof presented is flawed, so that the resulting claims remain unproved. In reply, Yu points out that the undesired phenomenon that was sited can be avoided by simply imposing the arbitrary mapping capacity of the network on lemma 1 in the article.     

Hierarchical models for analysis and recognition of handwritten characters

Different hierarchical models in pattern analysis and recognition are proposed, based on occurrence probability of patterns. As an important application of recognizing handprinted characters, three typical kinds of hierarchical models such asM _89-89,M _89-36 andM _36-36 have been presented, accompanied by the computer algorithms for computing recognition rates of pattern parts. Moreover, a comparative study of their recognition rates has been conducted theoretically; and numerical experiments have been carried out to verify the analytical conclusions made. Various hierarchical models deliberated in this paper can provide users more or better choices of pattern models in practical application, and lead to a uniform computational scheme (or code). The recognition rates of parts can be improved remarkably by a suitable hierarchical model. For the modelM _89-36 in which case some of the Canadian standard handprinted characters have multiple occurrence probabilities, the total mean recognition rates of the given sample may reach 120% of that by the model proposed by Li et al., and 156% of that obtained from the subjective experiments reported by Suen.     

Volcano-an extensible and parallel query evaluation system

To investigate the interactions of extensibility and parallelism in database query processing, we have developed a new dataflow query execution system called Volcano. The Volcano effort provides a rich environment for research and education in database systems design, heuristics for query optimization, parallel query execution, and resource allocation. Volcano uses a standard interface between algebra operators, allowing easy addition of new operators and operator implementations. Operations on individual items, e.g., predicates, are imported into the query processing operators using support functions. The semantics of support functions is not prescribed; any data type including complex objects and any operation can be realized. Thus, Volcano is extensible with new operators, algorithms, data types, and type-specific methods. Volcano includes two novel meta-operators. The choose-plan meta-operator supports dynamic query evaluation plans that allow delaying selected optimization decisions until run-time, e.g., for embedded queries with free variables. The exchange meta-operator supports intra-operator parallelism on partitioned datasets and both vertical and horizontal inter-operator parallelism, translating between demand-driven dataflow within processes and data-driven dataflow between processes. All operators, with the exception of the exchange operator, have been designed and implemented in a single-process environment, and parallelized using the exchange operator. Even operators not yet designed can be parallelized using this new operator if they use and provide the interator interface. Thus, the issues of data manipulation and parallelism have become orthogonal, making Volcano the first implemented query execution engine that effectively combines extensibility and parallelism     

E-kernel: an embedding kernel on the IBM victor V256 multiprocessorfor program mapping and network reconfiguration

We present the design of E-kernel, an embedding kernel on the Victor V256 message-passing partitionable multiprocessor, developed for the support of program mapping and network reconfiguration. E-kernel supports the embedding of a new network topology onto Victor's 2D mesh and also the embedding of a task graph onto the 2D mesh network or the reconfigured network. In the current implementation, the reconfigured network can be a line or an even-size ring, and the task graphs meshes or tori of a variety of dimensions and shapes or graphs with similar topologies. For application programs having these task graph topologies and that are designed according to the communication model of E-kernel, they can be run without any change on partitions connected by the 2D mesh, line, or ring. Further, E-kernel attempts the communication optimization of these programs on the different networks automatically, thus making both the network topology and the communication optimization attempt completely transparent to the application programs. Many of the embeddings used in E-kernel are optimal or asymptotically optimal (with respect to minimum dilation cost). The implementation of E-kernel translated some of the many theoretical results in graph embeddings into practical tools for program mapping and network reconfiguration in a parallel system. E-kernel is functional on Victor V256. Measurements of E-kernel's performance on V256 are also included     

Using recurrent neural networks for adaptive communication channelequalization

Nonlinear adaptive filters based on a variety of neural network models have been used successfully for system identification and noise-cancellation in a wide class of applications. An important problem in data communications is that of channel equalization, i.e., the removal of interferences introduced by linear or nonlinear message corrupting mechanisms, so that the originally transmitted symbols can be recovered correctly at the receiver. In this paper we introduce an adaptive recurrent neural network (RNN) based equalizer whose small size and high performance makes it suitable for high-speed channel equalization. We propose RNN based structures for both trained adaptation and blind equalization, and we evaluate their performance via extensive simulations for a variety of signal modulations and communication channel models. It is shown that the RNN equalizers have comparable performance with traditional linear filter based equalizers when the channel interferences are relatively mild, and that they outperform them by several orders of magnitude when either the channel's transfer function has spectral nulls or severe nonlinear distortion is present. In addition, the small-size RNN equalizers, being essentially generalized IIR filters, are shown to outperform multilayer perceptron equalizers of larger computational complexity in linear and nonlinear channel equalization cases.