Royi Rassin, Yaron Fairstein, Oren Kalinsky, Guy Kushilevitz, Nachshon Cohen, Alexander Libov, Yoav Goldberg. Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. 2024.

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.

Graph pattern matching (e.g., finding all cycles and cliques) has become an important component in domains such as social networks, biology and cyber-security. In recent years, the database community has shown that graph pattern matching problems can be mapped to an efficient new class of relational join algorithms.

In this big data era, data structures indexed by strings are the backbone of many systems - key-value stores, computing systems and relational database indexes. Traversing such data structures requires multiple string comparisons. This poster introduces keydomet, a string wrapper that optimizes key comparisons by storing string prefixes as integers and extending the comparison procedure accordingly.

Harnessing the potential of the Semantic Web for building knowledgeable machines entails the ability to understand RDF graphs and integrate them with applications. Analyzing the vast information using common tools requires skill and time. Towards that we develop ELinda - an explorer for linked data. ELinda enables the understanding of the rich content stored in an RDF graph, via a visual query language for interactive exploration. The focus is on rich and open-domain datasets where it is especially challenging to detect the precise value to the application at hand. In essence, the model is based on the concept of a bar chart that depicts the distribution of a focus set of nodes (URIs), and each bar can be expanded to a new bar chart for further exploration. Three types of expansions are supported: subclass, property, and object. Under the hood, our visual query language is compiled into SPARQL. Yet, these queries require prohibitively long execution times on a standard SPARQL engine. To address this challenge, we develop a specialized query engine that is based on the concept of a worst-case-optimal join algorithm. The novel query engine provides a speedup of 1-2 orders of magnitude compared to standard SPARQL engines, and thereby facilitates the practical implementation of ELinda.