STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Bibliographic References

P. K. Agarwal, L. Arge, and S. Govindarajan. CRB-Tree: An Efficient Indexing Scheme for Range Aggregate Queries. In Proc. 9th Int'l Conference on Database Theory (ICDT '03), pages 143–157, 2003.


R. Agarwal. A super scalar sort algorithm for RISC processors. In ACM SIGMOD International Conference on Management of Data, pages 240–246, 1996.


A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems. Communications of the ACM, 31(9):1116–1127, 1988.


Deepak Ajwani, Ulrich Meyer, and Vitaly Osipov. Improved external memory BFS implementation. In Proceedings of the Workshop on Algorithm Engineering and Experiments, page 3–12, 2007.


S. Albers, N. Garg, and S. Leonardi. Minimizing stall time in single and parallel disk systems. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC'98), pages 454–462, New York, May 23–26 1998. ACM Press.


L. Arge, K. H. Hinrichs, J. Vahrenhold, and J. S. Vitter. Efficient Bulk Operations on Dynamic R-trees. In 1st Workshop on Algorithm Engineering and Experimentation (ALENEX '99), Lecture Notes in Computer Science, pages 328–348. Springer-Verlag, 1999.


L. Arge, O. Procopiuc, and J. S. Vitter. Implementing I/O-efficient Data Structures Using TPIE. In 10th European Symposium on Algorithms (ESA), volume 2461 of LNCS, pages 88–100. Springer, 2002.


Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, and J. Ian Munro. Cache-oblivious priority queue and graph algorithm applications. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, STOC '02, page 268–276, New York, NY, USA, 2002. ACM.


Lars Arge, Rakesh Barve, David Hutchinson, Octavian Procopiuc, Laura Toma, Darren Erik Vengroff, and Rajiv Wickeremesinghe. TPIE: User manual and reference, November 2003.


L. Arge. The Buffer Tree: A New Technique for Optimal I/O-Algorithms. In 4th Workshop on Algorithms and Data Structures, number 955 in LNCS, pages 334–345. Springer, 1995.


M. Bander, Z. Duan, J. Iacono, and J. Wu. A locality-preserving cache-oblivious dynamic dictionary. In 13th Annual ACM-SIAM Symposium On Descrete Algorithms (SODA'02), 2002.


R. D. Barve, E. F. Grove, and J. S. Vitter. Simple randomized mergesort on parallel disks. Parallel Computing, 23(4):601–631, 1997.


R. Bayer and E. McCreight. Organization and maintenance of large ordered indices. Acta Informatica, page 173–189, 1972.


L.F. Bic and A.C. Shaw. Operating Systems Principles. Pearson Education, 2003.


Klaus Brengel, Andreas Crauser, Paolo Ferragina, and Ulrich Meyer. An experimental study of priority queues in external memory. ACM Journal of Experimental Algorithms, 5(17), 2000.


Gerth Stølting Brodal, Rolf Fagerberg, Ulrich Meyer, and Norbert Zeh. Cache-oblivious data structures and algorithms for undirected breadth-first search and shortest paths. In Algorithm Theory - SWAT 2004, number 3111 in Lecture Notes in Computer Science, pages 480–492. Springer Berlin Heidelberg, January 2004.


G. S. Brodal, R. Fagerberg, and K. Vinther. Engineering a cache-oblivious sorting algorithm. In 6th Workshop on Algorithm Engineering and Experiments, 2004.


P. Cao, E. W. Felten, A. R. Karlin, and K. Li. Implementation and performance of integrated application-controlled file caching, prefetching and disk scheduling. ACM Transactions on Computer Systems, 14(4):311–343, November 1996.


G. Chaudhry and T. H. Cormen. Getting more from out-of-core columnsort. In 4th Workshop on Algorithm Engineering and Experiments (ALENEX), number 2409 in LNCS, pages 143–154, 2002.


G. Chaudhry, T. H. Cormen, and L. F. Wisniewski. Columnsort lives! an efficient out-of-core sorting program. In 13th ACM Symposium on Parallel Algorithms and Architectures, pages 169–178, 2001.


Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamasia, D. E. Vengroff, and J. S. Vitter. External memory graph algorithms. In 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 139–149, 1995.


Y.-J. Chiang. Dynamic and I/O-Efficient Algorithms for Computational Geometry and Graph Algorithms. PhD thesis, Brown University, 1995.


Frederik Juul Christiani. Cache-oblivious graph algorithms. Master's thesis, 2005.


A. Crauser and P. Ferragina. A theoretical and experimental study on the construction of suffix arrays in external memory. Algorithmica, 32(1):1–35, 2002.


A. Crauser and K. Mehlhorn. LEDA-SM, extending LEDA to secondary memory. In 3rd International Workshop on Algorithmic Engineering (WAE), volume 1668 of LNCS, pages 228–242, 1999.


R. Dementiev and P. Sanders. Asynchronous parallel disk sorting. In 15th ACM Symposium on Parallelism in Algorithms and Architectures, pages 138–148, San Diego, 2003.


R. Dementiev, J. Mehnert, J. Kärkkäinen, and P. Sanders. Better External Memory Suffix Array Construction. In Workshop on Algorithm Engineering & Experiments, Vancouver,



Debora Donato, Luigi Laura, Stefano Leonardi, Ulrich Meyer, Stefano Millozzi, and Jop F. Sibeyn. Algorithms and experiments for the webgraph. 10(2):219––236, 2006.


Andreas Fabri, Geert-Jan Giezeman, Lutz Kettner, Stefan Schirra, and Sven Schönherr. On the design of CGAL, the computational geometry algorithms library. 1998.


R. Fadel, K. V. Jakobsen, J. Katajainen, and J. Teuhola. External heaps combined with effective buffering. In 4th Australasian Theory Symposium, volume 19-2 of Australian Computer Science Communications, pages 72–78. Springer, 1997.


R. Farias and C.T. Silva. Out-of-core rendering of large, unstructured grids. 21(4):42–50, 2001.


M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In 40th Symposium on Foundations of Computer Science, pages 285–298, 1999.


Andrew Hume. Handbook of massive data sets, chapter Billing in the large, pages 895–909. Kluwer Academic Publishers, 2002.


D. A. Hutchinson, P. Sanders, and J. S. Vitter. Duality between prefetching and queued writing with parallel disks. In 9th European Symposium on Algorithms (ESA), number 2161 in LNCS, pages 62–73. Springer, 2001.


M. Kallahalla and P. J. Varman. Optimal prefetching and caching for parallel I/O systems. In 13th Symposium on Parallel Algorithms and Architectures, pages 219–228, 2001.


Björn Karlsson. Beyond the C++ standard library: an introduction to Boost. Pearson Education, 2005.


Tracy Kimbrel and Anna R. Karlin. Near-optimal parallel prefetching and caching. SIAM Journal on Computing, 29(4):1051–1082, 2000.


D. E. Knuth. The Art of Computer Programming—Sorting and Searching, volume 3. Addison Wesley, 2nd edition, 1998.


Jens Mehnert. External Memory Suffix Array Construction. Master's thesis, University of Saarland, Germany, November 2004.


U. Meyer, P. Sanders, and J. Sibeyn, editors. Algorithms for Memory Hierarchies, volume 2625 of LNCS Tutorial. Springer, 2003.


R. W. Moore. Enabling petabyte computing., 2000.


J. von Neumann. First draft of a report on the EDVAC. Technical report, University of Pennsylvania, 1945.


C. Nyberg, T. Barclay, Z. Cvetanovic, J. Gray, and D. Lomet. AlphaSort: A RISC machine sort. In SIGMOD, pages 233–242, 1994.


C. Nyberg, C. Koester, and J. Gray. Nsort: A parallel sorting program for NUMA and SMP machines, 2000.


Michael A. Olson, Keith Bostic, and Margo Seltzer. Berkeley DB. In USENIX Annual Technical Conference, page 183–192, June 1999.


V. S. Pai and P. J. Varman. Prefetching with multiple disks for external mergesort: Simulation and analysis. In ICDE, pages 273–282, 1992.


David A. Patterson. Latency lags bandwith. 47(10):71––75, 2004.


O. Procopiuc, P. K. Agarwal, L. Arge, and J. S. Vitter. Bkd-tree: A Dynamic Scalable KD-Tree. In Proc. 8th Int'l Symposium on Spatial and Temporal Databases (SSTD '03), pages 46–65.


S. Rajasekaran. A framework for simple sorting algorithms on parallel disk systems. In 10th ACM Symposium on Parallel Algorithms and Architectures, pages 88–98, 1998.


Peter Sanders. Fast priority queues for cached memory. ACM Journal of Experimental Algorithmics, 5, 2000.


A. Silberschatz, H. F. Korth, and S. Sudarshan. Database System Concepts. McGraw-Hill, 4th edition, 2001.


A. A. Stepanov and M. Lee. The Standard Template Library. Technical Report X3J16/94-0095, WG21/N0482, Silicon Graphics Inc., Hewlett Packard Laboratories, 1994.


D. E. Vengroff and J. S. Vitter. I/O-Efficient Scientific Computation using TPIE. In Goddard Conference on Mass Storage Systems and Technologies, volume 2, pages 553–570, 1996. published in NASA Conference Publication 3340.


J. S. Vitter and D. A. Hutchinson. Distribution sort with randomized cycling. In 12th ACM-SIAM Symposium on Discrete Algorithms, pages 77–86, 2001.


J. S. Vitter and E. A. M. Shriver. Algorithms for parallel memory, I/II. Algorithmica, 12(2/3):110–169, 1994.


J. S. Vitter. External memory algorithms and data structures: Dealing with MASSIVE data. ACM Computing Surveys, 33(2):209–271, 2001.


J. Wyllie. SPsort: How to sort a terabyte quickly., 1999.


Norbert Ralf Zeh. I/O Efficient Algorithms for Shortest Path Related Problems. PhD thesis, Carleton University, Ottawa, April 2002.