Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 31, 2008 | public
Journal Article

Cache-oblivious selection in sorted X+Y matrices

Abstract

Let X[0 . . n - 1] and Y[0 . . m - 1] be two sorted arrays, and define the m x n matrix A by A[j][i] = X[i] + Y[j]. Frederickson and Johnson [G.N. Frederickson, D.B. Johnson. Generalized selection and ranking: Sorted matrices, SIAM J. Computing 13 (1984) 14-30] gave an efficient algorithm for selecting the kth smallest element from A. We show how to make this algorithm IO-efficient. Our cache-oblivious algorithm performs O ((m + n)/ B) IOs, where B is the block size of memory transfers.

Additional Information

© 2008 Elsevier B.V. Received 7 April 2008. Available online 4 September 2008. Communicated by F. Dehne. This research was supported by the Netherlands' Organisation for Scientific Research (NWO) under project no. 639.023.301

Additional details

Created:
August 22, 2023
Modified:
October 17, 2023