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

BIGDATA：协作研究：F：使大数据可在个人设备上访问：大网络算法、外部存储器和数据流

• 批准号: 1546108
• 负责人: Mohammad Hajiaghayi
• 金额: $ 50万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-12-01 至 2021-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1546108&HistoricalAwards=false
• 关键词: BIGDATA; Collaborative; Research; Making; Big

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.

大型网络的规模和相关性都在不断增长：从Facebook和Twitter等社交网络到大脑网络，基因调节网络以及健康/疾病网络。分析此类大数据集的传统方法是使用强大的超级计算机（群集），理想的很大足以将数据存储在主内存中。这种方法的不利因素是，许多大数据的潜在用户缺乏如此强大的计算资源（例如，销售点的比特币区块链分析），并且在这样大型基础架构中可能很难解决意外问题（例如，波士顿马拉松轰炸后的图像分析）。该项目中开发的算法将使可以在具有有限快速内存的计算设备上处理大量数据集，连接到相对较慢的外部数据源。该项目将调查可以在单个计算机上（甚至是智能手机）上的单个计算机上执行复杂的网络分析的程度。为此，该项目将开发外部记忆，可缓存和流媒体算法，以分析和理解大型网络数据，即使是在相对较弱的计算设备上也是如此。这些算法将使更广泛的受众访问大数据分析，从而实现新的应用程序。该方法独特地结合了高级算法，包括近似算法，参数化算法，图形算法，图形结构理论和计算几何形状，以解决大网络上的现实世界问题。