Wind-Bell Index: Towards Ultra-Fast Edge Query for Graph Databases

Graphs are good at presenting relational and structural information, making it powerful in the representation of various data. For the efficient storage and processing of graph-like data, graph databases have been rapidly developed and extensively studied. However, graph databases mostly use adjacency lists as their basic data structure (e.g., Neo4j), which could result in poor performance of edge due to the skewed degree distribution of graphs.

We design the Wind-Bell Index to address this problem. Wind-Bell Index is a memory-efficient index data structure, which can be attached to existing graph databases to speed up the edge. We have fully implemented our data structure in Neo4j, the most popular graph database today, and conduct theoretical and experimental analysis to evaluate the performance. Theoretical results prove the high query efficiency of our algorithm. And experimental results show that the average edge query speed is increased by hundreds of times compared with the original query interface of Neo4j. We believe that the excellent performance and scalability of Wind-Bell Index make it suitable for the application in a variety of graph databases.