Efficient parallel algorithms for selection and searching on sorted matrices

R. Sarnath; Xin He

Efficient parallel algorithms for selection and searching on sorted matrices

R. Sarnath
, Xin He

Department of Computer Science and Engineering

SUNY Buffalo

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

10 Scopus citations

Abstract

Parallel algorithms for more general versions of the well known selection and searching problems are formulated. We look at these problems when the set of elements can be represented as an n×n matrix with sorted rows and columns. The selection algorithm takes O(log n log log n log* n) time with O(n/log n log* n) processors on an EREW PRAM. The searching algorithm takes O(log log n) time with O(n/log log n) processors on a CREW PRAM, which is optimal. We also show that no algorithm using at most n log^c n processors, c≥1, can solve the matrix search problem in time faster than Ω(log log n).

Original language	English
Title of host publication	Proceedings of the International Conference on Parallel Processing
Publisher	Publ by IEEE
Pages	108-111
Number of pages	4
ISBN (Print)	0818626720
State	Published - 1992
Event	Proceedings of the 6th International Parallel Processing Symposium - Beverly Hills, CA, USA Duration: Mar 23 1992 → Mar 26 1992

Publication series

Name	Proceedings of the International Conference on Parallel Processing
ISSN (Print)	0190-3918

Conference

Conference	Proceedings of the 6th International Parallel Processing Symposium
City	Beverly Hills, CA, USA
Period	03/23/92 → 03/26/92

Cite this

@inproceedings{b5da199d9fde4f129444c32926009b9b,

title = "Efficient parallel algorithms for selection and searching on sorted matrices",

abstract = "Parallel algorithms for more general versions of the well known selection and searching problems are formulated. We look at these problems when the set of elements can be represented as an n×n matrix with sorted rows and columns. The selection algorithm takes O(log n log log n log* n) time with O(n/log n log* n) processors on an EREW PRAM. The searching algorithm takes O(log log n) time with O(n/log log n) processors on a CREW PRAM, which is optimal. We also show that no algorithm using at most n logc n processors, c≥1, can solve the matrix search problem in time faster than Ω(log log n).",

author = "R. Sarnath and Xin He",

year = "1992",

language = "English",

isbn = "0818626720",

series = "Proceedings of the International Conference on Parallel Processing",

publisher = "Publ by IEEE",

pages = "108--111",

booktitle = "Proceedings of the International Conference on Parallel Processing",

note = "Proceedings of the 6th International Parallel Processing Symposium ; Conference date: 23-03-1992 Through 26-03-1992",

}

Sarnath, R & He, X 1992, Efficient parallel algorithms for selection and searching on sorted matrices. in Proceedings of the International Conference on Parallel Processing. Proceedings of the International Conference on Parallel Processing, Publ by IEEE, pp. 108-111, Proceedings of the 6th International Parallel Processing Symposium, Beverly Hills, CA, USA, 03/23/92.

Efficient parallel algorithms for selection and searching on sorted matrices. / Sarnath, R.; He, Xin.
Proceedings of the International Conference on Parallel Processing. Publ by IEEE, 1992. p. 108-111 (Proceedings of the International Conference on Parallel Processing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Efficient parallel algorithms for selection and searching on sorted matrices

AU - Sarnath, R.

AU - He, Xin

PY - 1992

Y1 - 1992

N2 - Parallel algorithms for more general versions of the well known selection and searching problems are formulated. We look at these problems when the set of elements can be represented as an n×n matrix with sorted rows and columns. The selection algorithm takes O(log n log log n log* n) time with O(n/log n log* n) processors on an EREW PRAM. The searching algorithm takes O(log log n) time with O(n/log log n) processors on a CREW PRAM, which is optimal. We also show that no algorithm using at most n logc n processors, c≥1, can solve the matrix search problem in time faster than Ω(log log n).

AB - Parallel algorithms for more general versions of the well known selection and searching problems are formulated. We look at these problems when the set of elements can be represented as an n×n matrix with sorted rows and columns. The selection algorithm takes O(log n log log n log* n) time with O(n/log n log* n) processors on an EREW PRAM. The searching algorithm takes O(log log n) time with O(n/log log n) processors on a CREW PRAM, which is optimal. We also show that no algorithm using at most n logc n processors, c≥1, can solve the matrix search problem in time faster than Ω(log log n).

UR - https://www.scopus.com/pages/publications/0026984899

M3 - Conference contribution

AN - SCOPUS:0026984899

SN - 0818626720

T3 - Proceedings of the International Conference on Parallel Processing

SP - 108

EP - 111

BT - Proceedings of the International Conference on Parallel Processing

PB - Publ by IEEE

T2 - Proceedings of the 6th International Parallel Processing Symposium

Y2 - 23 March 1992 through 26 March 1992

ER -

Efficient parallel algorithms for selection and searching on sorted matrices

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this