Abstract
With today’s dynamic multimedia collections, maintenance of high-dimensional indexes is an important, yet understudied topic. Extended Cluster Pruning (eCP) is a highly-scalable approximate indexing approach based on clustering, that is targeted at stable performance in a disk-based scenario. In this work, we propose an index maintenance strategy for the eCP index, which utilizes the tree structure of the index and its approximate nature. We then develop a cost model for the strategy and evaluate its cost using a simulation model.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
References
Babenko, A., Lempitsky, V.: The inverted multi-index. In: Proceedings of the Conference on Computer Vision and Pattern Recognition (CVPR), Providence, RI, USA, pp. 3069–3076 (2012)
Chierichetti, F., Panconesi, A., Raghavan, P., Sozio, M., Tiberi, A., Upfal, E.: Finding near neighbors through cluster pruning. In: Proceedings of the Symposium on Principles of Database Systems (PODS), Beijing, China, pp. 103–112 (2007)
Fagin, R., Kumar, R., Sivakumar, D.: Efficient similarity search and classification via rank aggregation. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, San Diego, CA, USA, pp. 301–312 (2003)
Gu\({\eth }\)mundsson, G.Þ., Jónsson, B.Þ., Amsaleg, L.: A large-scale performance study of cluster-based high-dimensional indexing. In: Proceedings of the Workshop on Very-Large-Scale Multimedia Corpus, Mining and Retrieval (co-located with ACM Multimedia), Firenze, Italy (2010)
Jegou, H., Douze, M., Schmid, C.: Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell. 33(1), 117–128 (2011)
Jónsson, B.Þ., Amsaleg, L., Lejsek, H.: SSD technology enables dynamic maintenance of persistent high-dimensional indexes. In: Proceedings of the ACM International Conference on Multimedia Retrieval (ICMR), New York, NY, USA, pp. 347–350 (2016)
Lejsek, H., Ásmundsson, F.H., Jónsson, B.Þ., Amsaleg, L.: Transactional support for visual instance search. In: Marchand-Maillet, S., Silva, Y.N., Chávez, E. (eds.) SISAP 2018. LNCS, vol. 11223, pp. 73–86. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-02224-2_6
Ólafsson, A., Jónsson, B.Þ., Amsaleg, L., Lejsek, H.: Dynamic behavior of balanced NV-trees. Multimedia Syst. 17, 83–100 (2011)
Sigur\({\eth }\)ardóttir, R., Hauksson, H., Jónsson, B.Þ., Amsaleg, L.: Quality vs. time tradeoff for approximate image descriptor search. In: Proceedings of the IEEE EMMA Workshop (co-located with ICDE), Tokyo, Japan (2005)
Sivic, J., Zisserman, A.: Video Google: a text retrieval approach to object matching in videos. In: Proceedings of the IEEE International Conference on Computer Vision (ICCV), Nice, France, pp. 1470–1477 (2003)
Tao, Y., Yi, K., Sheng, C., Kalnis, P.: Quality and efficiency in high dimensional nearest neighbor search. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, Boston, MA, USA, pp. 563–576 (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Højsgaard, A.M., Jónsson, B.Þ., Bonnet, P. (2019). Index Maintenance Strategy and Cost Model for Extended Cluster Pruning. In: Amato, G., Gennaro, C., Oria, V., Radovanović , M. (eds) Similarity Search and Applications. SISAP 2019. Lecture Notes in Computer Science(), vol 11807. Springer, Cham. https://doi.org/10.1007/978-3-030-32047-8_3
Download citation
DOI: https://doi.org/10.1007/978-3-030-32047-8_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-32046-1
Online ISBN: 978-3-030-32047-8
eBook Packages: Computer ScienceComputer Science (R0)