arXiv Open Access 2008

Cache-Oblivious Selection in Sorted X+Y Matrices

Mark de Berg Shripad Thite

Lihat Sumber

Abstrak

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

Topik & Kata Kunci

cs.DS

Penulis (2)

Mark de Berg

Shripad Thite

Format Sitasi

APA MLA BibTeX

Berg, M.d., Thite, S. (2008). Cache-Oblivious Selection in Sorted X+Y Matrices. https://arxiv.org/abs/0804.0936

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2008
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓