{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T18:52:51Z","timestamp":1772909571717,"version":"3.50.1"},"reference-count":86,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2007,8,6]],"date-time":"2007-08-06T00:00:00Z","timestamp":1186358400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[2008,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present the software library S<jats:sc>TXXL<\/jats:sc>that is an implementation of the C++ standard template library (STL) for processing huge data sets that can fit only on hard disks. It supports parallel disks, overlapping between disk I\/O and computation and it is the first I\/O\u2010efficient algorithm library that supports the pipelining technique that can save more than half of the I\/Os. S<jats:sc>TXXL<\/jats:sc>has been applied both in academic and industrial environments for a range of problems including text processing, graph algorithms, computational geometry, Gaussian elimination, visualization, and analysis of microscopic images, differential cryptographic analysis, etc. The performance of S<jats:sc>TXXL<\/jats:sc>and its applications are evaluated on synthetic and real\u2010world inputs. We present the design of the library, how its performance features are supported, and demonstrate how the library integrates with STL. Copyright \u00a9 2007 John Wiley &amp; Sons, Ltd.<\/jats:p>","DOI":"10.1002\/spe.844","type":"journal-article","created":{"date-parts":[[2007,8,6]],"date-time":"2007-08-06T11:47:11Z","timestamp":1186400831000},"page":"589-637","source":"Crossref","is-referenced-by-count":51,"title":["S<scp>TXXL<\/scp>: standard template library for XXL data sets"],"prefix":"10.1002","volume":"38","author":[{"given":"R.","family":"Dementiev","sequence":"first","affiliation":[]},{"given":"L.","family":"Kettner","sequence":"additional","affiliation":[]},{"given":"P.","family":"Sanders","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,8,6]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/38.933523"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0005-6_25"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00125"},{"key":"e_1_2_1_5_2","unstructured":"MooreRW. Enabling petabyte computing.http:\/\/www.nap.edu\/html\/whitepapers\/ch\u201048.html[2 July2007]."},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"von NeumannJ. First draft of a report on the EDVAC. Technical Report University of Pennsylvania 1945. Available at:http:\/\/www.virtualtravelog.net\/entries\/2003\u201008\u2010TheFirstDraft.pdf[28 July2007].","DOI":"10.5479\/sil.538961.39088011475779"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185207"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1022594.1022596"},{"key":"e_1_2_1_9_2","unstructured":"FrigoM LeisersonCE ProkopH RamachandranS.Cache\u2010oblivious algorithms. Fortieth Symposium on Foundations of Computer Science New York City NY 1999; 285\u2013298."},{"key":"e_1_2_1_10_2","first-page":"268","volume-title":"Proceedings of the 34th ACM Symposium on Theory of Computing","author":"Arge L","year":"2002"},{"key":"e_1_2_1_11_2","unstructured":"BanderM DuanZ IaconoJ WuJ.A locality\u2010preserving cache\u2010oblivious dynamic dictionary. Thirteenth Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201002) San Francisco CA 2002."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27810-8_41"},{"key":"e_1_2_1_13_2","unstructured":"ChristianiFJ.Cache\u2010oblivious graph algorithms. Master's Thesis Department of Mathematics and Computer Science (IMADA) University of Southern Denmark Odense 2005."},{"key":"e_1_2_1_14_2","first-page":"3","volume-title":"Ninth Workshop on Algorithm Engineering and Experiments (ALENEX)","author":"Ajwani D","year":"2007"},{"key":"e_1_2_1_15_2","unstructured":"BrodalGS FagerbergR VintherK.Engineering a Cache\u2010oblivious sorting algorithm. Sixth Workshop on Algorithm Engineering and Experiments New Orleans LA 2004."},{"key":"e_1_2_1_16_2","series-title":"Lecture Notes in Computer Science Tutorial","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-36574-5","volume-title":"Algorithms for Memory Hierarchies","author":"Meyer U","year":"2003"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"},{"key":"e_1_2_1_18_2","unstructured":"VengroffDE VitterJS.I\/O\u2010Efficient scientific computation using TPIE. Goddard Conference on Mass Storage Systems and Technologies College Park MD vol. 2 1996; 553\u2013570. Published in NASA Conference Publication vol. 3340."},{"key":"e_1_2_1_19_2","unstructured":"ChiangY\u2010J.Dynamic and I\/O\u2010efficient algorithms for computational geometry and graph algorithms. Ph.D. Thesis Brown University 1995."},{"key":"e_1_2_1_20_2","doi-asserted-by":"crossref","unstructured":"ProcopiucO AgarwalPK ArgeL VitterJS.Bkd\u2010tree: A dynamic scalable KD\u2010tree. Eighth International Symposium on Spatial and Temporal Databases (SSTD '03) Santorini Island Greece 2003; 46\u201365.","DOI":"10.1007\/978-3-540-45072-6_4"},{"key":"e_1_2_1_21_2","series-title":"Lecture Notes in Computer Science","first-page":"328","volume-title":"First Workshop on Algorithm Engineering and Experimentation (ALENEX '99)","author":"Arge L","year":"1999"},{"key":"e_1_2_1_22_2","doi-asserted-by":"crossref","unstructured":"AgarwalPK ArgeL GovindarajanS.CRB\u2010Tree: An efficient indexing scheme for range aggregate queries. Ninth International Conference on Database Theory (ICDT '03) Siena Italy 2003; 143\u2013157.","DOI":"10.1007\/3-540-36285-1_10"},{"issue":"17","key":"e_1_2_1_23_2","first-page":"1","article-title":"An experimental study of priority queues in external memory","volume":"5","author":"Brengel K","year":"2000","journal-title":"ACM Journal of Experimental Algorithms"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0051-5"},{"key":"e_1_2_1_25_2","unstructured":"StepanovAA LeeM.The standard template library. Technical Report X3J16\/94\u20100095 WG21\/N0482 Silicon Graphics Inc. Hewlett Packard Laboratories 1994."},{"key":"e_1_2_1_26_2","volume-title":"Beyond the C++ Standard Library: An Introduction to Boost","author":"Karlsson B","year":"2005"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1002\/1097-024X(200009)30:11<1167::AID-SPE337>3.0.CO;2-B"},{"key":"e_1_2_1_28_2","doi-asserted-by":"crossref","unstructured":"CrauserA MehlhornK.LEDA\u2010SM extending LEDA to secondary memory. Third International Workshop on Algorithmic Engineering (WAE) London U.K. (Lecture Notes in Computer Science vol. 1668) 1999; 228\u2013242.","DOI":"10.1007\/3-540-48318-7_19"},{"key":"e_1_2_1_29_2","unstructured":"ArgeL BarveR HutchinsonD ProcopiucO TomaL VengroffDE WickeremesingheR. TPIE: User Manual and Reference. 2003."},{"key":"e_1_2_1_30_2","unstructured":"VengroffDE.A transparent parallel I\/O environment. Third DAGS Symposium on Parallel Computation Hanover NH July 1994; 117\u2013134."},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45749-6_12"},{"key":"e_1_2_1_32_2","volume-title":"The LEDA Platform of Combinatorial and Geometric Computing","author":"Mehlhorn K","year":"1999"},{"key":"e_1_2_1_33_2","volume-title":"Database System Concepts","author":"Silberschatz A","year":"2001"},{"key":"e_1_2_1_34_2","unstructured":"DavidsonER CormenTH.Building on a framework: Using FG for more flexibility and improved performance in parallel programs. IPDPS Denver CO 2005."},{"key":"e_1_2_1_35_2","unstructured":"OlsonMA BosticK SeltzerM. Berkeley DB White Paper.http:\/\/www.oracle.com\/technology\/products\/berkeley\u2010db\/index.html[2 July2007]."},{"key":"e_1_2_1_36_2","unstructured":"AnP JulaA RusS SaundersS SmithT TanaseG ThomasN AmatoN RauchwergerL.STAPL: An adaptive generic parallel C++ Library. Workshop on Languages and Compilers for Parallel Computing (LCPC) Cumberland Falls Kentucky August 2001; 193\u2013208."},{"key":"e_1_2_1_37_2","doi-asserted-by":"crossref","unstructured":"PutzeF SandersP SinglerJ. The multi\u2010core standard template library. Euro\u2010Par 2007 Parallel Processing Rennes France to appear.http:\/\/algo2.iti.uni\u2010karlsruhe.de\/singler\/mcstl\/[28 July2007].","DOI":"10.1007\/978-3-540-74466-5_72"},{"key":"e_1_2_1_38_2","unstructured":"University of California Berkeley. dbm(3) Unix Programmer's Manual."},{"key":"e_1_2_1_39_2","unstructured":"University of California Berkeley. ndbm(3) 4.3BSD Unix Programmer's Manual."},{"key":"e_1_2_1_40_2","unstructured":"GaumondP NelsonPA DownsJ. GNU dbm: A Database Manager 1999."},{"issue":"4","key":"e_1_2_1_41_2","first-page":"45","article-title":"Disk\u2010based container objects","volume":"16","author":"Nelson T","year":"1998","journal-title":"C\/C++ Users Journal"},{"key":"e_1_2_1_42_2","unstructured":"KnizhnikK. Persistent object storage for C++.http:\/\/www.garret.ru\/\u223cknizhnik\/post\/readme.htm[2 July2007]."},{"key":"e_1_2_1_43_2","unstructured":"SinghalV KakkadSV WilsonPR.Texas: An efficient portable persistent store. Fifth International Workshop on Persistent Object Systems San Miniato Italy September 1992."},{"key":"e_1_2_1_44_2","unstructured":"StevensA.The persistent template library. Dr. Dobb's 1998; 117\u2013120."},{"key":"e_1_2_1_45_2","unstructured":"GschwindT.PSTL: A C++ persistent standard template library. Sixth USENIX Conference on Object\u2010oriented Technologies and Systems (COOTS'01) San Antonio TX U.S.A. January\u2013February 2001."},{"key":"e_1_2_1_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_57"},{"key":"e_1_2_1_47_2","doi-asserted-by":"crossref","unstructured":"DementievR SandersP.Asynchronous parallel disk sorting. Fifteenth ACM Symposium on Parallelism in Algorithms and Architectures San Diego 2003; 138\u2013148.","DOI":"10.1145\/777412.777435"},{"key":"e_1_2_1_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44676-1_5"},{"key":"e_1_2_1_49_2","article-title":"Better external memory suffix array construction","author":"Dementiev R","year":"2007","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"e_1_2_1_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(97)00015-X"},{"key":"e_1_2_1_51_2","unstructured":"VitterJS HitchinsonDA.Distribution sort with randomized cycling. Twelfth ACM\u2013SIAM Symposium on Discrete Algorithms Washington DC 2001; 77\u201386."},{"key":"e_1_2_1_52_2","unstructured":"ChiangY\u2010J GoodrichMT GroveEF TamassiaR VengroffDE VitterJS.External memory graph algorithms. Sixth Annual ACM\u2013SIAM Symposium on Discrete Algorithms San Francisco CA 1995; 139\u2013149."},{"key":"e_1_2_1_53_2","doi-asserted-by":"crossref","unstructured":"DementievR SandersP SchultesD SibeynJ.Engineering an external memory minimum spanning tree algorithm. IFIP TCS Toulouse 2004; 195\u2013208.","DOI":"10.1007\/1-4020-8141-3_17"},{"key":"e_1_2_1_54_2","unstructured":"ZehN.I\/O efficient algorithms for shortest path related problems. Ph.D. Thesis Carleton University Ottawa April 2002."},{"key":"e_1_2_1_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60220-8_74"},{"key":"e_1_2_1_56_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/351827.384249","article-title":"Fast priority queues for cached memory","volume":"5","author":"Sanders P","year":"2000","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"e_1_2_1_57_2","series-title":"Australian Computer Science Communications","first-page":"72","volume-title":"Fourth Australasian Theory Symposium","author":"Fadel R","year":"1997"},{"key":"e_1_2_1_58_2","volume-title":"The Art of Computer Programming\u2014Sorting and Searching","author":"Knuth DE","year":"1998"},{"key":"e_1_2_1_59_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288683"},{"key":"e_1_2_1_60_2","unstructured":"OlsonMA BosticK SeltzerM BerkeleyDB. USENIX Annual Technical Conference Monterey CA June 1999; 183\u2013192."},{"key":"e_1_2_1_61_2","doi-asserted-by":"crossref","unstructured":"KallahallaM VarmanPJ.Optimal prefetching and caching for parallel I\/O systems. Thirteenth Symposium on Parallel Algorithms and Architectures Heraklion Crete Greece 2001; 219\u2013228.","DOI":"10.1145\/378580.378648"},{"key":"e_1_2_1_62_2","doi-asserted-by":"crossref","unstructured":"RajasekaranS.A framework for simple sorting algorithms on parallel disk systems. Tenth ACM Symposium on Parallel Algorithms and Architectures Puerto Vallarta Mexico 1998; 88\u201398.","DOI":"10.1145\/277651.277675"},{"key":"e_1_2_1_63_2","doi-asserted-by":"crossref","unstructured":"ChaudhryG CormenTH.Getting more from out\u2010of\u2010core columnsort. Fourth Workshop on Algorithm Engineering and Experiments (ALENEX) San Francisco CA (Lecture Notes in Computer Science vol. 2409) 2002; 143\u2013154.","DOI":"10.1007\/3-540-45643-0_11"},{"key":"e_1_2_1_64_2","doi-asserted-by":"crossref","unstructured":"ChaudhryG CormenTH WisniewskiLF.Columnsort lives! an efficient out\u2010of\u2010core sorting program. Thirteenth ACM Symposium on Parallel Algorithms and Architectures Heraklion Crete Greece 2001; 169\u2013178.","DOI":"10.1145\/378580.378627"},{"key":"e_1_2_1_65_2","doi-asserted-by":"crossref","unstructured":"PaiVS VarmanPJ.Prefetching with multiple disks for external mergesort: Simulation and analysis. ICDE Tempe AZ 1992; 273\u2013282.","DOI":"10.1109\/ICDE.1992.213183"},{"key":"e_1_2_1_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/235543.235544"},{"key":"e_1_2_1_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276858"},{"key":"e_1_2_1_68_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797326976"},{"key":"e_1_2_1_69_2","doi-asserted-by":"crossref","unstructured":"NybergC BarclayT CvetanovicZ GrayJ LometD.AlphaSort: A RISC machine sort. SIGMOD Minneapolis MN 1994; 233\u2013242.","DOI":"10.1145\/191843.191884"},{"key":"e_1_2_1_70_2","doi-asserted-by":"crossref","unstructured":"AgarwalR.A super scalar sort algorithm for RISC processors. ACM SIGMOD International Conference on Management of Data Montreal Canada 1996; 240\u2013246.","DOI":"10.1145\/235968.233336"},{"key":"e_1_2_1_71_2","unstructured":"NybergC KoesterC GrayJ. Nsort: A parallel sorting program for NUMA and SMP machines.http:\/\/www.ordinal.com\/lit.html[2 July2007]."},{"key":"e_1_2_1_72_2","unstructured":"WyllieJ. SPsort: How to sort a terabyte quickly.http:\/\/research.microsoft.com\/barc\/SortBenchmark\/SPsort.pdf[2 July2007]."},{"key":"e_1_2_1_73_2","unstructured":"GrayJ. Sort Benchmark Home Page.http:\/\/research.microsoft.com\/barc\/sortbenchmark\/[2 July2007]."},{"key":"e_1_2_1_74_2","unstructured":"GovindarajuK GrayJ KumarR ManochaD.GPU\u2010Tera\u2010Sort: High performance graphics coprocessor sorting for large database management. Technical Report MSR\u2010TR\u20102005\u2010183 Microsoft December2005. Revised March 2006."},{"key":"e_1_2_1_75_2","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_76_2","unstructured":"MehnertJ. External memory suffix array construction. Master's Thesis University of Saarland Germany November 2004. Available at:http:\/\/algo2.iti.uka.de\/dementiev\/esuffix\/docu\/data\/diplom.pdf[28 July2007]."},{"key":"e_1_2_1_77_2","volume-title":"Generative Programming: Methods, Tools, and Applications","author":"Czarnecki K","year":"2000"},{"key":"e_1_2_1_78_2","unstructured":"TangH.A suffix array based n\u2010gram extraction algorithm. Master's Thesis Faculty of Computer Science Dalhousie University 2005."},{"key":"e_1_2_1_79_2","unstructured":"RibichiniA. Tradeoff algorithms in streaming models. Progress Report University of Rome \u2018La Sapienza\u2019 2006. Available at:http:\/\/www.dis.uniroma1.it\/\u223cdottorato\/db\/relazioni\/relaz_ribichini_2.pdf[28 July2007]."},{"key":"e_1_2_1_80_2","doi-asserted-by":"publisher","DOI":"10.1145\/1148109.1148150"},{"key":"e_1_2_1_81_2","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137927"},{"key":"e_1_2_1_82_2","unstructured":"AjwaniD.Design implementation and experimental study of external memory BFS algorithms. Master's Thesis Max\u2010Planck\u2010Institut f\u00fcr Informatik Saarbr\u00fccken Germany January 2005."},{"key":"e_1_2_1_83_2","unstructured":"MunagalaK RanadeA.I\/O\u2010complexity of graph algorithms. Tenth Symposium on Discrete Algorithms Baltimore MD ACM\u2013SIAM 1999; 687\u2013694."},{"key":"e_1_2_1_84_2","doi-asserted-by":"crossref","unstructured":"MehlhornK MeyerU.External\u2010memory breadth\u2010first search with sublinear I\/O. Tenth Annual European Symposium on Algorithms (ESA) Rome Italy (Lecture Notes in Computer Science vol. 2461) 2002; 723\u2013735.","DOI":"10.1007\/3-540-45749-6_63"},{"key":"e_1_2_1_85_2","unstructured":"SchultesD. External memory spanning forests and connected components.http:\/\/i10www.ira.uka.de\/dementiev\/files\/cc.pdf[2 July2007]."},{"key":"e_1_2_1_86_2","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1979.9989889"},{"key":"e_1_2_1_87_2","unstructured":"DementievR.Algorithm engineering for large data sets. Dissertation University of Saarland 2006."}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.844","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.844","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T04:28:01Z","timestamp":1737347281000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.844"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8,6]]},"references-count":86,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["10.1002\/spe.844"],"URL":"https:\/\/doi.org\/10.1002\/spe.844","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"value":"0038-0644","type":"print"},{"value":"1097-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,8,6]]}}}