View publication

Title Exploration of Knowledge Graphs via Online Aggregation
Authors Oren Kalinsky, Aidan Hogan, Oren Mishali, Yoav Etsion, Benny Kimelfeld
Publication date 2022
Abstract Exploration systems over large-scale RDF knowledge graphs
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, stateof-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.
Pages 2695-2708
Conference name IEEE International Conference on Data Engineering
Publisher IEEE Press (Piscataway, NJ, USA)
Reference URL View reference page