Abstract
The "Web of Linked Data" presents a massive, distributed graph of information that is challenging to query in real-time. Traditional approaches rely on dereferencing IRIs via HTTP requests, which are significantly slower than local memory access. This paper treats navigational query evaluation as a search problem on an unknown graph and proposes an adaptation of the A algorithm. By utilizing a heuristic derived from the query's Non-deterministic Finite Automaton (NFA), the proposed method minimizes expensive network calls. Experimental evaluations across diverse datasets demonstrate that A consistently outperforms Breadth-First Search (BFS) and Depth-First Search (DFS) in efficiency and result quality.
Introduction
The Resource Description Framework (RDF) has enabled the creation of a global "Web of Linked Data," comprising billions of triples spread across a multitude of independent servers. While structured query languages like SPARQL are effective for local or federated databases, querying the entire live Web remains a significant challenge. The primary bottleneck is network latency; each step in a navigational path may require a new HTTP request to "dereference" an IRI.
The core problem addressed in this research is finding answers to complex navigational queries (e.g., "find all co-authors of co-authors") while making the absolute minimum number of network requests. The authors propose that this is best framed as an AI search problem on a graph where the structure is initially unknown.
Methodology: A* for the Web
The researchers adapt the classic A* search algorithm to the context of the live Web. In this model:
- Cost ($g$): Each hop in the graph (one dereferencing step) is assigned a cost of 1.
- Expansion: Expanding a node corresponds to performing an actual HTTP request to fetch an RDF document.
- Goal: Reaching a state that satisfies the navigational query.
The NFA-Based Heuristic
To guide the A* search effectively, a heuristic function ($h$) is required to estimate the distance to the goal. The authors observe that any regular path query can be represented as a Non-deterministic Finite Automaton (NFA).
The heuristic $h(s)$ is defined as the shortest path from the current state in the query's NFA to an accepting state. This provides a "map" that allows the algorithm to prioritize links that are more likely to lead to an answer. Because this heuristic is "admissible" (it never overestimates the distance), the A* algorithm is guaranteed to find the shortest paths to answers using the minimum number of node expansions.
Parallelism and Hybrid Infrastructure
To mitigate the impact of network latency, the authors introduced $k$-A*, which expands the top $k$ nodes in the priority queue simultaneously. Furthermore, the system supplements standard dereferencing by querying public SPARQL endpoints when available. This hybrid approach helps overcome the "missing inverse link" problem, where a resource might link to another, but the reverse link is not explicitly stated in the RDF data.
Experimental Evaluation
The approach was tested using 11 real-world navigational queries across major Linked Data domains, including DBLP (bibliography), YAGO (knowledge base), DBPedia (Wikipedia), and LinkedMDB (movies). Specific queries included finding co-authorship chains ($q\_Coauthor$), NATO-related locations ($q\_NATO$), and actor connections ($q\_Bacon$).
The results demonstrate the "dominance" of the A approach. As shown in the figures above, A consistently returns more answers with fewer network requests compared to BFS. While DFS can sometimes find answers quickly, it often explores deep, irrelevant paths, leading to lower-quality (longer) results and higher total request counts.
Key Insights and Results
- Optimality: A* is mathematically optimal in this setting, expanding the absolute minimum number of nodes required to find answers.
- Latency Management: Through parallelization ($k$-A*), the researchers achieved up to a tenfold speedup in wall-clock time, effectively hiding network latency.
- Robustness: The live A* search proved more robust than static SPARQL engines, which often timed out on the same complex queries when run against local snapshots of the datasets.
Conclusion and Future Work
By treating Web-scale RDF querying as a search problem, this research provides a highly efficient framework for navigating the Web of Linked Data. The NFA-based heuristic allows A* to navigate the unknown graph with surgical precision. Future work aims to extend this methodology to more expressive traversal languages and to integrate more lightweight protocols like Triple Pattern Fragments to further enhance reliability and reduce server load.
Summary updated