Global Structure Discovery on Sampled Spaces

在过去的十年里，磁盘存储成本的急剧下降和世界范围内高带宽光纤通信的建立，使得每个人都可以通过Web轻松地获得不同形式的海量数据(文本、图像、视频)。在科学、工程、商业和医学领域，高带宽传感器、大规模模拟和数据收集机器人生成了大量需要分析的数据集。理解所有这些不同的数据变得越来越具有挑战性和难度。与传统数据库不同，在传统数据库中，数据被仔细地修改以遵守严格的架构，而上面的许多数据是非结构化的，通常是动态的，而不是静态的，可能包含大量的噪音甚至错误，并且可能是不完整的。该项目旨在开发用于分析海量和分布式非结构化数据集的通用、严格和高效的技术。基本目标是在研究大型分布式数据集的全局结构时利用计算拓扑学和几何学中的某些思想--特别是开发使这种结构更加明显的数据表示和转换。拓扑学研究空间的连通性，因此它本质上是全球性的。它能够以不受对象变形影响的方式确定某些连通性不变量，并且不需要对象几何图形的显式参数化。在某种意义上，它的优势在于它对几何性质的相对不敏感，这使得它能够辨别关于几何对象如何构造的潜在组合信息，从而检测一些定性性质。这种类型的全局分析对于理解数据集的整体结构可能非常重要。几何学虽然本质上更具有局部性，但也可以通过发现一个对象的部分如何与另一个对象相关，或不同对象的部分如何相似来研究全球结构。例如，一个多世纪以来，Felix Klein的Erlanger程序激发了数学家对某些群作用下的不变性的兴趣，将其作为理解几何空间的关键原则。这种不变性或对称性也是理解和推理数据集的关键。本文提出的方法可以应用于大量非结构化数据集出现的许多不同环境中。在科学或工程领域，大规模的分布式模拟可以产生巨大的数据集；例如，斯坦福大学的Folding@Home项目使用世界各地数十万个CPU来生成蛋白质折叠轨迹。在商业领域，谷歌和雅虎！我必须挖掘数十亿次网络点击来开发将广告与网页内容或个人用户匹配的算法。在医学领域，3D成像正变得司空见惯。分布在全国各地医疗机构的医学成像诊断系统应该能够有效地共享有关器官形状的信息，从而共同了解某些变异是否与不同的诊断结果或治疗成功有关。在所有这些情况下，了解数据的全球结构可以提供有价值的科学、工程或医学见解，从而做出更好的商业决策，或导致更有效的医疗规划。

Over the past decade, the precipitous drop in the cost of disk storage and the build-up of world-wide high-bandwidth fiber optic communications has made massive amounts of data of different modalities (text, images,video) easily available to everyone over the Web. In science, engineering, business, and medicine, high-bandwidth sensors, large-scale simulations, and data collection bots generate immense data sets that need to be analyzed. Making sense of all this disparate data in becoming increasingly challenging and difficult. Unlike traditional databases where data is carefully massaged to adhere to rigid schemata, much of the above data comes unstructured, is often dynamic rather than static, can contain large amounts of noise or even errors, and can be incomplete. This project aims to develop general, rigorous and efficient techniques for analyzing massive and distributed sets of unstructured data. The basic aim is to exploit certain ideas from computational topology and geometry in the study of the global structure of large, distributed data sets -- and especially to develop data representations and transformations that makes this structure more apparent. Topology studies the connectivity of spaces, so it is global by its very nature. It is able to determine certain connectivity invariants in a way that is unaffected by deformations of an object and does not require explicit parameterizations of the object geometry. Its strength lies, in a sense, in its relative insensitivity to geometric properties, which permits it to discern underlying combinatorial information about how the geometric object is constructed, and therefore detect some qualitative properties. This type of global analysis can be quite important in understanding the overall structure of data sets. Geometry, though more local by nature, can also be used to study global structure by discovering how parts of an object relate to another, or how parts of different objects can be similar. For example, the Erlanger program of Felix Klein has fueled for over a century mathematicians' interest in invariance under certain group actions as a key principle for understanding geometric spaces. Such invariances or symmetries can also be key to understanding and reasoning about data sets.The methods proposed here can be applied in many different settings where massive unstructured data sets arise. In science or engineering, large-scale distributed simulations can produce immense data sets; as an example, consider the Folding@Home project at Stanford that generates protein folding trajectories using hundreds of thousands of CPUs throughout the world. In business, companies such as Google and Yahoo! have to mine billions of web clicks to develop algorithms for matching ads to web page content or to individual users. In medicine 3D imaging is becoming commonplace. Medical imaging diagnostic systems, distributed throughout medical offices nationwide, should be able to efficiently share information about shapes of organs and thereby collectively learn about whether certain variations are associated with different diagnostic outcomes or treatment successes. In all these cases, understanding the global structure of the data can provide valuable scientific, engineering, or medical insights, enabling better business decisions, or leading to more effective medical treatment planning.