Cache-oblivious selection in sorted X+Y matrices

M. Berg, de, S. Thite

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Let X[0..n-1] and Y[0..m-1] be two sorted arrays, and define the m×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.
Original languageEnglish
Pages (from-to)87-92
JournalInformation Processing Letters
Volume109
Issue number2
DOIs
Publication statusPublished - 2008

Fingerprint

Dive into the research topics of 'Cache-oblivious selection in sorted X+Y matrices'. Together they form a unique fingerprint.

Cite this