Matthias Ruhl

FOCS Conference 2004 Conference Paper

On the Streaming Model Augmented with a Sorting Primitive

• Gagan Aggarwal
• Mayur Datar
• Sridhar Rajagopalan
• Matthias Ruhl

The need to deal with massive data sets in many practical applications has led to a growing interest in computational models appropriate for large inputs. The most important quality of a realistic model is that it can be efficiently implemented across a wide range of platforms and operating systems. In this paper, we study the computational model that results if the streaming model is augmented with a sorting primitive. We argue that this model is highly practical, and that a wide range of important problems can be efficiently solved in this (relatively weak) model. Examples are undirected connectivity, minimum spanning trees, and red-blue line segment intersection, among others. This suggests that using more powerful, harder to implement models may not always be justified. Our main technical contribution is to show a hardness result for the "streaming and sorting" model, which demonstrates that the main limitation of this model is that it can only access one data stream at a time. Since our model is strong enough to solve "pointer chasing" problems, the communication complexity based techniques commonly used in showing lower bounds for the streaming model cannot be adapted to our model. We therefore have to employ techniques to obtain these results. Finally, we compare our model to a popular restriction of external memory algorithms that access their data mostly sequentially.

STOC Conference 2002 Conference Paper

Finding nearest neighbors in growth-restricted metrics

• David R. Karger
• Matthias Ruhl

Most research on nearest neighbor algorithms in the literature has been focused on the Euclidean case. In many practical search problems however, the underlying metric is non-Euclidean. Nearest neighbor algorithms for general metric spaces are quite weak, which motivates a search for other classes of metric spaces that can be tractably searched.In this paper, we develop an efficient dynamic data structure for nearest neighbor queries in growth-constrained metrics. These metrics satisfy the property that for any point q and number r the ratio between numbers of points in balls of radius 2r and r is bounded by a constant. Spaces of this kind may occur in networking applications, such as the Internet or Peer-to-peer networks, and vector quantization applications, where feature vectors fall into low-dimensional manifolds within high-dimensional vector spaces.

SODA Conference 2001 Conference Paper

Parallel processor scheduling with delay constraints

• Daniel W. Engels
• Jon Feldman
• David R. Karger
• Matthias Ruhl

FOCS Conference 1999 Conference Paper

The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals

• Jon Feldman
• Matthias Ruhl

We consider the Directed Steiner Network (DSN) problem, also called the Point-to-Point Connection problem, where given a directed graph G and p pairs {(s/sub 1/, t/sub 1/), .. ., (s/sub p/, t/sub p/)} of nodes in the graph, one has to find the smallest subgraph H of G that contains paths from s/sub i/ to t/sub i/ for all i. The problem is NP-hard for general p, since the Directed Steiner Tree problem is a special case. Until now, the complexity was unknown for constant p/spl ges/3. We prove that the problem is polynomially solvable if p is any constant number, even if nodes and edges in G are weighted and the goal is to minimize the total weight of the subgraph H. In addition, we give an efficient algorithm for the Strongly Connected Steiner Subgraph problem for any constant p, where given a directed graph and p nodes in the graph, one has to compute the smallest strongly connected subgraph containing the p nodes.