Abstract
We show a general relationship between the number of comparisons and the number of I/O-operations needed to solve a given problem. This relationship enables one to show lower bounds on the number of I/O-operations needed to solve a problem whenever a lower bound on the number of comparisons is known. We use the result to show lower bounds on the I/O-complexity on a number of problems where known techniques only give trivial bounds. Among these are the problems of removing duplicates from a multiset, a problem of great importance in e.g. relational data-base systems, and the problem of determining the mode — the most frequently occurring element — of a multiset. We develop algorithms for these problems in order to show that the lower bounds are tight.
This work was partially supported by the ESPRIT II Basic Research Actions Program of the EC under contract No. 7141 (project ALCOM II).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aggarwal, A., Vitter, J.S.: The I/O Complexity of Sorting and Related Problems. Proceedings of 14th ICALP (1987), Lecture Notes in Computer Science 267, Springer Verlag, 467–478, and: The Input/Output Complexity of Sorting and Related Problems. Communications of the ACM, Vol 31 (9) (1988) 1116–1127.
Ben-Or, M.: Lower bounds for algebraic computation trees. Proceedings of 15th STOC (1983), 80–86.
Blum, M., Floyd, R.W, Pratt, V.R, Rivest, R.L, Tarjan, R.E.: Time bounds for selection. Journal of Computer and System Sciences, 7(4) (1972), 448–461.
Knudsen, M., Larsen, K.,: I/O-complexity of comparison and permutation problems. M.Sc. Thesis, Aarhus University, November 1992.
Knuth, D.E.: The Art of Computer Programming, Vol 3: Sorting and Searching, Addison-Wesley (1973) (p. 205–206).
Misra, J., Gries, D.: Finding Repeated Elements. Science of Computer Programming 2 (1982), 143–152, North-Holland Publishing.
Munro, J.I., Raman, V.: Sorting Multisets and Vectors In-Place. Proceedings of 2nd WADS, Lecture Notes in Computer Science 519, Springer Verlag (1991), 473–479.
Munro, I., Spira, P.M.: Sorting and Searching in Multisets. SIAM Journal of Computing, 5 (1) (1976) 1–8.
Nodine, M.H., Vitter, J.S.: Optimal Deterministic Sorting on Parallel Disks. Brown University, CS-92-08, August 1992.
Vitter, J.S: Efficient Memory Access in Large-Scale Computation (invited paper). Proceedings of 8th STACS (1991), 26–41.
Vitter, J.S., Shriver, E.A.M.: Optimal Disk I/O with Parallel Block Transfer. Proceedings of 22nd STOC (1990), 159–169.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Arge, L., Knudsen, M., Larsen, K. (1993). A general lower bound on the I/O-complexity of comparison-based algorithms. In: Dehne, F., Sack, JR., Santoro, N., Whitesides, S. (eds) Algorithms and Data Structures. WADS 1993. Lecture Notes in Computer Science, vol 709. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57155-8_238
Download citation
DOI: https://doi.org/10.1007/3-540-57155-8_238
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57155-1
Online ISBN: 978-3-540-47918-5
eBook Packages: Springer Book Archive