Master’s Thesis Presentation • Data Systems — A+ Lists: Highly Flexible Adjacency Lists in Graph Databases

Shahid Khaliq, Master’s candidate
David R. Cheriton School of Computer Science

We describe a new indexing sub-system for GDBMSs that addresses the limitations of the adjacency lists indices present in current systems. Our indexing sub-system consists of two main components: (1) A+ lists; and (2) secondary B+ tree and bitmap indices that index aggregate properties of A+ lists. Our indices allow users to optimize a GDBMS to be efficient for a much wider range of queries than existing GDBMSs. We have implemented our indices on top of the Graphflow GDBMS.