论文标题
A+索引：图形数据库管理系统中的可调和空间效率的邻接列表
A+ Indexes: Tunable and Space-Efficient Adjacency Lists in Graph Database Management Systems
论文作者
论文摘要
图形数据库管理系统（GDBMS）通过在邻接列表中索引顶点的邻居来进行高度优化以执行快速遍历，即与邻居连接。但是，现有的GDBMS具有特定系统和固定的邻接列表结构，这使每个系统仅在一组固定的工作负载上有效。我们描述了一个针对GDBMS的新的可调索引子系统，我们称为+索引，并具有实质性的视图支持。子系统由两种类型的索引组成：（i）在源或目标顶点IDS上分区1-跳的索引中的顶点分区的索引中，将1-跳的视图物质化到邻接列表中； （ii）边缘分区的索引将2-跳单视图列入一个边缘ID上的邻接列表。与现有的GDBMS一样，默认情况下，系统需要一个向前和一个向后的顶点分区索引，我们将其称为主要A+索引。用户可以通过添加嵌套分区和排序标准来调整主要索引或辅助索引。我们的次要索引是空间效率的，并使用我们称为偏移列表的技术。我们的索引子系统允许更广泛的应用程序受益于GDBMSS的快速联接功能。我们通过在三个工作负载上进行大量实验来证明A+索引的可调性和空间效率。
Graph database management systems (GDBMSs) are highly optimized to perform fast traversals, i.e., joins of vertices with their neighbours, by indexing the neighbourhoods of vertices in adjacency lists. However, existing GDBMSs have system-specific and fixed adjacency list structures, which makes each system efficient on only a fixed set of workloads. We describe a new tunable indexing subsystem for GDBMSs, we call A+ indexes, with materialized view support. The subsystem consists of two types of indexes: (i) vertex-partitioned indexes that partition 1-hop materialized views into adjacency lists on either the source or destination vertex IDs; and (ii) edge-partitioned indexes that partition 2-hop views into adjacency lists on one of the edge IDs. As in existing GDBMSs, a system by default requires one forward and one backward vertex-partitioned index, which we call the primary A+ index. Users can tune the primary index or secondary indexes by adding nested partitioning and sorting criteria. Our secondary indexes are space-efficient and use a technique we call offset lists. Our indexing subsystem allows a wider range of applications to benefit from GDBMSs' fast join capabilities. We demonstrate the tunability and space efficiency of A+ indexes through extensive experiments on three workloads.
