Exploration of Knowledge Graphs via Online Aggregation

Exploration systems over large-scale RDF knowl-edge graphs often rely on aggregate count queries to indicate how many results the user can expect for the possible next steps of exploration. Such systems thus encounter a challenging computational problem: evaluating aggregate count queries efficiently enough to allow for interactive exploration. Given that precise results are not always necessary, a promising alternative is to apply online aggregation, where initially imprecise results converge towards more precise results over time. However, state-of-the-art online aggregation algorithms, such as Wander Join, fail to provide accurate results due to frequent rejected paths that slow convergence. We thus devise an algorithm for online aggregation that specializes in exploration queries on knowledge graphs; our proposal leverages the low dimension of RDF graphs, and the low selectivity of exploration queries, by augmenting random walks with exact partial computations using a worst-case optimal join algorithm. This approach reduces the number of rejected paths encountered while retaining a fast sample time. In an experimental study with random interactions exploring two large-scale knowledge graphs, our algorithm shows a clear reduction in error over time versus Wander Join.