An extensive list of time-sensitive applications requiring ultra-low latency ranging from a few microseconds to a few milliseconds are presented in recent publications and IEEE standards. Time-sensitive applications, include industrial, critical healthcare and transportation applications as also applications for Smart Grids and the Internet of Vehicles – one of the most active research fields of Intelligent Transportation Systems of Smart Cities. In this work, we mainly set our focus on the suite of safety applications which attracts strong interest from the research community, as it aims to avoid road accidents and save lives. The IEEE Time-Sensitive Networking (TSN) set of standards specifies fundamental real-time characteristics. Nevertheless, as TSN works on Data Link layer (Layer 2 of the OSI model) the benefits of these characteristics fade away when other layers are crossed from the Application layer (Layer 7). Indicatively, recent research works report latencies on the order of tens of seconds when benchmarking Data Stream Processing and IoT platforms, and thus they are not suited for time-critical applications. Such platforms mainly use loosely coupled components with asynchronous communication. On Application layer, we propose a novel End-to-End Synchronous, Distributed Architecture for Large-Scale, High-Bandwidth, Ultra-Low Latency Data Stream Processing. Through our Big Data Stream analysis experiments (4.7 Gbit/s total average aggregated throughput, 1 Terabyte in-memory distributed database, 4 milliseconds average query latency) we have demonstrated the suitability of our architecture for time-sensitive applications such as accident avoidance for the Internet of Vehicles.

An alternative proof is given of the existence of greatest lower bounds in the imbalance order of binary maximal instantaneous codes of a given size. These codes are viewed as maximal antichains of a given size in the infinite binary tree of 0–1 words. The proof proposed makes use of a single balancing operation within the same imbalance poset of codes of the same fixed size, instead of moving back and forth between posets of codes corresponding to two different code sizes using expansion and contraction, as in the previous proofs of the existence of glb. It also makes use of a new combinatorial characterization of the imbalance order.

Sustainable energy policies are of growing importance in all urban centers.Climate — and climate change — will play increasingly important roles in these policies.Climate zones defined by the California Energy Commissionhave long been influential in energy management.For example, recently a two-zone division of Los Angeles(defined by historical temperature averages) was introduced for electricity rate restructuring.The importance of climate zones has been enormous,and climate change could make them still more important. AI can provide improvements on the ways climate zones are derived and managed.This paper reports on analysis of aggregate household electricity consumption (EC) data from local utilities in Los Angeles,seeking possible improvements in energy management. In this analysis we noticed that EC data permits identificationof interesting geographical zones — regions having EC patterns that are characteristically different from surrounding regions.We believe these zones could be useful in a variety of urban models.

We present a complementary ensemble selection method that utilizes a novel priority queue-based diversity measure. The method considers voting weaknesses of the current ensemble in covering the training set, and finds a classifier that can remove the highest priority weaknesses. Individual classifiers are generated using different machine learning algorithms and different parameter settings. A key feature of our method is in selecting complementary classifiers, i.e., repeatedly adding individual classifiers that best complement incorrect voting patterns of the current ensemble in priority order. We refer to this approach as “complementarity”. To evaluate this approach, we have performed months of experiments, making comparisons between our complementary prioritized ensemble selection method and an “ensemble of ensembles” approach. The comparisons are based on the forward stepwise selection method from earlier work on 5 datasets, each of which consists of comparisons from 9 folds of validated data (from 2 fold to 10 fold cross validated data). Over 1600 different classifier types were considered, yielding a huge space of alternative ensembles. The experimental results showed that a small and compact complementary ensemble yielded performance as good as and sometimes better than a huge ensemble selected by a state-of-the-art Ensemble of Ensembles method.

We describe a technique for adding contextual distinctions to word embeddings by extending the usual embedding process -into two phases.The first phase resembles existing methods, but also constructs K classifications of concepts.The second phase uses these classifications in developing refined K embeddings for words, namely word K-embeddings.The technique is iterative, scalable, and can be combined with other methods (including Word2Vec) in achieving still more expressive representations.Experimental results show consistently large performance gains on a Semantic-Syntactic Word Relationship test set for different K settings.For example, an overall gain of 20% is recorded at K = 5.In addition, we demonstrate that an iterative process can further tune the embeddings and gain an extra 1% (K = 10 in 3 iterations) on the same benchmark.The examples also show that polysemous concepts are meaningfully embedded in our K different conceptual embeddings for words.

We introduce a distributed representation of nodes, node embeddings, in social network analysis. We compute embeddings for nodes based on their attributes and links. These embeddings can support many social network applications --- including analyses of community homogeneity, distance, and detection of community connectors (inter-community outliers, people who connect communities) --- thanks to the convenient yet efficient computation provided by node embeddings for structural comparisons. Our experimental results include many interesting insights about the computer science literature network (DBLP). For example, in DBLP prior to 2013 the best way for research in Natural Language & Speech to gain impact toward "best-paper" recognition was to emphasize aspects related to Machine Learning & Pattern Recognition.

Transdisciplinary research is a rapidly expanding part of science and engineering, demanding new methods for connecting results across fields. In biomedicine for example, modeling complex biological systems requires linking knowledge across multiple levels of science, from genes to disease. The move to multilevel research requires new strategies; in this paper we present path knowledge discovery, a novel methodology for linking published research findings. Path knowledge discovery consists of two integral tasks: 1) association path mining among concepts in a multipart lexicon that crosses disciplines, and 2) fine-granularity knowledge-based content retrieval along the path(s) to permit deeper analysis. Implementing this methodology has required development of innovative measures of association strength for pairwise associations, as well as the strength for sequences of associations, in addition to powerful lexicon-based association expansion to increase the scope of matching. In our discussions, we describe the validation of the methodology using a published heritability study from cognition research, and we obtain comparable results. We show how path knowledge discovery can greatly reduce a domain expert's time (by several orders of magnitude) when searching and gathering knowledge from the published literature, and can facilitate derivation of interpretable results.

In this study, we model how biomedical topics influence one another, given they are organized in a topic hierarchy, medical subject headings, in which the edges capture a parent-child/subsumption relationship among topics. This information enables studying influence of topics from a semantic perspective, which might be very important in analyzing topic evolution and is missing from the current literature. We first define a burst-based action for topics, which models upward momentum in popularity (or “elevated occurrences” of the topics), and use it to define two types of influence: accumulation influence and propagation influence. We then propose a model of influence between topics, and develop an efficient algorithm (TIPS) to identify influential topics. Experiments show that our model is successful at identifying influential topics and the algorithm is very efficient.

In this paper we consider the problem of mining influence in a network of topics, where we seek to model direct influences between topics over time, in the form of bursts of topic occurrence — so that influence is measured by topic co-occurrence in high-frequency intervals — and this influence propagates among topics, leading to frequent occurrences of the topics. Although it is clearly significant, this problem has gotten very little attention. To address the problem, we propose a novel model: SemInf. As topics can recur, influence in our model is not constant or single-timestamp (“one-shot”, as in social networks), but is instead multi-timestamp, with periods of influence that can span multiple time intervals. More specifically, this model of topic influence captures upward momentum in popularity over all time-stamps in a burst (a period of “elevated occurrence” of topics). A topic hierarchy is used to provide a distance measure among topics and characterize their semantic relatedness. Experiments on biomedical topics give some surprising results, showing both that our model is successful at identifying topics with high impact, and that it can be potentially used as an alternative model of impact in the scientific literature (which can be useful when citation information is not available). We also show that although semantic information helps boost performance of our model, it can work without such information. What's more, we show SemInf can be also generalized to other domains, such as topics in computer science research.

The Center for Computational Biology (CCB) is a multidisciplinary program where biomedical scientists, engineers, and clinicians work jointly to combine modern mathematical and computational techniques, to perform phenotypic and genotypic studies of biological structure, function, and physiology in health and disease. CCB has developed a computational framework built around the Manifold Atlas, an integrated biomedical computing environment that enables statistical inference on biological manifolds. These manifolds model biological structures, features, shapes, and flows, and support sophisticated morphometric and statistical analyses. The Manifold Atlas includes tools, workflows, and services for multimodal population-based modeling and analysis of biological manifolds. The broad spectrum of biomedical topics explored by CCB investigators include the study of normal and pathological brain development, maturation and aging, discovery of associations between neuroimaging and genetic biomarkers, and the modeling, analysis, and visualization of biological shape, form, and size. CCB supports a wide range of short-term and long-term collaborations with outside investigators, which drive the center's computational developments and focus the validation and dissemination of CCB resources to new areas and scientific domains.

Recent years have witnessed a great deal of attention in tracking news memes over the web, modeling shifts in the ebb and flow of their popularity. One of the most important features of news memes is that they seldom occur repeatedly, instead, they tend to shift to different but similar memes. In this work, we consider patterns in research memes, which differ significantly from news memes and have received very little attention. One significant difference between research memes and news memes lies in that research memes have cyclic development, motivating the need for models of cycles of research memes. Furthermore, these cycles may reveal important patterns of evolving research, shedding lights on how research progresses. In this paper, we formulate the modeling of the cycles of research memes, and propose solutions to the problem of identifying cycles and discovering patterns among these cycles. Experiments on two different domain applications indicate that our model does find meaningful patterns and our algorithms for pattern discovery are efficient for large scale data analysis.

For some time there has been increasing interest in the problem of monitoring the occurrence of topics in a stream of events, such as a stream of news articles. This has led to different models of bursts in these streams, i.e., periods of elevated occurrence of events. Today there are several burst definitions and detection algorithms, and their differences can produce very different results in topic streams. These definitions also share a fundamental problem: they define bursts in terms of an arrival rate. This approach is limiting; other stream dimensions can matter.

Research in visualization often revolves around visualizing information. However, visualization is a process that extends over time from initial exploration to hypothesis confirmation, and even to result presentation. It is rare that the final phases of visualization are solely about information. In this paper we present a more biased kind of visualization, in which there is a message or set of assumptions behind the presentation that is of interest to both the presenter and the viewer, and emphasizes points that the presenter wants to convey to the viewer. This kind of persuasive visualization -- presenting data in a way that emphasizes a point or message -- is not only common in visualization, but also often expected by the viewer. Persuasive visualization is implicit in the deliberate emphasis on interestingness and also in the deliberate use of graphical elements that are processed preattentively by the human visual system, which automatically groups these elements and guiding attention so that they "stand out". We discuss how these ideas have been implemented in the Morpherspective system for automated generation of information graphics.

The trans-genomic query (TGQ) problem--enabling the free query of biological information, even across genomes--is a central challenge facing bioinformatics. Solutions to this problem can alter the nature of the field, moving it beyond the jungle of data integration and expanding the number and scope of questions that can be answered. An alignment table is a binary relationship on locations (sequence segments). An important special case of alignment tables are hit tables ? tables of pairs of highly similar segments produced by alignment tools like BLAST. However, alignment tables also include general binary relationships, and can represent any useful connection between sequence locations. They can be curated, and provide a high-quality queryable backbone of connections between biological information. Alignment tables thus can be a natural foundation for TGQ, as they permit a central part of the TGQ problem to be reduced to purely technical problems involving tables of locations.Key challenges in implementing alignment tables include efficient representation and indexing of sequence locations. We define a location datatype that can be incorporated naturally into common off-the-shelf database systems. We also describe an implementation of alignment tables in BLASTGRES, an extension of the open-source POSTGRESQL database system that provides indexing and operators on locations required for querying alignment tables. This paper also reviews several successful large-scale applications of alignment tables for Trans-Genomic Query. Tables with millions of alignments have been used in queries about alternative splicing, an area of genomic analysis concerning the way in which a single gene can yield multiple transcripts. Comparative genomics is a large potential application area for TGQ and alignment tables.

Map-Reduce is a programming model that enables easy development of scalable parallel applications to process a vast amount of data on large clusters of commodity machines. Through a simple interface with two functions, map and reduce, this model facilitates parallel implementation of many real-world tasks such as data processing jobs for search engines and machine learning.

Recent research in biology has discovered that a large portion of genes that are responsible for core biological functions are conserved in most or all living cells. This has initiated development of, and emphasizes the importance of, common annotation facilities for biological knowledge, as features and functions of an unknown gene can be related to or inferred from those of a similar and well-studied gene. The Gene Ontology (‘GO’), a collection of three ontologies each defining a specialization hierarchy of biological terms, has been an extraordinary focus of this effort. This paper describes GOBASE, a publicly-available graph database for query and visualization of GO information. There are existing browsers for visualizing GO information, but GObase provides a more powerful interface, allowing both interactive query and interactive annotation of GO terms with other data sources. We will focus on how GOBASE achieves interactive annotation and query and its tight interactions with backend databases.

In this paper1 we introduce the Holodex, a ‘holistic index’ for databases that includes a facility for statistics and aggregate-like computations. The Holodex is an integration of the conventional index and summarization over traversals of the index. It can store customized summaries in its data structure, and in this way it can maintain, and provide fast access to, summarized information. The Holodex rests on the Summary-Traversal Architecture a customizable summarization scheme for tree indexes. An important property of the summary-traversal architecture is that index structures defining an ordering on data can be augmented to provide extra summary information as well. For example, both tree indexes (such as the B+- Tree) and tree-hash hybrids (e.g., Multi-Level Trie Hashing and Interpolation Search Tree ) define an ordering, and they can be naturally extended to include summary information. This combination of indexing and summarization has a variety of uses, including computation of aggregate functions, rollups, bulk computation, and a variety of kinds of statistics, particularly those that are in some way related to order. More specifically, it is useful for computing nonparametric statistics - including rank statistics and order statistics - as well as direct implementation of queries like basic statistical tests on sample distributions.

Abstract wonglediff is a program that tests the sensitivity of arbitrary program executables or processes to changes that are introduced by a process that runs in parallel. On Unix and Linux kernels, wonglediff creates a supervisor process that runs applications and, on the fly, introduces desired changes to their process state. When execution terminates, it then summarizes the resulting changes in the output files. The technique employed has a variety of uses. This paper describes an implementation of wonglediff that checks the sensitivity of programs to random changes in the floating‐point rounding modes. It runs a program several times, ‘wongling’ it each time: randomly toggling the IEEE‐754 rounding mode of the program as it executes. By comparing the resulting output, one gets a poor man's numerical stability analysis for the program. Although the analysis does not give any kind of guarantee about a program's stability, it can reveal genuine instability, and it does serve as a particularly useful and revealing idiot light. In our implementation, differences among the output files from the program's multiple runs are summarized in a report. This report is in fact an HTML version of the output file, with inline mark‐up summarizing individual differences among the multiple instances. When viewed with a browser, the differences can be highlighted or rendered in many different ways. Copyright © 2004 John Wiley & Sons, Ltd.

Finding effective methods for developing an ensemble of models has been an active research area of large-scale data mining in recent years. Models learned from data are often subject to some degree of uncertainty, for a variety of resoans. In classification, ensembles of models provide a useful means of averaging out error introduced by individual classifiers, hence reducing the generalization error of prediction.The plurality voting method is often chosen for bagging, because of its simplicity of implementation. However, the plurality approach to model reconciliation is ad-hoc. There are many other voting methods to choose from, including the anti-plurality method, the plurality method with elimination, the Borda count method, and Condorcet's method of pairwise comparisons. Any of these could lead to a better method for reconciliation.In this paper, we analyze the use of these voting methods in model reconciliation. We present empirical results comparing performance of these voting methods when applied in bagging. These results include some surprises, and among other things suggest that (1) plurality is not always the best voting method; (2) the number of classes can affect the performance of voting methods; and (3) the degree of dataset noise can affect the performance of voting methods. While it is premature to make final judgments about specific voting methods, the results of this work raise interesting questions, and they open the door to the application of voting theory in classification theory.

In this paper we present the landmark model, a model for time series that yields new techniques for similarity-based time series pattern querying. The landmark model does not follow traditional similarity models that rely on pointwise Euclidean distance. Instead, it leads to landmark similarity, a general model of similarity that is consistent with human intuition and episodic memory. By tracking different specific subsets of features of landmarks, we can efficiently compute different landmark similarity measures that are invariant under corresponding subsets of six transformations; namely, shifting, uniform amplitude scaling, uniform time scaling, uniform bi-scaling, time warping and non-uniform amplitude scaling. A method of identifying features that are invariant under these transformations is proposed. We also discuss a generalized approach for removing noise from raw time series without smoothing out the peaks and bottoms. Beside these new capabilities, our experiments show that landmark indexing is considerably fast.

Recursive block decomposition algorithms (also known as quadtree algorithms when the blocks are all square) have been proposed to solve well-known problems such as matrix addition, multiplication, inversion, determinant computation, block LDU decomposition and Cholesky and QR factorization. Until now, such algorithms have been seen as impractical, since they require leading submatrices of the input matrix to be invertible (which is rarely guaranteed). We show how to randomize an input matrix to guarantee that submatrices meet these requirements, and to make recursive block decomposition methods practical on well-conditioned input matrices. The resulting algorithms are elegant, and we show the recursive programs can perform well for both dense and sparse matrices, although with randomization dense computations seem most practical. By ‘homogenizing’ the input, randomization provides a way to avoid degeneracy in numerical problems that permits simple recursive quadtree algorithms to solve these problems.

We show that the space of all binary Huffman codes for a finite alphabet defines a lattice, ordered by the imbalance of the code trees. Representing code trees as path-length sequences, we show that the imbalance ordering is closely related to a majorization ordering on real-valued sequences that correspond to discrete probability density functions. Furthermore, this tree imbalance is a partial ordering that is consistent with the total orderings given by either the external path length (sum of tree path lengths) or the entropy determined by the tree structure. On the imbalance lattice, we show the weighted path-length of a tree (the usual objective function for Huffman coding) is a submodular function, as is the corresponding function on the majorization lattice. Submodular functions are discrete analogues of convex functions. These results give perspective on Huffman coding and suggest new approaches to coding as optimization over a lattice.

The authors take a real world application from a text database and present a case history. The techniques ultimately led to a discovery contradicting an accepted paradigm in seismology. Using simple, tailored, keyword extraction, they examined a text collection of earthquake data. A discovery was made when an unusual pattern emerged from the text. They then tested a more comprehensive numerical database, treating the the text discovery as a hypothesis. It was verified using a standard /spl chi//sup 2/ statistic. The hypothesis was significant earthquakes in the longitude regions that include California, occur more often in the morning hours than any other time of day.

Automatic graph layout is an important and long-studied problem. The basic straight-edge graph layout problem is to find spatial positions for the nodes of an input graph that maximize some measure of desirability. When graph layout is intended for human consumption, we call this measure of desirability an aesthetic. We seek an algorithm that produces graph layouts of high aesthetic quality not only for general graphs, but also for specific classes of graphs, such as trees and directed acyclic graphs. The Aesthetic Graph Layout (AGLO) approach described in this paper models graph layout as a multiobjective optimization problem, where the value of a layout is determined by multiple user-controlled layout aesthetics. The current AGLO algorithm combines the power and flexibility of the simulated annealing approach of Davidson and Harel (1989) with the relative speed of the method of Fruchterman and Reingold (1991). In addition, it is more general, and incorporates several new layout aesthetics to support new layout styles. Using these aesthetics, we are able to produce pleasing displays for graphs on which these other methods flounder.

A generalized quantifier is a particular kind of operator on sets. Coming under increasing attention recently by linguists and logicians, they correspond to many useful natural language phrases, including phrases like: three, Chamberlin's three, more than three, fewer than three, at most three, all but three, no more than three, not more than half the, at least two and not more than three, no student's, most male and all female, etc. Reasoning about quantifiers is a source of recurring problems for most SQL users, and leads to both confusion and incorrect expression of queries. By adopting a more modern and natural model of quantification these problems can be alleviated. We show how generalized quantifiers can be used to improve the SQL interface.>

Abstract Regulations are pervasive in information systems. They manifest themselves as design rules, integrity constraints, deadlines, conventions, information disclosure requirements, policies, procedures, contracts, taxes, quotas and other statutes. Managing regulations is difficult. Regulations are complex, change frequently and rest on models of the real world that involve unusual vocabulary if not unusual concepts. Consequently, checking compliance with regulations is tedious and error‐prone. Logic programming appears to provide a good framework for developing regulation management systems. Besides permitting arbitrary regulations to be modelled, it offers rapidity and ease of development, readability, incremental modifiability, extensibility and portability. These features are not provided by existing DP programming tools, database managers or conventional expert‐system shells. This paper investigates the application of logic programming in a significant regulation management application: Workers' Compensation Insurance premium auditing. The insurance premium computation rules for the State of California were encoded as a large Prolog program. This application illustrates specific strengths and weaknesses of logic programming and Prolog in dealing with large‐scale real‐world regulations.

An approach is presented for integrating AI (artificial intelligence) systems with DBMS (database management systems). The impedance mismatch that has made this integration a problem is, in essence, a difference in the two system models of data processing. The present approach is to avoid the mismatch by forcing both AI systems and DBMS into the common model of stream processing. The approach taken in the Tangram project at UCLA, which integrates Prolog with relational DBMS, is described. Prolog is extended to a functional language called Log(F) that facilitates development of stream processing programs. The integration of this system with DBMS is simultaneously elegant, easy to use, and relatively efficient.>

Tangram, an environment for modeling which is under development at UCLA, is discussed. One of the driving concepts behind Tangram has been the combination of large-scale data access and data reduction with a powerful programming environment. The Tangram environment is based on PROLOG, extending it with a number of features, including process management, distributed database access, and generalized stream processing. The authors describe the Tangram stream processor, the part of the Tangram environment performing query processing on large streams of data. The paradigm of transducers on streams is used throughout this system, providing a database flow computation capability.>

We introduce a programming paradigm in which statements are constraints over partial orders. A partial order programming problem has the form minimize u subject to u1 ⊒ v1, u2 ⊒ v2, ··· where u is the goal, and u1 ⊒ v1, u2 ⊒ v2, ··· is a collection of constraints called the program. A solution of the problem is a minimal value for u determined by values for u1, v1, etc. satisfying the constraints. The domain of values here is a partial order, a domain D with ordering relation ⊒.

According to the definition of satisfaction of Boolean dependencies, Theorem 15 is not true for Boolean dependencies with negation. (A positive Boolean dependency is built using the Boolean connectives ⋏, ⋎, and ↛; a general Boolean dependency (with negation) may use also the Boolean connective ¬.) Actually, the definition of satisfaction is not meaningful for Boolean dependencies with negation, since many are never satisfied. We show how the definition of satisfaction should be changed in order to make Boolean dependencies with negation meaningful and correct the error. We associate with each relation r a set α( r ) of truth assignments , as follows. For each pair of distinct tuples of r , the set α( r ) contains the truth assignment that maps an attribute A to true if the two tuples are equal on A , and to false if the two tuples have different values for A . A Boolean dependency σ is satisfied by a relation r if σ (i.e., the corresponding Boolean formula) satisfies every truth assignment of α( r ). The original definition given in the paper is equivalent to having α( r ) also include the truth assignment that is generated by pairs in which both tuples are really the same tuple of r , that is, to having α( r ) also always include the truth assignment τ mapping all attributes to true. Under that definition, however, many Boolean dependencies with negation are never satisfied and, hence, are meaningless. More precisely, according to the original definition, a Boolean dependency is satisfied by

In the spirit of integrating data base and artificial intelligence techniques, a number of concepts widely used in relational data base theory are introduced in a knowledge representation scheme. A simple network model, which allows the representation of types, is-a relationships and disjointness constraints is considered. The concepts of consistency and redundancy are introduced and characterized by means of implication of constraints and systems of inference rules, and by means of graph theoretic concepts.

We investigate three cost measures for the recently introduced brother search trees. In particular we characterize node visit optimal, comparison-cost optimal and space-cost optimal 1-2 brother trees and present linear-time algorithms to construct optimal 1-2 brother trees for each cost measure. Furthermore we also consider, briefly, these cost measures for brother leaf search trees.

The Gamma network is an interconnection network connecting N = 2n inputs to N outputs. It is a multistage network with N switches per stage, each of which is a 3 input, 3 output crossbar. The stages are linked via "power of two" and identify connections in such a way that redundant paths exist between the input and output terminals. In this network, a path from a source to a destination may be represented using one of the redundant forms of the difference between the source and destination numbers. The redundancy in paths may thus be studied using the theory of redundant number systems. Results are obtained on the distribution of paths connecting inputs and outputs, and the permuting capabilities of the Gamma network. Frequently used permutations and control mechanisms are discussed briefly. We also perform a detailed terminal reliability analysis of the Gamma network, deriving expressions for the reliability between an input and output terminal.

Many distributed systems are now being developed to provide users with convenient access to data via some kind of communications network. In many cases it is desirable to keep the system functioning even when it is partitioned by network failures. A serious problem in this context is how one can support redundant copies of resources such as files (for the sake of reliability) while simultaneously monitoring their mutual consistency (the equality of multiple copies). This is difficult since network faiures can lead to inconsistency, and disrupt attempts at maintaining consistency. In fact, even the detection of inconsistent copies is a nontrivial problem. Naive methods either 1) compare the multiple copies entirely or 2) perform simple tests which will diagnose some consistent copies as inconsistent. Here a new approach, involving version vectors and origin points, is presented and shown to detect single file, multiple copy mutual inconsistency effectively. The approach has been used in the design of LOCUS, a local network operating system at UCLA.

The Gamma network is an interconnection network connecting N=2' inputs to N outputs. It consists of log 2 N stages with N switches per stage, each of which is a 3 input, 3 output crossbar. The stages are linked via “power of two” and identity connections in such a way that redundant paths exist between the input and output terminals. In this network, a path from a source to a destination may be represented using one of the redundant forms of the difference between the source and destination numbers. The redundancy in paths may thus be studied using the theory of redundant number systems. Results are obtained on the distribution of paths connecting inputs to outputs, and the permuting capabilities of the Gamma network. Switch settings for certain frequently used permutations and control mechanisms are also considered in this paper. This network has an interesting application in solving tridiagonal systems using the odd-even elimination algorithm.

Many results in relational database theory on the structure of dependencies, query languages, and databases in general have now been established. However, neither (a) the reliance of these results on various assumptions, nor (b) the desirability or reasonableness of these assumptions themselves have been closely examined. These assumptions are nontrivial: examples include the universal relation assumption and the lossless join assumption.The purpose of the present paper is to clarify many of the existing assumptions, and point out weaknesses. This is desirable both to harden the statements of previous results, and to evaluate recent suggestions that certain assumptions (such as the acyclic JD assumption) may be useful for modeling "real world" databases. Specifically, studies are made of assumptions made for (1) universal relations, (2) functional dependency inference, and (3) decomposition theory. We show that:• Some assumptions (such as uniqueness of relationships among attributes) can be more powerful than they appear;• common treatment of FDs is sometimes inappropriate, and for example FD inferences such as {A → B, B → C} |= A → C can be incorrect;• the 'decomposition' approach to design may be hard to justify in real terms; and• Acyclic JDs may have drawbacks in eliminating ambiguity in queries and in modeling real enterprises.It is hoped that this exposition will help clarify some confusing issues in this field, and will lead to a better understanding of which assumptions are reasonable and useful in modeling the "real world".

A model of a general mass storage system is presented and its performance analyzed. The system is composed of a square two-dimensional grid of storage cells over which a single read/write head moves freely. The head can contain at most some fixed number b of cell contents. Algorithms for realizing an arbitrary permutation of the memory contents are presented for all ranges of b, particularly the important case $b = 1$; in each case the algorithms’ performances are explicitly characterized. Open problems, especially regarding the development of good heuristics, are then discussed.

It is known that there is an eqmvalence between functional dependencies m a relatmonal database and a certain fragment of proposmonal logic Thins eqmvalence is extended to include both functional and multivalued dependencmes.Thus, for each dependency there is a corresponding statement m proposmonal logic.It ms then shown that a dependency (funcuonal or multivalued) is a consequence of a set of dependencies ff and only ff the corresponding proposiuonal statement ~s a consequence of the corresponding set of proposmonal statements.Examples are given to show that these techniques are valuable mn provmdmg much shorter proofs of theorems about dependencies than have been obtained by more tradmonal means It is shown that this eqmvalence cannot be extended to include either join dependencies or embedded multmvalued dependencies.

Much work has been done recently on finding a complete set of dependency rules for Embedded Multivalued Dependencies (EMVDs), the generalization of the Multivalued Dependencies developed by Fagin and Zaniolo. We show that no finite such set of rules can exist by explicitly constructing a class containing, for all n, irreducible n-ary EMVD inference rules. These n-ary rules may be understood clearly when described in terms of the more "expressive" Transitive Dependencies (TDs) of Paredaens. However, we show in addition that no finite set of rules can exist for TDs either.

A new general formulation of Huffman tree construction is presented which has broad application. Recall that the Huffman algorithm forms a tree, in which every node has some associated weight, by specifying at every step of the construction which nodes are to be combined to form a new node with a new combined weight. We characterize a wide class of weight combination functions, the quasilinear functions, for which the Huffman algorithm produces optimal trees under correspondingly wide classes of cost criteria. In addition, known results about Huffman tree construction and related concepts from information theory and from the theory of convex functions are tied together. Suggestions for possible future applications are given.

In this paper a number of properties of Shuffle/Exchange networks are analyzed. A set of algebraic tools is developed and is used to prove that Lawrie's inverse Omega network, Pease's indirect binary n-cube array, and a network related to the 3-stage rearrangeable switching network studied by Clos and Beneš have identical switching capabilities. The approach used leads to a number of insights on the structure of the fast Fourier transform (FFT) algorithm. The inherent permuting power, or "universality," of the networks when used iteratively is then probed, leading to some nonintuitive results which have implications on the optimal control of Shuffle/Exchange-type networks for realizing permutations and broadcast connections.

Huffman's algorithm produces an optimal weighted r-ary tree on a given set of leaf weights, where the weight of any parent node is the maximum of the son weights plus some positive constant. If the weights are viewed as (parallel) completion times, the algorithm has useful applications to combinatorial circuit design— especially for merging, or "fanning-in," a set of inputs with varying ready times: the weight of the tree's root node is then the completion time of the whole merging process. In this note we give new, tight upper and lower bounds on the weight of this root node (extending some work of Golumbic), and briefly describe an application in multiplexor design which exercises both of these bounds.

The error properties of floating-point arithmetic using various rounding methods (including ROM rounding, a new scheme) are analyzed. Guard digits are explained, and the rounding schemes' effectiveness are evaluated and compared.

ROM-rounding is introduced and is shown to compare favorably with existing floating-point rounding methods on design considerations and on performance over a series of error tests. The error-retarding value of guard digits, of rounding the aligned operand, and of rounding in general are discussed.