A Caltech Library Service

Cache-oblivious selection in sorted X+Y matrices

de Berg, Mark and Thite, Shripad (2008) Cache-oblivious selection in sorted X+Y matrices. Information Processing Letters, 109 (2). pp. 87-92. ISSN 0020-0190. doi:10.1016/j.ipl.2008.09.001.

[img] PDF - Published Version
Restricted to Repository administrators only
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
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
Funding AgencyGrant Number
Netherlands' Organisation for Scientific Research (NWO)639.023.301
Subject Keywords:algorithms; cache-oblivious algorithms; matrix selection
Issue or Number:2
Record Number:CaltechAUTHORS:BERipl08
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:13323
Deposited By: Tony Diaz
Deposited On:04 Jun 2009 22:16
Last Modified:08 Nov 2021 22:36

Repository Staff Only: item control page