Automata Approach to XML Data Indexing

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F18%3A00316899" target="_blank" >RIV/68407700:21240/18:00316899 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.mdpi.com/2078-2489/9/1/12" target="_blank" >http://www.mdpi.com/2078-2489/9/1/12</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3390/info9010012" target="_blank" >10.3390/info9010012</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Automata Approach to XML Data Indexing

Popis výsledku v původním jazyce

The internal structure of XML documents can be viewed as a tree. Trees are among the fundamental and well-studied data structures in computer science. They express a hierarchical structure and are widely used in many applications. This paper focuses on the problem of processing tree data structures; particularly, it studies the XML index problem. Although there exist many state-of-the-art methods, the XML index problem still belongs to the active research areas. However, existing methods usually lack clear references to a systematic approach to the standard theory of formal languages and automata. Therefore, we present some new methods solving the XML index problem using the automata theory. These methods are simple and allow one to efficiently process a small subset of XPath. Thus, having an XML data structure, our methods can be used efficiently as auxiliary data structures that enable answering a particular set of queries, e.g., XPath queries using any combination of the child and descendant-or-self axes. Given an XML tree model with n nodes, the searching phase uses the index, reads an input query of size m, finds the answer in time O(m) and does not depend on the size of the original XML document.

Název v anglickém jazyce

Automata Approach to XML Data Indexing

Popis výsledku anglicky

The internal structure of XML documents can be viewed as a tree. Trees are among the fundamental and well-studied data structures in computer science. They express a hierarchical structure and are widely used in many applications. This paper focuses on the problem of processing tree data structures; particularly, it studies the XML index problem. Although there exist many state-of-the-art methods, the XML index problem still belongs to the active research areas. However, existing methods usually lack clear references to a systematic approach to the standard theory of formal languages and automata. Therefore, we present some new methods solving the XML index problem using the automata theory. These methods are simple and allow one to efficiently process a small subset of XPath. Thus, having an XML data structure, our methods can be used efficiently as auxiliary data structures that enable answering a particular set of queries, e.g., XPath queries using any combination of the child and descendant-or-self axes. Given an XML tree model with n nodes, the searching phase uses the index, reads an input query of size m, finds the answer in time O(m) and does not depend on the size of the original XML document.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2018

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 periodika

Information

ISSN

2078-2489

e-ISSN

2078-2489

Svazek periodika

9

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

CH - Švýcarská konfederace

Počet stran výsledku

25

Strana od-do

—

Kód UT WoS článku

000436146300012

EID výsledku v databázi Scopus

2-s2.0-85040102641