Schema Validation via Streaming Circuits

Summary: Introduce streaming circuits: a block-wise model passing constant info between fixed-size blocks to parallelize XML schema validation and import circuit-complexity results into the streaming setting. Construct O(log b)-depth (or constant) circuits and give efficient constant-depth constructions for nested-relational DTDs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1694
Venue: PODS
Year: 2016
Pagerank: 4.7135369e-05
Overall Rank: 7,504 | 47.85%
DOI: 10.1145/2902251.2902299

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,496	Stackless Processing of Streamed Trees	2021	PODS	4.7135369e-05
10,306	Streaming Validation of JSON Documents Against Schemas	2026	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,364	Validating Streaming XML Documents	2002	PODS	0.00012380546

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,253	Buffering in Query Evaluation over XML Streams	2005	PODS	5.6002448e-05
8,190	XML Schema Mappings	2009	PODS	4.5598146e-05
12,225	Simplifying XML Schema: Single-Type Approximations of Regular Tree Languages	2010	PODS	4.1905499e-05
12,165	Type-Based Detection of XML Query-Update Independence	2012	VLDB	4.1905499e-05
2,155	Frontiers of Tractability for Typechecking Simple XML Transformations	2004	PODS	9.4164126e-05
10,306	Streaming Validation of JSON Documents Against Schemas	2026	VLDB	4.1905499e-05
12,372	Stream Firewalling of XML Constraints	2008	SIGMOD	4.1905499e-05
3,697	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS	6.8281158e-05
1,854	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	0.00010320817
1,364	Validating Streaming XML Documents	2002	PODS	0.00012380546