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

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

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.