Benchmarking Access Structures for High-Dimensional Multimedia Data

• Author(s) / Creator(s)

  • Nascimento, Mario
  • Colossi, Nathan

• Technical report TR99-05. In multimedia databases it is usual to map objects into feature vectors in high-dimensional spaces. In order to speed query processing access structures, or indices, are required. Unfortunately, in the case of similarity queries, which are in fact nearest neighbor queries, classical spatial access structures such as the R*-tree are bound to fail when the space dimensional is not low. Fortunately, on the other hand, several access structures for high dimensional spaces, e.g., the SS-tree, SR-tree and M-tree have been proposed. However, each of those structures have been benchmarked in a rather ad-hoc manner. This paper benchmarks and compares all above structures using a real dataset of 40,000 high-dimensional objects. All structures have been implemented on top of the GiST infrastructure to minimize the risk of implementation bias. Even though no structure can be claimed to be the undisputed winner, we have found that the SR-tree presents the best overall results. | TRID-ID TR99-05

• Date created

  1999

• Subjects / Keywords

  • Access structures
  • Database Systems
  • Indexing
  • Multimedia databases

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3DV1CN2M

• License

  Attribution 3.0 International