Indexing schemes for similarity search: an illustrated paradigm
<|reference_start|>Indexing schemes for similarity search: an illustrated paradigm: We suggest a variation of the Hellerstein--Koutsoupias--Papadimitriou indexability model for datasets equipped with a similarity measure, with the aim of better understanding the structure of indexing schemes for similarity-based search and the geometry of similarity workloads. This in particular provides a unified approach to a great variety of schemes used to index into metric spaces and facilitates their transfer to more general similarity measures such as quasi-metrics. We discuss links between performance of indexing schemes and high-dimensional geometry. The concepts and results are illustrated on a very large concrete dataset of peptide fragments equipped with a biologically significant similarity measure.<|reference_end|>
@article{pestov2002indexing,
    title={Indexing schemes for similarity search: an illustrated paradigm},
    author={Vladimir Pestov and Aleksandar Stojmirovic},
    journal={Fundamenta Informaticae Vol. 70 (2006), No. 4, 367-385},
    year={2002},
    archivePrefix={arXiv},
    eprint={cs/0211018},
    primaryClass={cs.DS}
}