14113

Perfect Hashing Structures for Parallel Similarity Searches

Tuan Tu Tran, Mathieu Giraud, Jean-Stephane Varre
Johannes Gutenberg-Universitat Mainz, Mainz, Germany
14th IEEE International Workshop on High Performance Computational Biology (HiCOMB’15), 2015

@article{lille2015perfect,

   title={Perfect Hashing Structures for Parallel Similarity Searches},

   author={Lille, France},

   year={2015}

}

Download Download (PDF)   View View   Source Source   

1347

views

Seed-based heuristics have proved to be efficient for studying similarity between genetic databases with billions of base pairs. This paper focuses on algorithms and data structures for the filtering phase in seed-based heuristics, with an emphasis on efficient parallel GPU/manycores implementation. We propose a 2-stage index structure which is based on neighborhood indexing and perfect hashing techniques. This structure performs a filtering phase over the neighborhood regions around the seeds in constant time and avoid as much as possible random memory accesses and branch divergences. Moreover, it fits particularly well on parallel SIMD processors, because it requires intensive but homogeneous computational operations. Using this data structure, we developed a fast and sensitive OpenCL prototype read mapper.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: