CAREER: Practical Adaptive Filters and Applications

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

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.