Stackless Processing of Streamed Trees

Summary: Introduce a stackless streaming model: register automata with a single depth counter to validate and query streamed trees, sitting between finite-state and stack-based approaches. Characterize which RPQs are evaluable stacklessly (with or without registers) and confirm Segoufin–Vianu's conjecture for RPQ-defined DTD languages. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1847
Venue: PODS
Year: 2021
Pagerank: 5.5181056e-05
Overall Rank: 7,919 | 45.67%
DOI: 10.1145/3452021.3458320

Incoming Non-self Citations Over Time

Authors

1. Corentin Barloy (École Normale Supérieure)
2. Filip Murlak (University of Warsaw)
3. Charles Paperman (CNRS; INRIA; University of Lille)

BibTeX Citation

@inproceedings{barloy_pods21,
        address = {New York, NY, USA},
        series = {{PODS} '21},
        title = {{Stackless Processing of Streamed Trees}},
        url = {https://dl.acm.org/doi/10.1145/3452021.3458320},
        doi = {10.1145/3452021.3458320},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Barloy, Corentin and Murlak, Filip and Paperman, Charles},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,592	Streaming Validation of JSON Documents Against Schemas	2026	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
293	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00022259273
634	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD	0.00015533814
738	Stream Processing of XPath Queries with Predicates	2003	SIGMOD	0.00014484337
1,547	On Complexity and Optimization of Expensive Queries in Complex Event Processing	2014	SIGMOD	0.00010394989
1,758	Validating Streaming XML Documents	2002	PODS	9.8162828e-05
2,414	Filter Before You Parse: Faster Analytics on Raw Data with Sparser	2018	VLDB	8.6078841e-05
7,927	Schema Validation via Streaming Circuits	2016	PODS	5.5181056e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,969	Expressive and efficient pattern languages for tree-structured data (extended abstract)	2000	PODS
2	1,575	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS
3	9,168	Marrying Words and Trees	2007	PODS
4	5,579	Enumeration on Trees with Tractable Combined Complexity and Efficient Updates	2019	PODS
5	6,184	Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)	2000	PODS
6	13,954	On the Power of Walking for Querying Tree-Structured Data	2002	PODS
7	2,625	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
8	5,346	Running Tree Automata on Probabilistic XML	2009	PODS
9	11,525	Data Path Queries over Embedded Graph Databases	2022	PODS
10	6,318	Query Automata (extended abstract)	1999	PODS