TL;DR
This paper introduces a novel approach to evaluating navigational queries (property paths) over the decentralized Web of Linked Data by framing the problem as an AI search task. By adapting the classical A* algorithm with a query-aware heuristic, the authors provide a method that minimizes expensive network requests and guarantees finding the shortest paths—a feature currently missing from standard SPARQL engines.
What Problem Does This Paper Address?
The Semantic Web relies on the Resource Description Framework (RDF), which represents data as a massive, distributed graph. While we have powerful tools to query local RDF databases, querying the "Web of Linked Data" is much harder. In this setting, the graph isn't stored in one place; instead, it is discovered on-the-fly by "dereferencing" IRIs (essentially clicking links via HTTP requests) to find neighboring nodes.
Standard navigational queries, known as property paths in SPARQL, allow users to find nodes connected by complex patterns (e.g., "find all co-authors of co-authors of X"). Evaluating these over the live Web is challenging because:
- Network Latency: Every new node discovery requires an HTTP request, which is orders of magnitude slower than memory access.
- Open World: We don't know the full graph structure in advance.
- Efficiency: Traditional search methods like Breadth-First Search (BFS) or Depth-First Search (DFS) either waste time on shallow, irrelevant nodes or get lost in deep, long paths before finding a single answer.
Methods
The authors propose using the A* search algorithm to navigate this unknown graph. The core idea is to treat query evaluation as a path-finding problem on a "product graph" formed by the Web data and a Non-deterministic Finite Automaton (NFA) representing the query.
Key technical components include:
- Automata-based Heuristic: The authors define an admissible heuristic $h(s)$ based on the query's NFA. It estimates the remaining distance to a "goal" state by looking at the minimum number of transitions needed in the NFA to reach an accepting state.
- Parallel Expansions: To combat network latency, the algorithm is modified to fetch multiple IRIs in parallel (k-A*), significantly speeding up discovery.
- Hybrid Infrastructure: The system combines standard IRI dereferencing with public SPARQL endpoints to overcome common data gaps, such as missing "backwards" links.
- Pathmax Heuristic: A specialized tweak to the heuristic function that prevents the algorithm from prematurely expanding goal nodes, further reducing unnecessary network traffic.
Datasets
The researchers evaluated their approach using 11 real-world navigational queries across several prominent Linked Data domains:
- DBLP: Computer science bibliography data.
- YAGO: A large-scale knowledge base derived from Wikipedia.
- DBPedia: The structured version of Wikipedia.
- Linked Movie Database (LMDB): A semantic dataset for movie information.
These queries ranged from simple fixed-depth paths to complex patterns involving multiple Kleene star (*) operations, such as calculating "Bacon numbers" across multiple datasets.
Key Insights and Ideas
- Query Evaluation is Search: The fundamental "aha moment" is realizing that navigating the Web of Linked Data is exactly the kind of problem A* was designed for: finding a path in an implicitly defined graph where edge expansion is costly.
- Minimizing Requests is Everything: In Web querying, the number of HTTP requests is the primary bottleneck. A* is optimal here because its heuristic allows it to ignore parts of the graph that cannot possibly lead to a shorter solution.
- Shortest Paths Matter: Unlike DFS, which might return a very long, convoluted path as its first answer, A* (and BFS) guarantees finding the shortest path first. This provides better "quality" answers for users.
- Parallelism is a Great Equalizer: While A is superior in sequential execution, as the degree of parallelism increases, the performance gap between A, BFS, and DFS narrows, though A* remains the most consistent.
Key Results
The experimental results demonstrate that A* consistently outperforms or matches BFS and DFS across different query types.
- Efficiency: In queries like
q_Bacon, A* strictly beats both BFS and DFS by using the heuristic to prune irrelevant links. - Throughput: For queries requiring deep navigation (like
q_Coauthor), BFS often requires hundreds of requests before finding its first answer, whereas A* starts producing results almost immediately. - Speedup: Implementing parallel requests (20-40 threads) resulted in a nearly tenfold decrease in execution time across all algorithms.
Limitations and Future Work
The authors highlight a few ongoing challenges:
- Data Completeness: The "Linked Data Principles" are not always followed perfectly; many servers don't provide all triples for an IRI, especially inverse links.
- Infrastructure: Relying on full SPARQL endpoints can be unreliable due to erratic uptime. The authors suggest exploring Triple Pattern Fragments as a more lightweight and robust alternative.
- Language Extension: Future work includes applying these A* techniques to more expressive navigational languages like NautiLOD and LDQL, which offer finer control over how the Web is traversed.
Summary updated