TEDI: Efficient Shortest Path Query Answering on Graphs

A top-k keyword search query on an RDF graph finds the top-k answers according to some ranking criteria, where each answer is a substructure of the graph containing all query keywords. The keyword query scheme is attractive, because this simple, user-friendly query interface does not require users to master a complex query language or understand the underlying data schema.

Usually, the relationship between the keywords is reflected by the distances between the corresponding nodes in the graph. T If more than one path exists, it is desirable to retrieve the shortest distance between them, in the sense that shorter distance normally means higher rank of the connected elements. We propose a top-k keyword search method based on TEDI (TreE Decomposition based Indexing), an indexing and query processing scheme for shortest path computation.

TEDI: efficient shortest path query answering on graphs, Fang Wei, SIGMOD 2010.
Paper   Slide

Source code and datasets:
Source code in C++   Datasets