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. https://resolver.caltech.edu/CaltechAUTHORS:BERipl08

PDF - Published Version
Restricted to Repository administrators only
See Usage Policy.
191kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:BERipl08

Abstract

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:

URL	URL Type	Description
http://dx.doi.org/10.1016/j.ipl.2008.09.001	DOI	UNSPECIFIED

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

Funders:

Funding Agency	Grant Number
Netherlands' Organisation for Scientific Research (NWO)	639.023.301

Subject Keywords:

algorithms; cache-oblivious algorithms; matrix selection

Issue or Number:

DOI:

10.1016/j.ipl.2008.09.001

Record Number:

CaltechAUTHORS:BERipl08

Persistent URL:

https://resolver.caltech.edu/CaltechAUTHORS:BERipl08

Usage Policy:

No commercial reproduction, distribution, display or performance rights in this work are provided.

ID Code:

13323

Collection:

CaltechAUTHORS

Deposited By:

Tony Diaz

Deposited On:

04 Jun 2009 22:16

Last Modified:

08 Nov 2021 22:36

Repository Staff Only: item control page