Predicting the optimal ad-hoc index for reachability queries on graph databases

Due to the recent advances in graph databases, a large number of ad-hoc indexes for a fundamental query, in particular, reachability query, have been proposed. The performances of these indexes on different graphs have known to be very different. Worst still, deriving an accurate cost model for selecting the optimal index of a graph database appears to be a daunting task. In this paper, we propose a hierarchical prediction framework, based on neural networks and a set of graph features and a knowledge base on past predictions, to determine the optimal index for a graph database. For ease of presentation, we propose our framework with three structurally distinguishable indexes. Our experiments show that our framework is accurate.