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

相似性搜索是数据挖掘中的一项重要任务。几何形状（多边形和轨迹）上的最近邻相似性搜索用于各种领域，例如数字病理学，太阳物理学和地理空间智能。在用于肿瘤诊断的数字病理学中，组织被表示为多边形，并且Jaccard距离（相交与联合的面积的比率）用于相似性比较。在预测太阳耀斑的太阳物理学中，查询对象和数据集由表示太阳事件的多边形组成。在地理空间智能中，相似性搜索用于在全局参考数据集中对形状或轮廓进行地理定位。目前的文献，而丰富的文本和图像数据集的方法，是缺乏几何数据集。该项目将在多边形和轨迹数据集上开发可扩展的相似性搜索系统。它将为研究界产生多边形查询和响应的基准数据集，并为采用相似性原语的数据挖掘技术提供信息。它将帮助介绍并行，分布式，高性能和数据密集型计算，数据挖掘和空间计算课程的学生项目。这也将培养博士生，包括那些在西班牙裔服务机构。由于数据集的大小不断增加，需要扫描整个数据集的精确最近邻搜索很快变得不切实际，导致近似最近邻搜索。传统的方法，如使用树，受到维数的限制。近似相似性搜索是处理大量查询的可伸缩性、大空间数据的索引构建以及解决数据本身的动态特性所必需的。该项目将探索基于乘积量化和局部敏感哈希（LSH）技术的近似相似性搜索算法，用于100 - 1000亿规模的数据集。它将导致（i）用于创建几何数据的鲁棒签名的新方法，该方法基于对不同编码方案之间的性能/准确性权衡的全面探索，由数据的空间属性和相关距离度量的要求通知，（ii）通过保持超空间局部性属性来分层地将多边形数据集组织成邻域的可扩展粗量化技术，该奖项反映了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.