The artifact evaluated in this report is relevant to the paper “EBA: an Event-Buffer Allocator Specifically Suited for Parallel Discrete Event Simulation”. The author released the code used in the experimental section in a permanent repository. The instructions for building and executing the artifact are well-documented, including the dependencies needed. The process of running the experiments and generating data, plots and table terminates correctly. The results could be reproduced. The paper receives the badges Artifacts Available, Artifacts Evaluated—Reusable and Results Validated - Results Reproduced.

The artifact evaluated in this report is relevant to the paper “Grid Checkpointing in Speculative Simulation”. The author released the code used in the experimental section in a permanent repository. The instructions for building and executing the artifact are well-documented, which includes the dependencies needed and a script to test if the system satisfies those dependencies. The process of running the experiments and generating data, plots terminates correctly. The results could be reproduced. The paper receives the badges Artifacts Available, Artifacts Evaluated—Reusable and Results Validated—Results Reproduced.

We consider the task of performing Jaccard similarity queries over a large collection of items that are dynamically updated according to a streaming input model. An item here is a subset of a large universe U of elements. A well-studied approach to address this important problem in data mining is to design fast-similarity data sketches. In this paper, we focus on global solutions for this problem, i.e., a single data structure which is able to answer both Similarity Estimation and All-Candidate Pairs queries, while also dynamically managing an arbitrary, online sequence of element insertions and deletions received in input.

In the k-Diameter-Optimally Augmenting Tree Problem we are given a tree T of n vertices embedded in an unknown metric space. An oracle can report the cost of any edge in constant time, and we want to augment T with k shortcuts to minimize the resulting diameter. When k = 1 , O ( n log ⁡ n ) -time algorithms exist for paths and trees. We show that o ( n 2 ) queries cannot provide a better than 10/9-approximation for trees when k ≥ 3 . For any constant ε > 0 , we design a linear-time ( 1 + ε ) -approximation algorithm for paths when k = o ( log ⁡ n ) , thus establishing a dichotomy between paths and trees for k ≥ 3 . Our algorithm employs an ad-hoc data structure, which we also use in a linear-time 4-approximation algorithm for trees, and to compute the diameter of (possibly non-metric) graphs with n + k − 1 edges in time O ( n k log ⁡ n ) .

In this work, we propose, analyze and empirically validate a lazy-update approach to maintain accurate approximations of the 2-hop neighborhoods of dynamic graphs resulting from sequences of edge insertions. We first show that under random input sequences, our algorithm exhibits an optimal trade-off between accuracy and insertion cost: it only performs [EQUATION] (amortized) updates per edge insertion, while the estimated size of any vertex's 2-hop neighborhood is at most a factor ε away from its true value in most cases, regardless of the underlying graph topology and for any ε > 0. As a further theoretical contribution, we explore adversarial scenarios that can force our approach into a worst-case behavior at any given time t of interest. We show that while worst-case input sequences do exist, a necessary condition for them to occur is that the girth of the graph released up to time t be at most 4. Finally, we conduct extensive experiments on a collection of real, incremental social networks of different sizes, which typically have low girth. Empirical results are consistent with and typically better than our theoretical analysis anticipates. This further supports the robustness of our theoretical findings: forcing our algorithm into a worst-case behavior not only requires topologies characterized by a low girth, but also carefully crafted input sequences that are unlikely to occur in practice. Combined with standard sketching techniques, our lazy approach proves an effective and efficient tool to support key neighborhood queries on large, incremental graphs, including neighborhood size, Jaccard similarity between neighborhoods and, in general, functions of the union and/or intersection of 2-hop neighborhoods.