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.