Interactive graph search (IGS) has proven to be a useful information retrieval paradigm in a diverse set of applications. Robust IGS algorithms are notoriously difficult to design because they are deeply rooted in graph theory. The current state-of-the-art algorithms either fail to achieve an optimal number of interaction rounds or rely on interfaces demanding tedious user inputs. Furthermore, previous research has paid little attention to the underlying computation bottleneck, which is currently dealt with using primitive implementations. This work remedies the above issues altogether. Utilizing novel findings on the problem characteristics, we develop an algorithmic framework for IGS that requires a designer to fill in the details for only two ''black-box'' operations. Our framework, when instantiated with surprisingly simple black-box implementations, yields optimal algorithms not only in all the scenarios explored before but also in new scenarios never studied. We accompany our framework, designed to minimize interaction rounds, with a new algorithm designed to reduce the CPU time complexity significantly. Extensive experiments on both real and synthetic data confirm both the efficacy and efficiency of the proposed techniques.

Given a join with an acyclic set of degree constraints, we show how to draw a uniformly random sample from the join result in $O(\mathit{polymat}/ \max \{1, \mathrm{OUT} \})$ expected time after a preprocessing of $O(\mathrm{IN})$ expected time, where $\mathrm{IN}$, $\mathrm{OUT}$, and $\mathit{polymat}$ are the join's input size, output size, and polymatroid bound, respectively. This compares favorably with the state of the art (Deng et al.\ and Kim et al., both in PODS'23), which states that a uniformly random sample can be drawn in $\tilde{O}(\mathrm{AGM} / \max \{1, \mathrm{OUT}\})$ expected time after a preprocessing phase of $\tilde{O}(\mathrm{IN})$ expected time, where $\mathrm{AGM}$ is the join's AGM bound. We then utilize our techniques to tackle {\em directed subgraph sampling}. Let $G = (V, E)$ be a directed data graph where each vertex has an out-degree at most $λ$, and let $P$ be a directed pattern graph with $O(1)$ vertices. The objective is to uniformly sample an occurrence of $P$ in $G$. The problem can be modeled as join sampling with input size $\mathrm{IN} = Θ(|E|)$ but, whenever $P$ contains cycles, the converted join has {\em cyclic} degree constraints. We show that it is always possible to throw away certain degree constraints such that (i) the remaining constraints are acyclic and (ii) the new join has asymptotically the same polymatroid bound $\mathit{polymat}$ as the old one. Combining this finding with our new join sampling solution yields an algorithm to sample from the original (cyclic) join (thereby yielding a uniformly random occurrence of $P$) in $O(\mathit{polymat}/ \max \{1, \mathrm{OUT}\})$ expected time after $O(|E|)$ expected-time preprocessing. We also prove similar results for {\em undirected subgraph sampling} and demonstrate how our techniques can be significantly simplified in that scenario.

This paper studies communication-oblivious algorithms under the massively parallel computation (MPC) model. The communication patterns of these algorithms follow a distribution dependent only on the definition of the underlying problem, the problem size N, and the number p of machines, but not on the specific input elements. Our objective is to understand when obliviousness necessitates --- or does not necessitate --- heavier communication compared to the traditional MPC model that does not enforce such a requirement. The first part of our investigation focuses on single-round algorithms. We prove that skew-free hashing, a fundamental problem solvable with load Õ(N/p) (with high probability or w.h.p.\ for short) under the traditional model, demands a load of nearly Ω(N) under communication obliviousness. Intriguingly, we show that hashing can still be applied in an oblivious manner to process any natural join in one round with a load complexity matching that of the best traditional MPC algorithm. The second part of our investigation studies compilation methods that convert a traditional MPC algorithm A into a communication-oblivious counterpart. Given an A that operates within l = poly(p) rounds and entails a load at most L = Ω(p log p) w.h.p., we can produce w.h.p.\ a communication-oblivious version running in 2l rounds with a load at most (1 + δ) L, where δ < 0 can be an arbitrarily small constant. Additionally, we establish hardness results indicating that the theoretical guarantees of our compilation can no longer be significantly improved.

In a spatial join , we are given a constant number k ≥ 2 of sets - denoted as R1, R2, ..., Rk - containing axis-parallel rectangles in a 2D space. The objective is to report all k-tuples (r1, r2, ..., rk ) ∈ R1 × R2 × ... × Rk where the rectangles r1, r2, ..., rk have a non-empty intersection, i.e., r1 ∩ r2 ∩ ... ∩ rk ≠ ∅. The problem holds significant importance in spatial databases and has been extensively studied in the database community. In this paper, we show how to settle the problem in O(n logn + OUT) time - regardless of the constant k - where n = Ík i=1 |Ri | and OUT is the result size (i.e., the total number of k-tuples reported). The runtime is asymptotically optimal in the class of comparison-based algorithms, to which our solution belongs. Previously, the state of the art was an algorithm with running time O(n log 2k-1 n + OUT).

This paper studies how to design an index structure on a collection of sets$S_{1}, S_{2},{\ldots }, S_{n}$to answer the following queries: given distinct set ids$a, b \in [1, n]$, report$F(S_{a} \cap S_{b})$where$F(.)$is a filtering function. We present a solution that can support a great variety of filtering functions — range research, skyline, convex hull, nearest neighbor search, quantile (to name just a few) — with attractive performance guarantees. The guarantees are sensitive to the set collection'spseudoarboricity, a new notion for quantifying the density of$\lbrace S_{1}, S_{2},{\ldots }, S_{n}\rbrace$. Our index structures are simple to understand and implement.