Algorithms enable fast counting queries on complex data structures
Counting on Nowhere Dense Classes
Logic in Computer Science
Summary
Counting how many related items satisfy a particular rule in large, complex data sets can be slow. The authors designed an algorithm that preprocesses such data efficiently, so later counting queries can be answered instantly. Their approach works for certain broad classes of structured data and supports more advanced logical queries than before. This improves on earlier methods by handling more complex queries with efficient counting and enumeration.
What this means in practice
- •For database engineers: Design database engines that can preprocess data for instant counting queries on complex logical conditions.
- •For graph processing teams: Implement graph algorithms with fast query responses for counting substructures defined by expressive logical formulas.
Authors
Steffen van Bergerem, Nicole Schweikardt
Abstract
For every effectively nowhere dense class $\mathcal{C}$ of relational structures, we present an algorithm that runs an almost-linear-time preprocessing step on a given structure $\mathcal{A} \in \mathcal{C}$ and a first-order formula $φ(x_1, \dots, x_k, y_1, \dots, y_\ell)$. After the preprocessing, whenever given a tuple $\bar{v} \in A^k$, the algorithm computes the number of tuples $\bar{w} \in A^\ell$ that satisfy $\mathcal{A} \models φ(\bar{v}, \bar{w})$ in constant time. Building on this, we provide an algorithm for constant-time query answering and constant-delay enumeration after almost-linear-time preprocessing for the recently introduced logic clique-guarded first-order logic with counting (cgFOC) on effectively nowhere dense classes. This generalises the testing and enumeration results for first-order logic [Schweikardt, Segoufin, and Vigny, JACM 2022] and the evaluation result for the first-order logic with counting FOC1 [Grohe and Schweikardt, PODS 2018] on nowhere dense classes.