More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries (2009)
Grossi, Roberto, Orlandi, Alessio, Raman, Rajeev, Rao, S. Srinivasa
We consider the problem of representing, in a compressed format, a bit-vector $S$ of $m$ bits with $n$ 1s, supporting the following operations, where $b \in \{0, 1 \}$: $rank_b(S,i)$ returns the...
More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries (2009)
Grossi, Roberto, Orlandi, Alessio, Raman, Rajeev, Srinivasa Rao, S.
We consider the problem of representing, in a compressed format, a bit-vector $S$ of $m$ bits with $n$ $1$s, supporting the following operations, where $b \in \{ 0, 1 \}$: $rank_b(S,i)$ returns the...
More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries (2009)
Grossi, Roberto, Orlandi, Alessio, Raman, Rajeev, Srinivasa Rao, S.
We consider the problem of representing, in a compressed format, a bit-vector $S$ of $m$ bits with $n$ $1$s, supporting the following operations, where $b \in \{ 0, 1 \}$: $rank_b(S,i)$ returns the...
More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries (2009)
Grossi, Roberto, Orlandi, Alessio, Raman, Rajeev, Rao, S. Srinivasa
We consider the problem of representing, in a compressed format, a bit-vector~$S$ of $m$ bits with $n$ $mathbf{1}$s, supporting the following operations, where $b in { mathbf{0}, mathbf{1} }$:...
Engineering the LOUDS succinct tree representation (2008)
Abstract. Ordinal trees are arbitrary rooted trees where the children of each node are ordered. We consider succinct, or highly space-efficient, representations of (static) ordinal trees with n nodes...
DOI: 10.1007/s00453-004-1146-6 Representing Trees of Higher Degree 1 (2008)
David Benoit, Erik D. Demaine, J. Ian Munro, Rajeev Raman, Venkatesh Raman, S. Srinivasa Rao
Abstract. This paper focuses on space efficient representations of rooted trees that permit basic navigation in constant time. While most of the previous work has focused on binary trees, we turn our...
Ways of representing and efficiently manipulating data are central to many computer programs. Over the years, computer scientists have studied many different data structures for representing and...
Streaming Algorithms for Data in Motion (2008)
M. Hoffmann, S. Muthukrishnan, Rajeev Raman
Abstract. We propose two new data stream models: the reset model and the delta model, motivated by applications to databases, and to tracking the location of spatial points. We present algorithms for...
Computing Minimum Spanning Trees with Uncertainty (2008)
Erlebach, Thomas, Hoffmann, Michael, Krizanc, Danny, Mihal'ák, Matús, Raman, Rajeev
We consider the minimum spanning tree problem in a setting where information about the edge weights of the given graph is uncertain. Initially, for each edge $e$ of the graph only a set $A_e$, called...
Computing Minimum Spanning Trees with Uncertainty (2008)
Erlebach, Thomas, Hoffmann, Michael, Krizanc, Danny, Mihal'ák, Matús, Raman, Rajeev
We consider the minimum spanning tree problem in a setting where information about the edge weights of the given graph is uncertain. Initially, for each edge $e$ of the graph only a set $A_e$, called...
Computing Minimum Spanning Trees with Uncertainty (2008)
Erlebach, Thomas, Hoffmann, Michael, Krizanc, Danny, Mihal'ák, Matús, Raman, Rajeev
We consider the minimum spanning tree problem in a setting where information about the edge weights of the given graph is uncertain. Initially, for each edge $e$ of the graph only a set $A_e$, called...
25. Computing Minimum Spanning Trees with Uncertainty (2008)
Hoffmann, Michael, Erlebach, Thomas, Krizanc, Danny, Mihal'ák, Matús, Raman, Rajeev
We consider the minimum spanning tree problem in a setting where information about the edge weights of the given graph is uncertain. Initially, for each edge $e$ of the graph only a set $A_e$, called...
Delpratt, O'Neil, Rahman, Naila, Raman, Rajeev
Succinct DOM (SDOM), a DOM implementation, is written in C++, which is suitable for in-memory representation of large static XML documents. SDOM avoids the use of pointers, and is based upon succinct...
Random Sampling Techniques in Parallel Computation (2007)
Abstract. Random sampling is an important tool in the design of parallel algorithms. Using random sampling it is possible to obtain simple parallel algorithms which are e cient in practice. We will...
Routing on Meshes with Buses (2007)
Michael Kaufmann, Rajeev Raman, Jop F. Sibeyn
We consider the problem of routing packets on an n \Theta \Delta \Delta \Delta \Theta n MIMD mesh-connected array of processors augmented with row and column buses. We give lower bounds and...
Cache Analysis of Non-uniform Distribution Sorting Algorithms (2007)
We analyse the average-case cache performance of distribution sorting algorithms in the case when keys are independently but not necessarily uniformly distributed. The analysis is for both `in-place'...
Raman, Rajeev, Raman, Venkatesh, Satti, Srinivasa Rao
We consider the {\it indexable dictionary} problem, which consists of storing a set $S \subseteq \{0,...,m-1\}$ for some integer $m$, while supporting the operations of $\Rank(x)$, which returns the...
Deterministic Random Walks (2006)
Cooper, Joshua, Doerr, Benjamin, Spencer, Joel, Tardos, Gábor, Raman, Rajeev, Sedwgewick, Robert, ...
Jim Propp’s P-machine, also known as ‘rotor router model’ is a simple deterministic process that simulates random walk on a graph. Instead of distributing chips to randomly chosen neighbors, it...
A simple optimal representation for balanced parentheses (2004)
Richard F. Geary, Naila Rahman, Rajeev Raman
b Institute of Mathematical Sciences, Chennai 600 113, India. We consider succinct, or highly space-efficient, representations of a (static) string consisting of n pairs of balanced parentheses, that...
Succinct ordinal trees with level-ancestor queries (2004)
Richard F. Geary, Rajeev Raman
We consider succinct or space-efficient representations of trees that efficiently support a variety of navigation operations. We focus on static ordinal trees, i.e., arbitrary static rooted trees...
External-Memory Breadth-First Search with Sublinear I/O (2002)
Mehlhorn, Kurt, Meyer, Ulrich, Möhring, Rolf, Raman, Rajeev
Breadth-first search (BFS) is a basic graph exploration technique. We give the first external-memory algorithm for sparse undirected graphs with sublinear I/O. The best previous algorithm requires O(...
A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons (2002)
Berberich, Eric, Eigenwillig, Arno, Hemmer, Michael, Hert, Susan, Mehlhorn, Kurt, Schömer, Elmar, ...
We give an exact geometry kernel for conic arcs, algorithms for exact computation with low-degree algebraic numbers, and an algorithm for computing the arrangement of conic arcs that immediately...
Translating a Planar Object to Maximize Point Containment (2002)
Agarwal, Pankaj, Hagerup, Torben, Ray, Rahul, Sharir, Micha, Smid, Michiel, Welzl, Emo, ...
Let $C$ be a compact set in $\IR^2$ and let $S$ be a set of $n$ points in $\IR^2$. We consider the problem of computing a translate of $C$ that contains the maximum number, $\kappa^*$, of points...
SCIL - Symbolic Constraints in Integer Linear Programming. (2002)
Althaus, Ernst, Bockmayr, Alexander, Elf, Matthias, Kasper, Thomas, Jünger, Michael, Mehlhorn, Kurt, ...
We describe a new software system SCIL that introduces symbolic constraints into branch-and-cut-and-price algorithms for integer linear programs. Symbolic constraints are known from constraint...
Extending Reduction Techniques for the Steiner Tree Problem (2002)
Polzin, Tobias, Vahdati Daneshmand, Siavash, Möhring, Rolf, Raman, Rajeev
Exponential structures for efficient cache-oblivious algorithms (2002)
Michael A. Bender, Richard Cole, Rajeev Raman
Abstract. We present cache-oblivious data structures based upon exponential structures. These data structures perform well on a hierarchical memory but do not depend on any parameters of the...
On Relaxation Algorithms Based on Markov Random Fields. (1998)
Many computer vision problems can be formulated as computing the minimum energy states of thermal dynamic systems. However, due to the complexity of the energy functions, the solutions to the...
Randomized data structures for the dynamic closest-pair problem (1998)
Golin, Mordecai J., Raman, Rajeev, Schwarz, Christian, Smid, Michiel
We describe a new randomized data structure, the sparse partition, for solving the dynamic closest-pair problem. Using this data structure the closest pair of a set of n points in D-dimensional...
An Experimental Study of Word-Level Parallelism in Some Sorting Algorithms (1998)
Ed. Kurt Mehlhorn, Naila Rahman, Rajeev Raman
A number of algorithms for fundamental problems such as sorting, searching, priority queues and shortest paths have been proposed recently for the unit-cost RAM with word size w. These algorithms...
Three-dimensional acquisition and display system for ultrasonic imaging /--by Rajeev Raman. (1997)
Typescript.
Fast Algorithms for Shortest Paths and Sorting (1996)
A priority queue (pq) is said to be monotone if the value of the smallest element stored in the priority queue is a non-decreasing function of time. We consider the problem of maintaining a monotone...
A Summary of Shortest-Paths Results (1996)
This note attempts to summarize the best of the currently existing theoretical results on the single-source shortest paths problem for graphs with non-negative edge weights. The main purpose of this...
Improved Data Structures for Predecessor Queries in Integer Sets (1996)
We consider the problem of maintaining a dynamic ordered set of n integers in the range 0 : : 2^w - 1, under the operations of insertion, deletion and predecessor queries, on a unit-cost RAM with a...
Sorting in Linear Time? (1995)
Arne Andersson, Torben Hagerup, Stefan Nilsson, Rajeev Raman
We show that a unit-cost RAM with a word length of w bits can sort n integers in the range 0 : : 2 w \Gamma1 in O(n log log n) time, for arbitrary w log n, a significant improvement over the bound of...
Parallel Algorithms for Database Operations and a Database Operation for Parallel Algorithms (1995)
This paper establishes some significant links between two areas: (i) relational parallel database systems; and (ii) the design and analysis of parallel algorithms. The paper begins with a fundamental...
Lower bounds for set intersection queries (1995)
Dietz, Paul, Mehlhorn, Kurt, Raman, Rajeev, Uhrig, Christian
Pre-enhancement of chirp signal for inverse filtering in medical ultrasound (1994)
"Pre-enhancement of chirp signal for inverse filtering in medical ultrasound," Proceedings of the 16th Annual International Conference of IEEE Engineering in Medicine and Biology. Institute of...
Pre-enhancement of chirp signal for inverse filtering in medical ultrasound (1994)
"Pre-enhancement of chirp signal for inverse filtering in medical ultrasound," Proceedings of the 16th Annual International Conference of IEEE Engineering in Medicine and Biology. Institute of...
Very Fast Optimal Parallel Algorithms for Heap Construction (1994)
We give two algorithms for permuting n items in an array into heap order on a CRCW PRAM. The first is deterministic and runs in O(log log n) time and performs O(n) operations. This run-time is the...
Randomized data structures for the dynamic closest-pair problem (1993)
Mordecai Golin, Rajeev Raman, Christian Schwarz, Michiel Smid
Abstract. We describe a new randomized data structure, the sparse partition, for solving the dynamic closest-pair problem. Using this data structure the closest pair of a set of n points in...
Randomized Data Structures for the Dynamic Closest-Pair Problem (1993)
Mordecai Golin, Rajeev Raman, Christian Schwarz, Michiel Smid
We describe a new randomized data structure, the sparse partition, for solving the dynamic closestpair problem. Using this data structure the closest pair of a set of n points in D-dimensional space,...
Approximate and Exact Deterministic Parallel Selection (1993)
Shiva Chaudhuri, Torben Hagerup, Rajeev Raman, Im Stadtwald
The selection problem of size n is, given a set of n elements drawn from an ordered universe and an integer k with 1 k n, to identify the kth smallest element in the set. We study approximate and...
Randomized Routing on Meshes with Buses (1993)
Jop F. Sibeyn, Michael Kaufmann, Rajeev Raman
We give algorithms and lower bounds for the problem of routing k-permutations on d-dimensional MIMD meshes with additional buses. A straightforward argument shows that for all d 1, 2=3 \Delta n steps...
Lower Bounds for Set Intersection queries (1993)
Dietz, Paul, Mehlhorn, Kurt, Raman, Rajeev, Uhrig, Christian
Eliminating Amortization: On Data Structures with Guaranteed Response Time (1992)
Paul F. Dietz, thesis advisor. Thesis (Ph.D.) - Computer Science Department, University of Rochester. Simultaneously published in the Technical Report series.
"October 1992"--Cover.
The Power of Collision: Randomized Parallel Algorithms for Chaining and Integer Sorting (1991)
We address the problem of sorting n integers each in the range {l, ... ,m}, for m = n to the O(l), in parallel on the PRAM model of computation. We present a randomized algorithm that runs with very...
Optimal Sub-Logarithmic Time Integer Sorting on the CRCW PRAM (Note) (1991)
Rajasekaran and Reif considered the problem of sorting n integers, each in the range {l, ... , n}, in parallel on the CRCW PRAM, and gave a non-optimal sub-logarithmic time algorithm for this problem...
Generating Random Graphs Efficiently (1991)
We consider the algorithmic complexity of generating labeled (directed and undirected) graphs under various distributions. We describe three natural optimality criteria for graph generating...
A Constant Update Time Finger Search Tree (1989)
Levcopolous and Overmars [L088] described a search tree in which the time to insert or delete a key was O(1) once the position of the key to be inserted or deleted was known. Their data structure did...
On Relaxation Algorithms Based on Markov Random Fields (1987)
Many computer vision problems can be formulated as computing the minimum energy states of thermal dynamic systems. However, due to the complexity of the energy functions, the solutions to the...