COMP 5704: Parallel Algorithms and Applications in Bioinformatics

School of Computer Science
Carleton University, Ottawa, Canada

Project Title: Parallel Buffering Data Structures for Searching

Name: Cory Fraser

Project Outline:

Searching has always been a prominent problem in Computer Science. Data structures to assist with searching, such as a binary search trees and B-Trees, have been created and continually improved over time. In recent years much work has been done on creating concurrent and parallel versions of these data structures that can take advantage of the multi-core nature of today's computers. One approach to speed up searching is to batch up multiple operations to perform on a data structure and perform them all at once with optimizations. A particular example of this sort of structure is described in a paper published this year, A Parallel Buffer Tree. It combines the optimizations of batching operations along with the performance increase from making use of a system's multiple cores. This project will attempt to verify the paper's claims possibly by implementing the described algorithm and testing its performance in an assortment of conditions and inputs.

Startup Paper(s):

  • N. Sitchinava, N. Zeh, A Parallel Buffer Tree
  • Deliverables:

    Relevant References: