The choices for mining of decentralized data are numerous, and we have developed techniques to enumerate and optimize decentralized frequent itemset counting. We introduce our heuristic approach to improve the performance of such techniques developed in ways similar to query processing in database systems. We also describe empirical results that validate our heuristic techniques.

Efficient mining of data presents a significant challenge, due to problems of combinatorial explosion in the space and time often required for such processing. While previous work has focused on improving the efficiency of the mining algorithms, we consider how the representation, organization, and access of the data may significantly affect performance, especially when I/O costs are also considered. By a simple analysis and comparison of the counting stage for the a priori association rules algorithm, we show that a "column-wise" approach to data access is often more efficient than the standard row-wise approach. We also provide the results of empirical simulations to validate our analysis. The key idea in our approach is that counting in the a priori algorithm with data accessed in a column-wise manner, significantly reduces the number of disk accesses required to identify itemsets with a minimum support in the database-primarily by reducing the degree to which data and counters need to be repeatedly brought into memory.

Coordinating distributed executions is achieved by two widely used approaches: process groups and transactions. Typically, the two represent a trade-off in terms of the degrees of consistency and performance. By applying transaction concurrency control techniques to characterize and design process group multicast orderings, we aim to provide aspects of both ends of the trade-off. In particular, we propose a framework in which each message multicast is regarded as a transaction. Appropriate message ordering protocols are devised and shown to be correct using a variant of concurrency control theory. Also, we are able do incorporate certain aspects of application semantics for which existing process group approaches are inadequate. Finally, our framework provides a means to characterize the performance of orderings to allow a comparison of different ordering protocols.

Several emerging applications need a high performance, main memory database for which typical memory systems may be inadequate. In particular, the processor memory bandwidth proves to be a major performance limiting factor. We present the design of a back end object oriented database board and argue for its use in implementing high performance, real time applications. Our board uses programmable logic enhanced memory (i.e., data memory with select computing abilities) which is a novel way to obviate the low bandwidth problem for data intensive processing. Our efforts differ significantly from database machines by being more general purpose and targeting the bandwidth issue at a different level of the memory hierarchy. We describe the utility of logic enhanced memory in meeting the needs of high performance databases.

Several search engines, catalogs, and filtering services aim to help users of the Internet deal with a growing information "overload". However, these tools typically are either generic in scope, or limited to the needs of a particular user without regard for reuse in some related context. We propose an approach and architecture for customized filtering and cataloging which bridges these two extremes. We allow users to create and maintain a metadatabase of information gathered over time by using modular filters created for specific needs or drawn from a standard library. This metadatabase, which may be regarded as a database view of the Internet, can then be accessed to locate information relevant to specific or more generic tasks. Potentially, our approach achieves greater flexibility and specificity as compared to currently available tools. We describe our preliminary design, implementation, and experimentation for our proof of concept prototypical effort.

With the advent of asynchronous transfer mode (ATM), network speeds are increasing substantially, and the greater communication bandwidth provides considerable potential for distributed applications. However, communication throughput delivered to the user applications has not increased as rapidly: network interfacing has become the next bottleneck. Consequently, better designs for network interfaces are essential to take full advantage of the higher-speed communication links such as the ATM. We present a novel hardware architecture for an ATM network interface employing memory with select on-chip data processing logic; i.e., logic-enhanced memory (LEM). We exhibit how LEM-based interfaces are particularly suitable for servers, where the majority of the operations are memory-intensive processing for client requests.

In order to execute a database program written in sequential code efficiently on a parallel processor, we develop the use of transaction concurrency control paradigms to resolve data dependencies dynamically.The sequential code is divided into small units for execution, and these units are executed concurrently as separate "transactions."Our approach en.sures that the concurrent execution of the smaller units is logically equivalent to the original sequential program.We present an order-preserving concurrency control strategy to execute concurrently the nested invocations that are generated by the parallelized execution of the database program.We present performance figures from a preliminary implementation to indicate the benefits of our strategy.Finally, we provide a rough analysis to gauge the overheads associated with our approach that would impact performance in a full-fledged implementation.1

Real-time database systems associate the concept of deadlines with transaction executions. Previous approaches use "best effort" techniques to schedule a given set of transactions to meet the deadlines as well as to ensure the consistency of the database. However, such approaches are inadequate for target applications which have "hard" real-time deadlines that need to be met in the event of crisis situations. In such cases, it is important to obtain contingency plans that may be invoked with guaranteed execution time characteristics. This paper presents an alternative model for real-time database systems in which deadlines are associated with "contingency" constraints rather than directly with transactions. Our approach leads to a predicate-based model that intrinsically incorporates both triggering and relative timing constraints regarding the transaction executions. We exhibit that selecting contingency plans with respect to various optimality criteria has inherent computational inefficiencies. We study the issues in scheduling of the selected plans with the focus on the contention among the transactions for data resources. Our results exhibit that the data contention, by itself, has a severe adverse impact on the schedulability of the deadline-constrained transactions. We discuss some of the practical implications of our results, and we suggest some counter-measures to handle the computational complexities.>

Distributed real-time transaction systems are useful for both real-time and high-performance database applications. Standard transaction management approaches that use the two-phase commit protocol suffer from its high costs and blocking behavior which is problematic in real-time computing environments. Our approach in this paper is to identify ways in which a commit protocol can be made adaptive in the sense that under situations that demand it, such as a transient local overload, the system can dynamically change to a different commitment strategy. The decision to do so can be taken autonomously at any site. The different commitment strategies exploit a trade-off between the cost of commitment and the obtained degree of atomicity. Our protocols are based on optimistic commitment strategies, and they rely on local compensatory actions to recover from non-atomic executions. We provide the necessary framework to study the logical and temporal correctness criteria, and we describe examples to illustrate the use of our strategies.

Network Partition failures in traditional Distributed Databases cause severe problems for transaction processing. The only way to overcome the problems of “blocking” behavior for transaction processing in the event of such failures is, effectively, to execute them at single sites. A new approach to data representation and distribution is proposed and it is shown to be suitable for failure-prone environments. We propose techniques for transaction processing, concurrency control and recovery for the new representation. Several properties that arise as a result of these methods, such as non-blocking behavior, independent recovery and high availability, suggest that the techniques could be profitably implemented in a distributed environment.

Abstract Hopfield nets are a class of neural networks that are often applied to optimisation problems. The role played by certain constants appearing in the interconnections are crucial to the computations. A bad choice of constant values results in the convergence of the system to states that represent extraneous results. This paper examines a discrete model of the nets which allows a better characterisation of the constants. The formal approach followed in this paper allows the specification of values to the constants that ensure convergence of the system to states that represent results that are not extraneous. Using the Hopfield nets terminology, we have identified methods to remove extraneous energy minima in the discrete version of the system. Since any simulation study of Hopfield nets on real computers must use discretised approximations to analog values, the results are of interest in a practical domain as well.