XM-Tree, a new index for web information retrieval

Abstract

Web Information Retrieval is another problem of searching elements of a set that are closest to a given query under a certain similarity criterion. It is of interest to take advantage of metric spaces in order to solve a search in an effective and efficient way. In this article, we present an extension of the M-Tree index, called XM-Tree, in order to improve search results. This index allows dynamic insertion of new data, reduces search costs using pruning and precalculated distances, and uses a tolerable amount of space, which makes this index apt for the extensive and dynamic Web. The proposed extension indexes Web documents, uses L2 as indexing distance and L∞ as similarity criterion to solve queries. We also present experiments validating the results.

Keywords

• metric spaces
• similarity searching
• m-tree
• xm-tree