Metric space searching addresses the problem of efficient similarity searching across diverse applications, in particular for non-structured objects, for instance, natural language or images. Although promising, this approach is still immature in several aspects that are well-established in traditional databases. Particularly, most indexing schemes are not dynamic, as they cannot efficiently handle insertions over an ongoing index without significant performance degradation. Moreover, very few of them work efficiently in secondary memory. The List of Clusters (LC) has proven to be a competitive index in main memory due to its simplicity and good search performance in high dimensional metric spaces. We introduce a new dynamic, secondary-memory LC variant. Our new index efficiently handles the secondary memory scenario and achieves competitive search and insertion times compared to the state-of-the-art, making it a practical alternative for large-scale database applications. Also, our ideas are applicable to other secondary-memory indexes, where it is possible to control the disk page occupation.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

BOLDSC: A New Dynamic, Secondary-Memory Metric Index

  • Rodrigo Paredes,
  • Nora Reyes,
  • Karina Figueroa,
  • Manuel Hoffhein

摘要

Metric space searching addresses the problem of efficient similarity searching across diverse applications, in particular for non-structured objects, for instance, natural language or images. Although promising, this approach is still immature in several aspects that are well-established in traditional databases. Particularly, most indexing schemes are not dynamic, as they cannot efficiently handle insertions over an ongoing index without significant performance degradation. Moreover, very few of them work efficiently in secondary memory. The List of Clusters (LC) has proven to be a competitive index in main memory due to its simplicity and good search performance in high dimensional metric spaces. We introduce a new dynamic, secondary-memory LC variant. Our new index efficiently handles the secondary memory scenario and achieves competitive search and insertion times compared to the state-of-the-art, making it a practical alternative for large-scale database applications. Also, our ideas are applicable to other secondary-memory indexes, where it is possible to control the disk page occupation.