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.