Riso-tree: An efficient and scalable index for spatial entities in graph database management systems

With the ubiquity of spatial data, vertexes or edges in graphs can possess spatial location attributes side by side with other non-spatial attributes. For instance, as of June 2018, the Wikidata knowledge graph contains 48,547,142 data items (i.e., vertexes) and 13% of them have spatial location attributes. The article proposes Riso-Tree, a generic efficient and scalable indexing framework for spatial entities in graph database management systems. Riso-Tree enables the fast execution of graph queries that involve different types of spatial predicates (GraSp queries). The proposed framework augments the classic R-Tree structure with pre-materialized sub-graph entries. The pruning power of R-Tree is enhanced with the sub-graph information. Riso-Tree partitions the graph into sub-graphs based on their connectivity to the spatial sub-regions. The proposed index allows for the fast execution of GraSp queries by efficiently pruning the traversed vertexes/edges based upon the materialized sub-graph information. The experiments show that the proposed Riso-Tree achieves up to two orders of magnitude faster execution time than its counterparts when executing GraSp queries on real graphs (e.g., Wikidata). The strategy of limiting the size of each sub-graph entry (PNmax) is proposed to reduce the storage overhead of Riso-Tree. The strategy can save up to around 70% storage without harming the query performance according to the experiments. Another strategy is proposed to ensure the performance of the index maintenance (Irrelevant Vertexes Skipping). The experiments show that the strategy can improve performance, especially for slow updates. It proves that Riso-Tree is useful for applications that need to support frequent updates.