# Abstracts – University of Copenhagen

ARCO > ARCO Events > 21st ARCO-meeting 2015 at DTU > Abstracts

# Abstracts

We consider space-bounded computations on a random-access machine (RAM) where the input is given on a read-only random-access medium, the output is to be produced to a write-only sequential-access medium, and the available workspace allows random reads and writes but is of limited capacity. The length of the input is $N$ elements, the length of the output is limited by the computation, and the capacity of the workspace is $O(S)$ bits for some predetermined parameter $S$.

We present a state-of-the-art priority queue---called an adjustable navigation pile---for this restricted RAM model. Under some reasonable assumptions, our priority queue supports $\mathit{minimum}$ and $\mathit{insert}$ in $O(1)$ worst-case time and $\mathit{extract}$ in $O(N/S + \lg{} S)$ worst-case time for any $S \geq \lg{} N$. (We use $\lg{} x$ as a shorthand for $\log_2(\max\set{2, x})$.)

We show how to use this data structure to sort $N$ elements and to compute the convex hull of $N$ points in the two-dimensional Euclidean space in $O(N^2/S + N \lg{} S)$ worst-case time for any $S \geq \lg{} N$.

Following a known lower bound for the space-time product of any branching program for finding unique elements, both our sorting and convex-hull algorithms are optimal.

The adjustable navigation pile has turned out to be useful when designing other space-efficient algorithms, and we expect that it will find its way to yet other applications.

## Thomas Dybdahl Ahle, "On the Complexity of Inner Product Similarity Join"

A number of tasks in classification, information retrieval, recommendation systems, and record linkage reduce to the core problem of inner product similarity join (IPS join): identifying pairs of vectors in a collection that have a sufficiently large inner product. IPS join is well understood when vectors are normalized and some approximation of inner products is allowed. However, the general case where vectors may have any length appears much more challenging. Recently, new upper bounds based on asymmetric locality-sensitive hashing (ALSH) and asymmetric embeddings have emerged, but little has been known on the lower bound side. In this paper we initiate a systematic study of inner product similarity join, showing new lower and upper bounds.

### Our main results are:

* Approximation hardness of IPS join in subquadratic time, assuming the strong exponential time hypothesis.

* New upper and lower bounds for (A)LSH-based algorithms. In particular, we show that asymmetry can be avoided by relaxing the LSH definition to only consider the collision probability of distinct elements.

* A new indexing method for IPS based on linear sketches, implying that our hardness results are not far from being tight.

Our technical contributions include new asymmetric embeddings that may be of independent interest. At the conceptual level we strive to provide greater clarity, for example by distinguishing among signed and unsigned variants of IPS join and shedding new light on the effect of asymmetry.

## Patrick Cording, "Access, rank, and select in grammar-compressed strings"

Given a string $S$ of length $N$ on a fixed alphabet of $\sigma$ symbols, a grammar compressor produces a context-free grammar $G$ of size $n$ that generates $S$ and only $S$. In this paper we describe data structures to support the following operations on a grammar-compressed string: $\access(S,i,j)$ (return substring $S[i,j]$), $\rank_c(S,i)$ (return the number of occurrences of symbol $c$ before position $i$ in $S$), and $\select_c(S,i)$ (return the position of the $i$th occurrence of $c$ in $S$).

Our main result for $\access$ is a method that requires $\O(n\log N)$ bits of space and $\O(\log N+m/\log_\sigma N)$ time to extract $m=j-i+1$ consecutive symbols from $S$.

Alternatively, we can achieve $\O(\log_\tau N+m/\log_\sigma N)$ query time using $\O(n\tau\log_\tau (N/n)\log N)$ bits of space, matching a lower bound stated by Verbin and Yu for strings where $N$ is polynomially related to $n$ when $\tau=\log^\epsilon N$.

For $\rank$ and $\select$ we describe data structures of size $\O(n\sigma\log N)$ bits that support the two operations in $\O(\log N)$ time. We also extend our other structure to support both operations in $\O(\log_\tau N)$ time using $\O(n\tau\sigma\log_\tau (N/n)\log N)$ bits of space.

When $\tau=\log^\epsilon N$ the query time is $O(\log N/\log\log N)$ and we provide a hardness result showing that significantly improving this would imply a major breakthrough on a hard graph-theoretical problem.

## Stephan Lorenzen, "Steiner Tree Heuristic in Euclidean d-Space Using Bottleneck Distances"

Some of the most efficient heuristics for the Euclidean Steiner minimal tree problem in the d-dimensional space, d ≥ 2, use Delaunay tessellations and minimum spanning trees to determine subsets with up to d + 1, geometrically close terminals. Their Steiner minimal trees are then determined and concatenated in a greedy fashion. The weakness of this approach is that the produced solutions are closely related to minimum spanning trees. To avoid this and to obtain even better solutions, we utilize bottleneck distances to determine good subsets of terminals without being constraint by minimum spanning trees. Computational experiments show a significant improvement in quality when using bottleneck distances instead of minimum spanning trees. Problem instances with up to 90000 terminals in R3 5300 terminals in R4 and 500 terminals in R5 can be solved within a minute.

Joint work with Pawel Winter

## Nodari Sitchinava, "Recent algorithmic advances in GPGPU computing"

Graphics Processing Units (GPUs) have emerged as a powerful platform for general purpose computations due to their massive hardware parallelism. However, there is very little understanding from the theoretical perspective, what makes various parallel algorithms fast on GPUs. In this talk I will review recent advances in modeling GPUs from the algorithmic perspective and will present our recent algorithmic results, identifying some non-trivial and somewhat unexpected open problems.

## Valentin Polishchuk, "Geometric kth shortest paths"

We show how to list the homotopy types of paths in a polygonal domain in the order of increasing length. We also present the k-th shortest path map -- a data structure to answer efficiently queries for length of the k shortest homotopically different paths from a given starting point to the query point.

Joint work with S. Eriksson-Bique, J. Hershberger, B. Speckmann, S. Suri, T. Talvitie, K. Verbeek, H. Yıldız, presented at SODA 2015

## Christian Wulff-Nilsen, "Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff"

We consider approximate distance oracles for edge-weighted n-vertex undirected planar graphs. Given fixed epsilon > 0, we present a (1+epsilon)-approximate distance oracle with O(n(log log n)^2) space and O((log log n)^3) query time. This improves the previous best product of query time and space of the oracles of Thorup (FOCS 2001, J.ACM 2004) and Klein (SODA 2002) from O(n log n) to O(n(log log n)^5).

## Riko Jacob, "On the Complexity of List Ranking in the Parallel External Memory Model"- joint work with Tobias Lieber and Nodari Sitchinava

This work has already been presented at MFCS 2014 and MASSIVE 2015.

We study the problem of {\em list ranking} in the parallel external memory (PEM) model.

We observe an interesting dual nature for the hardness of the problem due to limited information exchange among the processors about the structure of the list, on the one hand, and its close relationship to the problem of permuting data, which is known to be hard for the external memory models, on the other hand.

By carefully defining the power of the computational model, we prove a permuting lower bound in the PEM model.

Furthermore, we present a stronger $\Omega(\log^2 \inputSize)$ lower bound for a special variant of the problem and for a specific range of the model parameters, which takes us a step closer toward proving a non-trivial lower bound for the list ranking problem in the bulk-synchronous parallel (BSP) and MapReduce models.

Finally, we also present an algorithm that is tight for a larger range of parameters of the model than in prior work.