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

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

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.