BIGDATA: Collaborative Research: F: Making Big Data Accessible on Personal Devices: Big Network Algorithms, External Memory, and Data Streams

大型网络的规模和相关性都在不断增长：从Facebook和Twitter等社交网络到大脑网络、基因调控网络和健康/疾病网络。 分析如此大的数据集的传统方法是使用强大的超级计算机（集群），理想情况下足够大以将数据存储在主内存中。 这种方法的缺点是，许多大数据的潜在用户缺乏如此强大的计算资源（例如销售点比特币区块链分析），并且在如此庞大的基础设施中很难解决意外问题（例如波士顿马拉松爆炸事件后的图像分析）。 该项目开发的算法将使在连接到相对较慢的外部数据源的有限快速内存的计算设备上处理庞大的数据集成为可能。该项目将研究在单台计算机上甚至在智能手机等移动终端上进行复杂网络分析的程度。为此，该项目将开发外部内存，缓存无关和流式算法，用于分析和理解大网络数据，即使在相对较弱的计算设备上。 这些算法将使更广泛的受众可以访问大数据分析，从而实现新的应用程序。该方法独特地结合了先进的算法技术，包括近似算法，参数化算法，图算法，图结构理论和计算几何，以解决大型网络上的现实问题。

Big networks are constantly growing in both size and relevance: from social networks such as Facebook and Twitter, to brain networks, gene regulatory networks, and health/disease networks.  The traditional approach to analyzing such big datasets is to use powerful supercomputers (clusters), ideally large enough to store the data in main memory.  The downsides to this approach are that many potential users of big data lack such powerful computational resources (e.g. point-of-sale Bitcoin blockchain analysis), and it can be difficult to solve unexpected problems within such a large infrastructure (e.g. image analysis after the Boston Marathon Bombing).  The algorithms developed in this project will enable the processing of huge datasets on computational devices with a limited amount of fast memory, connected to a relatively slow external data source.This project will investigate the extent to which complex network analysis can be performed on a single computer, even a mobile device such as a smartphone. To this end, the project will develop external-memory, cache-oblivious, and streaming algorithms for analyzing and understanding big network data, even on relatively weak computational devices.  These algorithms will make big data analysis accessible to a much broader audience, enabling new applications. The approach uniquely combines advanced algorithmic techniques, including approximation algorithms, parameterized algorithms, graph algorithms, graph structure theory, and computational geometry, to solve real-world problems on big networks.