CAREER: Practical Adaptive Filters and Applications

About This Grant

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.