💻 computer science

Earliest query answering over streamed trees

This paper presents a method for earliest query answering on streamed trees that minimizes latency and memory usage by returning or discarding nodes as soon as their status is guaranteed, proving that this is achievable for all unary queries expressible in monadic second-order logic (MSO) with constant update time.

Original authors: Mateusz Gienieczko, Martín Muñoz, Filip Murlak, Charles Paperman

Published 2026-06-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mateusz Gienieczko, Martín Muñoz, Filip Murlak, Charles Paperman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a librarian trying to find specific books in a massive, endless delivery truck that is unloading thousands of boxes one by one. You can't wait for the whole truck to unload and then sort through the entire pile; that would take too long and require a warehouse the size of a city. Instead, you need to decide immediately as each box arrives whether to keep it, throw it away, or hand it to a customer.

This paper is about solving that exact problem for computer data (like huge JSON or XML files) using a method called "Earliest Query Answering."

Here is the breakdown of their solution using simple analogies:

1. The Problem: The "Wait-and-See" Dilemma

Usually, when computers search through a huge file, they try to build a complete map of the whole file in their memory first. If the file is massive, this crashes the computer's memory.

Even if they process it as it comes in (streaming), they often get stuck in a "wait-and-see" mode.

The Scenario: You see a box labeled "Apple." You don't know if it's the answer yet because maybe the very last box in the truck (which hasn't arrived) will tell you that only "Apples" found at the very end of the truck count.
The Result: You have to keep that "Apple" box in your hand, waiting, until the truck is empty. This clogs up your hands (memory) and delays giving the answer to the customer (latency).

The goal of this paper is to say: "Don't wait! Tell me the answer the exact moment you know for sure, no matter how the truck ends."

2. The Solution: The "Magic Stack" and "Color-Coded Buckets"

The authors created a new algorithm that acts like a super-efficient librarian. They use two main tricks to make this work for very complex questions (mathematically known as "MSO queries"):

A. The "What If" Stack (The Context)

Imagine you are reading a story. Sometimes, the meaning of a sentence depends on what comes later.

The algorithm keeps a stack (like a pile of sticky notes) that remembers the "context" of the story so far.
It calculates: "If the story ends right now, is this box an answer? If the story continues with anything possible, does this box still count?"
If the answer is "Yes, it's definitely an answer no matter what happens next," it hands the box to the customer immediately.
If the answer is "No, it can never be an answer," it throws the box away immediately.
It only keeps the box in its hand if the future is still too uncertain.

B. The "Magic Buckets" (The Data Structure)

The hardest part is that there might be thousands of boxes you are currently holding, waiting to see if they are answers. You can't check them one by one every time a new box arrives; that would be too slow.

The authors invented a special "Magic Bucket" system:

Instead of looking at every single box, they group them into buckets based on their "status" (a specific color code).
When a new box arrives, they don't check every box in the room. They just apply a rule to the entire bucket at once.
- Example: "All boxes in the 'Red' bucket are now definitely answers." -> Poof! The whole bucket is emptied to the customer instantly.
- Example: "All boxes in the 'Blue' bucket are now definitely trash." -> Poof! The whole bucket is thrown away instantly.
This allows them to update their memory and make decisions in constant time (the same speed whether they have 10 boxes or 10 million).

3. The "Iterator" Trick

The paper mentions a specific way of handing out the answers. Instead of saying "Here is box #1, here is box #2," they hand you a magic pointer (an iterator).

Think of it like giving someone a list of names on a piece of paper. You don't read the names out loud one by one. You just hand them the paper and say, "Go ahead, read the names at your own pace."
This ensures the computer doesn't get slowed down by the act of "printing" the answers; it just prepares the list and lets the user read it.

4. What They Actually Proved

The authors proved that for a very broad class of questions (those expressible in Monadic Second-Order Logic, which covers things like "Find all nodes that have a specific label and are children of a node with a different label"), you can:

Minimize Memory: You never hold onto a box longer than you logically have to.
Minimize Delay: You give the answer the instant it becomes certain.
Stay Fast: The time it takes to process each new piece of data is constant, regardless of how huge the file is.

What They Did NOT Do (Important Limits)

They didn't solve everything: They admit that for some very specific, weird questions, you must keep a lot of data in memory. Their method is optimal, but it can't magically make impossible memory requirements disappear.
They didn't build a new product: This is a theoretical proof of a method. They didn't build a new software tool called "SuperSearch" to sell to companies.
They didn't handle "Subtree Equality": They noted that if your question is "Find me two identical trees hidden in this file," their method breaks down because comparing two huge trees requires holding both in memory, which violates the "streaming" rules.

Summary

In short, this paper teaches computers how to be decisive. Instead of hoarding data and waiting for the whole file to finish, the algorithm uses a clever "bucket" system to instantly know which data is a winner, which is a loser, and which is still a maybe. It guarantees that you get your answers as fast as mathematically possible without running out of memory.

Technical Summary: Earliest Query Answering over Streamed Trees

Problem Statement
The paper addresses the challenge of evaluating queries over massive, semi-structured data (such as XML or JSON) represented as streams. In high-throughput settings, materializing the entire input tree in memory is often infeasible due to time and space constraints. The authors focus on Earliest Query Answering (EQA), a paradigm that minimizes both latency and memory footprint by adhering to two strict principles:

Minimal Latency: A node must be returned as soon as the current stream prefix guarantees it is an answer, regardless of how the document ends.
Minimal Memory: A node must be discarded as soon as the current prefix guarantees it cannot become an answer.

While EQA is straightforward for simple path-based queries, it becomes significantly more complex for practical query languages (like XPath or JSONPath) that support filters. Filters require information from various parts of the document, potentially forcing the algorithm to retain candidate nodes in memory until their status is definitively resolved. The paper investigates whether EQA is achievable for unary queries expressible in Monadic Second-Order (MSO) logic over streamed trees, specifically aiming for constant update time and optimal space usage relative to the necessary candidate set.

Methodology
The authors model trees as nested words (streams of opening and closing tags) and utilize bottom-up, right-to-left deterministic forest automata to represent MSO queries. The core of their methodology involves a specialized data structure and a streaming enumeration algorithm.

Automata and State Tracking:
- The algorithm processes the stream tag by tag. It maintains a "current node" and decomposes the visited forest into three parts: the current node ( $C$ ), its visited proper descendants ( $B$ ), and the visited ancestors/context ( $A$ ).
- For Boolean queries, the algorithm maintains two functions: an "above" function ( $\alpha$ ) representing the context $A$ and a "below" function ( $\beta$ ) representing the subtree $B$ . These functions map states to sets of possible outcomes ( $\top$ for accepted, $\bot$ for rejected). Using lemmas derived from the automaton's transition function, the algorithm updates these functions in constant time upon reading opening or closing tags. A node's status is determined as soon as the composition of these functions forces a definitive outcome.
Extension to Unary Queries:
- For unary queries (selecting specific nodes), the algorithm must track the status of every potential candidate node simultaneously. Instead of a single triple of functions, it maintains a collection of triples $\langle \alpha_v, \beta_v, \gamma_v \rangle$ for each candidate node $v$ .
- To achieve constant update time despite managing potentially many candidates, the authors introduce a Multi-Stack Data Structure. This structure groups candidates by their associated state triples (colors).
- The Multi-Stack supports operations like Multi-push, Multi-pop, and Multi-swap that update the state triples for all candidates of a specific color simultaneously.
- Crucially, the implementation uses buckets (lists of candidates) and logs (stacks of events) to handle history and "staleness." When a candidate is emitted or discarded, an Invalidate event is pushed to the log. During subsequent Multi-pop operations, the algorithm checks these logs to ensure that nodes already processed are not reintroduced, maintaining constant delay without iterating over every individual node.

Key Contributions and Results
The paper presents a streaming enumeration algorithm for unary MSO queries that satisfies the following guarantees in the RAM model:

Constant Update Time: The time to process each input tag is constant with respect to the input size (though it depends on the query/automaton size).
Constant Delay Enumeration: Once an enumeration phase begins, the time between outputs is constant.
Optimal Space Usage: The instantaneous space is $O(|Cands(\phi, w)| + f(\phi) \cdot depth(w))$ , where $|Cands|$ is the number of candidate nodes that cannot yet be decided, and $depth(w)$ is the depth of the current prefix. This ensures no node is kept longer than logically necessary.
Earliest Guarantee: The algorithm outputs or discards a node exactly when the stream prefix forces its status, independent of syntactic markers like closing tags.

The authors prove that for general unary MSO queries, a linear memory lower bound ( $\Omega(n)$ ) is unavoidable in the worst case (e.g., queries depending on the last leaf), but their algorithm achieves the best possible performance by only storing what is strictly required.

Significance and Claims
The paper claims to provide the first streaming algorithm for arbitrary unary MSO queries that achieves earliest query answering with constant update time.

It distinguishes itself from prior work on bounded delay/concurrency (which often restricts the query language) and from recent streaming enumeration frameworks (like Muñoz and Riveros) that do not guarantee the earliest possible answer, only efficient enumeration.
The authors note that while the construction relies on compiling MSO formulas into automata (which may incur a blow-up), the algorithmic contribution lies in the data structure that manages the candidate set efficiently.
The paper explicitly states that the results are limited to the finite-state view (MSO) and do not yet handle subtree equality comparisons found in advanced JSONPath filters, which would require retaining entire subtrees and thus violate the constant update time or space constraints.

In summary, the work establishes that it is theoretically possible to process complex, filter-based queries over massive tree streams with minimal latency and memory, provided the output is managed via iterators and the query is expressible in MSO.