Succinct Range Filters.
We present the Succinct Range Filter (SuRF), a fast and compact data structure for approximate membership tests. Unlike traditional Bloom filters, SuRF supports both singlekey lookups and common range queries, such as range counts. SuRF is based on a new data structure called the Fast Succinct Trie...
| Publicado en: | Communications of the ACM Vol. 64; no. 4; pp. 166 - 174 |
|---|---|
| Autores principales: | , , , , , , |
| Formato: | Artículo |
| Publicado: |
Association for Computing Machinery
Apr2021
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=149459816&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 149459816 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00010782 ACM jtl: Communications of the ACM issn: 00010782 maglogo: N pubinfo: dt: Apr2021 vid: 64 iid: 4 pid: 68 pub: Association for Computing Machinery artinfo: ui: 149459816 10.1145/3450262 ppf: 166 ppct: 8 formats: tig: atl: Succinct Range Filters. aug: au: Huanchen Zhang Lim, Hyeontaek Leis, Viktor Andersen, David G. Kaminsky, Michael Keeton, Kimberly Pavlo, Andrew affil: Carnegie Mellon University, Pittsburgh, PA, USA Friedrich Schiller University, Jena, Germany BrdgAI, Pittsburgh, PA, USA Hewlett Packard Labs, Palo Alto, CA, USA su: Query languages (Computer science) Databases Computer storage capacity Information theory sug: subj: Query languages (Computer science) Databases Computer storage capacity Information theory ab: We present the Succinct Range Filter (SuRF), a fast and compact data structure for approximate membership tests. Unlike traditional Bloom filters, SuRF supports both singlekey lookups and common range queries, such as range counts. SuRF is based on a new data structure called the Fast Succinct Trie (FST) that matches the performance of state-of-the-art order-preserving indexes, while consuming only 10 bits per trie node--a space close to the minimum required by information theory. Our experiments show that SuRF speeds up range queries in a widely used database storage engine by up to 5×. pubtype: Periodical doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2021 holdings: @attributes: islocal: N |
|---|