TWO ALGORITHMS FOR LOCATING ANCESTORS OF A LARGE SET OF VERTICES IN A TREE

Oleksandr Panchenko, Arian Treffer, Hasso Plattner, Alexander Zeier

2011

Abstract

A lot of tree-shaped data exists: XML documents, abstract syntax trees, hierarchies, etc. To accelerate query processing on trees stored in a relational database a pre-post-ordering can be used. It works well for locating ancestors of a single or few vertices because pre-post-ordering avoids recursive table access. However, it is slow if it comes to locating ancestors of hundreds or thousands of vertices because ancestors of each of the input vertices are located sequentially. In this paper, two novel algorithms (sort-tilt-scan and single-pass-scan) for solving this problem are proposed and compared with a näıve approach. While the sort-tilt-scan improves the performance by a constant factor, the single-pass-scan achieves a better complexity class. The performance gain is achieved because of a single table scan which can locate all result vertices by a single run. Using generated data, this paper demonstrates that the single-pass-scan is orders of magnitude faster than the näıve approach.

Download


Paper Citation


in Harvard Style

Panchenko O., Treffer A., Plattner H. and Zeier A. (2011). TWO ALGORITHMS FOR LOCATING ANCESTORS OF A LARGE SET OF VERTICES IN A TREE . In Proceedings of the 6th International Conference on Software and Database Technologies - Volume 1: ICSOFT, ISBN 978-989-8425-76-8, pages 280-285. DOI: 10.5220/0003599202800285

in Bibtex Style

@conference{icsoft11,
author={Oleksandr Panchenko and Arian Treffer and Hasso Plattner and Alexander Zeier},
title={TWO ALGORITHMS FOR LOCATING ANCESTORS OF A LARGE SET OF VERTICES IN A TREE},
booktitle={Proceedings of the 6th International Conference on Software and Database Technologies - Volume 1: ICSOFT,},
year={2011},
pages={280-285},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003599202800285},
isbn={978-989-8425-76-8},
}


in EndNote Style

TY - CONF
JO - Proceedings of the 6th International Conference on Software and Database Technologies - Volume 1: ICSOFT,
TI - TWO ALGORITHMS FOR LOCATING ANCESTORS OF A LARGE SET OF VERTICES IN A TREE
SN - 978-989-8425-76-8
AU - Panchenko O.
AU - Treffer A.
AU - Plattner H.
AU - Zeier A.
PY - 2011
SP - 280
EP - 285
DO - 10.5220/0003599202800285