Global Structure Discovery on Sampled Spaces

在过去的十年中，磁盘存储成本的急剧下降和全球高带宽光纤通信的建立使得每个人都可以通过Web轻松获得大量不同形式的数据（文本，图像，视频）。在科学、工程、商业和医学领域，高带宽传感器、大规模模拟和数据收集机器人会产生大量需要分析的数据集。理解所有这些不同的数据变得越来越具有挑战性和困难。与传统数据库不同，传统数据库中的数据被仔细处理以遵守严格的模式，上述大部分数据都是非结构化的，通常是动态的而不是静态的，可能包含大量的噪音甚至错误，并且可能是不完整的。该项目旨在开发通用的，严格的和有效的技术来分析大量和分布式的非结构化数据集。其基本目标是利用计算拓扑学和几何学中的某些思想来研究大型分布式数据集的全局结构，特别是开发数据表示和转换，使这种结构更加明显。拓扑学研究空间的连通性，因此它本质上是全局的。它能够以不受对象变形影响的方式确定某些连接不变量，并且不需要对象几何的显式参数化。从某种意义上说，它的优势在于它对几何属性的相对不敏感性，这使得它能够辨别关于几何对象如何构造的潜在组合信息，从而检测一些定性属性。这种类型的全局分析对于理解数据集的整体结构非常重要。几何学虽然本质上更具有局部性，但也可以通过发现一个对象的部分如何与另一个对象相关，或者不同对象的部分如何相似来研究全局结构。例如，菲利克斯·克莱因的埃尔朗格计划激发了世纪数学家对某些群作用下的不变性的兴趣，将其作为理解几何空间的关键原则。这种不变性或对称性也可以是理解和推理数据集的关键。这里提出的方法可以应用于大量非结构化数据集出现的许多不同的设置。在科学或工程领域，大规模的分布式模拟可以产生大量的数据集;例如，斯坦福大学的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.