Source author record

David Tench

David Tench appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Performance Programming Languages

Catalog footprint

What is connected

4works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams

Finding the connected components of a graph is a fundamental problem with uses throughout computer science and engineering. The task of computing connected components becomes more difficult when graphs are very large, or when they are dynamic, meaning the edge set changes over time subject to a stream of edge insertions and deletions. A natural approach to computing the connected components on a large, dynamic graph stream is to buy enough RAM to store the entire graph. However, the requirement that the graph fit in RAM is prohibitive for very large graphs. Thus, there is an unmet need for systems that can process dense dynamic graphs, especially when those graphs are larger than available RAM. We present a new high-performance streaming graph-processing system for computing the connected components of a graph. This system, which we call GraphZeppelin, uses new linear sketching data structures (CubeSketches) to solve the streaming connected components problem and as a result requires space asymptotically smaller than the space required for a lossless representation of the graph. GraphZeppelin is optimized for massive dense graphs: GraphZeppelin can process millions of edge updates (both insertions and deletions) per second, even when the underlying graph is far too large to fit in available RAM. As a result GraphZeppelin vastly increases the scale of graphs that can be processed.

preprint2021arXiv

Maximum Coverage in the Data Stream Model: Parameterized and Generalized

We present algorithms for the Max-Cover and Max-Unique-Cover problems in the data stream model. The input to both problems are $m$ subsets of a universe of size $n$ and a value $k\in [m]$. In Max-Cover, the problem is to find a collection of at most $k$ sets such that the number of elements covered by at least one set is maximized. In Max-Unique-Cover, the problem is to find a collection of at most $k$ sets such that the number of elements covered by exactly one set is maximized. Our goal is to design single-pass algorithms that use space that is sublinear in the input size. Our main algorithmic results are: If the sets have size at most $d$, there exist single-pass algorithms using $\tilde{O}(d^{d+1} k^d)$ space that solve both problems exactly. This is optimal up to polylogarithmic factors for constant $d$. If each element appears in at most $r$ sets, we present single pass algorithms using $\tilde{O}(k^2 r/ε^3)$ space that return a $1+ε$ approximation in the case of Max-Cover. We also present a single-pass algorithm using slightly more memory, i.e., $\tilde{O}(k^3 r/ε^{4})$ space, that $1+ε$ approximates Max-Unique-Cover. In contrast to the above results, when $d$ and $r$ are arbitrary, any constant pass $1+ε$ approximation algorithm for either problem requires $Ω(ε^{-2}m)$ space but a single pass $O(ε^{-2}mk)$ space algorithm exists. In fact any constant-pass algorithm with an approximation better than $e/(e-1)$ and $e^{1-1/k}$ for Max-Cover and Max-Unique-Cover respectively requires $Ω(m/k^2)$ space when $d$ and $r$ are unrestricted. En route, we also obtain an algorithm for a parameterized version of the streaming Set-Cover problem.

preprint2019arXiv

Mesh: Compacting Memory Management for C/C++ Applications

Programs written in C/C++ can suffer from serious memory fragmentation, leading to low utilization of memory, degraded performance, and application failure due to memory exhaustion. This paper introduces Mesh, a plug-in replacement for malloc that, for the first time, eliminates fragmentation in unmodified C/C++ applications. Mesh combines novel randomized algorithms with widely-supported virtual memory operations to provably reduce fragmentation, breaking the classical Robson bounds with high probability. Mesh generally matches the runtime performance of state-of-the-art memory allocators while reducing memory consumption; in particular, it reduces the memory of consumption of Firefox by 16% and Redis by 39%.

preprint2015arXiv

Densest Subgraph in Dynamic Graph Streams

In this paper, we consider the problem of approximating the densest subgraph in the dynamic graph stream model. In this model of computation, the input graph is defined by an arbitrary sequence of edge insertions and deletions and the goal is to analyze properties of the resulting graph given memory that is sub-linear in the size of the stream. We present a single-pass algorithm that returns a $(1+ε)$ approximation of the maximum density with high probability; the algorithm uses $O(ε^{-2} n \polylog n)$ space, processes each stream update in $\polylog (n)$ time, and uses $\poly(n)$ post-processing time where $n$ is the number of nodes. The space used by our algorithm matches the lower bound of Bahmani et al.~(PVLDB 2012) up to a poly-logarithmic factor for constant $ε$. The best existing results for this problem were established recently by Bhattacharya et al.~(STOC 2015). They presented a $(2+ε)$ approximation algorithm using similar space and another algorithm that both processed each update and maintained a $(4+ε)$ approximation of the current maximum density in $\polylog (n)$ time per-update.