{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T09:10:12Z","timestamp":1726218612304},"reference-count":24,"publisher":"SAGE Publications","issue":"6","license":[{"start":{"date-parts":[[2010,11,5]],"date-time":"2010-11-05T00:00:00Z","timestamp":1288915200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Information Science"],"published-print":{"date-parts":[[2010,12]]},"abstract":" 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. <\/jats:p>","DOI":"10.1177\/0165551510386170","type":"journal-article","created":{"date-parts":[[2010,11,6]],"date-time":"2010-11-06T00:52:22Z","timestamp":1289004742000},"page":"751-762","source":"Crossref","is-referenced-by-count":0,"title":["An efficient strategy for storing and searching binary trees in WORM external memory"],"prefix":"10.1177","volume":"36","author":[{"suffix":"Jr","given":"Elias P.","family":"Duarte","sequence":"first","affiliation":[{"name":"Federal University of Parana, Department of Informatics, Curitiba, PR, Brazil,"}]},{"given":"Karine","family":"Pires","sequence":"additional","affiliation":[{"name":"Federal University of Parana, Department of Informatics, Curitiba, PR, Brazil"}]},{"given":"Rui A.E.","family":"Tavares","sequence":"additional","affiliation":[{"name":"Federal University of Parana, Department of Informatics, Curitiba, PR, Brazil"}]}],"member":"179","published-online":{"date-parts":[[2010,11,5]]},"reference":[{"key":"atypb1","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2009","edition":"3"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/1031120.1031122"},{"journal-title":"Ph.D. Thesis","year":"2000","author":"C.N.S. Pedersen","key":"atypb4"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","year":"1979","author":"M.R. Garey","key":"atypb6"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1561\/0400000014"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0005-6_9"},{"volume-title":"Proceedings of the International Symposium on Spatial and Temporal Databases","author":"O. Procopiuc","key":"atypb9"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04989-7_3"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-1208-z"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1177\/0165551509340360"},{"volume-title":"Proceedings of the International ACM Conference on Information and Knowledge Management","author":"I. Kamel","key":"atypb13"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1021-x"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2005.02.002"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36574-5_4"},{"volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science","author":"U. Meyer","key":"atypb17"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970342585X"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703431573"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1002\/spe.844"},{"volume-title":"STXXL: C++ Standard Template Library for Extra Large Data Sets","year":"2010","key":"atypb21"},{"volume-title":"A Transparent Parallel I\/O Environment","year":"2010","author":"Tpie","key":"atypb22"},{"volume-title":"Approximation algorithms for bin-packing - an updated survey","year":"1984","author":"E.G. Coffman Jr","key":"atypb23"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2008.03.001"}],"container-title":["Journal of Information Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0165551510386170","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0165551510386170","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T08:20:56Z","timestamp":1726215656000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0165551510386170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,5]]},"references-count":24,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1177\/0165551510386170"],"URL":"https:\/\/doi.org\/10.1177\/0165551510386170","relation":{},"ISSN":["0165-5515","1741-6485"],"issn-type":[{"type":"print","value":"0165-5515"},{"type":"electronic","value":"1741-6485"}],"subject":[],"published":{"date-parts":[[2010,11,5]]}}}