Cache-oblivious selection in sorted X+Y matrices

M. Berg, de; S. Thite

doi:10.1016/j.ipl.2008.09.001

Cache-oblivious selection in sorted X+Y matrices

M. Berg, de, S. Thite

Algorithms

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

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 language	English
Pages (from-to)	87-92
Journal	Information Processing Letters
Volume	109
Issue number	2
DOIs	https://doi.org/10.1016/j.ipl.2008.09.001
Publication status	Published - 2008

Access to Document

10.1016/j.ipl.2008.09.001

Cite this

@article{37c4b11594a8445eaf875e7d82181c92,

title = "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×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.",

author = "{Berg, de}, M. and S. Thite",

year = "2008",

doi = "10.1016/j.ipl.2008.09.001",

language = "English",

volume = "109",

pages = "87--92",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Cache-oblivious selection in sorted X+Y matrices

AU - Berg, de, M.

AU - Thite, S.

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

U2 - 10.1016/j.ipl.2008.09.001

DO - 10.1016/j.ipl.2008.09.001

M3 - Article

SN - 0020-0190

VL - 109

SP - 87

EP - 92

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

Cache-oblivious selection in sorted X+Y matrices

Abstract

Access to Document

Fingerprint

Cite this