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 http://resolver.caltech.edu/CaltechAUTHORS:BERipl08
![[img]](http://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Published Version
Restricted to Repository administrators only See Usage Policy. 187Kb |
Use this Persistent URL to link to this item: http://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 | ||||
|---|---|---|---|---|---|
| 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: |
| ||||
| Subject Keywords: | algorithms; cache-oblivious algorithms; matrix selection | ||||
| Record Number: | CaltechAUTHORS:BERipl08 | ||||
| Persistent URL: | http://resolver.caltech.edu/CaltechAUTHORS:BERipl08 | ||||
| Related URLs: | |||||
| 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: | 26 Dec 2012 10:48 |
Repository Staff Only: item control page
