Transforming XML Streams with References

Sebastian Maneth; Alberto Ordóñez; Helmut Seidl

doi:10.1007/978-3-319-23826-5_4

Transforming XML Streams with References

Sebastian Maneth, Alberto Ordóñez, Helmut Seidl

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Many useful xml transformations can be formulated through deterministic top-down tree transducers. If transducers process parts of the input repeatedly or in non-document order, then they cannot be realized over the xml stream with constant or even depth-bounded memory. We show that by enriching streams by forward references both in the input and in the output, every such transformation can be compiled into a stream processor with a space consumption depending only on the transducer and the depth of the xml document. References allow to produce DAG-compressed output that is guaranteed to be linear in the size of the input (up to the space required for labels). Our model is designed so that without decompression, the output may again serve as the input of a subsequent transducer.

Original language	English
Title of host publication	String Processing and Information Retrieval
Subtitle of host publication	22nd International Symposium, SPIRE 2015, London, UK, September 1-4, 2015, Proceedings
Editors	Costas Iliopoulos, Simon Puglisi, Emine Yilmaz
Publisher	Springer
Pages	33-45
Number of pages	13
ISBN (Electronic)	978-3-319-23826-5
ISBN (Print)	978-3-319-23825-8
DOIs	https://doi.org/10.1007/978-3-319-23826-5_4
Publication status	Published - Sept 2015

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer International Publishing
Volume	9309
ISSN (Print)	0302-9743

Access to Document

10.1007/978-3-319-23826-5_4

Maneth et al 2015 Transforming XML StreamsAccepted author manuscript, 433 KB

http://link.springer.com/chapter/10.1007%2F978-3-319-23826-5_4

Cite this

Maneth, S., Ordóñez, A., & Seidl, H. (2015). Transforming XML Streams with References. In C. Iliopoulos, S. Puglisi, & E. Yilmaz (Eds.), String Processing and Information Retrieval: 22nd International Symposium, SPIRE 2015, London, UK, September 1-4, 2015, Proceedings (pp. 33-45). (Lecture Notes in Computer Science; Vol. 9309). Springer. https://doi.org/10.1007/978-3-319-23826-5_4

@inproceedings{d5fe5fd7277f4b0e853a53184f984c15,

title = "Transforming XML Streams with References",

abstract = "Many useful xml transformations can be formulated through deterministic top-down tree transducers. If transducers process parts of the input repeatedly or in non-document order, then they cannot be realized over the xml stream with constant or even depth-bounded memory. We show that by enriching streams by forward references both in the input and in the output, every such transformation can be compiled into a stream processor with a space consumption depending only on the transducer and the depth of the xml document. References allow to produce DAG-compressed output that is guaranteed to be linear in the size of the input (up to the space required for labels). Our model is designed so that without decompression, the output may again serve as the input of a subsequent transducer.",

author = "Sebastian Maneth and Alberto Ord{\'o}{\~n}ez and Helmut Seidl",

year = "2015",

month = sep,

doi = "10.1007/978-3-319-23826-5\_4",

language = "English",

isbn = "978-3-319-23825-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "33--45",

editor = "Costas Iliopoulos and Simon Puglisi and Emine Yilmaz",

booktitle = "String Processing and Information Retrieval",

address = "United Kingdom",

}

Maneth, S, Ordóñez, A & Seidl, H 2015, Transforming XML Streams with References. in C Iliopoulos, S Puglisi & E Yilmaz (eds), String Processing and Information Retrieval: 22nd International Symposium, SPIRE 2015, London, UK, September 1-4, 2015, Proceedings. Lecture Notes in Computer Science, vol. 9309, Springer, pp. 33-45. https://doi.org/10.1007/978-3-319-23826-5_4

Transforming XML Streams with References. / Maneth, Sebastian; Ordóñez, Alberto; Seidl, Helmut.
String Processing and Information Retrieval: 22nd International Symposium, SPIRE 2015, London, UK, September 1-4, 2015, Proceedings. ed. / Costas Iliopoulos; Simon Puglisi; Emine Yilmaz. Springer, 2015. p. 33-45 (Lecture Notes in Computer Science; Vol. 9309).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Transforming XML Streams with References

AU - Maneth, Sebastian

AU - Ordóñez, Alberto

AU - Seidl, Helmut

PY - 2015/9

Y1 - 2015/9

N2 - Many useful xml transformations can be formulated through deterministic top-down tree transducers. If transducers process parts of the input repeatedly or in non-document order, then they cannot be realized over the xml stream with constant or even depth-bounded memory. We show that by enriching streams by forward references both in the input and in the output, every such transformation can be compiled into a stream processor with a space consumption depending only on the transducer and the depth of the xml document. References allow to produce DAG-compressed output that is guaranteed to be linear in the size of the input (up to the space required for labels). Our model is designed so that without decompression, the output may again serve as the input of a subsequent transducer.

AB - Many useful xml transformations can be formulated through deterministic top-down tree transducers. If transducers process parts of the input repeatedly or in non-document order, then they cannot be realized over the xml stream with constant or even depth-bounded memory. We show that by enriching streams by forward references both in the input and in the output, every such transformation can be compiled into a stream processor with a space consumption depending only on the transducer and the depth of the xml document. References allow to produce DAG-compressed output that is guaranteed to be linear in the size of the input (up to the space required for labels). Our model is designed so that without decompression, the output may again serve as the input of a subsequent transducer.

U2 - 10.1007/978-3-319-23826-5_4

DO - 10.1007/978-3-319-23826-5_4

M3 - Conference contribution

SN - 978-3-319-23825-8

T3 - Lecture Notes in Computer Science

SP - 33

EP - 45

BT - String Processing and Information Retrieval

A2 - Iliopoulos, Costas

A2 - Puglisi, Simon

A2 - Yilmaz, Emine

PB - Springer

ER -

Transforming XML Streams with References

Abstract

Publication series

Access to Document

Fingerprint

Cite this