WFRF:(Schliep Alexander 1967)
Search: WFRF:(Schliep Alexander 1967) > (2015-2019) > An optimization pro...
- 1 of 15
- Previous record
- Next record
- To hitlist
An optimization problem related to bloom filters with bit patterns
-
- Damaschke, Peter, 1963 (author)
- Chalmers tekniska högskola,Chalmers University of Technology
-
- Schliep, Alexander, 1967 (author)
- Gothenburg University,Göteborgs universitet,Institutionen för data- och informationsteknik, datavetenskap (GU),Department of Computer Science and Engineering, Computing Science (GU),University of Gothenburg
- (creator_code:org_t)
- 2017-12-22
- 2018
- English.
- In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Cham : Springer International Publishing. - 0302-9743 .- 1611-3349.
- Conference paper (peer-reviewed)
Abstract
Subject headings
Close
- © 2018, Springer International Publishing AG. Bloom filters are hash-based data structures for membership queries without false negatives widely used across many application domains. They also have become a central data structure in bioinformatics. In genomics applications and DNA sequencing the number of items and number of queries are frequently measured in the hundreds of billions. Consequently, issues of cache behavior and hash function overhead become a pressing issue. Blocked Bloom filters with bit patterns offer a variant that can better cope with cache misses and reduce the amount of hashing. In this work we state an optimization problem concerning the minimum false positive rate for given numbers of memory bits, stored elements, and patterns. The aim is to initiate the study of pattern designs best suited for the use in Bloom filters. We provide partial results about the structure of optimal solutions and a link to two-stage group testing.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- Antichain
- Bloom filter
- Disjunct matrix
- Genomics
- Group testing
- Bloom filter
Publication and Content Type
- ref (subject category)
- kon (subject category)
Find in a library
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artifici... (Search for host publication in LIBRIS)
To the university's database
- 1 of 15
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Damaschke, Peter ...
- Schliep, Alexand ...
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Computer Science ...
- Articles in the publication
- Lecture Notes in ...
- By the university
- University of Gothenburg
- Chalmers University of Technology
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
