Bulk processing (sorting; partitioning; multiset discrimination; associative data structures)

Academic Journals

1. A. Elmasry, A. Hammad. Inversion-sensitive sorting algorithms in practice. Journal of Experimental Algorithmics (JEA), 13:1-11, 2009.
2. Fritz Henglein. What is a Sorting Function?. J. Logic and Algebraic Programming (JLAP), Invited submisstion to special issue on 19th Nordic Workshop on Programming Theory (NWPT), 78(5):381-401, 2009.
3. Amr Elmasry, Abdelrahman Hammad. Inversion-sensitive sorting algorithms in practice. ACM Journal of Experimental Algorithmics, 13, 2008.
4. D. Singh, A. M. Ibrahim, T. Yohanna, J. N. Singh. An Overview of the Applications of Multisets. Novi Sad J. Math, 37(2):73-92, 2007.
5. Goetz Graefe. Implementing sorting in database systems. ACM Comput. Surv, 38(3), 2006. download
6. Amer Al-Badarneh, Fouad El-Aker. Efficient Adaptive In-Place Radix Sorting. Informatica, 15(3):295-302, 2004.
7. Yijie Han. Deterministic sorting in O(nlog logn) time and linear space. J. Algorithms, 50(1):96-105, 2004.
8. Yijie Han. Improved fast integer sorting in linear space. Inf. Comput, 170(1):81-94, 2001.
9. Ralf Hinze. Generalizing Generalized Tries. Journal of Functional Programming, 10(4):327-351, 2000.
10. Laurent Mauborgne. An Incremental Unique Representation for Regular Trees. Nordic Journal of Computing, 7(4):290-311, 2000.
11. Arne Andersson, Stefan Nilsson. Implementing radixsort. J. Exp. Algorithmics, 3, 1998.
12. Arne Andersson, Torben Hagerup, Stefan Nilsson, Rajeev Raman. Sorting in linear time?. Journal of Computer and System Sciences (JCSS), 57(1):74-93, August 1998.
13. Preston Briggs, Keith D. Cooper, L. Taylor Simpson. Value Numbering. Software - Practice and Experience, 27(6):701-724, 1997.
14. W. Panny, H. Prodinger. Bottom-up mergesort‚ a detailed analysis. Algorithmica, 14(4):340-354, 1995.
15. Jiazhen Cai, Robert Paige. Using Multiset Discrimination to Solve Language Processing Problems Without Hashing. Theoretical Computer Science (TCS), 145(1):189-228, July 1995.
16. Jiazhen Cai, Robert Paige. Multiset Discrimination - a Method for Implementing Programming Language Systems Without Hashing. Theoretical Computer Science (TCS), To appear, 1994.
17. Amir M. Ben-Amram. Unit-cost pointers versus logarithmic-cost addresses. Theoretical Computer Science, (132):377-385, 1994.
18. J.L. Bentley, M.D. McIlroy. Engineering a Sort Function. Software - Practice and Experience, 23(11):1249-1265, 1993.
19. Randal E. Bryant. Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams. ACM Computing Surveys, 24(3):293-318, September 1992.
20. Amir M. Ben-Amram, Zvi Galil. On Pointers versus Addresses. Journal of the ACM, 39(3):617-648, July 1992.
21. Andrew Chi-Chih Yao. Lower Bounds for Algebraic Computation Trees with Integer Inputs. SIAM J. Comput, 20(4):655-668, 1991.
22. Paris C. Kanellakis, Peter Z. Revesz. On the Relationship of Congruence Closure and Unification. Journal of Symbolic Computation, Unification: Part 1, 7(3):427-444, 1989.
23. Per-Ake Larson. Dynamic hash tables. Commun. ACM, 31(4):446-457, 1988. download
24. R. Paige, R.E. Tarjan. Three partition refinement algorithms. SIAM Journal on Computing, 16(6):973-989, 1987.
25. Robert Paige, Robert E. Tarjan. Three Partition Refinement Algorithms. SIAM Journal of Computing, 16(6):973-989, December 1987.
26. Randal Bryant. Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers, C-35(8):677-691, August 1986.
27. R. Paige, R. Tarjan, R. Bonic. A Linear Time Solution to the Single Function Coarsest Partition Problem. Theoretical Computer Science, 40:67-84, 1985.
28. M. Ajtai, J. Komlós, E. Szemerédi. Sorting in $c \log n$ parallel steps. Combinatorica, 3:1-19, 1983.
29. J. P. Jouannaud, P. Lescanne. On Multiset Orderings. Information Processing Letters, 25(2):57-63, 1982.
30. A. Cardon, M. Crochemore. Partitioning a Graph in $O(|A| \log_2 |V|)$. Theoretical Computer Science (TCS), 19:85-98, 1982.
31. Greg Nelson, Derek C. Oppen. Fast Decision Procedures Based on Congruence Closure. J. ACM, 27(2):356-364, 1980. download
32. P. Downey, R. Sethi, R. Tarjan. Variations on the Common Subexpression Problem. J. ACM, 27(4):758-771, October 1980.
33. Nachum Dershowitz, Zohar Manna. Proving termination with multiset orderings. Commun. ACM, 22(8):465-476, 1979. download
34. Ronald Fagin, Jurg Nievergelt, Nicholas Pippenger, H. Raymond Strong. Extendible hashing - fast access method for dynamic files. ACM Trans. Database Syst, 4(3):315-344, 1979.
35. Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9):509-517, 1975. download
36. M. Harrison. Implementation of Substring Test by Hashing. Communications of the ACM, 14(12):777-779, December 1971.
37. J. W. J. Williams. Algorithm 232 - Heapsort. Communications of the ACM, 7(6):347-348, 1964.
38. C. A. R. Hoare. Algorithm 63: partition. Commun. ACM, 4(7), 1961. download
39. D. L. Shell. A High-Speed Sorting Procedure. Communications of the ACM, 2(7), 1959.
40. Amir M. Ben-Amram, Zvi Galil. When can we sort in $o(n \log n)$ time?. Jour. of Comp. and System Sci, Preliminary version presented at FOCS' 93, 0.
41. F. El-Aker, A. Al-Badarneh. MSL: An Efficient Adaptive In-Place Radix Sort Algorithm. 0.
42. A. Maus. Making a fast unstable sorting algorithm stable. 0.

International Conferences

1. Duane Merrill, Andrew Grimshaw. Revisiting Sorting for GPGPU Stream Architectures. In Proc. Parallel Architectures and Compilation Techniques (PACT), September 2010.
2. Fritz Henglein. Optimizing relational algebra operations using discrimination-based joins and lazy products. In Proc. ACM SIGPLAN 2010 Workshop on Partial Evaluation and Program Manipulation, Also DIKU TOPPS D-report no. 611, Pages 73-82, New York, NY, USA, 2010. download
3. Jeffrey Sarnat, Carsten Schürmann. Lexicographic Path Induction. In TLCA, Pages 279-293, 2009.
4. Fritz Henglein. Generic discrimination: Sorting and partitioning unshared data in linear time. In ICFP '08: Proceeding of the 13th ACM SIGPLAN international conference on Functional programming, James Hook, Peter Thiemann (eds.), Nominated by ACM SIGPLAN for CACM Research Highlights (see http://sigplan.org/CACMPapers.htm), Pages 91-102, New York, NY, USA, September 2008. download
5. Gianni Franceschini, S. Muthukrishnan, Mihai P\vatra\cscu. Radix Sorting with No Extra Space. In Proc. 15th European Symposium on Algorithms (ESA), Eilat, Israel, Lecture Notes in Computer Science (LNCS), Volume 4698, Pages 194-205, October 2007.
6. Fritz Henglein. What is a Sort Function?. In Proc. 19th Nordic Workshop on Programming Theory (NWPT), Oslo, Norway, 2007.
7. Ranjan Sinha, Justin Zobel. Efficient Trie-Based Sorting of Large Sets of Strings. In ACSC, Pages 11-18, 2003.
8. Arne Maus. ARL, a faster in-place, cache friendly sorting algorithm. In Norwegian Informatics Conference (NIK), Kongsberg, Norway, ISBN 82-91116-45-8, 2002.
9. Yijie Han, Mikkel Thorup. Integer sorting in $O(n \sqrt\log \log n$ expected time and linear space. In Proceedings of the 43d Annual IEEE Sympositum on Foundations of Computer Science (FOCS), Pages 135-144, 2002.
10. Yijie Han. Deterministic sorting in O(n log log n) time and linear space. In STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, Pages 602-608, New York, NY, USA, 2002.
11. Mikkel Thorup. Even strongly universal hashing is pretty fast. In SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, Pages 496-497, Philadelphia, PA, USA, 2000.
12. Mikkel Thorup. Faster deterministic sorting and priority queues in linear space. In SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, Pages 550-555, Philadelphia, PA, USA, 1998.
13. Jon L. Bentley, Robert Sedgewick. Fast algorithms for sorting and searching strings. In SODA '97: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, Pages 360-369, Philadelphia, PA, USA, 1997.
14. Mikkel Thorup. Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operations. In SODA '97: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, Pages 352-359, Philadelphia, PA, USA, 1997.
15. Lars Arge, Paolo Ferragina, Roberto Grossi, Jeffrey Scott Vitter. On sorting strings in external memory (extended abstract). In STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, Pages 540-548, New York, NY, USA, 1997. download
16. Robert Paige, Zhe Yang. High Level Reading and Data Structure Compilation. In Proc.\ 24th ACM SIGPLAN-SIGACT Symp.\ on Principles of Programming Languages (POPL), Paris, France, Pages 456-469, http://www.acm.org, January 1997.
17. Jesper G. Henriksen, Jakob L. Jensen, Michael E. J\orgensen, Nils Klarlund, Robert Paige, Theis Rauhe, Anders Sandholm. Mona: Monadic Second-Order Logic in Practice. In Tools and Algorithms for the Construction and Analysis of Systems, Ed Brinksma, Rance Cleaveland, Kim Guldstrand Larsen, Tiziana Margaria, Bernhard Steffen (eds.), Volume 1019, Pages 89-110, 1995.
18. Arne Andersson, Torben Hagerup, Stefan Nilsson, Rajeev Raman. Sorting in linear time?. In STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, Pages 427-436, New York, NY, USA, 1995. download
19. A. Andersson, S. Nilsson. A new efficient radix sort. In Proc. 35th Anniual IEEE Symposium on Foundations of Computer Science (FOCS), Pages 714-721, 1994.
20. Robert Paige. Efficient Translation of External Input in a Dynamically Typed Language. In Proc. 13th World Computer Congress, Vol. 1, B. Pehrson, I. Simon (eds.), Also have submission, February 1994.
21. Bard Bloom, Robert Paige. Tranformational Design and Implementation of a New Efficient Solution to the Ready Simulation Problem. In Proc. CONCUR '93, 1993.
22. Nachum Dershowitz. Trees, Ordinals and Termination. In Proc. Theory and Practice of Software Development (TAPSOFT), Orsay, France, M.-C. Gaudel, J.-P. Jouannaud (eds.), Lecture Notes in Computer Science, Volume 668, April 1993.
23. B. Bloom, R. Paige. Computing Ready Simulations Efficiently. In Proc. 3rd Int'l Conf. on Concurrency Theory (CONCUR), Stony Brook, New York, August 1992.
24. A. Cichon, P. Lescanne. Polynomial Interpretations and the Complexity of Algorithms. In Proc. 11th Int'l Conf. on Automated Deduction (CADE), Saratoga Springs, New York, D. Kapur (ed.), Lecture Notes in Computer Science, Vol. 607, Pages 139-147, June 1992.
25. Nader H. Bshouty. Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains. In ICCI, Pages 55-65, 1991.
26. J. Cai, R. Paige. Look Ma, No Hashing, and No Arrays Neither. In Proc. 18th Annual ACM Symp. on Principles of Programming Languages (POPL), Orlando, Florida, January (ed.), Pages 143-154, 1991.
27. R. Paige, R. Tarjan. A Linear Time Algorithm to Solve the Single Function Coarsest Partition Problem. In Proc. Int'l Conf. on Algorithms, Languages, and Programming, 1984.
28. M. Ajtai, J. Komlós, E. Szemerédi. An $0(n log n)$ sorting network. In STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing, Pages 1-9, New York, NY, USA, 1983. download
29. A. Borodin, S. Cook. A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation. In Proc. 1980 STOC, Pages 294-301, 1980.
30. K. E. Batcher. Sorting Networks and their Applications. In Proc. AFIPS Spring Joint Computer Conference, Volume 32, Pages 307-314, 1968.

Technical Reports

1. Fritz Henglein. Generic Top-down Discrimination for Sorting and Partitioning in Linear Time. Research Report Department of Computer Science, University of Copenhagen (DIKU), December 2010.
2. Fritz Henglein, Ken Friis Larsen. Generic Multiset Programming for Language-Integrated Querying. TOPPS D-Report Department of Computer Science, University of Copenhagen (DIKU), No 609, October 2009.
3. Fritz Henglein. Generic Top-down Discrimination. TOPPS Report Department of Computer Science, University of Copenhagen (DIKU), No 608, October 2009.
4. Fritz Henglein. Optimizing relational algebra operations using generic partitioning discriminators and lazy products. TOPPS D-Report Department of Computer Science, University of Copenhagen (DIKU), No 610, May 2009.
5. Fritz Henglein. Generic Discrimination: Sorting and Partitioning Unshared Data in Linear Time. TOPPS Report D-582 Department of Computer Science, University of Copenhagen (DIKU), December 2007.
6. Fritz Henglein. Intrinsically defined sorting functions. TOPPS Report D-565 Department of Computer Science, University of Copenhagen (DIKU), September 2007.
7. Fritz Henglein. Generic discrimination: Partitioning and Sorting Complex Data in Linear Time. TOPPS Report D-559 Department of Computer Science, University of Copenhagen (DIKU), December 2006.
8. Fritz Henglein. Multiset discrimination. Manuscript (incomplete) Department of Computer Science, University of Copenhagen (DIKU), September 2003. download
9. Amir M. Ben-Amram. ``When can We sort in $o(n \log n)$ Time?'' Revisited. Research Report DIKU, University of Copenhagen, No 95, 1995.
10. Amir M. Ben-Amram. Pointer Machines and Pointer Algorithms: An Annotated Bibliography. Research Report DIKU, University of Copenhagen, No 95, 1995.
11. Robert Paige, Jiazhen Cai. Using Multiset Discrimination To Solve Language Processing Problems Without Hashing. Research Report DIKU, University of Copenhagen, No 94, 1994.

Miscellaneous

1. Wikipedia. Sorting algorithm. 2007. download
2. R. Paige. Preconditioning Input in High Level Languages. manuscript, 1990.
3. A. Apostolico, C. Iliopoulos, Paige R.. An $O(n log n)$ Cost Parallel Algorithm for the Single Function Coarsest Partition Problem. Draft, 1987.
4. A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, A. Wigderson. A Time-Space Tradeoff for Element Distinctness. Manuscript, 1983.
5. R. Paige, R. Tarjan. Three Efficient Algorithms Based on Partition Refinement - Extended Abstract. 0.
6. . Burstsort implementation in C++. 0. download

Dissertations

1. E. Cichon. Sub-Recursive Hierarchies and Ordinals. PhD Thesis University of Leeds, November 1985.

Master's thesis

1. Thomas Ambus. Multiset Discrimination for Internal and External Data Management. Master's theses DIKU, University of Copenhagen, July 2004.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.