Collaborative Research: OAC: Approximate Nearest Neighbor Similarity Search for Large Polygonal and Trajectory Datasets

合作研究：OAC：大型多边形和轨迹数据集的近似最近邻相似性搜索

• 批准号: 2313039
• 负责人: Sushil Prasad
• 金额: $ 36.5万
• 依托单位: University of Texas at San Antonio
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-08-01 至 2026-07-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2313039&HistoricalAwards=false
• 关键词: Collaborative; Research; OAC; Approximate; Nearest

Similarity searches are a critical task in data mining. Nearest neighbor similarity search over geometrical shapes - polygons and trajectories - are used in various domains such as digital pathology, solar physics, and geospatial intelligence. In digital pathology for tumor diagnosis, tissues are represented as polygons and Jaccard distance - ratio of areas of intersection to union - is used for similarity comparisons. In solar physics for predicting solar flares, the query object and the dataset is made up of polygons representing solar events. In geospatial intelligence, similarity search is used to geo-locate a shape or a contour in global reference datasets. The current literature, while rich in methods for textual and image datasets, is lacking for geometric datasets. This project will develop scalable similarity search systems on polygonal and trajectory datasets. It will produce benchmark datasets of polygonal queries and responses for the research community and inform the data mining techniques which employ similarity primitives. It will help introduce student projects for courses on parallel, distributed, high performance, and data intensive computing, data mining, and spatial computing. This will also train PhD students, including those at a Hispanic Serving Institution. Given the ever increasing size of datasets, exact nearest neighbor searches requiring a scan of the entire dataset quickly become impractical, leading to approximate nearest neighbor searches. Traditional methods, such as using trees, suffer from the constraints of dimensionality. Approximate similarity search is required for scalability in processing large numbers of queries, index construction over big spatial data, and to address the dynamic nature of data itself. This project will explore approximate similarity search algorithms based on product quantization and locality sensitive hashing (LSH) techniques for 10-100 billion scale datasets. It will result in (i) new methods for creating robust signatures of geometric data, based on comprehensive exploration of the performance/accuracy tradeoffs among different encoding schemes, informed by spatial properties of the data and requirements of relevant distance metrics, (ii) scalable coarse quantization techniques to hierarchically organize the polygonal datasets into neighborhoods by preserving hyperspace locality properties, leading to product quantization based scalable systems, and (iii) LSH-based techniques focusing on designing LSH functions for Jaccard distance.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.

相似性搜索是数据挖掘中的一项关键任务。对几何形状（多边形和轨迹）的最近邻相似性搜索用于各种领域，例如数字病理学、太阳物理学和地理空间智能。在肿瘤诊断的数字病理学中，组织被表示为多边形，并且杰卡德距离（交叉面积与联合面积的比率）用于相似性比较。在预测太阳耀斑的太阳物理学中，查询对象和数据集由表示太阳事件的多边形组成。在地理空间智能中，相似性搜索用于对全球参考数据集中的形状或轮廓进行地理定位。当前的文献虽然丰富了文本和图像数据集的方法，但缺乏几何数据集的方法。该项目将开发针对多边形和轨迹数据集的可扩展相似性搜索系统。它将为研究社区生成多边形查询和响应的基准数据集，并为采用相似基元的数据挖掘技术提供信息。它将帮助介绍并行、分布式、高性能和数据密集型计算、数据挖掘和空间计算课程的学生项目。这还将培训博士生，包括西班牙裔服务机构的博士生。鉴于数据集的大小不断增加，需要扫描整个数据集的精确最近邻搜索很快变得不切实际，从而导致近似最近邻搜索。传统方法（例如使用树）受到维度的限制。处理大量查询、在大空间数据上构建索引以及解决数据本身的动态特性时，需要近似相似性搜索来实现可扩展性。该项目将探索基于乘积量化和局部敏感哈希（LSH）技术的近似相似度搜索算法，适用于 10-1000 亿规模的数据集。它将产生（i）基于对不同编码方案之间的性能/精度权衡的全面探索，根据数据的空间属性和相关距离度量的要求，创建稳健的几何数据签名的新方法，（ii）可扩展粗量化技术，通过保留超空间局部性属性，将多边形数据集分层组织成邻域，从而产生基于乘积量化的可扩展系统，以及 (iii) 基于 LSH 的技术，专注于为 Jaccard 距离设计 LSH 函数。该奖项反映了通过使用基金会的智力价值和更广泛的影响审查标准进行评估，NSF 的法定使命被认为值得支持。