Infrastructure to Support Analytics on Massive-Scale Dynamic Graphs

支持大规模动态图分析的基础设施

• 批准号: RGPIN-2019-06905
• 负责人: Ripeanu, Matei
• 金额: $ 4.01万
• 依托单位: University of British Columbia
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=752243
• 关键词: Infrastructure; Support; Analytics; Massive; Scale

A challenging problem emerging in several application domains is to accurately identify the main source of a particular information flow (e.g., a source of fake news, spam, or social-bot attack) that is coordinating a large-scale campaign, using temporal event data. What makes this challenging for today's analytics systems is that events are typically: (i) only observed at the level of the participating entities (e.g., network devices, email inboxes, social network accounts), and (ii) aggregated from numerous independent sources with no guarantees for the timeliness of receiving the events. This problem can be solved by modelling the system as a dynamic graph where: (i) the nodes (i.e., vertices) are the entities participating in the system; (ii) the links (i.e., edges) are the interactions between those entities; and (iii) both nodes and links can be dynamically added to the evolving graph as new events are observed. Given the dynamicity of the system, this model is not only a good conceptual fit but it also makes it possible to "jump through time" while maintaining an accurate view of the overall state of the system - a key enabler for audits and forensic investigations. Current systems are far from offering the scale, the reaction time, and the querying semantics required to support this scenario in the real world. To offer support for this scenario and for the many others that can be modelled as time-evolving graphs, our project aims to explore four intertwined research directions. Firstly, designing the abstractions, data-structures, and parallel algorithms able to effectively support processing large-scale dynamic graphs. Secondly, uncovering the optimizations enabled by domain-specific graph-structures as well as frequent data access patterns, and harnessing them transparently through specialized runtimes. Thirdly, exploring avenues to simplify the development of graph analytics through domain-specific languages. Finally, exploring the feasibility of harnessing two recent technological advances: storage-class memories (e.g., Intel's Optane DC) and software-defined networks, to both increase performance and reduce the energy footprint for graph analytics. While the set of potential domains that benefit from an efficient framework that supports analytics on dynamic graphs is huge, we plan to focus on two high-impact areas: social-networks and cyber-security. These domains offer challenging requirements in terms of problem scale, data diversity, data velocity, and time-to-solution, and, at the same time, witness the rapid development of an increasingly diverse set of complex analytics which justifies our focus on application-development friendliness. .

在几个应用领域中出现的一个具有挑战性的问题是，使用时间事件数据准确识别协调大规模活动的特定信息流（例如，假新闻、垃圾邮件或社交机器人攻击的来源）的主要来源。这对今天的分析系统来说是一个挑战，因为事件通常是：(i)只能在参与实体（例如，网络设备，电子邮件收件箱，社交网络帐户）的层面上观察到的，以及（ii）从许多独立的来源聚合而来，无法保证接收事件的及时性。这个问题可以通过将系统建模为动态图来解决，其中：(i)节点（即顶点）是参与系统的实体；（ii）链接（即边缘）是这些实体之间的相互作用；（iii）当观察到新的事件时，节点和链接都可以动态地添加到不断发展的图中。考虑到系统的动态性，该模型不仅在概念上很适合，而且还使“跨越时间”成为可能，同时保持对系统整体状态的准确视图——这是审计和取证调查的关键推动因素。当前的系统远远不能提供在现实世界中支持这种场景所需的规模、反应时间和查询语义。为了支持这个场景和其他许多可以建模为时间演变图的场景，我们的项目旨在探索四个相互交织的研究方向。首先，设计能够有效支持大规模动态图处理的抽象、数据结构和并行算法。其次，揭示特定于领域的图结构以及频繁的数据访问模式所支持的优化，并通过专门的运行时透明地利用它们。第三，探索通过特定领域语言简化图形分析开发的途径。最后，探讨利用两项最新技术进步的可行性：存储级内存（例如，英特尔的Optane DC）和软件定义网络，以提高性能并减少图形分析的能源足迹。虽然从支持动态图形分析的高效框架中受益的潜在领域非常多，但我们计划将重点放在两个影响较大的领域：社交网络和网络安全。这些领域在问题规模、数据多样性、数据速度和解决时间方面提出了具有挑战性的要求，同时，见证了越来越多样化的复杂分析的快速发展，这证明了我们对应用程序开发友好性的关注。