Abstract | ||
---|---|---|
The existing literatures of the query processing on knowledge graphs focus on an exhaustive enumeration of all matches, which is time-consuming. Users are often interested in diversified top-k matches, rather than the entire match set. Motivated by these, this paper formalizes the diversified top-k querying (DTQ) problem in the context of RDF/SPARQL and proposes a diversification function to balance importance and diversity. We first prove that the decision problem of DTQ is NP-complete, and give a baseline algorithm with an approximation ratio of 2. Secondly, an index-based algorithm with the early termination property is proposed. The index is adept in parallel diversified top-k selection in multicore architectures. Using real-world and synthetic data, we experimentally verify that our algorithms are efficient and effective in computing meaningful diversified top-k matches. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1007/978-3-030-60259-8_24 | Interational Conference on Web-Age Information Management |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Xintong Guo | 1 | 0 | 0.34 |
Hong Gao | 2 | 1086 | 120.07 |
Yinan An | 3 | 0 | 0.34 |
Zhaonian Zou | 4 | 331 | 15.78 |