Proceedings chapter

Quantifying the Invariance and Robustness of Permutation-Based Indexing Schemes

Presented at Tokyo (Japan), 24-26 October 2016
PublisherCham : Springer International Publishing
Publication date2016

Providing a fast and accurate (exact or approximate) access to large-scale multidimensional data is a ubiquitous problem and dates back to the early days of large-scale Information Systems. Similarity search, requiring to resolve nearest neighbor (NN) searches, is a fundamental tool for structuring information space. Permutation-based Indexing (PBI) is a reference-based indexing scheme that accelerates NN search by combining the use of landmark points and ranking in place of distance calculation. In this paper, we are interested in understanding the approximation made by the PBI scheme. The aim is to understand the robustness of the scheme created by modeling and studying by quantifying its invariance properties. After discussing the geometry of PBI, in relation to the study of ranking, from empirical evidence, we make proposals to cater for the inconsistencies of this structure.

  • Permutation based indexing
  • Ranking
  • Geometry
Citation (ISO format)
MARCHAND-MAILLET, Stéphane et al. Quantifying the Invariance and Robustness of Permutation-Based Indexing Schemes. In: Similarity Search and Applications, 9th International Conference, SISAP 2016, Tokyo, Japan, October 24-26, 2016, Proceedings. Tokyo (Japan). Cham : Springer International Publishing, 2016. p. 79–92. doi: 10.1007/978-3-319-46759-7_6
Main files (1)
Proceedings chapter (Published version)

Technical informations

Creation09/13/2019 3:51:00 PM
First validation09/13/2019 3:51:00 PM
Update time03/15/2023 6:02:01 PM
Status update03/15/2023 6:02:01 PM
Last indexation01/17/2024 6:16:14 AM
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack