  We propose a visual query language for interactively exploring large-scale
knowledge graphs. Starting from an overview, the user explores bar charts
through three interactions: class expansion, property expansion, and
subject/object expansion. A major challenge faced is performance: a
state-of-the-art SPARQL engine may require tens of minutes to compute the
multiway join, grouping and counting required to render a bar chart. A
promising alternative is to apply approximation through online aggregation,
trading precision for performance. However, state-of-the-art online aggregation
algorithms such as Wander Join have two limitations for our exploration
scenario: (1) a high number of rejected paths slows the convergence of the
count estimations, and (2) no unbiased estimator exists for counts under the
distinct operator. We thus devise a specialized algorithm for online
aggregation that augments Wander Join with exact partial computations to reduce
the number of rejected paths encountered, as well as a novel estimator that we
prove to be unbiased in the case of the distinct operator. In an experimental
study with random interactions exploring two large-scale knowledge graphs, our
algorithm shows a clear reduction in error with respect to computation time
versus Wander Join.
