Cache-Oblivious Selection in Sorted X+Y Matrices

Simple item page
dc.creatorde Berg, Mark
dc.creatorThite, Shripad
dc.date2008-04-06
dc.date.accessioned2026-07-07T09:30:45Z
dc.date.available2026-07-07T09:30:45Z
dc.descriptionLet X[0..n-1] and Y[0..m-1] be two sorted arrays, and define the mxn matrix A by A[j][i]=X[i]+Y[j]. Frederickson and Johnson gave an efficient algorithm for selecting the k-th 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.
dc.identifierhttps://arxiv.org/abs/0804.0936
dc.identifierhttp://arxiv.org/abs/0804.0936
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/158221
dc.subjectData Structures and Algorithms
dc.titleCache-Oblivious Selection in Sorted X+Y Matrices
dc.typetext

Files

Collections

arXiv