SHF: Small: MIGS -- Efficiently Evaluating Multiple Iterative Graph Queries

由于图可以很容易地表示实体和实体之间的关系，因此它们被广泛用于表示从社会网络到生物和大脑网络等领域的大量数据。挖掘大图以从数据中发展洞察力通常采取评估迭代图分析查询的形式，所述迭代图分析查询起源于图中的不同点，并且计算潜在地依赖于整个图的结构的全局属性值。这些算法都是计算和数据密集型的；由于真实世界图的大尺寸和高度不规则的结构，优化它们是一个挑战。虽然已经开发了许多用于评估迭代图查询的系统，但它们的重点是最小化单个查询的执行时间，尽管在实践中需要评估许多查询。这项研究的目标是通过协同评估一组查询来显著提高它们的评估时间，以利用这样的观察：评估单个查询涉及大量相互重叠的图遍历和计算。这项研究有助于发现识别和利用这种重叠的新技术，以减少与单机和多机平台上的并行执行相关的冗余成本和开销。建造如此强大的系统加速了在使用图形分析的领域的新发现。此外，在国家需求领域对学生进行培训也会产生更广泛的影响。具体地说，这项研究开发了系统级优化和算法创新，共同努力极大地提高了同时评估多个迭代查询的可扩展性。为了确保所产生的技术的多功能性，新的优化和算法正在共享内存多核机器以及多机器的分布式集群的背景下实现。多功能性还通过支持不同类型的查询(点对点和点对所有)和不同形式的图形(固定图形和流或动态图形)来实现。每种查询类型和图类型都对开发既正确又实现高性能的算法提出了独特的挑战。为了利用在评估不同查询期间执行的工作的重叠，正在开发基于重用的算法，同时为了响应图中的变化来更新查询结果，正在设计增量算法。这些方法旨在实现共享内存计算机上的高性能和高系统利用率。为了进一步将性能扩展到大批量查询，正在开发分布式算法来利用分布式集群中多台机器的资源。这些评估利用了来自Konnect和SNAP等公共存储库的大型图表数据集。开发的软件在本项目过程中可供其他研究人员使用。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Since graphs can readily represent entities and relationships among them, they are widely used to represent large volumes of data from domains ranging from social networks to biological and brain networks. Mining of large graphs for developing insights from data often takes the form of evaluating iterative graph analytics queries that originate at different points in the graph and compute global property values that are potentially dependent upon the structure of the entire graph. Such algorithms are both compute- and data-intensive; optimizing them is a challenge due to the large size and highly irregular structure of real-world graphs. While many systems for evaluating iterative graph queries have been developed, their focus is on minimizing the execution time of a single query though in practice many queries need to be evaluated. The goal of this research is to dramatically improve evaluation times of a group of queries by synergistically evaluating them to exploit the observation that evaluating individual queries involves graph traversals and computations that greatly overlap with each other. This research helps discover novel techniques for identifying and exploiting such overlap to reduce redundant costs and overheads associated with parallel executions on single-machine and multiple-machine platforms. Building such powerful systems accelerates new discoveries in fields that employ graph analytics. In addition, broader impact also results from training students in an area of national need.Specifically, this research develops both system level optimizations and algorithmic innovations that work together to greatly increase the scalability of simultaneously evaluating multiple iterative queries. To guarantee versatility of techniques produced, the new optimizations and algorithms are being realized both in the context of a shared-memory multicore machine as well as a distributed cluster of multiple machines. Versatility is also achieved by supporting different kinds of queries (point-to-point and point-to-all) and different forms of graphs (fixed graphs and streaming or dynamic graphs). Each query type and graph type pose unique challenges to developing algorithms that are both correct and achieve high-performance. To exploit the overlap of work performed during evaluation of different queries, reuse-based algorithms are being developed while to update the results of queries in response to changes in the graph, incremental algorithms are being devised. These approaches are aimed at enabling high-performance and high system utilization on a shared-memory machine. To further scale performance to large batches of queries, distributed algorithms are being developed to utilize the resources from multiple machines in a distributed cluster. The evaluations utilize large graph data sets from public repositories such as KONNECT and SNAP. The software developed is made available to other researchers over the course of this project.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.