Search Result Clustering via Randomized Partitioning of Query-Induced Subgraphs

Abstract

In this paper, we present an approach to search result clustering, using partitioning of underlying link graph. We define the notion of "query-induced subgraph" and formulate the problem of search result clustering as a problem of efficient partitioning of a given subgraph into topic-related clusters. Also, we propose a novel algorithm for approximative partitioning of such a graph, which results in a cluster quality comparable to the one obtained by deterministic algorithms, while operating in a more efficient computation time, suitable for practical implementations. Finally, we present a practical clustering search engine developed as a part of this research and use it to get results about real-world performance of proposed concepts.

Keywords

• Information Search and Retrieval
• Graph Clustering
• Randomized Algorithms
• Web Measurement