Publication:

GPU-accelerated Perfect Hash Construction: Parallel Implementation of the BDZ Algorithm and Application to Xor Filters

Thumbnail Image

Open/View Files

Primary CHUA-DOCUMENT-2023.pdf (581.07 KB)

Date

2023-05-01

Authors

Published Version

Published Version

Journal Title

Journal ISSN

Volume Title

Publisher

The Harvard community has made this article openly available. Please share how this access benefits you.

Research Projects

Organizational Units

Journal Issue

Citation

Chua, Lu Sien. 2023. GPU-accelerated Perfect Hash Construction: Parallel Implementation of the BDZ Algorithm and Application to Xor Filters. Master's thesis, Harvard University Division of Continuing Education.

Abstract

A perfect hash function (PHF) is an injection on a set of n keys S, mapping every key in S to integers in the interval [0,m − 1] with no collisions, m ≥ n. The BDZ algorithm constructs PHFs using peeling processes on random hypergraphs, and is an algorithm suited for key set sizes where the induced hypergraph fits in internal memory. In this work, we exploit the inherent parallelism present in the BDZ algorithm to introduce a GPU-accelerated construction algorithm, and show how it can be applied to a new type of approximate membership query (AMQ) data structure called the xor filter. We compare construction performance with sequential implementations, where our results show discernible improvements in construction time.

Description

Other Available Sources

Research Data

Keywords

Approximate set membership, Parallel algorithms, Peeling algorithms, Perfect hashing, Probabilistic algorithms, Xor filters, Computer science, Computer engineering, Information technology

Terms of Use

This article is made available under the terms and conditions applicable to Other Posted Material (LAA), as set forth at Terms of Service

URI

https://nrs.harvard.edu/URN-3:HUL.INSTREPOS:37375028

Collections

DCE Theses and Dissertations

Endorsement

Review

Supplemented By

Related Stories