Worst-Case Optimal BGPs on Temporal Graphs

Worst-Case Optimal BGPs on Temporal Graphs

An index structure that, for a temporal graph with N edges, requires O(N) space and can evaluate extended BGPs in wco time and yields wco guarantees for related query types, including snapshot evaluation, version queries, and other temporal variants.

Cedar: A Columnar LSM-Engine for Temporal Property Graphs

Uplifting the Superpowers of Worst-Case-Optimal Join Algorithms

Worst-case-optimal (wco) join algorithms have demonstrated their power -- in both theory and practice -- to efficiently solve complex Basic Graph Patterns (BGPs). Modern graph query languages, such as SPARQL and GQL, have BGPs at their core, but also have a wide range of other features, including filters (aka.\ selections). Such conditions are typically handled via pre- or post-filtering, before or after processing the BGPs. In this paper we show how to uplift wco join algorithms so as to incorporate such filtering natively, improving efficiency. We demonstrate the superiority of this approach by extending the \textit{Ring} -- a compact index that provides wco resolution of BGPs within almost no extra space on top of the graph -- so as to handle property graphs using our new techniques while retaining compactness. We implement this extension and experimentally show that it outperforms various baseline systems.

Efficient Simple Temporal Cycle Enumeration on Large Graphs with Lightweight Preprocessing

This work introduces a novel edge-centric framework that treats temporal edges as the core units of exploration and eliminates redundant temporal checks, and extends this framework to dynamic settings by introducing an efficient incremental update algorithm that selectively identifies affected paths only.

Effective Durable Community Search in Large Temporal Graph

A temporal graph is an undirected graph where each edge is associated with a timestamp indicating when it occurs. As a fundamental topic in graph analysis, community search (CS) in temporal graphs has received much attention. Existing CS works on temporal graphs typically identify sets of vertices that form a k -core within a specific time window (temporal k -core). However, they overlook the duration of a temporal community, which is the continues time period that its members remain unchanged. Intuitively, the longer the duration of a temporal community, the higher its stability. Long-duration communities are useful in many areas, such as event detection and network analysis. In this paper, we introduce a novel community model, called temporal durable community (TDC), which is the temporal k -core with the longest duration in the temporal graph, and aim to efficiently find the TDC containing a query vertex. To solve this problem, we first propose a novel online algorithm based on binary search. We further develop two index structures that can quickly determine the duration of a given temporal k -core, followed by query algorithms. Experiments on ten real large temporal graphs show that our TDC model is effective for finding stable communities, and our index-based query algorithms are up to five orders of magnitude faster than the online algorithm.

Latency-Optimal Geo-Distributed Storage over Structured Networks

It is shown that for every fixed number of files, computing a latency-minimizing assignment is NP-hard via a reduction from the domatic number problem.