Efficient Algorithms for Context Query Evaluation over a Tagged Corpus
Jérémy Barbay, Alex López-Ortiz · 2009
We present an optimal adaptive algorithm for context queries in tagged content The queries consist of locating instances of a tag within a context specified by the query using patterns with preorder, ancestor-descendant and proximity operators in the document tree implied by the tagged content. The time taken to resolve a query Q on a document tree T is logarithmic in the size of T, proportional to the size of Q, and to the difficulty of the combination of Q with T, as measured by the minimal size of a certificate of the answer. The performance of the algorithm is no worse than the classical worst-case optimal, while provably better on simpler queries and corpora. More formally, the algorithm runs in time O(δk lg (n/δk)) in the standard RAM model and in time O(δk lg lg min(n, σ)) in the Θ(lg (n))-word RAM model, where k is the number of edges in the query, δ is the minimum number of operations required to certify the answer to the query, n is the number of nodes in the tree, and σ is the number of labels indexed.