Cache-oblivious selection in sorted X+Y matrices
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 kill 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. (C) 2008 Elsevier B.V. All rights reserved.
algorithms cache-oblivious algorithms matrix selection