Quotient filters: Approximate membership queries on the GPU

Afton Geil, Martin Farach-Colton, John Owens

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    In this paper, we present our GPU implementation of the quotient filter, a compact data structure designed to implement approximate membership queries. The quotient filter is similar to the more well-known Bloom filter; however, in addition to set insertion and membership queries, the quotient filter also supports deletions and merging filters without requiring rehashing of the data set. Furthermore, the quotient filter can be extended to include counters without increasing the memory footprint. This paper describes our GPU implementation of two types of quotient filters: The standard quotient filter and the rank-And-select-based quotient filter. We describe the parallelization of all filter operations, including a comparison of the four different methods we devised for parallelizing quotient filter construction. In solving this problem, we found that we needed an operation similar to a parallel scan, but for non-Associative operators. One outcome of this work is a variety of methods for computing parallel scan-Type operations on a non-Associative operator. For membership queries, we achieve a throughput of up to 1.13 billion items/second for the rank-And-select-based quotient filter: A speedup of 3x over the BloomGPU filter. Our fastest filter build method achieves a speedup of 2.1-3.1x over BloomGPU, with a peak throughput of 621 million items/second, and a rate of 516 million items/second for a 70% full filter. However, we find that our filters do not perform incremental updates as fast as the BloomGPU filter. For a batch of 2 million items, we perform incremental inserts at a rate of 81 million items/second-a 2.5x slowdown compared to BloomGPU's throughput of 201 million items/second. The quotient filter's memory footprint is comparable to that of a Bloom filter.

    Original languageEnglish (US)
    Title of host publicationProceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Pages451-462
    Number of pages12
    ISBN (Print)9781538643686
    DOIs
    StatePublished - Aug 3 2018
    Event32nd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018 - Vancouver, Canada
    Duration: May 21 2018May 25 2018

    Publication series

    NameProceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018

    Conference

    Conference32nd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018
    Country/TerritoryCanada
    CityVancouver
    Period5/21/185/25/18

    Keywords

    • Algorithms
    • Approximate membership queries
    • Bloom filter
    • Data structures
    • GPU computing

    ASJC Scopus subject areas

    • Artificial Intelligence
    • Computer Networks and Communications
    • Hardware and Architecture
    • Information Systems and Management

    Fingerprint

    Dive into the research topics of 'Quotient filters: Approximate membership queries on the GPU'. Together they form a unique fingerprint.

    Cite this