Mitzenmacher, MichaelWang, HongmingChua, Lu Sien2023-05-0220232023-05-012023Chua, 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.30485914https://nrs.harvard.edu/URN-3:HUL.INSTREPOS:37375028A 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.application/pdfenApproximate set membershipParallel algorithmsPeeling algorithmsPerfect hashingProbabilistic algorithmsXor filtersComputer scienceComputer engineeringInformation technologyThesis or Dissertation2023-05-02