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）和软件定义网络，以提高性能并减少图形分析的能源足迹。虽然从支持动态图分析的高效框架中受益的潜在领域是巨大的，但我们计划专注于两个高影响力的领域：社交网络和网络安全。这些领域在问题规模、数据多样性、数据速度和解决时间方面提出了具有挑战性的要求，同时，见证了日益多样化的复杂分析的快速发展，这证明了我们对应用程序开发友好性的关注。.