Cache-oblivious selection in sorted X+Y matrices

被引：1

作者：

de Berg, Mark ^{[1
]}

Thite, Shripad ^{[2
]}

机构：

[1] Tech Univ Eindhoven, Dept Comp Sci, Eindhoven, Netherlands

[2] CALTECH, Ctr Math Informat IST, Pasadena, CA 91125 USA

来源：

INFORMATION PROCESSING LETTERS | 2008年 / 109卷 / 02期

关键词：

Algorithms; Cache-oblivious algorithms; Matrix selection;

D O I：

10.1016/j.ipl.2008.09.001

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 kill 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. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：87 / 92

页数：6

共 13 条

[1] Efficient algorithms for geometric optimization [J].

Agarwal, PK ;

Sharir, M .

ACM COMPUTING SURVEYS, 1998, 30 (04) :412-458

[2] THE INPUT OUTPUT COMPLEXITY OF SORTING AND RELATED PROBLEMS [J].

AGGARWAL, A ;

VITTER, JS .

COMMUNICATIONS OF THE ACM, 1988, 31 (09) :1116-1127

[3]

[Anonymous], P 40 ANN S FDN COMP

[4]

Blum M., 1973, Journal of Computer and System Sciences, V7, P448, DOI 10.1016/S0022-0000(73)80033-9

[5]

Cormen T. H., 2001, Introduction to Algorithms, V2nd

[6] Computing the maximum overlap of two convex polygons under translations [J].

de Berg, M ;

Cheong, O ;

Devillers, O ;

van Kreveld, M ;

Teillaud, M .

THEORY OF COMPUTING SYSTEMS, 1998, 31 (05) :613-628

[7]

EFRAT A, 1996, P 7 INT S ALG COMP, P115

[8] CORRECTION [J].

FREDERICKSON, GN .

SIAM JOURNAL ON COMPUTING, 1990, 19 (01) :205-206

[9] GENERALIZED SELECTION AND RANKING - SORTED MATRICES [J].

FREDERICKSON, GN ;

JOHNSON, DB .

SIAM JOURNAL ON COMPUTING, 1984, 13 (01) :14-30

[10]

GOLZMAN A, 1995, LNCS, V955, P26

← 1 2 →