Yuqi Zhou’s paper “gTop: An efficient SPARQL Query Engine” was accepted by APWEB-WAIM 2022 and won the Best Demo Paper Award.

SPARQL Top-k query can be understood as process of subgraph matching and results sorting. If the query graph is acyclic, there exit algorithms of linear time and space relative to the size of the final result set. This paper proposes to divide Top-k queries into two categories, which are cyclic and acyclic. For acyclic query graph, gTop uses existing efficient algorithms. For the cyclic graph, based on the characteristics of RDF and SPARQL, this paper proposes a heuristic query graph splitting strategy, which first completes the acyclic query in the query graph, then completes the cut part, checks the correctness of the results, and completes the results of the entire query graph. The efficiency of the proposed framework is verified by experimental data.