All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Indexing XML Documents Using Tree Paths Automaton

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F17%3A00314286" target="_blank" >RIV/68407700:21240/17:00314286 - isvavai.cz</a>

  • Result on the web

    <a href="http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7945" target="_blank" >http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7945</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.4230/OASIcs.SLATE.2017.10" target="_blank" >10.4230/OASIcs.SLATE.2017.10</a>

Alternative languages

  • Result language

    angličtina

  • Original language name

    Indexing XML Documents Using Tree Paths Automaton

  • Original language description

    An XML document can be viewed as a tree in a natural way. Processing tree data structures usually requires a pushdown automaton as a model of computation. Therefore, it is interesting that a finite automaton can be used to solve the XML index problem. In this paper, we attempt to support a significant fragment of XPath queries which may use any combination of child (i.e., /) and descendant-or-self (i.e., //) axis. A systematic approach to the construction of such XML index, which is a finite automaton called Tree Paths Automaton, is presented. Given an XML tree model T, the tree is first of all preprocessed by means of its linear fragments called string paths. Since only path queries are considered, the branching structure of the XML tree model can be omitted. For individual string paths, smaller Tree Paths Automata are built, and they are afterwards combined to form the index. The searching phase uses the index, reads an input query Q 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 the size of the XML document. Although the number of queries is clearly exponential in the number of nodes of the XML tree model, the size of the index seems to be, according to our experimental results, usually only about 2.5 times larger than the size of the original document.

  • Czech name

  • Czech description

Classification

  • Type

    D - Article in proceedings

  • CEP classification

  • OECD FORD branch

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

Result continuities

  • Project

  • Continuities

    S - Specificky vyzkum na vysokych skolach

Others

  • Publication year

    2017

  • Confidentiality

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

Data specific for result type

  • Article name in the collection

    6th Symposium on Languages, Applications and Technologies

  • ISBN

    978-3-95977-056-9

  • ISSN

  • e-ISSN

    1868-8969

  • Number of pages

    14

  • Pages from-to

    "10:1"-"10:14"

  • Publisher name

    Dagstuhl Publishing,

  • Place of publication

    Saarbrücken

  • Event location

    Vila do Conde

  • Event date

    Jun 26, 2017

  • Type of event by nationality

    WRD - Celosvětová akce

  • UT code for WoS article