An experimental evaluation of k2 -tree on external memory

An experimental evaluation of k2 -tree on external memory | Authorea try { document.documentElement.classList.add('js'); } catch (e) { } var _gaq = _gaq || []; _gaq.push(['_setAccount', 'G-8VDV14Y67G']); _gaq.push(['_trackPageview']); (function() { var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true; ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s); })(); Skip to main content Preprints Collections Wiley Open Research IET Open Research Ecological Society of Japan All Collections About About Authorea FAQs Contact Us Quick Search anywhere Search for preprint articles, keywords, etc. Search Search ADVANCED SEARCH SCROLL Software: Practice and Experience This is a preprint and has not been peer reviewed. Data may be preliminary. 13 June 2025 V1 Latest version Share on An experimental evaluation of k2 -tree on external memory Authors : Gilberto Gutiérrez , Miguel Romero , Miguel R. Penabad 0000-0001-5455-6088 [email protected] , Fernando Santolaya , Mónica Caniupán , and Rodrigo Torres Authors Info & Affiliations https://doi.org/10.22541/au.174981976.68727737/v1 Published Software: Practice and Experience Version of record Peer review timeline 261 views 151 downloads Contents Abstract Supplementary Material Information & Authors Metrics & Citations View Options References Figures Tables Media Share Abstract The k 2 -tree compact data structure has gained great popularity to represent binary relationships in main memory. It presents a good performance and a good trade-off between storage and execution time. However, datasets being too large, or limited resources, may prevent the dataset from fitting into RAM even in compressed form. This work presents an experimental evaluation of a k 2 -tree in external memory (disk), in terms data access (I/O operation or cache misses) and execution time for 4 types of common queries. We compare the k 2 -tree with other data structures, namely a Quadtree (specifically, a Linear QuadTree, LQT) and the classical adjacency matrix, all of them being in external memory. We used for the test both synthetical as well as large, real world, datasets. Several aspects, such as the size of the memory buffer and its replacement scheme, or specific parameters like the arity ( k value) of the k 2 -tree were considered in the experiments. In terms of storage needs, the k 2 -tree clearly outperforms the other alternatives, in extreme cases needing only 1% of the LQT space, or 0.01% of the adjacency matrix (and for some large datasets neither the LQT nor the adjacency matrix could be built). In terms of performance, except for cases with small datasets, where the adjacency matrix is the best option for some queries, the k 2 -tree is either competitive or outperforms the alternatives. Supplementary Material File (an_experimental_evaluation_of_k_2_tree_on_external_memory.pdf) Download 1.04 MB Information & Authors Information Version history V1 Version 1 13 June 2025 Peer review timeline Published Software: Practice and Experience Version of Record 24 Oct 2025 Published Copyright This work is licensed under a Non Exclusive No Reuse License. Collection Software: Practice and Experience Keywords k2-tree compact data structures external memory Authors Affiliations Gilberto Gutiérrez Universidad del Bio-Bio - Sede Chillan View all articles by this author Miguel Romero Universidad del Bio-Bio - Sede Chillan View all articles by this author Miguel R. Penabad 0000-0001-5455-6088 [email protected] Universidade da Coruna Centro de Investigacion en Tecnologias de la Informacion y las Comunicaciones de Galicia View all articles by this author Fernando Santolaya Universidad del Bio-Bio - Sede Chillan View all articles by this author Mónica Caniupán Universidad del Bio-Bio - Sede Chillan View all articles by this author Rodrigo Torres Universidad del Bio-Bio - Sede Chillan View all articles by this author Metrics & Citations Metrics Article Usage 261 views 151 downloads .FvxKWukQNSOunydq8rnd { width: 100px; } Citations Download citation Gilberto Gutiérrez, Miguel Romero, Miguel R. Penabad, et al. An experimental evaluation of k2 -tree on external memory. Authorea . 13 June 2025. DOI: https://doi.org/10.22541/au.174981976.68727737/v1 If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download. For more information or tips please see 'Downloading to a citation manager' in the Help menu . Format Please select one from the list RIS (ProCite, Reference Manager) EndNote BibTex Medlars RefWorks Direct import Tips for downloading citations document.getElementById('citMgrHelpLink').addEventListener('click', function() { popupHelp(this.href); return false; }); $(".js__slcInclude").on("change", function(e){ if ($(this).val() == 'refworks') $('#direct').prop("checked", false); $('#direct').prop("disabled", ($(this).val() == 'refworks')); }); View Options View options PDF View PDF Figures Tables Media Share Share Share article link Copy Link Copied! Copying failed. Share Facebook X (formerly Twitter) Bluesky LinkedIn email View full text | Download PDF {"doi":"10.22541/au.174981976.68727737/v1","type":"Article"} Now Reading: Share Figures Tables Close figure viewer Back to article Figure title goes here Change zoom level Go to figure location within the article Download figure Toggle share panel Toggle share panel Share Toggle information panel Toggle information panel Go to previous graphic Go to next graphic Go to previous table Go to next table All figures All tables View all material View all material xrefBack.goTo xrefBack.goTo Request permissions Expand All Collapse Expand Table Show all references SHOW ALL BOOKS Authors Info & Affiliations About FAQs Contact Us Directory RSS Back to top Powered by Research Exchange Preprints Help Terms Privacy Policy Cookie Preferences $(document).ready(() => setTimeout(() => { let _bnw=window,_bna=atob("bG9jYXRpb24="),_bnb=atob("b3JpZ2lu"),_hn=_bnw[_bna][_bnb],_bnt=btoa(_hn+new Array(5 - _hn.length % 4).join(" ")); $.get("/resource/lodash?t="+_bnt); },4000)); (function(){function c(){var b=a.contentDocument||a.contentWindow.document;if(b){var d=b.createElement('script');d.innerHTML="window.__CF$cv$params={r:'9fea6a0dfcef06e3',t:'MTc3OTI3MDM4Ng=='};var a=document.createElement('script');a.src='/cdn-cgi/challenge-platform/scripts/jsd/main.js';document.getElementsByTagName('head')[0].appendChild(a);";b.getElementsByTagName('head')[0].appendChild(d)}}if(document.body){var a=document.createElement('iframe');a.height=1;a.width=1;a.style.position='absolute';a.style.top=0;a.style.left=0;a.style.border='none';a.style.visibility='hidden';document.body.appendChild(a);if('loading'!==document.readyState)c();else if(window.addEventListener)document.addEventListener('DOMContentLoaded',c);else{var e=document.onreadystatechange||function(){};document.onreadystatechange=function(b){e(b);'loading'!==document.readyState&&(document.onreadystatechange=e,c())}}}})();