Scientific and artistic investigation of multi-dimensional fractals on the AT & T pixel machine

The pipelined architecture and parallel organization of the AT&T Pixel Machine image computer are described and demonstrated with applications for the visualization of multidimensional fractals, particularly linear fractals and quaternion/ stacked Julia sets. Techniques for pushing the Pixel Machine to its peak abilities are described and apply to more recent parallel image computers as well.     

Presupposition failure — A comedy of errors

Presuppositions of utterances are the pieces of information you convey with an utterance no matter whether your utterance is true or not. We first study presupposition in a very simple framework of updating propositional information, with examples of how presuppositions of complex propositional updates can be calculated. Next we move on to presuppositions and quantification, in the context of a dynamic version of predicate logic, suitably modified to allow for presupposition failure. In both the propositional and the quantificational case, presupposition failure can be viewed as error abortion of procedures. Thus, a dynamic assertion logic which describes the preconditions for error abortion is the suitable tool for analysing presupposition.     

Function materialization in object bases: design, realization, andevaluation

View materialization is a well-known optimization technique of relational database systems. We present a similar, yet more powerful, optimization concept for object-oriented data models: function materialization. Exploiting the object-oriented paradigm-namely, classification, object identity, and encapsulation-facilitates a rather easy incorporation of function materialization into (existing) object-oriented systems. Only those types (classes) whose instances are involved in some materialization are appropriately modified and recompiled, thus leaving the remainder of the object system invariant. Furthermore, the exploitation of encapsulation (information hiding) and object identity provides for additional performance tuning measures that drastically decrease the invalidation and rematerialization overhead incurred by updates in the object base. First, it allows us to cleanly separate the object instances that are irrelevant for the materialized functions from those that are involved in the materialization of some function result, and this to penalize only those involved objects upon update. Second, the principle of information hiding facilitates fine-grained control over the invalidation of precomputed results. Based on specifications given by the data type implementor, the system can exploit operational semantics to better distinguish between update operations that invalidate a materialized result and those that require no rematerialization. The paper concludes with a quantitative analysis of function materialization based on two sample performance benchmarks obtained from our experimental object base system GOM     

Site and query scheduling policies in multicomputer databasesystems

We study run-time issues, such as site allocation and query scheduling policies, in executing read-only queries in a hierarchical, distributed memory, multicomputer system. The particular architecture considered is based on the hypercube interconnection. The data are stored in a base cube, which is controlled by a control cube and host node hierarchy. Input query trees are transformed into operation sequence trees, and the operation sequences become the units of scheduling. These sequences are scheduled dynamically at run-time. Algorithms for dynamic site allocation are provided. Several query scheduling policies that support interquery concurrency are also studied. Average query completion times and initiation delays are obtained for the various policies using simulations     

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     

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     

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.