Algorithmic Abstractions for Dynamic Data
Many application require computing with dynamically changing data. Examples abound: online data-intensive applications operate on web data that change dynamically as the network topology, users, and site contents change; scientific computations often involve calculations with continuously moving or deforming objects; robots interact with dynamically changing physical worlds; compilers operate on code that changes over time. In many applications, dynamic data changes occur slowly, i.e., in small amounts, over time. Being small, such changes often require small updates to the output, permitting computations to adapt or respond to dynamic changes asymptotically more efficiently than a complete re-computation. Motivated by the potential of asymptotic improvements in efficiency and the broad domain of applicability, my collaborators and I have been developing algorithmic abstraction for expressing such computations and realizing the abstractions by extending existing, general-purpose programming languages. The algorithmic abstractions provide the algorithm designer with techniques for developing efficient algorithms that can respond to dynamically changing data. The programming languages offer means for the developer to realize such dynamic algorithms and more broadly dynamic systems by using high-level language constructs that shove tricky implementation details to the compiler. We refer to this approach to designing and developing dynamic software systems as self-adjusting computation. In this talk, I will present an overview of the main challenges of computing with dynamic data, our proposals for addressing these challenges, and a range of applications, both theoretical and practical, that we have considered.
Michael Bender, SUNY Stony Brook, USA
Don't Thrash: How to Cache your Hash on Flash
Many large storage systems use approximate-membership-query (AMQ) data structures to deal with the massive amounts of data that they process. An AMQ data structure is a dictionary that trades off space for a false positive rate on membership queries. It is designed to fit into small, fast storage, and it is used to avoid I/Os on slow storage. The Bloom filter is a well-known example of an AMQ data structure. Bloom filters, however, do not efficiently scale outside of main memory. This paper describes the Cascade Filter, an AMQ data structure that scales beyond main memory, supporting over half a million insertions/deletions per second and over 500 lookups per second on a commodity flash-based SSD. We describe how the Cascade Filter relates to write-optimized data structures and storage systems.
(joint work with Martin Farach-Colton, Rob Johnson, Bradley Kuszmaul, Dzejla Medjedovic, Pablo Montes, Pradeep Shetty, Richard Spillane, Erez Zadok)
Petra Berenbrink, Simon Fraser U., Canada
Speeding up random walks
First we consider the following marking random walk process on a connected undirected graph G. Let v denote the vertex visited by the random walk in the current step. If v has not been marked before, then mark it. If v is already marked, then mark a randomly chosen unmarked neighbor of v, if any. In the next step proceed to a random neighbor, according to the random walk process. We also consider a variant of the process, which first assigns to each vertex a global random rank. Our results imply that on many important graph classes, random walks which are allowed to mark (cover) neighbors, have same cover time as the corresponding centralized coupon collecting process. Then consider a modified random walk which makes transitions using unvisited edges whenever possible. Our main result is the following: Let G=G(r,n) be a random r-regular graph of constant even degree r >= 4, and vertex set of size n. We prove that with high probability, the cover time of G by the walk is O(n). This is to be compared with the O(n log n) cover time of G by a simple random walk. We provide empirical evidence to suggest that the same process behaves asymptotically worse on random regular graphs of odd degree, and that a related process which moves to an unvisited neighbour whenever possible, behaves asymptotically worse on random regular graphs of even degree. As far as we know, this is the first theoretical analysis of the cover time of a non-Markovian process on a general class of graphs. Our study supports the intuitive idea that random walks which prefer unvisited vertices or edges may have an improved cover time.
PHAST: Hardware-Accelerated Shortest Path Trees
Computing driving directions has motivated many shortest path heuristics that answer queries on continental-scale networks, with tens of millions of intersections, in real time. The underlying algorithms are intuitive, but until recently there was no theoretical explanation of their performance. We review some of these algorithms and give the first theoretical analysis for them on a non-trivial class of networks. For our analysis, we introduce the notion of highway dimension. The analysis works for networks with low highway dimension and gives a unified explanation of algorithms' good performance. Our analysis explores an unexpected relationship to VC-dimension and applies boosting to graph algorithm design. We also show that a labeling algorithm, previously studied by the distributed computation community, achieves a better theoretical time bound. This motivates a heuristic implementation of the labeling algorithm. Our experimenters show that the implementation outperforms the fastest previous codes, validating the theoretical prediction.
Paper available at http://research.microsoft.com/pubs/144834/phast_ipdps.pdf
(joint work with Andrew Goldberg, Andreas Nowatzyk, and Renato Werneck)
Faith Ellen, University of Toronto, Canada
TBA
Funda Ergun, Simon Fraser U., Canada
Periodicity in Data Streams
In this work we study sublinear space algorithms for detecting periodicity over data streams. A sequence of length n is said to be periodic if it consists of repetitions of a block of length p for some p <= n 2. In the first part of this paper, we give a 1-pass randomized streaming algorithm that uses O(log 2 n) space and reports the shortest period if the given stream is periodic. At the heart of this result is a 1-pass O(log n log m) space streaming pattern matching algorithm. This algorithm uses similar ideas to Porat and Porat's algorithm in FOCS 2009 but it does not need an offline pre-processing stage and is considerably simpler. In the second part, we study distance to p-periodicity under the Hamming metric, where we estimate the minimum number of character substitutions needed to make a given sequence p-periodic. In streaming terminology, this problem can be described as computing the cascaded aggregate L1 . F res(1) 1 over a matrix Ap×d given in column ordering. For this problem, we present a randomized streaming algorithm with approximation factor 2 + eps that takes O(eps-2) space. We also show a 1+eps randomized streaming algorithm which uses O(eps-5.5p1/2) space.
(joint work with Hossein Jowhari and Mert Saglam)
Amos Fiat, Tel Aviv U., Israel
How to bribe a prison guard and applications
We present a tool that allows us to devise mechanisms, truthful in expectation, for a wide variety of problems, with some caveats.
(joint work with Elias Koutsoupias and Angelina Videli)
Irene Finocchi, Sapienza U. Rome, Italy
Resilient Dynamic Programming
Random access memories suffer from failures that can lead the logical state of some bits to be read differently from how they were last written. Silent data corruptions may be harmful to the correctness and performance of software. In this talk we will address the problem of computing in unreliable memories, focusing on the design of resilient dynamic programming algorithms. We will present algorithms that are correct with high probability (i.e., obtain exactly the same result as a non-resilient implementation in the absence of memory faults) and can tolerate a polynomial number of faults while maintaining asymptotically the same space and running time as their non-resilient counterparts.
(joint work with Saverio Caminiti, Emanuele Fusco, and Francesco Silvestri)
Loukas Georgiadis, U. Western Macedonia, Greece
Dominator Verification, Independent Spanning Trees, and 2-Vertex Connectivity
We revisit the problems of verifying dominators in a flowgraph and computing pairs of (strongly) independent spanning trees, and present simpler linear-time algorithms. Based on these constructions, we provide fast algorithms for the following problems: Computing certificates for dominator trees, testing 2-vertex connectivity, computing pairs of vertex-disjoint s-t paths, and computing 2-vertex connected spanning subgraphs.
(based on joint work with Bob Tarjan)
Highway and VC-dimension: From Practice to Theory and Back
We present a novel algorithm to solve the nonnegative single-source shortest path problem on road networks and other graphs with low highway dimension. After a quick preprocessing phase, we can compute all distances from a given source in the graph with essentially a linear sweep over all vertices. Because this sweep is independent of the source, we are able to reorder vertices in advance to exploit locality. Moreover, our algorithm takes advantage of features of modern CPU architectures, such as SSE and multi-core. Compared to Dijkstra's algorithm, our method makes fewer operations, has better locality, and is better able to exploit parallelism at multi-core and instruction levels. We gain additional speedup when implementing our algorithm on a GPU, where our algorithm is up to three orders of magnitude faster than Dijkstra's algorithm on a high-end CPU. This makes applications based on all-pairs shortest-paths practical for continental-sized road networks. The applications include, for example, computing graph diameter, exact arc flags, and centrality measures such as exact reaches or betweenness.
(joint work with Ittai Abraham, Daniel Delling, Amos Fiat, and Renato Werneck)
Torben Hagerup, U. Augsburg, Germany
Linear-Time Kernelization for Planar Dominating Set
A kernelization for Dominating Set is an algorithm that, given an instance I=(G,k) of the problem, uses time bounded by p(|I|) for some polynomial p to compute an instance I'=(G',k') of the problem with |G'|<=f(k) and k'<=k for some function f such that I in Dominating Set <=> I' in Dominating Set. Informally, the difficulty of the original instance I is "concentrated" in the much smaller instance I' in polynomial time. The talk describes a kernelization for the NP-complete Dominating Set problem in planar graphs for which both p and f are linear. Such a result was previously known (van Bevern et al., personal communication), but the new kernelization is simpler.
John Iacono, Polytechnic U., USA
Why some heaps have constant-time decrease-key, and others do not
Abstract TBA.
Giuseppe F. Italiano, University of Rome "Tor Vergata", Italy
Improved Algorithms for Min Cut and Max Flow in Undirected Planar Graphs
We study the min st-cut and max st-flow problems on planar graphs, both in static and in dynamic settings. First, we present an algorithm that given an undirected planar graph and two vertices s and t computes a min st-cut in O(n log log n) time. Second, we show how to achieve the same bound for the problem of computing a max st-flow in an undirected planar graph. These are the first algorithms breaking the O(n log n) barrier for those two problems, which has been standing for more than 25 years. Third, we present a fully dynamic algorithm for maintaining the value of the min st-cuts and the max st-flows in an undirected plane graph (i.e., a planar graph with a fixed embedding): our algorithm is able to insert and delete edges and answer min st-cut weight queries between any pair of vertices in O(n^{2/3} log^{8/3} n) time per operation. This result is based on a new dynamic shortest path algorithm for planar graphs which may be of independent interest. We remark that this is the first known non-trivial dynamic algorithm for min st-cut and max st-flow.
(joint work with Yahav Nussbaum, Piotr Sankowski and Christian Wulff-Nilsen)
Haim Kaplan, Tel-Aviv U., Israel
How to split a flow?
Many practically deployed flow algorithms produce the output as a set of values associated with the network links. However, to actually deploy a flow in a network we often need to represent it as a set of paths between the source and destination nodes. In this paper we consider the problem of decomposing a flow into a small number of paths. We show that there is some fixed constant β > 1 such that it is NP-hard to find a decomposition in which the number of paths is larger than the optimal by a factor of at most β. Furthermore, this holds even if arcs are associated only with three different flow values. We also show that straightforward greedy algorithms for the problem can produce much larger decompositions than the optimal one, on certain well tailored inputs. On the positive side we present a new approximation algorithm that decomposes all but an epsilon-fraction of the flow into at most O(1/epsilon2) times the smallest possible number of paths. We compare the decompositions produced by these algorithms on real production networks and on synthetically generated data. Our results indicate that the dependency of the decomposition size on the fraction of flow covered is exponential. Hence, covering the last few percent of the flow may be costly, so if the application allows, it may be a good idea to decompose most but not all the flow. The experiments also reveal the fact that while for realistic data the greedy approach works very well, our novel algorithm which has a provable worst case guarantee, typically produces only slightly larger decompositions.
Valerie King, U. Victoria, Canada
Conflict on a Communication Channel
Is it inherently cheaper to communicate than to block communication? In this paper we attempt to model the cost of censorship. We primarily consider communication in a wireless network where Alice wants to send a message to Bob along a channel and Carol wants to prevent this. Each player can either send, listen or block the channel in any time step for some small, fixed cost. where the costs to Alice, Bob and Carol can represent expenditure of both computational and human resources. We answer this question in the affirmative by showing that it is significantly more costly for Carol to block the message than for Alice to communicate it to Bob. Specifically, we describe an algorithm for Alice and Bob that ensures that if Carol spends C, then Alice and Bob spend only O(Cphi-1 + 1) = O(C0.62 + 1) dollars, where phi is the golden ratio. This holds even if Alice and Bob do not know the value C. We generalize this result to many players, and describe applications in mitigating denial-of-service attacks and open problems related to web censorship.
(joint work with Jared Saia and Max Young)
Ian Munro, U. Waterloo, Canada
Range majority and Orthogonal Range Counting using Techniques from Succinct Data Structures
Algorithms and data structures developed for one application domain and set of constraints are often applied to other situations. Succinct data structures were developed, to a large extent, for extremely space efficient string indexing. We now seem to be in an era in which such methods are being used for applications in which space requirements are not as severe and indeed for applications outside stringology, such as geometric problems. We give a couple of examples of this trend through recent results on reporting range majority and dynamic orthogonal range counting.
(joint work with Meng He et al.)
Parallel Computation of Best Connections in Public Transportation Networks
We present a novel algorithm for the one-to-all profile-search problem in public transportation networks. It answers the question for all fastest connections between a given station S and any other station at any time of the day in a single query. Moreover, this algorithm allows for a very natural parallelization yielding excellent speed-ups on standard multi-core servers. Our approach exploits the fact that first, time-dependent travel-time functions in such networks can be represented as a special class of piecewise linear functions, and that second, only few connections from S are useful to travel far away. Introducing the connection-setting property, we are able to extend Dijkstra's algorithm in a sound manner.
Cynthia Phillips, Sandia National Labs, US
Streaming Dynamic Connected Components
Demetrescu, Finocchi, and Ribichini (SODA 2006, ACM TALG 2009) gave an elegant algorithm for computing the connected components of an n-node graph in the W-stream model. In their algorithm, edges arrive one by one in a finite stream. The algorithm has access to finite space s generally much smaller than n, the number of nodes in the graph. The algorithm can emit a new intermediate stream, and reprocess that stream after the current finite stream ends. After O(n lg n/s) such passes, the algorithm has computed the connected components of the graph. In this work, we consider maintaining the connected components of a graph that arrives in an infinite stream. The algorithm supports queries about connected components and supports aging operations, where all edges at least t seconds old leave simultaneously. We propose a new streaming model called X-stream, essentially a parallel processing model for streaming applications. We describe an algorithm for maintaining connected components with aging in the X-stream model based on the Demetrescu et al. W-stream (finite) connected components algorithm. The Demetrescu et al. algorithm will stream through smoothly end-to-end on the X-Stream model. However, once the system must handle an infinite stream and must store all edges, there are significant storage management complications. This is a work in progress, as the performance proofs are not finished. However, we believe the algorithm has the following properties: The algorithm correctly answers connected component queries, except for a period of stabilization after an aging command. The algorithm does not drop any edges provided there is space in the overall system, even during aging. The algorithm effectively uses the total system space by storing Ω(ps) edges, for p processors each with s << n local memory. We will present the main pieces of the algorithm, with arguments supporting this list of properties.
(joint work with Jon Berry - Sandia, Matthew Oster - Rutgers, Steve Plimpton - Sandia)
Liam Roditty, Bar-Ilan U., Israel
The Minimum Weight Cycle Problem
We consider the fundamental algorithmic problem of finding a cycle of minimum weight in a graph of nonnegative edge weights. Extending the seminal work of Itai and Rodeh [SIAM J. Computing 1978 and STOC'77] on minimum cycle in unweighted graphs, we show that the minimum weight cycle problem in a (directed or undirected) n-node graph with weights in {1,...,M} can be efficiently reduced to finding a minimum weight triangle in an Θ(n)-node graph with weights in {1,...,O(M)}. We also show that given a weighted undirected graph G(V,E,w), with a minimum cycle of weight t* whose maximal edge weight is w* it is possible to efficiently compute the following approximations: 1) For integral weights from the range [1,M] we report a cycle of weight at most 4/3 t* in O(n2 log n (log n + log M)) time. 2) For integral weights from the range [1,M] we report a cycle of weight at most t* + w* in O(n2 log n (log n + log M)) time. 3) For non-negative real edge weights and for any eps>0 we report a cycle of weight at most (4/3+eps)t* in O(1/eps n2 log n (log log n)) time.
(joint work with Roei Tov and with Virginia Vassilevska Williams)
Cenk Sahinalp, Simon Fraser U., Canada
Algorithmic Methods for Structural Variation Detection among Multiple High Throughput Sequenced Genomes
High throughput sequencing (HTS) technologies have been decreasing the cost and increasing the world-wide capacity for genome sequence production at an unprecedented rate, making the initiation of large scale projects aiming to sequence more than 1000s of genomes possible. The ability to detect structural alterations on HTS personal genomes will change the way diseases of genomic origin are diagnosed and treated. In this talk we will briefly go through some of the algorithm development efforts at the Lab for Computational Biology in SFU for analyzing large collections of HTS genomes and transcriptomes, for the purposes of identifying common and rare structural variants with high accuracy. Our algorithms, which we collectively call CommonLAW (Common Loci structural Alteration detection Widgets) move away from the current model of 1. detecting genomic variants in single HTS donor genomes independently, and 2. checking whether two or more donor genomes indeed agree or disagree on the variations, to a new model in which structural variants are detected among multiple genomes and transcriptomes simultaneously. One of our methods, Comrad, for example, enables integrated analysis of transcriptome (i.e. RNA) and genome (i.e. DNA) sequence data for the purposes of discovering genomic rearrangements and aberrant transcripts (non-standard mRNAs) in multiple (possibly related) individuals simultaneously.
Jared Saia, University of New Mexico, USA
Scalable Rational Secret Sharing
In this talk, we consider the classical secret sharing problem in the case where all agents are selfish but rational. In recent work, Kol and Naor show that in the non-simultaneous communication model (i.e. when rushing is possible), there is no Nash equilibrium that ensures all agents learn the secret. However, they describe a mechanism for this problem that is an epsilon-Nash equilibrium, i.e. it is close to an equilibrium in the sense that no player can gain more than epsilon utility by deviating from it. Unfortunately, the Kol and Naor mechanism, and, to the best of our knowledge, all previous mechanisms for this problem require each agent to send O(n) messages in expectation, where n is the number of agents. This may be problematic for some applications of rational secret sharing such as secure multiparty computation and simulation of a mediator. We address this issue by describing a mechanism for rational n-out-of-n secret sharing that is an epsilon-Nash equilibrium, and is scalable in the sense that it requires each agent to send only an expected O(1) messages and polylogarithmic number of bits. Moreover, the latency of our mechanism is O(log n) in expectation, compared to O(n) expected latency for the Kol and Naor result. We also design scalable mechanisms for a relaxed variant of rational m-out-of-n secret sharing where m = θ(n). Our mechanisms are non-cryptographic, and are not susceptible to backwards induction.
(joint with Varsha Dasani, Mahnush Mohavedi and Yamel Rodriguez)
Siddhartha Sen, Princeton U., USA
The Price of Equivocation: Characterizing Byzantine Agreement via Hypergraph Coloring
In the Byzantine agreement problem, a set of n processors, any f of whom may be arbitrarily faulty, must reach agreement on a value proposed by one of the correct processors. It is a celebrated result that unless n > 3f, Byzantine agreement is not possible in a variety of computation and communication models. This is due to the fact that faulty processors can equivocate, that is, say different things to different processors. If this ability is mitigated, for example by assuming a global broadcast channel, then n > 2f is sufficient. With very few exceptions, the literature on Byzantine agreement has been confined to the n > 2f and n > 3f paradigms. We bridge the gap between these two paradigms by assuming partial broadcast channels among sets of three processors, observing that equivocation is fundamentally an act involving three parties (one processor lying to two other processors. We characterize the conditions under which Byzantine agreement is possible for all n = 2f + h, h an integer in [1..n/3], by giving asymptotically tight bounds on the number of necessary and sufficient partial broadcast channels. We prove these bounds by a reduction to a problem in extremal combinatorics, itself a natural generalization of a well-studied hypergraph coloring problem. Deciding whether a given set of broadcast channels enables Byzantine agreement is co-NP-complete. Although partial broadcast channels have been studied in prior work, the bounds obtained were sub-optimal by up to a quadratic factor.
(joint work with Alex Jaffe and Thomas Moscibroda)
Achieving the Unified Bound in the BST Model
We describe cache-splay, the first BST algorithm that is provably constant-competitive to the Unified Bound of Iacono. This shows that it is possible to build an augmentable data structure capable of range-sum queries that performs well when queries exhibit a combination of locality in space and time (i.e., queries are fast, in the amortized sense, when they are near to a recently accessed element). In comparison to the skip-splay trees of Derryberry and Sleator, our new BST maintains a more well-defined structure to the tree. This added structure simplifies the proof of competitiveness to the Unified Bound, and allows our BST to eliminate the additive O(lg lg n) term that skip-splay trees require in their running time bound relative to the Unified Bound.
(joint work with Jon Derryberry)
Robert Tarjan, Princeton U. and HP, USA
Deletion without Rebalancing in Balanced Search Trees
Deletion in a balanced search tree is a probematic operation: rebalancing on deletion has more cases than rebalancing on insertion, and it is easy to get wrong. We describe a way to maintain search trees so that rebalancing occurs only on insertion, not on deletion, but the tree depth remains logarithmic in the number of insertions, independent of the number of deletions. Our results provide theoretical justification for common practice in B-tree implementations, as well as providing a new kind of balanced binary tree that is more efficient in several ways than those previously known. We also show by means of an exponential potential function that insertion rebalancing affects height h exponentially infrequently in h.
(joint work with Sid Sen)
Natural Cuts and Customizable Route Planning
I will present an extremely practical algorithm to compute shortest paths on continental road networks with arbitrary metrics (cost functions). The approach has very low space usage per metric, supports real-time queries, and can incorporate a new metric in a few seconds. As a result, it can easily handle real-time traffic updates and personalized optimization functions. Unlike most previous methods, ours does not rely on the strong hierarchy observed on road networks with travel times as the cost function, making it much more robust to metric changes. Our algorithm uses the fact that road networks can be partitioned into loosely connected regions. To find such partitions, we developed a new algorithm based on the notion of natural cuts, which are sparse regions separating much denser areas.
(joint work with Daniel Delling, Andrew Goldberg, Thomas Pajor, and Ilya Razenshteyn)
Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. Most deterministic pivoting rules are known, however, to require an exponential number of steps to solve some linear programs. No non-polynomial lower bounds were known, prior to this work, for randomized pivoting rules. We provide the first subexponential (i.e., of the form 2Ω(nalpha), for some alpha>0) lower bounds for the two most natural, and most studied, randomized pivoting rules suggested to date. The first randomized pivoting rule we consider is Random-Edge, which among all improving pivoting steps (or edges) from the current basic feasible solution (or vertex) chooses one uniformly at random. The second randomized pivoting rule we consider is Random-Facet, a more complicated randomized pivoting rule suggested by Kalai (1992) and Matousek, Sharir and Welzl (1996). Our lower bound for the Random-Facet pivoting rule essentially matches the subexponential upper bounds of Kalai and Matousek et al. Lower bounds for Random-Edge and Random-Facet were known before only in abstract settings, and not for concrete linear programs. Our lower bounds are obtained by utilizing connections between pivoting steps performed by simplex-based algorithms and improving switches performed by policy iteration algorithms for 1-player and 2-player games. We start by building 2-player parity games (PGs) on which suitable randomized policy iteration algorithms perform a subexponential number of iterations. We then transform these 2-player games into 1-player Markov Decision Processes (MDPs) which correspond almost immediately to concrete linear programs.
(joint work with Thomas Dueholm Hansen and Oliver Friedmann)