DocumentCode
1913674
Title
Deleting keys of B-trees in parallel
Author
Heejin Park ; Kunsoo Park ; Yookun Cho
Author_Institution
Sch. of Comput. Sci. & Eng., Seoul Nat. Univ., South Korea
fYear
2001
fDate
15-19 April 2001
Abstract
The B-tree is a fundamental data structure that is used to access and update a large number of keys. In this paper we present a parallel algorithm on the EREW PRAM that deletes keys in a B-tree. Our algorithm runs in O(t(log k+log, n)) time with k processors, where n is the number of keys in the B-tree, t is the minimum degree of the B-tree, and k is the number of unsorted keys to delete, and it improves upon the previous algorithm by a factor of t.
Keywords
computational complexity; parallel algorithms; pipeline processing; search problems; tree data structures; B-trees; EREW PRAM; balanced search trees; computational complexity; data structure; dictionary operations; parallel algorithms; pipeline processing; Computer science; Data engineering; Data structures; Dictionaries; Distributed processing; Parallel algorithms; Phase change random access memory; Pipeline processing;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel and Distributed Processing Symposium., Proceedings International, IPDPS 2002, Abstracts and CD-ROM
Conference_Location
Ft. Lauderdale, FL
Print_ISBN
0-7695-1573-8
Type
conf
DOI
10.1109/IPDPS.2002.1015581
Filename
1015581
Link To Document