Mikołaj Bojańczyk

XML algorithms

July 14, 2015
  1. Mikołaj Bojańczyk, Pawel Parys
    XPath evaluation in linear time. J. ACM, 2011   PDF

  2. Mikołaj Bojańczyk, Pawel Parys
    Efficient Evaluation of Nondeterministic Automata Using Factorization Forests. ICALP (1), 2010   PDF

  3. Mikołaj Bojańczyk, Diego Figueira
    Efficient evaluation for a temporal logic on changing XML documents. PODS  PDF

This is a group of algorithms that work with XML documents in linear or almost linear time. This is in contrast with the XML motivated algorithms on data words and data trees, where typically the running time is exponential or much worse. The first paper shows that XPath can be evaluated in linear time (improving on previous quadratic algorithms), while the second paper tries to explain this phenomenon using automata theory. The last paper considers evolving XML documents. It describes a logic that can express properties like “if a node in the document gets label a at some point in time, then at later points in time all of its descendants will have label b“. The main contribution is an algorithm that runs in time c \cdot n \cdot \log n where n is the number of edits, and c is a constant that depends (unfortunately, in a nonelementary way) on the formula.

Paper [1] is a journal version of

  • Mikołaj Bojańczyk, Pawel Parys
    XPath evaluation in linear time. PODS, 2008   PDF

and a PODS 2009 paper by Paweł Parys.


Leave a Reply

Your email address will not be published.