IIT Home Page CNR Home Page

Cluster Generation and Cluster Labelling for Web Snippets:A Fast and Accurate Hierarchical Solution

This paper describes Armil, a meta-search engine that groups into disjoint labelled clusters the Web snippets returned by auxiliary search engines. The cluster labels generated by Armil provide the user with a compact guide to assessing the relevance of each cluster to her information need. Strik- ing the right balance between running time and cluster well- formedness was a key point in the design of our system. Both the clustering and the labelling tasks are performed on the °y by processing only the snippets provided by the auxil- iary search engines, and use no external sources of knowl- edge. Clustering is performed by means of a fast version of the furthest-point-¯rst algorithm for metric k-center cluster- ing. Cluster labelling is achieved by combining intra-cluster and inter-cluster term extraction based on a variant of the information gain measure. We have tested the clustering ef- fectiveness of Armil against Vivisimo, the de facto industrial standard in Web snippet clustering, using as benchmark a comprehensive set of snippets obtained from the Open Di- rectory Project hierarchy. According to two widely accepted \external' metrics of clustering quality, Armil achieves bet- ter performance levels by 10%. We also report the results of a thorough user evaluation of both the clustering and the cluster labelling algorithms. On a standard 1GHz ma- chine, Armil performs clustering and labelling altogether in less than one second.

Internet Mathematics, 2007

Authors: F.Geraci, M.Pellegrini, F.Sebastiani, M. Maggini
IIT authors:

Type: Article in non-ISI Journal with international referees
Field of reference: Information Technology and Communication Systems
Accettato per la pubblicazione Da pagina 413 a pagina 444

Activity: Algoritmica per tecnologie web