Recently, multidimensional point indexing has generated a great deal of interest in applications where objects are usually represented through feature vectors belonging to high-dimensional spaces and are searched by similarity according to a given example. Unfortunately, although traditional data structures and access methods work well for low-dimensional spaces, they perform poorly as dimensionality increases. The application of a dimensionality reduction approach, such as the Karhunen-Loève transform, is often not very effective to deal with the indexing problem, since the substantial loss of information does not allow patterns to be sufficiently discriminated in the reduced space. In this work we present a novel hierarchical data structure based on the Multispace KL transform, a generalization of the KL transform, specifically designed to cope with locally correlated data. In the MKL-tree, dimensionality reduction is performed at each node, allowing more selective features to be extracted and thus increasing the dis criminant power of the index. In this work the mathematical foundations and the algorithms on which the MKL-tree is based are presented and preliminary experimental results are reported.

Cappelli R., Lumini A., Maio D. (2002). MKL-tree: A hierarchical data structure for indexing multidimensional data. Berlin : Springer Verlag [10.1007/3-540-46146-9_90].

MKL-tree: A hierarchical data structure for indexing multidimensional data

Cappelli R.;Lumini A.;Maio D.
2002

Abstract

Recently, multidimensional point indexing has generated a great deal of interest in applications where objects are usually represented through feature vectors belonging to high-dimensional spaces and are searched by similarity according to a given example. Unfortunately, although traditional data structures and access methods work well for low-dimensional spaces, they perform poorly as dimensionality increases. The application of a dimensionality reduction approach, such as the Karhunen-Loève transform, is often not very effective to deal with the indexing problem, since the substantial loss of information does not allow patterns to be sufficiently discriminated in the reduced space. In this work we present a novel hierarchical data structure based on the Multispace KL transform, a generalization of the KL transform, specifically designed to cope with locally correlated data. In the MKL-tree, dimensionality reduction is performed at each node, allowing more selective features to be extracted and thus increasing the dis criminant power of the index. In this work the mathematical foundations and the algorithms on which the MKL-tree is based are presented and preliminary experimental results are reported.
2002
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
914
924
Cappelli R., Lumini A., Maio D. (2002). MKL-tree: A hierarchical data structure for indexing multidimensional data. Berlin : Springer Verlag [10.1007/3-540-46146-9_90].
Cappelli R.; Lumini A.; Maio D.
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/914148
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact