Abstract
In this paper, we investigate space-time tradeoffs for answering Boolean conjunctive queries. The goal is to create a data structure in an initial preprocessing phase and use it for answering (multiple) queries. Previous work has developed data structures that trade off space usage for answering time and has proved conditional space lower bounds for queries of practical interest such as the path and triangle query. However, most of these results cater to only those queries, lack a comprehensive framework, and are not generalizable. The isolated treatment of these queries also fails to utilize the connections with extensive research on related problems within the database community. The key insight in this work is to exploit the formalism of relational algebra by casting the problems as answering join queries over a relational database. Using the notion of boolean adorned queries and access patterns, we propose a unified framework that captures several widely studied algorithmic problems. Our main contribution is three-fold. First, we present an algorithm that recovers existing space-time tradeoffs for several problems. The algorithm is based on an application of the join size bound to capture the space usage of our data structure. We combine our data structure with query decomposition techniques to further improve the tradeoffs and show that it is readily extensible to queries with negation. Second, we falsify two proposed conjectures in the existing literature related to the space-time lower bound for path queries and triangle detection for which we show unexpectedly better algorithms. This result opens a new avenue for improving several algorithmic results that have so far been assumed to be (conditionally) optimal. Finally, we prove new conditional space-time lower bounds for star and path queries.
Introduction
Many fundamental algorithmic tasks follow a two-phase pattern: a preprocessing phase, where a data structure is constructed using space $S$, and an answering phase, where queries are resolved in time $T$. Determining the "Pareto frontier" of the tradeoff between $S$ and $T$ is a central objective in theoretical computer science. Historically, problems such as 2-Set Disjointness and k-Reachability were treated as distinct challenges, with bespoke data structures and conditional lower bounds based on assumptions like the 3SUM conjecture. However, these isolated treatments lacked a cohesive theory, making it difficult to generalize techniques or recognize when a "proven" limit might be surmountable.
Methodology: A Unified Relational Framework
The core innovation of this work is the use of Relational Algebra as a common language to unify these disparate problems. By modeling algorithmic challenges as Boolean Conjunctive Queries (CQs), we can apply powerful database theory tools to standard algorithmic problems.
Adorned Queries and Fractional Edge Covers
We utilize "adornments" to specify which variables are provided at query time (bound, 'b') and which are internal to the database (free, 'f'). Our primary algorithm uses fractional edge covers to determine the optimal amount of data to precompute. We introduce a "slack" parameter ($\alpha$) to quantify the degree of query compression possible while maintaining a specific answering time.
Tree Decompositions
For complex queries, such as long paths, we employ $V_b$-connex tree decompositions. This technique allows a large query to be partitioned into smaller "bags," optimizing the space-time tradeoff at each step of the join operation.
Advanced Techniques
For path queries specifically, we implement a heavy-light decomposition that distinguishes between high-degree ("heavy") and low-degree ("light") nodes, applying distinct join strategies to each. Furthermore, the framework naturally extends to queries involving negation (e.g., finding a path that excludes a specific edge), a feature that is often difficult to incorporate in traditional algorithm design but fits seamlessly into the relational model.
Key Results
Refuting Existing Conjectures
A significant finding of this research is the falsification of two major conjectures from previous literature (specifically from WADS'17). We demonstrate that for $k$-reachability ($k \ge 4$) and edge triangle detection, the previously accepted lower bounds were based on erroneous reductions. We provide new algorithms that strictly outperform these presumed limits.
Improved Performance Metrics
- $k$-Reachability: For paths of length $k \ge 4$, we improve the space-time tradeoff from $S \cdot T^{2/(k-1)} = O(|D|^2)$ to $S \cdot T^{2/(k-2)} = O(|D|^2)$, offering substantial efficiency gains for large-scale graphs.
- Triangle Detection: We present a data structure for edge triangle detection with size $S = O(|E|^{3/2}/T)$, which is faster than the previously conjectured limit for specific ranges of $T$.
- New Lower Bounds: While breaking some conjectures, we establish new, robust conditional lower bounds for "star" and "path" queries, clarifying the true computational limits in this domain.
Conclusion and Future Work
This work provides a unified framework that simplifies existing results and breaks long-standing conjectures by viewing algorithmic challenges through the lens of database theory. Future research directions include extending this framework to dynamic settings where data is updated after preprocessing, and exploring the application of these techniques to improve approximate distance oracles for massive graphs. Proving unconditional lower bounds in the RAM model remains a significant open challenge.
Summary updated