Digenis: an hybridic proposal for (dis)similarity search

摘要

In modern databases effective similarity search is usually based on data or space partitioning, using similarity trees. Although these methods perform effectively in cases of low dimensionality, their performance generally degrades as dimensionality increases ('dimensional curse'). On the other hand, VA-file constitutes a simple approximate method which manages to outperform any other similarity search at high dimensionality. While both in similarity trees and VA-file the performance is depended on object dimensionality, neither trees nor VA-files can serve as multi-purpose methods. The research challenge of our study was the flexible combination of trees and VA-files, for the introduction of a method having the representation and organization power of hierarchical similarity trees and the benefits of 'no-dimensional curse' of a VA-file. Finally, the resultant proposal named DIGENIS1, includes the DIGENIS-tree, for object organization in the conceptual level and the DIGENIS-file - based on DIGENIS-tree -for the partial search in the physical level.