Tree String Path Subsequences Automaton and Its Use for Indexing XML Documents

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F15%3A00238831" target="_blank" >RIV/68407700:21240/15:00238831 - isvavai.cz</a>

Výsledek na webu

<a href="http://link.springer.com/chapter/10.1007/978-3-319-27653-3_17" target="_blank" >http://link.springer.com/chapter/10.1007/978-3-319-27653-3_17</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-27653-3_17" target="_blank" >10.1007/978-3-319-27653-3_17</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Tree String Path Subsequences Automaton and Its Use for Indexing XML Documents

Popis výsledku v původním jazyce

The theory of indexing texts is well-researched, which does not hold for indexing other data structures, such as trees for example. In this paper a simple method of indexing a tree for subsequences of string paths in the tree by finite automaton is presented. The use of the index is shown on indexing XML documents for XPath descendant-or-self axis inspired queries. Given a subject tree T with n nodes, the tree is preprocessed and an index, which is a directed acyclic subsequence graph for a set of strings, is constructed. The searching phase uses the index, reads an input string path subsequence Q inspired by the specific XPath query of size m and computes the list of positions of all occurrences of Q in the tree T. The searching is performed in time O(m) and does not depend on n. Although the number of distinct valid queries is O(2n), the size of the index is O(hk), where h is the height of the tree T and k is the number of its leaves. Moreover, we discuss that in the case of indexing

Název v anglickém jazyce

Tree String Path Subsequences Automaton and Its Use for Indexing XML Documents

Popis výsledku anglicky

The theory of indexing texts is well-researched, which does not hold for indexing other data structures, such as trees for example. In this paper a simple method of indexing a tree for subsequences of string paths in the tree by finite automaton is presented. The use of the index is shown on indexing XML documents for XPath descendant-or-self axis inspired queries. Given a subject tree T with n nodes, the tree is preprocessed and an index, which is a directed acyclic subsequence graph for a set of strings, is constructed. The searching phase uses the index, reads an input string path subsequence Q inspired by the specific XPath query of size m and computes the list of positions of all occurrences of Q in the tree T. The searching is performed in time O(m) and does not depend on n. Although the number of distinct valid queries is O(2n), the size of the index is O(hk), where h is the height of the tree T and k is the number of its leaves. Moreover, we discuss that in the case of indexing

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA13-03253S" target="_blank" >GA13-03253S: Zpracování textových a stromových struktur a jejich aplikace</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Languages, Applications and Technologies

ISBN

978-3-319-27652-6

ISSN

1865-0929

e-ISSN

—

Počet stran výsledku

11

Strana od-do

171-181

Název nakladatele

Springer International Publishing AG

Místo vydání

Cham

Místo konání akce

Madrid

Datum konání akce

18. 6. 2015

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000370191100017