NDLI: Schema Validation via Streaming Circuits

Please wait, while we are loading the content...

A Theory of Regular Queries

2016 ACM PODS Alberto O. Mendelzon Test-of-Time Award

Optimal Score Aggregation Algorithms

Incremental View Maintenance For Collection Programming

Data Management for Social Networking

Verification of Hierarchical Artifact Systems

Schema Validation via Streaming Circuits

Logical Aspects of Massively Parallel and Distributed Systems

Counting Answers to Existential Positive Queries: A Complexity Classification

Towards Tight Bounds for the Streaming Set Cover Problem

Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures

FAQ: Questions Asked Frequently

Hypertree Decompositions: Questions and Answers

AJAR: Aggregations and Joins over Annotated Relations

Recency-Bounded Verification of Dynamic Database-Driven Systems

Variability in Data Streams

Computing Join Queries with Functional Dependencies

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems

Space Lower Bounds for Itemset Frequency Sketches

Shortest Paths and Distances with Differential Privacy

Bounded Query Rewriting Using Views

Making SQL Queries Correct on Incomplete Databases: A Feasibility Study

Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors

Semantic Acyclicity Under Constraints

Better Algorithms for Counting Triangles in Data Streams

Are Few Bins Enough: Testing Histogram Distributions

Minimization of Tree Pattern Queries

Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable

Designing a Query Language for RDF: Marrying Open and Closed Worlds

Efficient Top-k Indexing via General Reductions

Tractable Lineages on Treelike Instances: Limits and Extensions

Locating a Small Cluster Privately

Range-Max Queries on Uncertain Data

Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins

Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries

Fast Algorithms for Parsing Sequences of Parentheses with Few Errors

On the Complexity of Inner Product Similarity Join

Schema Validation via Streaming Circuits

Content Provider	ACM Digital Library
Author	Pilipczuk, Michał Murlak, Filip Paperman, Charles
Abstract	XML schema validation can be performed in constant memory in the streaming model if and only if the schema admits only trees of bounded depth - an acceptable assumption from the practical view-point. In this paper we refine this analysis by taking into account that data can be streamed block-by-block, rather then letter-by-letter, which provides opportunities to speed up the computation by parallelizing the processing of each block. For this purpose we introduce the model of streaming circuits, which process words of arbitrary length in blocks of fixed size, passing constant amount of information between blocks. This model allows us to transfer fundamental results about the circuit complexity of regular languages to the setting of streaming schema validation, which leads to effective constructions of streaming circuits of depth logarithmic in the block size, or even constant under certain assumptions on the input schema. For nested-relational DTDs, a practically motivated class of bounded-depth XML schemas, we provide an efficient construction yielding constant-depth streaming circuits with particularly good parameters.
Starting Page	237
Ending Page	249
Page Count	13
File Format	PDF
ISBN	9781450341912
DOI	10.1145/2902251.2902299
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-06-15
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Streaming Nested-relational dtds Semi-structured data Xml Boolean circuits Schema validation
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in