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

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

基本信息

  • 批准号:
    2103813
  • 负责人:
  • 金额:
    $ 14.87万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2021
  • 资助国家:
    美国
  • 起止时间:
    2021-06-15 至 2024-11-30
  • 项目状态:
    已结题

项目摘要

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反转调整为相似性搜索可以给出更好的边界。其次,该项目将研究文本字符串上下文中的相似性搜索。文本字符串上的相似性搜索有丰富的专门针对字符串的技术文献,通常使用基于尝试的数据结构。本项目试图将这些技术与其他领域的最新进展(通常使用哈希)结合起来,以获得更好的边界。最后,这个项目正在检查编辑距离相似搜索的启发式方法,其目标是匹配或改进当前(空间效率低下)的技术状态,同时保留非常小的空间需求。该奖项反映了美国国家科学基金会的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(1)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Telescoping Filter: A Practical Adaptive Filter
  • DOI:
    10.4230/lipics.esa.2021.60
  • 发表时间:
    2021-07
  • 期刊:
  • 影响因子:
    0
  • 作者:
    David J. Lee;Samuel McCauley;Shikha Singh;Maximilian Stein
  • 通讯作者:
    David J. Lee;Samuel McCauley;Shikha Singh;Maximilian Stein
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Samuel McCauley其他文献

APPENDIX : Cache-Adaptive Analysis ( Full Version )
附录:缓存自适应分析(完整版)
  • DOI:
  • 发表时间:
    2017
  • 期刊:
  • 影响因子:
    0
  • 作者:
    M. A. Bender;E. Demaine;Roozbeh Ebrahimi;Jeremy T. Fineman;Rob Johnson;Andrea Lincoln;J. Lynch;Samuel McCauley
  • 通讯作者:
    Samuel McCauley
G T ] 1 5 A ug 2 01 9 Non-Cooperative Rational Interactive Proofs ∗
GT ] 1 5 A ug 2 01 9 非合作理性交互证明 *
  • DOI:
  • 发表时间:
    2019
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Jiehua Chen;Samuel McCauley;Shikha Singh
  • 通讯作者:
    Shikha Singh
Resource Optimization for Program Committee Members: A Subreview Article
程序委员会成员的资源优化:分评论文章
  • DOI:
    10.4230/lipics.fun.2016.7
  • 发表时间:
    2016
  • 期刊:
  • 影响因子:
    0
  • 作者:
    M. A. Bender;Samuel McCauley;B. Simon;Shikha Singh;F. Vivien
  • 通讯作者:
    F. Vivien
Cache-Adaptive Algorithms
缓存自适应算法
  • DOI:
    10.1137/1.9781611973402.71
  • 发表时间:
    2014
  • 期刊:
  • 影响因子:
    3.7
  • 作者:
    M. A. Bender;Roozbeh Ebrahimi;Jeremy T. Fineman;Golnaz Ghasemiesfeh;Rob Johnson;Samuel McCauley
  • 通讯作者:
    Samuel McCauley
Support Optimality and Adaptive Cuckoo Filters
支持最优性和自适应布谷鸟滤波器
  • DOI:
    10.1007/978-3-030-83508-8_40
  • 发表时间:
    2021
  • 期刊:
  • 影响因子:
    5.2
  • 作者:
    T. Kopelowitz;Samuel McCauley;E. Porat
  • 通讯作者:
    E. Porat

Samuel McCauley的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Samuel McCauley', 18)}}的其他基金

EAPSI:Facilitating cooperation between unreliable processors without direct communication
EAPSI:促进不可靠处理器之间无需直接通信的合作
  • 批准号:
    1414973
  • 财政年份:
    2014
  • 资助金额:
    $ 14.87万
  • 项目类别:
    Fellowship Award

相似国自然基金

基于前瞻性队列的双酚AF联合果糖加重代谢损伤的靶向代谢组学研究
  • 批准号:
    2025JJ30049
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
U2AF2-circMMP1信号轴促进结直肠癌进展的分子机制研究
  • 批准号:
    2025JJ80723
  • 批准年份:
    2025
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
U2AF2精氯酸甲基化调控RNA转录合成在MTAP缺失骨肉瘤T细胞耗竭中的机制研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0 万元
  • 项目类别:
    青年科学基金项目
BDA-366通过MYD88/NF-κB/PGC1β通路杀伤 KMT2A/AF9 AML细胞的机制研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    15.0 万元
  • 项目类别:
    省市级项目
Lu AF21934减少缺血性脑卒中导致的神经损伤的机制研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
H2S介导剪接因子BraU2AF65a的S-巯基化修饰促进大白菜开花的分子机制
  • 批准号:
    32372727
  • 批准年份:
    2023
  • 资助金额:
    50 万元
  • 项目类别:
    面上项目
AF9通过ARRB2-MRGPRB2介导肠固有肥大细胞活化促进重症急性胰腺炎发生MOF的研究
  • 批准号:
    82300739
  • 批准年份:
    2023
  • 资助金额:
    30 万元
  • 项目类别:
    青年科学基金项目
剪接因子U2AF1突变在急性髓系白血病原发耐药中的机制研究
  • 批准号:
    82370157
  • 批准年份:
    2023
  • 资助金额:
    49 万元
  • 项目类别:
    面上项目
线粒体活性氧介导的胎盘早衰在孕期双酚AF暴露致婴幼儿神经发育迟缓中的作用
  • 批准号:
    82304160
  • 批准年份:
    2023
  • 资助金额:
    30 万元
  • 项目类别:
    青年科学基金项目
U2AF2-circMMP1调控能量代谢促进结直肠癌肝转移的分子机制
  • 批准号:
    82303789
  • 批准年份:
    2023
  • 资助金额:
    30 万元
  • 项目类别:
    青年科学基金项目

相似海外基金

CRII: AF: RUI: New Frontiers in Fundamental Error-Correcting Codes
CRII:AF:RUI:基本纠错码的新领域
  • 批准号:
    2347371
  • 财政年份:
    2024
  • 资助金额:
    $ 14.87万
  • 项目类别:
    Standard Grant
CRII: AF: RUI: Algorithmic Fairness for Computational Social Choice Models
CRII:AF:RUI:计算社会选择模型的算法公平性
  • 批准号:
    2348275
  • 财政年份:
    2024
  • 资助金额:
    $ 14.87万
  • 项目类别:
    Standard Grant
AF: Small: RUI: Toward High-Performance Block Krylov Subspace Algorithms for Solving Large-Scale Linear Systems
AF:小:RUI:用于求解大规模线性系统的高性能块 Krylov 子空间算法
  • 批准号:
    2327619
  • 财政年份:
    2023
  • 资助金额:
    $ 14.87万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: RUI: Data Science from Economic Foundations
合作研究:AF:小型:RUI:来自经济基础的数据科学
  • 批准号:
    2218814
  • 财政年份:
    2022
  • 资助金额:
    $ 14.87万
  • 项目类别:
    Standard Grant
CRII: AF: RUI: Breaking Ground on Circulant TSP
CRII:AF:RUI:循环 TSP 破土动工
  • 批准号:
    2153331
  • 财政年份:
    2022
  • 资助金额:
    $ 14.87万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: RUI: Data Science from Economic Foundations
合作研究:AF:小型:RUI:来自经济基础的数据科学
  • 批准号:
    2218813
  • 财政年份:
    2022
  • 资助金额:
    $ 14.87万
  • 项目类别:
    Standard Grant
CRII: AF: RUI: Markov Chains and Random Sampling on Graphs
CRII:AF:RUI:马尔可夫链和图上的随机采样
  • 批准号:
    2104795
  • 财政年份:
    2021
  • 资助金额:
    $ 14.87万
  • 项目类别:
    Standard Grant
CRII: AF: RUI: Engineering and Experiments with Geometric Spanner Construction Algorithms for Massive Point Sets
CRII:AF:RUI:大规模点集的几何扳手构造算法的工程和实验
  • 批准号:
    1947887
  • 财政年份:
    2020
  • 资助金额:
    $ 14.87万
  • 项目类别:
    Standard Grant
CRII: AF: RUI: Verifiable Computation Outsourcing: A Non-Cooperative Approach
CRII:AF:RUI:可验证计算外包:一种非合作方法
  • 批准号:
    1947789
  • 财政年份:
    2020
  • 资助金额:
    $ 14.87万
  • 项目类别:
    Standard Grant
AF: Small: RUI: Towards Resolving the Dynamic Optimality Conjecture.
AF:小:RUI:解决动态最优猜想。
  • 批准号:
    1910873
  • 财政年份:
    2019
  • 资助金额:
    $ 14.87万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了