Ranking the answer trees of graph search by both structure and content
Ming Zhong, Mengchi Liu · 2012
Keyword search on graphs aims to find minimum connected trees containing the keywords. Normally, the answer trees are ranked by their topological structures. However, this basic ranking scheme does not distinguish answer trees well when many answer trees have the same structures or contain redundant information. This paper proposes a novel ranking scheme, which combines both structure-based and content-based ranking factors. It can effectively prioritize the answer trees with more valuable content and punish the ones with redundant information. Meanwhile, it will not reduce the efficiency of top-k search algorithms by performing an edge re-weighting process offline.