PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Dohnal V., Gennaro C., Savino P., Zezula P. Access Structures for Advanced Similarity Search in Metric Spaces. In: Symposium on Advanced Database Systems (Cetraro (CS), Italy, June 24-27). Atti, pp. 483 - 494. Sergio Flesca, Sergio Greco, Domenico Sacc, Ester Zumpano (eds.). Rubettino, 2003.
 
 
Abstract
(English)
Similarity retrieval is an important paradigm for searching in environments where exact match has little meaning. Moreover, in order to enlarge the set of data types for which the similarity search can efficiently be performed, the notion of mathematical metric space provides a useful abstraction for similarity. In this paper we consider the problem of organizing and searching large data-sets from arbitrary metric spaces, and a novel access structure for similarity search in metric data, called D-Index, is discussed. D-Index combines a novel clustering technique and the pivot-based distance searching strategy to speed up execution of similarity range and nearest neighbor queries for large files with objects stored in disk memories. Moreover, we propose an extension of this access structure (eD-Index) which is able to deal with the problem of similarity self join. Though this approach is not able to eliminate the intrinsic quadratic complexity of similarity joins, significant performance improvements are confirmed by experiments.
Subject Metric space, Access structure, Similarity Search, Similarity Join,Edit distance
H.3.4 Systems and Software. Performance evaluation (efficiency andeffectiveness)


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional