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