AF: Small: Approximation Algorithms and Data Structures for Geometric Retrieval

许多数据集可以被视为高维空间中的点，这是有利可图的：想想员工的工资和资历，气象站每小时发布的温度、湿度、风速和方向报告，甚至手机摄像头的图像都是每像素的颜色值。几何检索问题寻求对多维几何数据进行预处理，以便于快速访问；例如，“最近邻查询”可以找到与查询图像相似的图像，而“范围查询”可以在温度和湿度高于给定阈值的情况下找到所有时间。这些查询在工程和科学中具有基本的重要性，在知识发现和数据挖掘、模式识别和分类、机器学习、数据压缩、多媒体数据库、文档检索和统计中都有应用。高维中最近邻和范围查询的高计算复杂性激发了对近似解决方案的研究。本课题的工作加深和拓宽了我们对这两个问题计算复杂性的理解。它研究了新的、更有效的解决关键特殊情况的解决方案，包括对凸体的低复杂性近似、多面体成员查询的快速算法、近邻搜索的应用、欧几里得和最小生成树的高效近似算法以及带结构查询的范围搜索。这些改进的算法将在上述应用中产生更高效的解决方案。作为该项目的一部分开发的软件系统和库将在Web上免费提供，以帮助其他学科的科学家和工程师。作为该项目的一部分，开发的算法将被纳入马里兰大学的研究生和本科生课程。课程材料将在网上提供，作为有兴趣了解更多这一领域的研究人员的资源。

Many data sets can profitably be viewed as points in ahigh-dimensional space: think of employee salary and seniority,weather stations' hourly reports of temperature, humidity, wind speed,and direction, or even the images from your cellphone camera as colorvalues per pixel. Geometric retrieval problems seek to preprocessmulti-dimensional geometric data for rapid access; for two examples,"nearest neighbor queries" could find images similar to a query image,and "range queries" could find all times with temperature and humidityabove given thresholds. These queries are of fundamental importance throughoutengineering and science, and have applications in knowledge discoveryand data mining, pattern recognition and classification, machinelearning, data compression, multimedia databases, document retrieval,and statistics.The high computational complexity of nearest neighbor and range queries in high dimensions hasinspired research into approximate solutions. The work of this projectdeepens and broadens our understanding of the computationalcomplexity of these two problems. It studies new, more efficient solutions tokey special cases, includinglow-complexity approximations to convex bodies, faster algorithms forpolytope membership queries, applications to approximate nearestneighbor searching, efficient approximation algorithms for Euclideanminimum spanning trees, and range searching with structural queries.These improved algorithms will lead to more efficient solutions in theapplications described above.Software systems and libraries developed as part of this project will bemade freely available over the Web to help scientists and engineers inother disciplines. The algorithms developed as a part of this projectwill be incorporated into graduate and undergraduate courses at theUniversity of Maryland. Course materials will be made available over theWeb as a resource for researchers interested in learning more about thisarea.