惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

J
Java Code Geeks
量子位
MongoDB | Blog
MongoDB | Blog
N
Netflix TechBlog - Medium
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
B
Blog
A
About on SuperTechFans
腾讯CDC
The GitHub Blog
The GitHub Blog
云风的 BLOG
云风的 BLOG
雷峰网
雷峰网
Last Week in AI
Last Week in AI
H
Help Net Security
WordPress大学
WordPress大学
博客园 - 司徒正美
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
H
Hackread – Cybersecurity News, Data Breaches, AI and More
T
Tailwind CSS Blog
博客园 - 【当耐特】
S
SegmentFault 最新的问题
美团技术团队
M
MIT News - Artificial intelligence
L
LangChain Blog
博客园 - 聂微东

cs.DB updates on arXiv.org

Block-Sphere Vector Quantization GroupAffect-4: A Multimodal Dataset of Four-Person Collaborative Interaction CogScale: Scalable Benchmark for Sequence Processing TextAlign: Preference Alignment for Text Rendering with Hierarchical Rewards LogRouter: Adaptive Two-Level LLM Routing for Log Question Answering in Big Data Systems Agentic Cost-Aware Query Planning with Knowledge Distillation for Big Data Analytics Covariance Structure and Coordinate Heterogeneity Govern Binary Quantization of Contrastive Embeddings IVF-TQ: Calibration-Free Streaming Vector Search via a Codebook-Free Residual Layer Automatic Unsupervised Ensemble Outlier Model Selection--Extended Version A Generative AI Framework for Intelligent Utility Billing CO 2 Analytics and Sustainable Resource Optimisation Towards Foundation Models for Relational Databases with Language Models and Graph Neural Networks Gaussian Relational Graph Transformer Croissant Baker: Metadata Generation for Discoverable, Governable, and Reusable ML Datasets Reducing Hallucination in Vision-Language Models via Stage-wise Preference Optimization under Distribution Shift A Horn extension of DL-Lite with NL data complexity 3D Primitives are a Spatial Language for VLMs Enabling AI-Native Mobility in 6G: A Real-World Dataset for Handover, Beam Management, and Timing Advance A CAP-like Trilemma for Large Language Models: Correctness, Non-bias, and Utility under Semantic Underdetermination EpiCastBench: Datasets and Benchmarks for Multivariate Epidemic Forecasting FERMI: Exploiting Relations for Membership Inference Against Tabular Diffusion Models Toward Multi-Database Query Reasoning for Text2Cypher Autonomous FAIR Digital Objects: From Passive Assertions to Active Knowledge HOME-KGQA: A Benchmark Dataset for Multimodal Knowledge Graph Question Answering on Household Daily Activities Detect, Localize, and Explain: Interactive Hierarchical Log Anomaly Analytics with LLM Augmentation Open Ontologies: Tool-Augmented Ontology Engineering with Stable Matching Alignment Machine Learning-Based Pre-Test Risk Stratification for PCR-Confirmed Chlamydia Using Patient-Reported Data and Urine Biomarkers Reconciling Consistency-Based Diagnosis with Actual-Causality-Based Explanations PrepBench: How Far Are We from Natural-Language-Driven Data Preparation? Anatomy of a Query: W5H Dimensions and FAR Patterns for Text-to-SQL Evaluation Building informative materials datasets beyond targeted objectives
Daisy Bloom Filters
Ioana O. Bercea, Jakob Bæk Tejs Houen, Rasmus Pagh · 2022-05-30 · via cs.DB updates on arXiv.org

A filter is a widely used data structure for storing an approximation of a given set $S$ of elements from some universe $U$ (a countable set).It represents a superset $S'\supseteq S$ that is ''close to $S$'' in the sense that for $x\not\in S$, the probability that $x\in S'$ is bounded by some $\varepsilon > 0$. The advantage of using a Bloom filter, when some false positives are acceptable, is that the space usage becomes smaller than what is required to store $S$ exactly. Though filters are well-understood from a worst-case perspective, it is clear that state-of-the-art constructions may not be close to optimal for particular distributions of data and queries. Suppose, for instance, that some elements are in $S$ with probability close to 1. Then it would make sense to always include them in $S'$, saving space by not having to represent these elements in the filter. Questions like this have been raised in the context of Weighted Bloom filters (Bruck, Gao and Jiang, ISIT 2006) and Bloom filter implementations that make use of access to learned components (Vaidya, Knorr, Mitzenmacher, and Krask, ICLR 2021). In this paper, we present a lower bound for the expected space that such a filter requires. We also show that the lower bound is asymptotically tight by exhibiting a filter construction that executes queries and insertions in worst-case constant time, and has a false positive rate at most $\varepsilon $ with high probability over input sets drawn from a product distribution. We also present a Bloom filter alternative, which we call the $\textit{Daisy Bloom filter}$, that executes operations faster and uses significantly less space than the standard Bloom filter.