Monitoring Regular Expressions on Out-of-Order Streams (2008)
We present an efficient algorithm for regular expression matching on streams with out of order data, while maintaining a small state and without complete stream reconstruction. We have implemented...
Monitoring Regular Expressions on Out-of-Order Streams (2008)
We present an efficient algorithm for regular expression matching on streams with out of order data, while maintaining a small state and without complete stream reconstruction. We have implemented...
Trends: Magnetic Disk vs. Semiconductor Memory Trends: Magnetic Disk vs. Tape (2008)
Theodore Johnson, Jeanne Behnke, Nasa Gsfc, V. Chinnaswamy, P. C. Hariharan, Ses Inc, ...
• Application pull
Tamraparni Dasu, Theodore Johnson, S. Muthukrishnan, Vladislav Shkapenyuk
Data mining research typically assumes that the data to be analyzed has been identified, gathered, cleaned, and pro-cessed into a convenient form. While data mining tools greatly enhance the ability...
Abstract Queuing Models of Tertiary Storage 1 (2008)
Large scale scientific projects generate and use huge amounts of data. For example, the NASA EOSDIS project is expected to archive one petabyte per year of raw satellite data. This data is made...
Michael Stonebraker, Mitch Cherniack, Magdalena Balazinska, Hari Balakrishnan, Michael J. Franklin, Joseph M. Hellerstein, ...
The Bulletin of the Technical Committee on Data Engineering is published quarterly and is distributed to all TC
Chuck Cranor, Theodore Johnson, Oliver Spatscheck, Vladislav Shkapenyuk
Managing a large scale network requires a network monitoring infrastructure. However, network monitoring is a difficult application. In response to shortcomings in the readily available tools, we...
An Optimal Algorithm for the Construction of the System Dependence Graph (2007)
Panos E. Livadas, Theodore Johnson
Program slicing can be used to aid in a variety of software maintenance activities including code understanding, code testing, debugging, and program reengineering. Program slicing (as well as other...
2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm (2007)
Theodore Johnson, Dennis Shasha
In a path-breaking paper last year Pat and Betty O'Neil and Gerhard Weikum proposed a self-tuning improvement to the Least Recently Used (LRU) buffer management algorithm[15]. Their improvement...
Finding A Minimum Cost Acceptable Path in Parallel (2007)
Theodore Johnson, Panos E. Livadas
We consider the problem of finding a minimum cost acceptable path on a toroidal grid graph, where each horizontal and each vertical edge have the same orientation. An acceptable path is closed path...
A Parallel Algorithm For Surface Triangulation (2007)
Theodore Johnson Panos, Theodore Johnson, Panos E. Livadas, Sunjay E. Talele
In many scientific fields, three dimensional surfaces must be reconstructed from a given collection of its surface points. Applications for surface reconstruction exist in medical research and...
Supporting Insertions and Deletions in Striped Parallel Filesystems (2007)
The dramatic improvements in the processing rates of parallel computers are turning many compute-bound jobs into IO-bound jobs. Parallel file systems have been proposed to better match IO throughput...
A Fair Fast Distributed Concurrent-Reader Exclusive-Writer Synchronization (2007)
Theodore Johnson And, Theodore Johnson, Hankil Yoon
Distributed synchronization is needed to arbitrate access to a shared resource in a message passing system. Reader/writer synchronization can improve efficiency and throughput if a large fraction of...
December Vol No, Letter Editor-in-chief, David Lomet, Letter Special, Christos Faloutsos, Peter J. Haas, ...
this paper we describe and evaluate several popular techniques for data reduction.
: The Data Mining Project at ATT Research (2007)
Stefan Berchtold, Christos Faloutsos, H. V. Jagadish, Theodore Johnson, Raymond Ng, Ken Ross
Revision : 6:1 The goal of this white paper is to define research directions. We start with the problem definition, present a classification of tools and issues, and list completed or on-going...
A simple correctness proof of the MCS contention-free lock (2007)
Theodore Johnson, Krishna Harathi
Mellor-Crummey and Scott present a spin-lock that avoids network contention by having processors spin on local memory locations. Their algorithm is equivalent to a lock-free queue with a special...
Towards a Toolkit for Data Analysis and Mining (2007)
Theodore Johnson, Laks Lakshmanan, Raymond Ng
Data analysis and mining is typically a multistep process, involving an iterated process of data space partitioning, aggregate computation, and data transformations. These activities typically...
Sensitivity Analysis of Frequency Counting (2007)
Many database optimization activities, such as prefetching, data clustering and partitioning, and buffer allocation, depend on the detection of hot spots in access patterns. While a database designer...
Distributed Shared Memory Using Reflective Memory: The LAM System (2007)
Roger Denton Theodore, Theodore Johnson
In the past, acceptance of Distributed Shared Memory (DSM) systems suffered because of poor performance. Performance has primarily been limited by the availability of an interconnect media whose...
Distributed Shared Memory Using Reflective Memory: The LAM System (2007)
Roger Denton, Theodore Johnson
In the past, acceptance of Distributed Shared Memory (DSM) systems suffered because of poor performance. Performance has primarily been limited by the availability of an interconnect media whose...
Designing Distributed Search Structures with Lazy Updates (2007)
Theodore Johnson, Padmashree Krishna
Very large database systems require distributed storage for expansibility and high throughput, which means that they need distributed search structures for fast and efficient access to the data. In a...
The Performance of Holding Versus Releasing Locks in a Multiprogrammed Multiprocessor (2007)
Theodore Johnson, Krishna Harathi
In a multiprogrammed multiprocessor system, existing lock based mechanisms hold the lock for a task during a context-switch. In this case, the time that a task holds a lock can be greatly increased,...
epsilon-Optimal Solutions to Nonlinear 0-1 Integer Programs Using the Subgradient Algorithm (2007)
Aravind Srinivasan, Suresh Chari, Pankaj Rohatgi, Zhijun Wu, Zhijun Wu, Theodore Johnson
S PARALLEL PROCESSING OF DISCRETE OPTIMIZATION PROBLEMS April 28-29, 1994 DIMACS Organized by P.M. Pardalos, M.G.C. Resende, and K.G. Ramakrishnan The talks in this workshop have covered a wide...
Q: A Low Overhead High Performance Buffer Management Replacement Algorithm (2007)
Theodore Johnson, Dennis Shasha, Gerhard Weikum Proposed
In a path-breaking paper last year Pat and Betty O'Neil and Gerhard Weikum proposed a self-tuning improvement to the Least Recently Used (LRU) buffer management algorithm[15]. Their improvement...
Distributed Computing and Databases for High Energy Physics (2007)
Principal Investigator, David G. Cassel, Kenneth Birman, Aleta Ricciardi, Michael Ogg, Keith Marzullo, ...
We are proposing to develop a fault-tolerant distributed computing and database system for use in High Energy Physics, but applicable to other disciplines. This system will allow us to solve the...
A Fair Fast Distributed Concurrent-Reader Exclusive-Writer Synchronization (2007)
Distributed synchronization is needed to arbitrate access to a shared resource in a message passing system. Reader/writer synchronization can improve efficiency and throughput if a large fraction of...
Dong-kweon Hong, Sharama Chakravarthy, Theodore Johnson
Abstract | Many real-time applications have very tight time constraints which couldn't be met by disk resident databases. For those applications, main memory database where entire database is...
Efficient Modeling of Massive Longitudinal Data Using Transition Arrays (2007)
Tamraparni Dasu, Theodore Johnson
We propose a fast, inexpensive technique for summarizing and modeling massive, multidimensional, longitudinal data sets using specialized summaries called transition arrays. We do this in three...
Database Exploration and Bellman (2007)
Theodore Johnson, Amit Marathe, Tamraparni Dasu
Large industrial-scale databases tend to be poorly structured, dirty, and very confusing. There are many reasons for this disorder, not the least of which is that the application domains themselves...
The 3W Model and Algebra for Uni ed Data Mining (2007)
Real data mining/analysis applications call for a framework which adequately supports knowledge discovery as a multi-step process, where the input of one mining operation can be the output of...
Abstract Analysis of the Access Patterns at GSFC Distributed Active Archive Center (2007)
Theodore Johnson, Jean-jacques Bedet
has been operational for more than two years. Its mission is to support existing and pre-
A heartbeat mechanism and its application in Gigascope (2005)
Theodore Johnson, S. Muthukrishnan, Vladislav Shkapenyuk, Oliver Spatscheck
Data stream management systems often rely on ordering properties of tuple attributes in order to implement non-blocking operators. However, query operators that work with multiple streams, such as...
A Heartbeat Mechanism and its Application in Gigascope (2005)
Theodore Johnson Muthukrishnan, Theodore Johnson, S. Muthukrishnan, Vladislav Shkapenyuk, Oliver Spatscheck
Data stream management systems often rely on ordering properties of tuple attributes in order to implement non-blocking operators. However, query operators that work with multiple streams, such as...
Streams, Security and Scalability (2005)
Theodore Johnson Muthukrishnan, Theodore Johnson, S. Muthukrishnan, Oliver Spatscheck, Divesh Srivastava
Network-based attacks, such as DDoS attacks and worms, are threatening the continued utility of the Internet. As the variety and the sophistication of attacks grow, early detection of potential...
Sampling algorithms in a stream operator (2005)
Theodore Johnson, S. Muthukrishnan, Irina Rozenbaum
Complex queries over high speed data streams often need to rely on approximations to keep up with their input. The research community has developed a rich literature on approximate streaming...
Holistic UDAFs at Streaming Speeds (2004)
Graham Cormode, Theodore Johnson, Flip Korn, S. Muthukrishnan
Many algorithms have been proposed to approximate holistic aggregates, such as quantiles and heavy hitters, over data streams. However, little work has been done to explore what techniques are...
Gigascope: a stream database for network applications (2003)
Chuck Cranor, Theodore Johnson, Oliver Spataschek
We have developed Gigascope, a stream database for network applications including traffic analysis, intrusion detection, router configuration analysis, network research, network monitoring, and and...
Efficient OLAP query processing in distributed data warehouses (2002)
Michael O. Akinde, Michael H. Böhlen, Theodore Johnson, Laks V. S, Divesh Srivastava
Abstract. The success of Internet applications has led to an explosive growth in the demand for bandwidth from ISPs. Managing an IP network requires collecting and analyzing network data, such as...
Mining database structure; or, how to build a data quality browser (2002)
Tamraparni Dasu, Theodore Johnson, S. Muthukrishnan, Vladislav Shkapenyukat
ABSTRACT Data mining research typically assumes that the data to be analyzed has been identified, gathered, cleaned, and processed into a convenient form. While data mining tools greatly enhance the...
Efficient OLAP query processing in distributed data warehouses (2002)
Michael O. Akinde, Michael H. B"ohlen, Theodore Johnson, Laks V. S
, and Divesh Srivastava 2 1 Aalborg University
How to Query Network Traffic Data Using Data Streams (2002)
Chuck Cranor, Theodore Johnson, Oliver Spatscheck
In this paper, we show how ad-hoc queries can be made in real time on network traffic data using a data stream model. We define a rich class of ordering properties and use them to label the...
Efficient OLAP Query Processing in Distributed Data Warehouses (2002)
Michael Akinde Strategy, Michael Akinde, Michael Böhlen, Theodore Johnson, Divesh Srivastava
sets of the detail data. Skalla generates distributed query evaluation plans (for the coordinator architecture) as a sequence of rounds, where a round consists of: (i) each local site performing some...
Efficient OLAP Query Processing in Distributed Data Warehouses (2002)
Michael O. Akinde, Michael H. Böhlen, Theodore Johnson, Laks V. S, Divesh Srivastava
The success of Internet applications has led to an explosive growth in the demand for bandwidth from ISPs. Managing an IP network requires collecting and analyzing network data, such as flow-level...
Efficient OLAP query processing in distributed data warehouses (2002)
Michael Akinde, Michael Böhlen, Theodore Johnson, Divesh Srivastava
The success of Internet applications has led to an explosive growth in the demand for bandwidth from ISPs. Managing an IP network includes complex data analysis (see, e.g., [1]) that can often be...
Mining database structure; or, how to build a data quality browser (2002)
Tamraparni Dasu, Theodore Johnson, S. Muthukrishnan, Vladislav Shkapenyuk
The MD-join: An operator for complex OLAP (2001)
Michael Akinde, Theodore Johnson, Samuel Kim
OLAP queries (i.e. group-by or cube-by queries with aggregation) have proven to be valuable for data analysis and exploration. Many decision support applications need very complex OLAP queries,...
Optimizing queries on compressed bitmaps (2000)
Sihem Amer-yahia, Theodore Johnson
Bitmap indices are used by DBMS's to accelerate decision support queries. A significant advantage of bitmap indices is that complex logical selection operations can be performed very quickly, by...
The 3W Model and Algebra for Unified Data Mining (2000)
Theodore Johnson, Raymond T. Ng
Real data mining/analysis applications call for a framework which adequately supports knowledge discovery as a multi-step process, where the input of one mining operation can be the output of...
Online Data Mining for Co-Evolving Time Sequences (2000)
Byoung-kee Yi, N. D. Sidiropoulos, Theodore Johnson, H. V. Jagadish, Christos Faloutsos, Alexandros Biliris
In many applications, the data of interest comprises multiple sequences that evolve over time. Examples include currency exchange rates, network traffic data. We develop a fast method to analyze such...
Online Data Mining for Co-Evolving Time Sequences (2000)
Byoung-kee Yi, N. D. Sidiropoulos, Theodore Johnson, H. V. Jagadish, Christos Faloutsos, ...
In many applications, the data of interest comprises multiple sequences that evolve over time. Examples include currency exchange rates, network traffic data. We develop a fast method to analyze such...
William Dumouchel, Christos Faloutsos, Peter J. Haas, Joseph M. Hellerstein, Yannis Ioannidis, H. V. Jagadish, ...
The Bulletin of the Technical Committee on Data Engineering is published quarterly and is distributed to all TC members. Its scope includes the design, implementation, modelling, theory and...
Tape group parity protection (1999)
Theodore Johnson, Sunil Prabhakar
We propose a new method of ensuring the redundant storage of information on tertiary storage, especially tape storage. Conventional methods for redundant data storage on tape include mirroring...
Range Selectivity Estimation for Continuous Attributes (1999)
Flip Korn, Theodore Johnson, H. V. Jagadish
Many commercial database systems maintain histograms to efficiently estimate query selectivities as part of query optimization. Most work on histogram design is implicitly geared towards discrete or...
Squashing Flat Files Flatter (1999)
William Dumouchel, Chris Volinsky, Theodore Johnson, Corinna Cortes, Daryl Pregibon
A feature of data mining that distinguishes it from "classical" machine learning (ML) and statistical modeling (SM) is scale. The community seems to agree on this yet progress to this point...
Hunting of the Snark - Finding Data Glitches using Data Mining Methods (1999)
Tamraparni Dasu, Theodore Johnson
Data quality is critical to data analysis because bad data can lead to incorrect conclusions. Problems with data are best detected early, before too much time and effort are spent ingesting and...
Scalable Data Space Partitioning In High Dimension (1999)
Theodore Johnson Tamraparni, Theodore Johnson, Tamraparni Dasu
A fundamental process in data mining is to approximate the joint distribution of a multivariate data set. A typical approach is to use histograms. However, conventional histograms (with...
Tape Group Parity Protection (1999)
Theodore Johnson, Sunil Prabhakar
We propose a new method of ensuring the redundant storage of information on tertiary storage, especially tape storage. Conventional methods for redundant data storage on tape include mirroring...
December Vol, Christos Faloutsos, Peter J. Haas, Joseph M. Hellerstein, Yannis Ioannidis, H. V. Jagadish, ...
this paper we describe and evaluate several popular techniques for data reduction. Historically, the primary need for data reduction has been internal to a database system, in a cost-based query...
Tape group parity protection (1999)
Theodore Johnson, Sunil Prabhakar
We propose a new method of ensuring the redundant storage of information on tertiary storage, especially tape storage. Conventional methods for redundant data storage on tape include mirroring...
An architecture for using tertiary storage in a data warehouse (1998)
In this paper, we present an architecture for a data warehouse that provides convenient, flexible, and high-performance access to tape-resident data. Data warehouses allow an organization to store...
Benchmarking tape system performance (1998)
Theodore Johnson, Ethan L. Miller
In spite of the rapid decrease in magnetic disk prices, tertiary storage (i.e., removable media in a robotic storage library) is becoming increasingly popular. The fact that so much data can be...
Performance measurements of robotic storage libraries (1998)
Robotic storage libraries extend the storage hierarchy to an additional layer of tertiary storage (or near-line storage). The near-line storage layer is slower but vaster than on-line (magnetic disk)...
Finding Idle Periods on Networks of Workstations (1998)
Peter Wyckoff Theodore, Theodore Johnson, Karpjoo Jeong
We present a simple technique for predicting the probability that an idle workstation will continue to be idle for i minutes, given that it has been idle for x minutes (i.e., find the remaining idle...
Analytic Performance Models of Robotic Storage Libraries: Status Update (1998)
Large tertiary storage systems tend to be expensive, so performance models are needed for sizing and for performance optimization. Several researchers (including ourselves) have attempted to supply...
Comparing Massive High-dimensional Data Sets (1998)
Theodore Johnson Tamraparni, Theodore Johnson, Tamraparni Dasu
The comparison of two data sets can reveal a great deal of information about the time-varying nature of an observed process. For example, suppose that the points in a data set represent a...
Piecewise Linear Regression For Massive Data Through Dataspheres (1998)
Tamraparni Dasu Theodore, Theodore Johnson
: We propose enhancing the fitting of linear regression models to massive multidimensional data by partitioning the data using a DataSphere (proposed in our previous work) and fitting piecewise...
Performance measurements of tertiary storage devices (1998)
Theodore Johnson, Ethan L. Miller
In spite of the rapid decrease in magnetic disk prices, tertiary storage (i.e., removable media in a robotic storage library) is becoming in-creasingly popular. The fact that so much data can be...
Tamraparni Dasu Theodore, Theodore Johnson
We propose a computationally inexpensive nonparametric method for the analysis of multivariate data. The data are ordered using the Mahalanobis distance of every point from a center of the data...
A High Performance Data Server Optimized for HEP Data (1997)
Karpjoo Jeong, Theodore Johnson, Hankil Yoon, Martin Lohner, Paul Avery
Introduction HEP event analysis provides a challenge for data management both because of the amount of data which must be processed many times and the fact that each analysis job can potentially...
The New Jersey Data Reduction Report (1997)
Daniel Barbar'a, William Dumouchel, Christos Faloutsos, Peter J. Haas, Joseph M. Hellerstein, Yannis Ioannidis, ...
this paper we describe and evaluate several popular techniques for data reduction. Historically, the primary need for data reduction has been internal to a database system, in a cost-based query...
A High Performance Data Server Optimized for HEP Data (1997)
Karpjoo Jeong, Theodore Johnson, Hankil Yoon, Martin Lohner, Paul Avery
This paper appears in the CD ROM version of Proceedings of the '97 Computing in High Energy Physics, Berlin, Germany, April, 1997. Preprint submitted to Elsevier Preprint 13 May exploiting HEP...
Karpjoo Jeong, Hankil Yoon, Theodore Johnson, Sanjay Ranka
this document, we describe HEP characteristics, discuss the design and implementation of HEPOS,
C.: The New Jersey Data Reduction Report (1997)
Daniel Barbara, William Dumouchel, Christos Faloutsos, Peter J. Haas, Joseph M. Hellerstein, Yannis Ioannidis, ...
There is often a need to get quick approximate answers from large databases. This leads to a need for data reduction. There are many di erent approaches to this problem, some of them not...
A concurrent dynamic task graph (1996)
Task graphs are used for scheduling tasks on parallel processors when the tasks have dependencies. If the execution of the program is known ahead of time, then the tasks can be statically and...
Selection Predicate Indexing for Active Databases Using Interval Skip Lists (1996)
Eric N. Hanson, Theodore Johnson
A new, efficient selection predicate indexing scheme for active database systems is introduced. The selection predicate index proposed uses an interval index on an attribute of a relation or object...
Analysis of the access patterns at GSFC Distributed Active Archive Center (1996)
Theodore Johnson, Jean-jacques Bedet
this paper, we first study some of the user requests patterns and their impact on the on the overall system loading. Rather than examining all orders submitted at GSFC DAAC in 1995, a subset has been...
Hierarchically Split Cube Forests for Decision Support: description and tuned design (1996)
Theodore Johnson, Dennis Shasha
The paradigmatic view of data in decision support consists of a set of dimensions (e.g., location, product, time period, ...), each encoding a hierarchy (e.g., location has hemisphere, country,...
An Analytical Performance Model of Robotic Storage Libraries (1996)
Theodore Johnson Dept, Theodore Johnson
Large scale scientific projects generate and use huge amounts of data. For example, the NASA EOSDIS project is expected to archive one petabyte per year of raw satellite data. This data is made...
Selection Predicate Indexing for Active Databases Using Interval Skip Lists (1996)
A new, efficient selection predicate indexing scheme for active database systems is introduced. The selection predicate index proposed uses an interval index on an attribute of a relation or object...
An Analytical Performance Model of Robotic Storage Libraries (1996)
Large scale scientific projects generate and use huge amounts of data. For example, the NASA EOSDIS project is expected to archive one petabyte per year of raw satellite data. This data is made...
An Analytical Performance Model of Robotic Storage Libraries (1996)
Large scale scientific projects generate and use huge amounts of data. For example, the NASA EOSDIS project is expected to archive one petabyte per year of raw satellite data. This data is made...
Analysis of the access patterns at GSFC Distributed Active Archive Center (1996)
Theodore Johnson, Jean-jacques Bedet
this paper, we first study some of the user requests patterns and their impact on the on the overall system loading. Rather than examining all orders submitted at GSFC DAAC in 1995, a subset has been...
A Fair Fast Distributed Concurrent-Reader Exclusive-Writer Synchronization (1996)
Distributed synchronization is needed to arbitrate access to a shared resource in a message passing system. Reader/writer synchronization can improve efficiency and throughput if a large fraction of...
Approximate Analysis of Reader/Writer Queues (1995)
Theodore Johnson Dept, Theodore Johnson
We analyze the performance of queues that serve readers and writers. Readers are served concurrently, while writers require exclusive service. We approximately analyze a first-come-first-serve (FCFS)...
Characterizing the Performance of Algorithms for Lock-free Objects (1995)
Concurrent access to shared data objects must be regulated by a concurrency control protocol to ensure correctness. Many concurrency control protocols require that a process set a lock on the data it...
Analysis of the Request Patterns to the NSSDC On-line Archive (1995)
NASA missions, both for earth science and for space science, collect huge amounts of data, and the rate at which data is being gathered is increasing. For example, the EOSDIS project is expected to...
Load Balancing in a Distributed Processing System for High-Energy Physics (UFMulti) (1995)
Jagadeesh Kasaraneni, Theodore Johnson, Paul Avery
Experiments in High Energy Physics (HEP) generate tremendous amounts of data. For example, the accelerator at CERN is expected to generate petabytes per year. New HEP discoveries require that the...
Analysis of the Request Patterns to the NSSDC On-line Archive (1995)
NASA missions# both forearth science and for space science# collect huge amounts of data# and the rate at which data is being gathered is increasing. For example# the EOSDIS project is expected to...
Designing a Distributed Queue (1995)
A common paradigm for distributed computing is the producer-consumer model. One set of processes produce objects that are consumed by another set of processes. These objects might be data, resources,...
Analysis of the Request Patterns to the NSSDC On-line Archive (1995)
Theodore Johnson, Carlos Guerra
The successful implementation of mass storage archives require careful attention to performance optimizations, to ensure that the system can handle the offered load. However, performance...
Highly Scalable Data Balanced Distributed B-trees (1995)
Padmashree Krishna, Theodore Johnson
Scalable distributed search structures are needed to maintain large volumes of data and for parallel databases. In this paper, we analyze the performance of two large scale data-balanced distributed...
A Performance Comparison of Fast Distributed Synchronization Algorithms (1994)
Distributed synchronization is an essential component of parallel and distributed computing. Several fast and low-overhead distributed synchronization algorithms have been proposed. Each of these...
A New Approach to Finding Objects in Programs (1994)
Panos Livadas Theodore, Theodore Johnson
Software maintenance is difficult and costly because the maintainer must understand the existing relationships in the maintained code. The maintainer's job can be made considerably easier if the...
A Distributed, Replicated, Data-Balanced Search Structure (1994)
Theodore Johnson, Adrian Colbrook
Many concurrent dictionary data structures have been proposed, but usually in the context of shared memory multiprocessors. In this paper, we present an algorithm for a concurrent distributed B-tree...
New Rules for Early Delivery in an Atomic Multicast System (1994)
Theodore Johnson, Lionnel Maugis
An atomic multicast facility guarantees that a multicast message is delivered to the multicast group, and that every process receives messages in the same order. The availability of an atomic...
Implementing Distributed Search Structures (1994)
Padmashree Krishna, Theodore Johnson
Distributed search structures are useful for parallel databases and in maintaining distributed storage systems. In this paper we discuss some issues in the design and implementation of distributed...
Two Approaches for High Concurrency in Multicast-Based Object Replication (1994)
Theodore Johnson, Theodore Johnson, Lionnel Maugis, Lionnel Maugis
This report presents a replica control protocol for atomic objects. The protocol is derived from an atomic broadcast primitive, and places constraints on the delivery of messages to provide a...
The Performance of Concurrent Data Structure Algorithms (1994)
This thesis develops a validated model of concurrent data structure algorithm performance, concentrating on concurrent B-trees. The thesis first develops two analytical tools, which are explained in...
A Simple Approach to Distributed Pools (1994)
Benedict M. Rafanello, Theodore Johnson
This paper presents a simple solution to the distributed producer/consumer problem. This solution, which is based upon the notion of a distributed pool, is described in detail and its performance...
A Comparison of Fast and Low Overhead Distributed Priority Locks (1994)
Theodore Johnson, Richard Newman-wolfe
Distributed synchronization is necessary to coordinate the diverse activities of a distributed system. Priority synchronization is needed for real time systems, or to improve the performance of...
A Fast and Low Overhead Distributed Priority Lock (1994)
Theodore Johnson, Richard Newman-wolfe
Distributed synchronization is necessary to coordinate the diverse activities of a distributed system. Priority synchronization is needed for real time systems, or to improve the performance of...
Interruptible Critical Sections (1994)
Theodore Johnson, Krishna Harathi
We present a new approach to synchronization on uniprocessors with special applicability to embedded and real-time systems. Existing methods for synchronization in real-time systems are pessimistic,...
Interruptible Critical Sections for Real-time Systems (1993)
In this paper, we present a new approach to synchronization in real-time systems. Existing methods for synchronization in real-time systems are pessimistic, and use blocking to enforce concurrency...
Lazy Updates for Distributed Search Structures (1993)
Theodore Johnson, Padmashree Krishna
Very large database systems require distributed storage, which means that they need distributed search structures for fast and efficient access to the data. In this paper, we present an approach to...
A Prioritized Multiprocessor Spin Lock (1993)
Theodore Johnson, Krishna Harathi
In this paper, we present the PR-lock, a prioritized spin-lock mutual exclusion algorithm for real time systems. The PR-lock is a contention-free spin lock, in which blocked processes spin on locally...
A Concurrent Dynamic Task Graph (1993)
Task graphs are used for scheduling tasks on parallel processors when the tasks have dependencies. If the execution of the program is known ahead of time, then the tasks can be statically and...
A Distributed Data-Balanced Dictionary Based on the B-link Tree (1992)
Theodore Johnson, Adrian Colbrook
Many concurrent dictionary data structures have been proposed, but usually in the context of shared memory multiprocessors. In this paper, we present an algorithm for a concurrent distributed B-tree...
On the Natural Growth of Random Forests (1992)
Theodore Johnson, Harold S. Stone
We explore several aspects of the natural growth of random forests. We show that if initially there are k single-node forests and N nodes to add to the forest, and every forest node is equally likely...
The Interval Skip List: A Data Structure for Finding All Intervals That Overlap a Point (1992)
Eric N. Hanson, Theodore Johnson
A problem that arises in computational geometry, pattern matching, and other applications is the need to quickly determine which of a collection of intervals overlap a point. Requests of this type...
Space Efficient Parallel Buddy Memory Management (1992)
Shared memory multiprocessor systems need efficient dynamic storage allocators, both for system purposes and to support parallel programs. Memory managers are often based on the buddy system, which...
Implementing Distributed Search Structures (1992)
Padmashree Krishna, Theodore Johnson
Distributed search structures are useful for parallel databases and in maintaining distributed storage systems. Although a considerable amount of research has been done on developing parallel search...
A Distributed Data-balanced Dictionary Based on the B-link Tree (1992)
Theodore Johnson, Adrian Colbrook
Many concurrent dictionary data structures have been proposed, but usually in the context of shared memory multiprocessors. In this paper, we present an algorithm for a concurrent distributed B-tree...
Analysis of Optimistic Concurrency Control Revisited (1992)
Ryu and Thomasian have analyzed several varieties of optimistic concurrency control under two assumptions: that the characteristics of a transaction remain constant throughout its execution, and that...
Vlist: A Vectorized List (1992)
Many current supercomputers use vector or SIMD processors to exploit parallelism inexpensively and effectively. Many fast and efficient kernels have been written for vector and matrix computations,...
A Concurrent Fast-Fits Memory Manager (1991)
Shared memory multiprocessor systems need efficient dynamic storage allocators, both for system purposes and to support parallel programs. Most memory manager algorithms are based either on a free...
Non-Blocking Algorithms for Concurrent Data Structures (1991)
Sundeep Prakash, Yann-hang Lee, Theodore Johnson
Non-blocking algorithms for concurrent data structure guarantee that a data structure is always accessible, in contrast to blocking algorithms in which a slow or halted process can render part or all...
A Highly Concurrent Priority Queue Based on the B-link Tree (1991)
We present a highly concurrent priority queue algorithm based on the B-link tree, which is a B + -tree in which every node has a pointer to its right sibling. The algorithm is built on the concurrent...
Reduction of school costs through tuition-paying pupils ... /--by Theodore Johnson. (1940)
Typescript (photocopy)