2017/05/27 by Madhulika Mohanty, Mohanty, Madhulika, Maya Ramanath +1
Computer Science · Physics and Astronomy · #Advanced Database Systems and Queries #Complex Network Analysis Techniques #Data Management and Algorithms #FOS: Computer and information sciences #Information Retrieval (cs.IR) #cs.IR
paper · pdf · doi:10.48550/arxiv.1705.09808
16 pages, 2 Figures
arxiv created 2017/05/27 · openalex publication_date 2017/05/27 · arxiv updated 2017/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 and has led to research in a variety of directions -- structured queries, keyword and natural language queries, automatic translation of these queries to structured queries, etc. 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 could consist of hundreds of answers. The problem of keyword search on graphs has been explored for over a decade now, but an important aspect that is not as extensively studied is that of user experience. We propose KlusTree, which presents clustered results to the users instead of a list of all the 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.