Abstract On External Memory Graph Traversal (2008)
Adam L. Buchsbaum, Michael Goldwasser, Suresh Venkatasubramanian, Jeffery R. Westbrook
We describe a new external memory data structure, the buffered repository tree, and use it to provide the first non-trivial external memory algorithm for directed breadth-first search (BFS) and an...
Abstract Fast Prefix Matching of Bounded Strings (2008)
Adam L. Buchsbaum, Glenn S. Fowler, Kiem-phong Vo
Longest Prefix Matching (LPM) is the problem of finding which string from a given set is the longest prefix of another, given string. LPM is a core problem in many applications, including IP routing,...
DOI: 10.1007/s00453-004-1138-6 Biased Skip Lists 1 (2008)
Amitabha Bagchi, Adam L. Buchsbaum, Michael T. Goodrich
Abstract. We design a variation of skip lists that performs well for generally biased access sequences. Given n items, each with a positive weight wi,1 ≤ i ≤ n, the time to access item i is O(1 +...
Three-dimensional layers of maxima (2008)
Adam L. Buchsbaum, Michael T. Goodrich
Abstract. We present an O(n log n)-time algorithm to solve the threedimensional layers-of-maxima problem, an improvement over the prior O(n log n log log n)-time solution. A previous claimed O(n log...
Abstract On External Memory Graph Traversal (2008)
Adam L. Buchsbaum, Michael Goldwasser, Suresh Venkatasubramanian
We describe a new external memory data structure, the buffered repository tree, and use it to provide the first non-trivial external memory algorithm for directed breadth-first search (BFS) and an...
Directed Graphs and Rectangular Layouts (Extended abstract) (2008)
Adam L. Buchsbaum, Emden R. Gansner, Suresh Venkatasubramanian
Abstract. This paper deals with the problem, arising in practice, of drawing a directed graph as a collection of disjoint, isothetic rectangles, where the rectangles of the nodes of each edge must...
DOI: 10.1007/s00453-004-1082-5 Three-Dimensional Layers of Maxima 1 (2008)
Adam L. Buchsbaum, Michael T. Goodrich
Abstract. We present an O(n log n)-time algorithm to solve the three-dimensional layers-of-maxima problem. This is an improvement over the prior O(n log n log log n)-time solution. A previous claimed...
Amitabha Bagchi, Adam L. Buchsbaum, Michael T. Goodrich
We design a variation of skip lists that performs well for generally biased access sequences. Given n items, each with a positive weight w i , 1 i n, the time to access item i is O 1 + log , where W...
Rectangular Layouts and Contact Graphs (2007)
Buchsbaum, Adam L., Gansner, Emden R., Procopiuc, Cecilia M., Venkatasubramanian, Suresh
Contact graphs of isothetic rectangles unify many concepts from applications including VLSI and architectural design, computational geometry, and GIS. Minimizing the area of their corresponding {\em...
Rectangular Layouts and Contact Graphs (2007)
Buchsbaum, Adam L., Gansner, Emden R., Procopiuc, Cecilia M., Venkatasubramanian, Suresh
Contact graphs of isothetic rectangles unify many concepts from applications including VLSI and architectural design, computational geometry, and GIS. Minimizing the area of their corresponding {\em...
Rectangular Layouts and Contact Graphs (2007)
Buchsbaum, Adam L., Gansner, Emden R., Procopiuc, Cecilia M., Venkatasubramanian, Suresh
Contact graphs of isothetic rectangles unify many concepts from applications including VLSI and architectural design, computational geometry, and GIS. Minimizing the area of their corresponding {\em...
Restricted strip covering and the sensor cover problem (2007)
Adam L. Buchsbaum, Alon Efrat, Shaili Jain, Suresh Venkatasubramanian, Ke Yi
Suppose we are given a set of objects that cover a region and a duration associated with each object. Viewing the objects as jobs, can we schedule their beginning times to maximize the length of time...
Restricted strip covering and the sensor cover problem (2007)
Adam L. Buchsbaum, Alon Efrat, Shaili Jain, Suresh Venkatasubramanian, Ke Yi
Suppose we are given a set of objects that cover a region and a duration associated with each object. Viewing the objects as jobs, can we schedule their beginning times to maximize the length of time...
Rectangular Layouts and Contact Graphs (2006)
Buchsbaum, Adam L., Gansner, Emden R., Procopiuc, Cecilia M., Venkatasubramanian, Suresh
Contact graphs of isothetic rectangles unify many concepts from applications including VLSI and architectural design, computational geometry, and GIS. Minimizing the area of their corresponding {\em...
Restricted Strip Covering and the Sensor Cover Problem (2006)
Buchsbaum, Adam L., Efrat, Alon, Jain, Shaili, Venkatasubramanian, Suresh, Yi, Ke
Given a set of objects with durations (jobs) that cover a base region, can we schedule the jobs to maximize the duration the original region remains covered? We call this problem the sensor cover...
Amitabha Bagchi, Adam L. Buchsbaum, Michael T. Goodrich
We design a variation of skip lists that performs well for generally biased access sequences. Given n items, each with a positive weight w i, 1
Small parity-check erasure codes - exploration and observations (2005)
James S. Plank, Adam L. Buchsbaum, Rebecca L. Collins, Michael G. Thomason
Erasure codes have profound uses in wide- and mediumarea storage applications. While infinite-size codes have been developed with optimal properties, there remains a need to develop small codes with...
Amitabha Bagchi, Adam L. Buchsbaum, Michael T. Goodrich
We design a variation of skip lists that performs well for generally biased access sequences. Given � n items, each with a positive weight wi, 1 ≤ i ≤ n, the time to access item i is O 1 + log...
Amitabha Bagchi, Adam L. Buchsbaum, Michael T. Goodrich
Abstract. We design a variation of skip lists that performs well for generally biased access sequences. Given n items, each � with a positive weight wi, 1 ≤ i ≤ n, the time to access item i is...
1 Small Parity-Check Erasure Codes- Exploration and Observations (2004)
James S. Plank, Adam L. Buchsbaum, Rebecca L. Collins, Michael G. Thomason, Michael G. Thomason
This paper has been submitted for publication. Please see the above web site for up-to-date information about the publication status of the paper.
Fast prefix matching of bounded strings (2003)
Adam L. Buchsbaum, Glenn S. Fowler, Balachander Krishnamurthy, Kiem-phong Vo, Jia Wang
Longest Prefix Matching (LPM) is the problem of finding which string from a given set is the longest prefix of another, given string. LPM is a core problem in many applications, including IP routing,...
OPT versus LOAD in Dynamic Storage Allocation (2003)
Adam L. Buchsbaum, Howard Karloff, Claire Kenyon, Nick Reingold, Mikkel Thorup
Dynamic Storage Allocation is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. Where L = LOAD...
Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on Trees and Graphs (2002)
Buchsbaum, Adam L., Georgiadis, Loukas, Kaplan, Haim, Rogers, Anne, Tarjan, Robert E., Westbrook, Jeffery R.
We present algorithms that run in linear time on pointer machines for a collection of problems, each of which either directly or indirectly requires the evaluation of a function defined on paths in a...
Improving Table Compression with Combinatorial Optimization (2002)
Buchsbaum, Adam L., Fowler, Glenn S., Giancarlo, Raffaele
We study the problem of compressing massive tables within the partition-training paradigm introduced by Buchsbaum et al. [SODA'00], in which a table is partitioned by an off-line training procedure...
Improving Table Compression with Combinatorial Optimization (2002)
Adam L. Buchsbaum, Glenn S. Fowler, Raffaele Giancarlo
We study the problem of compressing massive tables within the partition-training paradigm introduced by Buchsbaum et al. [SODA'00], in which a table is partitioned by an off-line training...
CNOP - {A} Package for Constrained Network Optimization (2001)
Mehlhorn, Kurt, Ziegelmann, Mark, Buchsbaum, Adam L., Snoeyink, Jack
We present a generic package for resource constrained network optimization problems. We illustrate the flexibility and the use of our package by solving four applications: route planning, curve...
On external memory graph traversal (2000)
Adam L. Buchsbaum, Michael Goldwasser, Suresh Venkatasubramanian, Jeffery R. Westbrook
We describe a new external memory data structure, the buffered repository tree, and use it to provide the first non-trivial external memory algorithm for directed breadth-first search (BFS) and an...
On external memory graph traversal (2000)
Adam L. Buchsbaum, Michael Goldwasser, Suresh Venkatasubramanian, Jeffery R. Westbrook
We describe a new external memory data structure, the buffered repository tree, and use it to provide the first non-trivial external memory algorithm for directed breadth-first search (BFS) and an...
On the Determinization of Weighted Finite Automata (2000)
Adam L. Buchsbaum, Raffaele Giancarlo, Jeffery R. Westbrook
Abstract. We study determinization of weighted finite-state automata (WFAs), which has important applications in automatic speech recognition (ASR). We provide the first polynomial-time algorithm to...
Range Searching Over Tree Cross Products (2000)
Adam L. Buchsbaum, Michael T. Goodrich, Jeffery R. Westbrook
We introduce the tree cross-product problem, which abstracts a data structure common to applications in graph visualization, string matching, and software analysis. We design solutions with a variety...
On The Determinization Of Weighted Finite Automata (2000)
Adam L. Buchsbaum, Raffaele Giancarlo, Jeffery R. Westbrook, R. Westbrook
We study the problem of constructing the deterministic equivalent of a nondeterministic weighted finite-state automaton (WFA). Determinization of WFAs has important applications in automatic speech...
A New, Simpler Linear-Time Dominators Algorithm (1999)
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
this article is organized as follows. Section 2 outlines Lengauer and Tarjan's approach. Section 3 gives a broad overview of our algorithm and differentiates it from previous work. Section 4...
A Functional Approach to External Graph Algorithms (1999)
James Abello, Adam L. Buchsbaum, Jeffery R. Westbrook
We present a new approach for designing external graph algorithms and use it to design simple deterministic and randomized external algorithms for computing connected components, minimum spanning...
A new, simpler linear-time dominators algorithm (1998)
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
We present a new linear-time algorithm to nd the immediate dominators of all vertices in a owgraph. Our algorithm is simpler than previous linear-time algorithms: rather than employ complicated data...
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
We present two new data structure tools---disjoint set union with bottom-up linking, and pointer-based radix sort---and combine them with bottom-level microtrees to devise the first linear-time...
A Functional Approach to External Graph Algorithms (1998)
James Abello, Adam L. Buchsbaum, Jeffery R. Westbrook
Abstract. We present a new approach for designing external graph algorithms and use it to design simple external algorithms for computing connected components, minimum spanning trees, bottleneck...
Shrinking Language Models by Robust Approximation (1998)
Adam L. Buchsbaum, Raffaele Giancarlo, Jeffery R. Westbrook
We study the problem of reducing the size of a language model while preserving recognition performance (accuracy and speed). A successful approach has been to represent language models by weighted...
A Functional Approach to External Graph Algorithms (1998)
James Abello, Adam L. Buchsbaum, Jeffery R. Westbrook
We present a new approach for designing external graph algorithms and use it to design simple deterministic and randomized external algorithms for computing connected components, minimum spanning...
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
We present two new data structure tools---disjoint set union with bottom-up linking, and pointer-based radix sort---and combine them with bottom-level microtrees to devise the first linear-time...
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
We present two new data structure tools—disjoint set union with bottom-up linking, and pointer-based radix sort—and combine them with bottom-level microtrees to devise the first linear-time...
A comparison of head transducers and transfer for a limited domain translation application (1997)
Hiyan Alshawi, Adam L. Buchsbaum
We compare the effectiveness of two related • machine translation models applied to the same limited-domain task. One is a trans-fer model with monolingual head automata for analysis and...
StateTransition Cost Functions and an Application to Language Translation (1997)
Hiyan Alshawi, Adam L. Buchsbaum
We define a general method for ranking the solutions of a search process by associating costs with equivalence classes of state transitions of the process. We show how the method accommodates models...
State-Transition Cost Functions and an Application to Language Translation (1997)
Hiyan Alshawi, Adam L. Buchsbaum
We define a general method for ranking the solutions of a search process by associating costs with equivalence classes of state transitions of the process. We show how the method can accommodate...
On Reduction via Determinization of Speech-Recognition Lattices (1997)
Adam L. Buchsbaum, Raffaele Giancarlo, Jeffery R. Westbrok
We establish a framework for studying the behavior of automatic speech recognition (ASR) lattices (viewed as automata) undergoing determinization. Using this framework, we provide initial insights...
A Comparison of Head Transducers and Transfer for a Limited Domain Translation Application (1997)
Hiyan Alshawi, Adam L. Buchsbaum, Fei Xia
We compare the effectiveness of two related machine translation models applied to the same limited-domain task. One is a transfer model with monolingual head automata for analysis and generation; the...
Methods for Optimal Text Selection (1997)
Construction of both text-to-speech synthesis (TTS) and automatic speech recognition (ASR) systems involves usage of speech data bases. These data bases usually consist of read text, which means that...
Head Automata and Bilingual Tiling: Translation with Minimal Representations (1996)
Hiyan Alshawi, Adam L. Buchsbaum
We present a language model consisting of a collection of costed bidirectional finite state automata associated with the head words of phrases. The model is suitable for incremental application of...
Buchsbaum, Adam L, Sundar, Rajamani, Tarjan, Robert E
A deque with heap order is a linear list of elements with real-valued keys that allows insertions and deletions of elements at both ends of the list. It also allows the findmin (alternatively...
Buchsbaum, Adam L, Sundar, Rajamani, Tarjan, Robert E
A deque with heap order is a linear list of elements with real-valued keys that allows insertions and deletions of elements at both ends of the list. It also allows the findmin (alternatively...
Adam L. Buchsbaum, Rajamani Sundar, Robert E. Tarjan
A deque with heap order is a linear list of elements with real-valued keys which allows insertions and deletions of elements at both ends of the list. It also allows the findmin (equivalently...
Confluently Persistent Deques via Data-Structural Bootstrapping (1993)
Adam L. Buchsbaum, Robert E. Tarjan
We introduce data-structural bootstrapping, a technique to design data structures recursively, and use it to design confluently persistent deques. Our data structure requires O(log 3 k) worstcase...
Lazy Structure Sharing for Query Optimization (1993)
Adam L. Buchsbaum, Rajamani Sundar, Robert E. Tarjan
We study lazy structure sharing as a tool for optimizing equivalence testing on complex data types. We investigate a number of strategies for a restricted case of the problem and provide upper and...
Monte Carlo And Markov Chain Techniques for Network Reliability and Sampling (1992)
Adam L. Buchsbaum, Milena Mihail
We outline a heuristic to approximate various reliability related parameters of communications networks under link failures. Our scheme is based on Monte Carlo and Markov chain simulation techniques....
Determining Single Connectivity in Directed Graphs (1992)
Adam L. Buchsbaum, Martin C. Carlisle
In this paper, we consider the problem of determining whether or not a directed graph contains a pair of vertices connected by two distinct simple paths; if it does not, we say it is singly...