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

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

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.