CRII: AF: RUI: New Approaches for Space-Efficient Similarity Search

CRII：AF：RUI：节省空间的相似性搜索的新方法

• 批准号: 2103813
• 负责人: Samuel McCauley
• 金额: $ 14.87万
• 依托单位: Williams College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-06-15 至 2024-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2103813&HistoricalAwards=false
• 关键词: CRII; AF; RUI; New; Approaches

Given a large dataset, how can one find a similar item to a given query? Preprocessing the dataset to quickly find these similar items is called "similarity search." Similarity search is a fundamental computing problem with applications in data science, machine learning, and bioinformatics. Similarity search has been studied extensively both in theory and in practice, and the state of the art has been highly optimized. Unfortunately, many previous techniques require a very large amount of extra storage space to help answer queries quickly. This can be a significant limitation, as storage space is limited by the hardware being used to store the dataset. Surprisingly, space-efficient similarity-search methods have only been studied in a few restricted settings. This project seeks to close this gap, first by creating black-box methods that can be used for space-efficient similarity search in a far wider variety of settings, and then by extending known methods to achieve improved results. This project will be integrated into undergraduate courses and research opportunities at Williams College.The project seeks to solve this problem from several new directions. First, Fiat-Naor function inversion is a cryptographic technique giving a time-space tradeoff for inverting functions. Initial results show that Fiat-Naor inversion can be used to give a black-box result that improves the space usage of a wide variety of similarity-search algorithms. Even better, Fiat-Naor inversion can be integrated with known space-efficient similarity-search techniques to give improved query times using the same space. Furthermore, it appears that Fiat-Naor inversion interfaces particularly well with similarity search, and that tuning Fiat-Naor inversion to similarity search can give even better bounds. Second, the project will look at similarity search in the context of text strings. Similarity search on text strings has a rich literature of distinctive techniques tailor-made to the case of strings, generally using trie-based data structures. This project seeks to combine these techniques with more recent advances made in other areas (usually using hashing), to achieve better bounds. Finally, this project is examining heuristics for edit-distance similarity search, with the goal of matching or improving the current (space-inefficient) state of the art while retaining very small space requirements.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.

给定一个大型数据集，如何找到与给定查询相似的项目？ 预处理数据集以快速找到这些相似项称为“相似性搜索”。 相似性搜索是数据科学、机器学习和生物信息学应用中的一个基本计算问题。 相似性搜索在理论和实践中都得到了广泛的研究，并且现有技术已经高度优化。 不幸的是，许多先前的技术需要非常大量的额外存储空间来帮助快速回答查询。 这可能是一个重大限制，因为存储空间受到用于存储数据集的硬件的限制。 令人惊讶的是，节省空间的相似性搜索方法仅在少数受限的环境中进行了研究。 该项目旨在缩小这一差距，首先创建可用于在更广泛的环境中进行节省空间的相似性搜索的黑盒方法，然后扩展已知方法以实现改进的结果。 该项目将融入威廉姆斯学院的本科课程和研究机会。该项目力求从几个新的方向解决这个问题。 首先，Fiat-Naor 函数求逆是一种密码技术，为求逆函数提供了时空权衡。 初步结果表明，Fiat-Naor 反演可用于给出黑盒结果，从而提高各种相似性搜索算法的空间利用率。更好的是，Fiat-Naor 反演可以与已知的节省空间的相似性搜索技术集成，以使用相同的空间提供改进的查询时间。 此外，Fiat-Naor 反演与相似性搜索的接口似乎特别好，并且将 Fiat-Naor 反演调整为相似性搜索可以给出更好的界限。 其次，该项目将研究文本字符串上下文中的相似性搜索。 文本字符串的相似性搜索有丰富的文献，其中包含针对字符串情况量身定制的独特技术，通常使用基于 trie 的数据结构。 该项目旨在将这些技术与其他领域的最新进展（通常使用散列）相结合，以实现更好的边界。 最后，该项目正在研究编辑距离相似性搜索的启发式方法，其目标是匹配或改进当前（空间效率低下）的技术水平，同时保留非常小的空间要求。该奖项反映了 NSF 的法定使命，并被认为是值得的通过使用基金会的智力优势和更广泛的影响审查标准进行评估来获得支持。

项目成果

Telescoping Filter: A Practical Adaptive Filter

伸缩滤波器：实用的自适应滤波器

• DOI: 10.4230/lipics.esa.2021.60
• 发表时间: 2021-08
• 期刊: Leibniz international proceedings in informatics
• 作者: Lee, David J.;McCauley, Samuel;Singh, Shikha;Stein, Ma
• 通讯作者: Stein, Ma