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等社交网络到大脑网络、基因调控网络和健康/疾病网络。分析此类大型数据集的传统方法是使用强大的超级计算机（集群）、这种方法的缺点是，许多大数据的潜在用户缺乏这种强大的计算资源（例如，销售点比特币区块链分析），并且在如此大的基础设施内解决意外问题可能很困难（例如波士顿马拉松爆炸事件后的图像分析）。在该项目中开发的算法将使得能够在具有有限数量的快速存储器的计算设备上处理巨大的数据集，本项目将研究在一台计算机上甚至是智能手机等移动终端上进行复杂网络分析的程度。为此，该项目将开发用于分析和理解大网络数据的外部内存、缓存无关和流算法，即使在相对较弱的计算设备上也是如此。这些算法将使大数据分析能够被更广泛的受众访问，从而实现新的应用。该方法独特地结合了先进的算法技术，包括近似算法，参数化算法，图算法，图结构理论和计算几何，以解决大型网络上的现实问题。