Cache-oblivious selection in sorted X+Y matrices

M. Berg, de, S. Thite

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)87-92
TijdschriftInformation Processing Letters
Volume109
Nummer van het tijdschrift2
DOI's
StatusGepubliceerd - 2008

Vingerafdruk

Duik in de onderzoeksthema's van 'Cache-oblivious selection in sorted X+Y matrices'. Samen vormen ze een unieke vingerafdruk.

Citeer dit