CAREER: Practical Adaptive Filters and Applications

过滤器在准确性和空间之间进行权衡，偶尔会返回带有有限错误的假阳性匹配。过滤器广泛用于在快速内存（RAM）中紧凑地表示大型数据集，并避免跨数据库、存储系统、计算生物学、网络安全和网络的不必要I/ o。然而，现代数据密集型应用受到过滤器限制的严重瓶颈。传统过滤器的一个基本限制是，它们在看到假阳性匹配时不会改变它们的表示。因此，最大误报率只能保证单个查询，而不能保证查询流。如果用户能够在看到假阳性匹配后进行调整，他们就可以提高查询流（特别是倾斜分布）的过滤性能。该项目侧重于两个目标。首先，设计具有强自适应保证的高性能、空间高效和实用的自适应滤波器，这意味着即使在对抗性工作负载下，性能和误报概率保证仍然保持不变。其次，深入研究应用程序中的各种性能权衡，并将自适应滤波器集成到数据库、网络安全应用程序和计算生物学工具中。这项工作重新设计了现有的应用程序，并开发了新的软件工具，以建立适当的权衡，并实现高性能和空间效率。该项目有以下顶层方法：开发理论和附带的数据结构库，用于在各种实际工作负载下的强自适应过滤器，包括删除和更新、调整大小和合并两个自适应过滤器。它通过将自适应滤波器集成到应用程序中，并为倾斜和对抗性工作负载实现大量加速和健壮的性能，展示了自适应滤波器在现实世界中的影响。该项目将增强跨数据库、计算生物学和网络安全应用程序的能力，以实现更高、更强的性能保证。加速计算（允许更快的反馈和更多的实验）和更广泛的计算都可能加速科学发现的过程。此外，本项目非常注重理论与实践的结合。此外，研究小组还将编写关于自适应数据结构及其在现代数据密集型应用中的使用的教材，并在网上免费提供。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Filters tradeoff accuracy for space and occasionally return false positive matches with a bounded error. Filters are extensively used to compactly represent large datasets in fast memory (RAM) and avoid unnecessary I/Os across databases, storage systems, computational biology, cybersecurity, and networks. Yet modern data-intensive applications are severely bottlenecked by the limitations in filters. A fundamental limitation of traditional filters is that they do not change their representation upon seeing a false positive match. Therefore, the maximum false positive rate is only guaranteed for a single query, not a stream of queries. If users can adapt after seeing false positive matches, they can improve the filter performance for a stream of queries (especially skewed distributions). This project focuses on two goals. First, to design a high-performance, space-efficient, and practical adaptive filter with strong adaptivity guarantees, which means that the performance and false-positive probability guarantees continue to hold even for adversarial workloads. Second, to do a deep dive into various performance trade-offs in applications and integrate the adaptive filter in databases, cybersecurity applications, and computational biology tools. The effort redesigns existing applications and develops new software tools to establish appropriate trade-offs and achieve high performance and space efficiency. This project has the following top-level approach: develop the theory and an accompanying data structure library for strong adaptive filters under various real-world workloads involving deletions and updates, resizing, and merging two adaptive filters. It demonstrates the impact of adaptive filters in the real world by integrating the adaptive filter into applications and achieving massive speed-ups and robust performance for skewed and adversarial workloads. This project will enhance the capability of applications across databases, computational biology, and cybersecurity to achieve higher and stronger performance guarantees. Both accelerated computation (allowing quicker feedback and more experiments) and more extensive computation potentially accelerate the process of scientific discovery. Furthermore, this project places a strong emphasis on combining theory and practice. In addition, the research team will also develop teaching material on adaptive data structures and their usage in modern data-intensive applications and make it freely available online.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.