A SPACE-EFFICIENT ALGORITHM FOR PAGING UNBALANCED BINARY TREES

Rui A. E. Tavares, Elias P. Duarte Jr

2007

Abstract

This work presents a new approach for paging large unbalanced binary trees which frequently appear in computational biology. The proposed algorithm aims at reducing the number of pages accessed for searching, and at decreasing the amount of unused space in each page as well as reducing the total number of pages required to store a tree. The algorithm builds the best possible paging when it is possible and employs an efficient strategy based on bin packing for allocating trees that are not complete. The complexity of the algorithm is presented. Experimental results are reported and compared with other approaches, including balanced trees. The comparison shows that the proposed approach is the only one that presents an average number of page accesses for searching close to the optimal and, at the same time, the page filling percentage is also close to the optimal.

Download


Paper Citation


in Harvard Style

A. E. Tavares R. and P. Duarte Jr E. (2007). A SPACE-EFFICIENT ALGORITHM FOR PAGING UNBALANCED BINARY TREES . In Proceedings of the Second International Conference on Software and Data Technologies - Volume 1: ICSOFT, ISBN 978-989-8111-05-0, pages 38-43. DOI: 10.5220/0001334500380043

in Bibtex Style

@conference{icsoft07,
author={Rui A. E. Tavares and Elias P. Duarte Jr},
title={A SPACE-EFFICIENT ALGORITHM FOR PAGING UNBALANCED BINARY TREES},
booktitle={Proceedings of the Second International Conference on Software and Data Technologies - Volume 1: ICSOFT,},
year={2007},
pages={38-43},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001334500380043},
isbn={978-989-8111-05-0},
}


in EndNote Style

TY - CONF
JO - Proceedings of the Second International Conference on Software and Data Technologies - Volume 1: ICSOFT,
TI - A SPACE-EFFICIENT ALGORITHM FOR PAGING UNBALANCED BINARY TREES
SN - 978-989-8111-05-0
AU - A. E. Tavares R.
AU - P. Duarte Jr E.
PY - 2007
SP - 38
EP - 43
DO - 10.5220/0001334500380043