Klustree
Madhulika Mohanty, Maya Ramanath · 2018
Graph structured data on the web is now massive as well as diverse, ranging from social networks, web graphs to knowledge-bases. Effectively querying this graph structured data is non-trivial. We are concerned with a class of queries called relationship queries, which are usually expressed as a set of keywords (each keyword denoting a named entity). The results returned are a set of ranked trees, each of which denotes relationships among the various keywords. The result list typically consists of hundreds to thousands of answers. A drawback of showing the entire list to the user is that it hinders result analysis and leads to a bad user experience. We propose KlusTree, which presents clustered results to the users instead of a list of all the results and thus, improves result interpretation and increases diversity in the top results. In our approach, the result trees are represented using language models and are clustered using JS divergence as a distance measure. We compare KlusTree with the well-known approaches based on isomorphism and tree-edit distance based clustering. The user evaluations show that KlusTree outperforms the other two in providing better clustering, thereby enriching user experience, revealing interesting patterns and improving result interpretation by the user.