Top-k Keyword Search Algorithms with Redundancy Elimination on Large Graph Databases
Meirong Wang, Liru Zhang, Yinshi Jin, Tadashi Ohmori · 2011
In this paper, by modifying an existing graph-database search algorithm DPBF [1] in a straightforward strategy, we propose such an algorithm that can find exact top-k answers, with eliminating redundant answers, in an exact ranked order in O((2l+1mk + 3lnk ∙ logk)log(2lnk)) run time (l: the number of keywords; k: top-k; n: the number of nodes in the graph database; m: the number of edges in the graph database) with the space complexity of O(2l+1nk). Keyword Top-k,Keyword Search,Graph Database