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

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

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.