Not logged in.

Quick Search - Contribution

Contribution Details

Type Journal Article
Scope Discipline-based scholarship
Title Efficient top-k approximate subtree matching in small memory
Organization Unit
Authors
  • Nikolaus Augsten
  • Denilson Barbosa
  • Michael Böhlen
  • Themis Palpanas
Item Subtype Original Work
Refereed Yes
Status Published in final form
Language
  • English
Journal Title IEEE Transactions on Knowledge & Data Engineering
Publisher IEEE
Geographical Reach international
ISSN 1041-4347 (P) 1558-2191 (E)
Volume 23
Number 8
Page Range 1123 - 1137
Date 2011
Abstract Text We consider the Top-k Approximate Subtree Matching (TASM) problem: finding the k best matches of a small query tree within a large document tree using the canonical tree edit distance as a similarity measure between subtrees. Evaluating the tree edit distance for large XML trees is difficult: the best known algorithms have cubic runtime and quadratic space complexity, and, thus, do not scale. Our solution is TASM-postorder, a memory-efficient and scalable TASM algorithm. We prove an upper bound for the maximum subtree size for which the tree edit distance needs to be evaluated. The upper bound depends on the query and is independent of the document size and structure. A core problem is to efficiently prune subtrees that are above this size threshold. We develop an algorithm based on the prefix ring buffer that allows us to prune all subtrees above the threshold in a single postorder scan of the document. The size of the prefix ring buffer is linear in the threshold. As a result, the space complexity of TASM-postorder depends only on k and the query size, and the runtime of TASM-postorder is linear in the size of the document. Our experimental evaluation on large synthetic and real XML documents confirms our analytic results.
Digital Object Identifier 10.1109/TKDE.2010.245
Other Identification Number merlin-id:6169
PDF File Download from ZORA
Export BibTeX
EP3 XML (ZORA)
Additional Information © 2011 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.