A retrieval data structure for a static function $f:S\rightarrow \{0,1\}^r$ supports queries that return $f(x)$ for any $x \in S$. Retrieval data structures can be used to implement a static approximate membership query data structure (AMQ) (i.e., a Bloom filter alternative) with false positive rate $2^{-r}$. The information-theoretic lower bound for both tasks is $r|S|$ bits. While succinct theoretical constructions using $(1+o(1))r|S|$ bits were known, these could not achieve very small overheads in practice because they have an unfavorable space-time tradeoff hidden in the asymptotic costs or because small overheads would only be reached for physically impossible input sizes. With bumped ribbon retrieval (BuRR), we present the first practical succinct retrieval data structure. In an extensive experimental evaluation BuRR achieves space overheads well below $1\,\%$ while being faster than most previously used retrieval data structures (typically with space overheads at least an order of magnitude larger) and faster than classical Bloom filters (with space overhead $\geq 44\,\%$). This efficiency, including favorable constants, stems from a combination of simplicity, word parallelism, and high locality. We additionally describe homogeneous ribbon filter AMQs, which are even simpler and faster at the price of slightly larger space overhead.


翻译:用于静态函数的检索数据结构 $f : S\\ rightrow = 10,1 ⁇ r $ 支持返回 $x $x $x 的查询 。 检索数据结构可用于实施静态近似成员查询数据结构 (AMQ)(即Bloom过滤器替代方案), 假正率为 2 ⁇ - r 美元 。 两种任务的信息- 理论下限为 $@ $s 。 虽然已知使用 $( 1+o(1)) r ⁇ S $ 位的简单理论结构, 但这些结构在实际操作中不可能达到非常小的间接费用, 因为它们有隐藏在静态成本中的不受欢迎的时空时间交易, 或因为小的间接投资只能用于实际无法投入的大小 。 在缓冲的丝带检索(BARR) 中,我们第一次提出了实用的简洁的检索数据结构。 在广泛的实验性评估中, BuRR 实现的空间管理费大大低于 $\, $ $, 而比大多数使用的数据检索结构要快( 通常使用的数据结构, 以至少是空间管理器, 以至少一个更简洁的平的平的平的平的平的平的平, 。

0
下载
关闭预览

相关内容

iOS 8 提供的应用间和应用跟系统的功能交互特性。
  • Today (iOS and OS X): widgets for the Today view of Notification Center
  • Share (iOS and OS X): post content to web services or share content with others
  • Actions (iOS and OS X): app extensions to view or manipulate inside another app
  • Photo Editing (iOS): edit a photo or video in Apple's Photos app with extensions from a third-party apps
  • Finder Sync (OS X): remote file storage in the Finder with support for Finder content annotation
  • Storage Provider (iOS): an interface between files inside an app and other apps on a user's device
  • Custom Keyboard (iOS): system-wide alternative keyboards

Source: iOS 8 Extensions: Apple’s Plan for a Powerful App Ecosystem
【2020新书】Python文本分析,104页pdf
专知会员服务
98+阅读 · 2020年12月23日
【WSDM2021】保存节点相似性的图卷积网络
专知会员服务
40+阅读 · 2020年11月22日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
71+阅读 · 2020年8月2日
商业数据分析,39页ppt
专知会员服务
159+阅读 · 2020年6月2日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
已删除
将门创投
5+阅读 · 2019年5月5日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】Python机器学习生态圈(Scikit-Learn相关项目)
机器学习研究会
6+阅读 · 2017年8月23日
Arxiv
0+阅读 · 2021年10月25日
Arxiv
0+阅读 · 2021年10月22日
VIP会员
相关VIP内容
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
已删除
将门创投
5+阅读 · 2019年5月5日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】Python机器学习生态圈(Scikit-Learn相关项目)
机器学习研究会
6+阅读 · 2017年8月23日
Top
微信扫码咨询专知VIP会员