Amine Mhedhbi, PhD candidate
David R. Cheriton School of Computer Science
Adjacency lists are the most fundamental storage structures in existing graph database management systems (GDBMSs) to index input graphs. Adjacency lists are universally linked list-like per-vertex structures that provide access to a set of edges that are adjacent to a vertex. In several systems, adjacency lists can also allow efficient access to subsets of a vertex's adjacent edges that satisfy a fixed set of predicates, such as those with the same label, and support a fixed set of ordering criteria, such as by the IDs of destination vertices.
This talk describes a highly flexible indexing sub-system for GDBMSs, which consists of two components. The primary component, called A+ indexes, stores adjacency lists which provide flexibility in three aspects: (1) in addition to per-vertex lists, users can define per-edge adjacency lists; (2) the edges in lists can satisfy a wide range of predicates; and (3) the lists can support flexible sorting criteria. Existing indexes in GDBMSs index as elements the vertices or edges in input graphs. The second component of our indexing sub-system is secondary B+ tree and bitmap indexes that index aggregate properties of adjacency lists. Therefore, our secondary indexes index adjacency lists as elements. We have implemented our indexing sub-system on top of GraphflowDB.
200 University Avenue West
Waterloo, ON N2L 3G1