% -*- fill-column: 1000 -*- @InProceedings{APV02, author = "L. Arge and O. Procopiuc and J. S. Vitter", title = "{Implementing I/O-efficient Data Structures Using TPIE}", booktitle = "10th European Symposium on Algorithms (ESA)", pages = "88--100", year = 2002, volume = 2461, series = "LNCS", publisher = "Springer" } @InProceedings{CraMeh99, author = "A. Crauser and K. Mehlhorn", title = "{LEDA-SM}, extending {LEDA} to Secondary Memory", booktitle = "3rd International Workshop on Algorithmic Engineering (WAE)", pages = "228--242", year = 1999, volume = 1668, series = "LNCS" } @Article{VitShr94both, author = "J. S. Vitter and E. A. M. Shriver", title = "Algorithms for parallel memory, {I/II}", journal = "Algorithmica", year = 1994, volume = 12, number = "2/3", pages = "110--169" } @InProceedings{HutSanVit01b, author = "D. A. Hutchinson and P. Sanders and J. S. Vitter", title = "Duality Between Prefetching and Queued Writing with Parallel Disks", booktitle = "9th European Symposium on Algorithms (ESA)", year = 2001, number = 2161, pages = "62--73", series = "LNCS", publisher = "Springer", } @InProceedings{DemSan03, author = "R. Dementiev and P. Sanders", title = "Asynchronous Parallel Disk Sorting", booktitle = "15th ACM Symposium on Parallelism in Algorithms and Architectures", pages = "138--148", year = 2003, address = "San Diego", } @Manual{tpie_manual, author = "Lars Arge and Rakesh Barve and David Hutchinson and Octavian Procopiuc and Laura Toma and Darren Erik Vengroff and Rajiv Wickeremesinghe", title = "{TPIE}: User manual and reference", year = 2003, month = nov } @InProceedings{DKMS05, author = "R. Dementiev and J. Mehnert and J. K{\"a}rkk{\"a}inen and P. Sanders", title = "{Better External Memory Suffix Array Construction}", booktitle = "Workshop on Algorithm Engineering {\&} Experiments", year = 2005, address = "Vancouver", note = "\url{http://i10www.ira.uka.de/dementiev/files/DKMS05.pdf}" } @InProceedings{VitHut01, author = "J. S. Vitter and D. A. Hutchinson", title = "Distribution sort with randomized cycling", booktitle = "12th ACM-SIAM Symposium on Discrete Algorithms", pages = "77--86", year = 2001 } @Article{BarGroVit97, author = "R. D. Barve and E. F. Grove and J. S. Vitter", title = "Simple Randomized Mergesort on Parallel Disks", journal = "Parallel Computing", year = 1997, volume = 23, number = 4, pages = "601--631", annote = "auch TR CS-1996-15, Duke" } @Book{BicShaw2003, author = {L.F. Bic and A.C. Shaw}, title = {Operating Systems Principles}, publisher = {Pearson Education}, year = {2003}, } @PhdThesis{ZehPhd, author = {Norbert Ralf Zeh}, title = {I/O Efficient Algorithms for Shortest Path Related Problems}, school = {Carleton University, Ottawa}, year = {2002}, month = apr, } @InProceedings{ChiEtAl95, author = "Y.-J. Chiang and M. T. Goodrich and E. F. Grove and R. Tamasia and D. E. Vengroff and J. S. Vitter", title = "External memory graph algorithms", pages = "139--149", booktitle = "6th Annual {ACM}-{SIAM} Symposium on Discrete Algorithms", year = 1995 } @Article{San00b, author = "Peter Sanders", title = "Fast Priority Queues for Cached Memory", journal = "ACM Journal of Experimental Algorithmics", volume = 5, year = 2000, } @Book{MSS03, editor = "U. Meyer and P. Sanders and J. Sibeyn", title = "Algorithms for Memory Hierarchies", publisher = "Springer", year = 2003, volume = 2625, series = "LNCS Tutorial" } @InProceedings{Arg95, author = "L. Arge", title = "{The Buffer Tree: A New Technique for Optimal I/O-Algorithms}", number = 955, series = "LNCS", pages = "334--345", booktitle = "4th Workshop on Algorithms and Data Structures", year = 1995, publisher = "Springer" } @Book{Knu98, author = "D. E. Knuth", title = "The Art of Computer Programming---Sorting and Searching", publisher = "Addison Wesley", year = 1998, edition = "2nd", volume = 3, annote = "leftist trees, looser trees" } @Article{Brengel00, author = {Klaus Brengel and Andreas Crauser and Paolo Ferragina and Ulrich Meyer}, title = {An Experimental Study of Priority Queues in External Memory}, journal = {ACM Journal of Experimental Algorithms}, year = {2000}, volume = {5}, number = {17}, } @InProceedings{FJKT97, author = "R. Fadel and K. V. Jakobsen and J. Katajainen and J. Teuhola", title = "External heaps combined with effective buffering", volume = "19-2", series = "Australian Computer Science Communications", pages = "72--78", booktitle = "4th Australasian Theory Symposium", year = 1997, publisher = "Springer" } @Article{BM72, author = {R. Bayer and E. McCreight}, title = {Organization and maintenance of large ordered indices}, journal = {Acta Informatica}, year = {1972}, pages = {173–189}, } @InProceedings{BDIW02, author = {M. Bander and Z. Duan and J. Iacono and J. Wu}, title = {A locality-preserving cache-oblivious dynamic dictionary}, booktitle = {13th Annual ACM-SIAM Symposium On Descrete Algorithms (SODA'02)}, year = {2002}, } @InProceedings{BDB99, author = {Michael A. Olson and Keith Bostic and Margo Seltzer }, title = "{Berkeley DB}", booktitle = "{USENIX Annual Technical Conference}", pages = {183–192}, year = {1999}, month = {June}, } @InProceedings{KalVar01, author = {M. Kallahalla and P. J. Varman}, title = {Optimal prefetching and caching for parallel {I/O} systems}, booktitle = "13th Symposium on Parallel Algorithms and Architectures", pages = "219--228", year = 2001, } @InProceedings{Raj98, author = "S. Rajasekaran", title = "A Framework for Simple Sorting Algorithms on Parallel Disk Systems", booktitle = "10th {ACM} Symposium on Parallel Algorithms and Architectures", pages = "88--98", year = 1998 } @InProceedings{ChaCor02, author = "G. Chaudhry and T. H. Cormen", title = "Getting More From Out-of-Core Columnsort", booktitle = "4th Workshop on Algorithm Engineering and Experiments (ALENEX)", pages = "143--154", year = 2002, number = 2409, series = "LNCS" } @InProceedings{ChaCorWis01, author = "G. Chaudhry and T. H. Cormen and L. F. Wisniewski", title = "Columnsort Lives! An Efficient Out-of-Core Sorting Program", booktitle = "13th {ACM} Symposium on Parallel Algorithms and Architectures", year = 2001, pages = "169--178", } @InProceedings{PaiVar92, author = "V. S. Pai and P. J. Varman", title = "Prefetching with Multiple Disks for External Mergesort: Simulation and Analysis", booktitle = "ICDE", pages = "273--282", year = 1992 } @Article{CaoFelKarLi96, author = "P. Cao and E. W. Felten and A. R. Karlin and K. Li", title = "Implementation and Performance of Integrated Application-Controlled File Caching, Prefetching and Disk Scheduling", journal = "ACM Transactions on Computer Systems", year = 1996, month = Nov, volume = "14", number = 4, pages = "311--343" } @InProceedings{AlbGarLeo98, author = "S. Albers and N. Garg and S. Leonardi", title = "Minimizing Stall Time in Single and Parallel Disk Systems", pages = "454--462", ISBN = "0-89791-962-9", booktitle = "Proceedings of the 30th Annual {ACM} Symposium on Theory of Computing ({STOC}'98)", month = may # "~23--26", publisher = "ACM Press", address = "New York", year = "1998", } @Article{KimKar00, author = "Tracy Kimbrel and Anna R. Karlin", title = "Near-optimal Parallel Prefetching and Caching", journal = "SIAM Journal on Computing", year = "2000", volume = "29", number = 4, pages = "1051--1082" } @InProceedings{NBCGL94, author = "C. Nyberg and T. Barclay and Z. Cvetanovic and J. Gray and D. Lomet", title = "{AlphaSort}: A {RISC} Machine Sort", booktitle = "SIGMOD", pages = "233--242", year = 1994, } @InProceedings{Aga96, author = "R. Agarwal", title = "A super scalar sort algorithm for {RISC} processors", booktitle = "{ACM SIGMOD} International Conference on Management of Data", pages = "240--246", year = 1996, annote = "msd radix sort mentions TLB and branches" } @Misc{NKG00, author = "C. Nyberg and C. Koester and J. Gray", title = "Nsort: A Parallel Sorting Program for {NUMA} and {SMP} Machines", year = 2000, note = "\url{http://www.ordinal.com/lit.html}" } @Misc{Wyl99, author = "J. Wyllie", title = "{SPsort}: How to Sort a Terabyte Quickly", year = 1999, howpublished = {\url{http://research.microsoft.com/barc/SortBenchmark/SPsort.pdf}} } @Article{AggVit88, author = "A. Aggarwal and J. S. Vitter", title = "The Input/Output Complexity of Sorting and Related Problems", journal = "Communications of the ACM", year = 1988, volume = 31, number = 9, pages = "1116--1127", } @MastersThesis{JensThesis, author = {Jens Mehnert}, title = "{External Memory Suffix Array Construction}", school = {University of Saarland, Germany}, year = {2004}, month = {November}, note = "\url{http://algo2.iti.uka.de/dementiev/esuffix/docu/data/diplom.pdf}", } @Book{SKS01, author = "A. Silberschatz and H. F. Korth and S. Sudarshan", title = "Database System Concepts", publisher = "McGraw-Hill", year = 2001, edition = "4th" } @InBook{BillingLarge, author = {Andrew Hume}, title = {Handbook of massive data sets}, chapter = {Billing in the large}, publisher = {Kluwer Academic Publishers}, year = {2002}, pages = {895--909} } @article{Farias2001, title = {Out-of-core rendering of large, unstructured grids}, volume = {21}, issn = {0272-1716}, doi = {10.1109/38.933523}, number = {4}, author = {Farias, R. and Silva, {C.T.}}, year = {2001}, pages = {42--50}, } @Misc{Moore2000, author = {R. W. Moore}, title = {Enabling Petabyte Computing}, howpublished = {\url{http://www.nap.edu/html/whitepapers/ch-48.html}}, year = {2000} } @TechReport{Neu45, author = "Neumann, J. von", title = "First Draft of a Report on the {EDVAC}", institution = "University of Pennsylvania", year = "1945", key = "computers-history", note = "{\url{http://www.histech.rwth-aachen.de/www/quellen/vnedvac.pdf}}", annote = "{\it ~\\ The report that got von Neumann's name associated with the serial, stored-program, general purpose, digital architecture upon which 99.99\% of all computers today are based.}", } @article{Donato2006, title = {Algorithms and Experiments for the Webgraph.}, volume = {10}, number = {2}, author = {Donato, Debora and Laura, Luigi and Leonardi, Stefano and Meyer, Ulrich and Millozzi, Stefano and Sibeyn, Jop F.}, year = {2006}, pages = {219–-236}, }, @article{Patterson2004, title = {Latency lags bandwith}, volume = {47}, number = {10}, author = {Patterson, David A.}, year = {2004}, pages = {71–-75}, } @InProceedings{FLPR99, author = "M. Frigo and C. E. Leiserson and H. Prokop and S. Ramachandran", title = "Cache-Oblivious Algorithms", booktitle = "40th Symposium on Foundations of Computer Science", year = 1999, pages = "285--298" } @inproceedings{ABDHBM02, address = {New York, {NY}, {USA}}, series = {{STOC} '02}, title = {Cache-oblivious priority queue and graph algorithm applications}, isbn = {1-58113-495-9}, doi = {10.1145/509907.509950}, booktitle = {Proceedings of the thiry-fourth annual {ACM} symposium on Theory of computing}, publisher = {{ACM}}, author = {Arge, Lars and Bender, Michael A. and Demaine, Erik D. and Holland-Minkley, Bryan and Munro, J. Ian}, year = {2002}, pages = {268–276}, } @incollection{BFMZ04, series = {Lecture Notes in Computer Science}, title = {Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths}, copyright = {2004 Springer-Verlag Berlin Heidelberg}, isbn = {978-3-540-22339-9, 978-3-540-27810-8}, number = {3111}, booktitle = {Algorithm Theory - {SWAT} 2004}, publisher = {Springer Berlin Heidelberg}, author = {Brodal, Gerth Stølting and Fagerberg, Rolf and Meyer, Ulrich and Zeh, Norbert}, month = jan, year = {2004}, pages = {480--492}, } @MastersThesis{ChristianiThesis, title = {Cache-oblivious Graph Algorithms}, year = 2005, author = {Christiani, Frederik Juul}, journal = {Master's thesis, Department of Mathematics and Computer Science (IMADA), University of Southern Denmark, Odense} } @inproceedings{Ajwani2007, title = {Improved external memory {BFS} implementation}, urldate = {2013-02-14}, booktitle = {Proceedings of the Workshop on Algorithm Engineering and Experiments}, author = {Ajwani, Deepak and Meyer, Ulrich and Osipov, Vitaly}, year = {2007}, pages = {3–12}, file = {alx07_001ajwanid.pdf:files/3066/alx07_001ajwanid.pdf:application/pdf} } @InProceedings{BFV04, author = "G. S. Brodal and R. Fagerberg and K. Vinther", title = "Engineering a Cache-Oblivious Sorting Algorithm", booktitle = "6th Workshop on Algorithm Engineering and Experiments", year = 2004 } @Article{Vit01, author = "J. S. Vitter", title = "External memory algorithms and data structures: {D}ealing with {MASSIVE} data", journal = "ACM Computing Surveys", volume = "33", number = "2", pages = "209--271", year = "2001", } @InProceedings{TPIEscientific96, author = {D. E. Vengroff and J. S. Vitter}, title = "{I/O-Efficient Scientific Computation using TPIE}", booktitle = {Goddard Conference on Mass Storage Systems and Technologies}, pages = {553--570}, year = {1996}, volume = {2}, note = {published in NASA Conference Publication 3340}, } @PhdThesis{ChiangPHD, author = {Y.-J. Chiang}, title = {Dynamic and I/O-Efficient Algorithms for Computational Geometry and Graph Algorithms}, school = {Brown University}, year = {1995} } @InProceedings{Bkdtree03, author = {O. Procopiuc and P. K. Agarwal and L. Arge and J. S. Vitter}, title = "{Bkd-tree: A Dynamic Scalable KD-Tree}", booktitle = {Proc. 8th Int'l Symposium on Spatial and Temporal Databases (SSTD '03)}, pages = {46-65} } @InProceedings{DynRTrees99, author = {L. Arge and K. H. Hinrichs and J. Vahrenhold and J. S. Vitter}, title = "{Efficient Bulk Operations on Dynamic R-trees}", booktitle = {1st Workshop on Algorithm Engineering and Experimentation (ALENEX '99)}, pages = {328-348}, year = {1999}, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag}, } @InProceedings{CRBtree03, author = {P. K. Agarwal and L. Arge and S. Govindarajan}, title = "{CRB-Tree: An Efficient Indexing Scheme for Range Aggregate Queries}", booktitle = {Proc. 9th Int'l Conference on Database Theory (ICDT '03)}, pages = {143-157}, year = {2003}, } @Article{CraFer02, author = "A. Crauser and P. Ferragina", title = "A Theoretical and Experimental Study on the Construction of Suffix Arrays in External Memory", journal = "Algorithmica", year = 2002, volume = 32, pages = "1-35", number = 1 } @techreport{stepanov94standard, author = "A. A. Stepanov and M. Lee", title = "{The Standard Template Library}", number = "X3J16/94-0095, WG21/N0482", year = "1994", institution = "Silicon Graphics Inc., Hewlett Packard Laboratories" } @book{karlsson2005beyond, title = {Beyond the C++ standard library: an introduction to Boost}, shorttitle = {Beyond the C++ standard library}, publisher = {Pearson Education}, author = {Karlsson, Björn}, year = {2005} } @article{fabri1998design, title = {On the design of {CGAL}, the computational geometry algorithms library}, author = {Fabri, Andreas and Giezeman, Geert-Jan and Kettner, Lutz and Schirra, Stefan and Schönherr, Sven}, year = {1998}, } @InProceedings{Vengroff94, author = {D. E. Vengroff}, title = "{A Transparent Parallel I/O Environment}", booktitle = {Third DAGS Symposium on Parallel Computation}, pages = {117-134}, year = {1994}, address = {Hanover, NH}, month = {July}, }