Consider the problem of searching and storing a massive binary tree in WORM (Write Once Read Many) secondary memory. Tree nodes are organized in pages, each of which contains a fixed number of nodes. Pages are transferred to primary memory as the tree is traversed. This work presents a new strategy for paging that aims to decrease the amount of unused space in each page as well as to reduce the total number of pages required to store the tree while also reduce the number of pages accessed for searching. The algorithm employs an efficient strategy based on bin packing for allocating unbalanced trees. Experimental results are reported comparing the performance of two bin-packing heuristics, as well as other paging strategies and B-trees. Results confirm the superior performance of the proposed approach both in terms of the number of page transfers required for searching and the page filling percentage.
T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, 3rd edn ( MIT Press, Cambridge, MA, 2009).
2.
D. Comer, The ubiquitous B-Tree, ACM Computing Surveys11(2) (1979) 121-137.
3.
J. Cohen, Bioinformatics - an introduction for computer scientists, ACM Computing Surveys36(2) (2004) 122-158.
4.
C.N.S. Pedersen , Algorithms in computational biology, Ph.D. Thesis (University of Aarhus, Denmark, 2000).
5.
J.S. Vitter , External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys33(2) (2001) 209-271.
6.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ( W.H. Freeman and Company, New York, 1979).
7.
J.S. Vitter , Algorithms and data structures for external memory, Foundation and Trends in Theoretical Computer Science2(4) ( 2006) 305-474.
8.
L. Arge.External memory data structures. In: J. Abello, P.M. Pardalos and M.G.C. Resende (eds), Handbook of Massive Data Sets (Kluwer Academic Publishers , New York, 2002).
9.
O. Procopiuc , P.K. Agarwal, L. Arge and J.S. Vitter, Bkd-tree: a dynamic scalable KD-tree. In: Proceedings of the International Symposium on Spatial and Temporal Databases (Springer-Verlag, Heidelberg, 2003).
10.
A. Kiefer , E.P. Duarte Jr. and C.D. Murta, Monitoring multiple concurrent service level parameters with multidimensional trees. In: Lecture Notes in Computer Science5841 ( Springer-Verlag, Heidelberg, 2009 ).
11.
L. Arge, D.E. Vengroff and J.S. Vitter, External-memory algorithms for processing line segments in geographic information systems, Algorithmica47(1) (2007) 1-25.
12.
A.F. Al-Badarneh , Q. Yaseen and I. Hmeidi, A new enhancement to the R-tree node splitting , Journal of Information Science36(1) (2010) 3-18.
13.
I. Kamel and C. Faloutsos, On packing R-trees. In: Proceedings of the International ACM Conference on Information and Knowledge Management (1993 ).
14.
L. Arge, The Buffer Tree: a technique for designing batched external data structures , Algorithmica37(1) (2003) 1-24.
15.
J.F. Sibeyn , External selection, Journal of Algorithms58(2) (2006) 104-117.
16.
I. Katriel and U. Meyer, Elementary graph algorithms in external memory. In: U. Meyer, P. Sanders and J. Sibeyn (eds), Algorithms for Memory Hierarchies (Springer-Verlag, Heidelberg, 2003).
17.
U. Meyer, On dynamic breadth-first search in external-memory. In: Proceedings of the Symposium on Theoretical Aspects of Computer Science ( 2008).
18.
S. Khuller, Y.A. Kim and Y.-C.J. Wan, Algorithms for data migration with cloning, SIAM Journal on Computing33(2) (2004) 448-461, 2004.
19.
D.A. Hutchinson , P. Sanders and J.S. Vitter, Duality between prefetching and queued writing with parallel disks, SIAM Journal on Computing34(6) (2005) 1443-1463.
20.
R. Dementiev , L. Kettner and P. Sanders, STXXL: standard template library for XXL data sets, Software - Practice and Experience38(6) (2008) 589-637.
21.
STXXL: C++ Standard Template Library for Extra Large Data Sets . Available at http://stxxl.sourceforge.net/ (accessed October 2010).
22.
Tpie:A Transparent Parallel I/O Environment. Available at: www.madalgo.au.dk (accessed October 2010).
23.
E.G. Coffman Jr, M.R. Garey and D.S. Johnson, Approximation algorithms for bin-packing - an updated survey. In: G. Ausiello, M. Lucertini and P. Serafini (eds) Algorithm Design for Computer System Design ( Springer-Verlag, Heidelberg, 1984 ).
24.
H. Sundell and P. Tsigas, Lock-free deques and doubly linked lists , Journal of Parallel and Distributed Computing68(7) (2008) 1008-1020.
