Abstract
We present the Snake Table, an index structure designed for supporting streams of k-NN searches within a content-based similarity search framework. The index is created and updated in the online phase while resolving the queries, thus it does not need a preprocessing step. This index is intended to be used when the stream of query objects fits a snake distribution, that is, when the distance between two consecutive query objects is small. In particular, this kind of distribution is present in content-based video retrieval systems, when the set of query objects are consecutive frames from a query video. We show that the Snake Table improves the efficiency of k-NN searches in these systems, avoiding the building of a static index in the offline phase.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barrios, J.M., Bustos, B.: Competitive content-based video copy detection using global descriptors. Multimedia Tools and Applications, 1–36 (2011)
Bustos, B., Pedreira, O., Brisaboa, N.: A dynamic pivot selection technique for similarity search. In: Proc. of the Int. Workshop on Similarity Search and Applications (SISAP 2008), pp. 105–112. IEEE (2008)
Chávez, E., Navarro, G., Baeza-Yates, R., Marroquín, J.L.: Searching in metric spaces. ACM Computing Surveys 33(3), 273–321 (2001)
Kim, C., Vasudev, B.: Spatiotemporal sequence matching for efficient video copy detection. IEEE Transactions on Circuits and Systems for Video Technology 15(1), 127–132 (2005)
Law-To, J., Joly, A., Boujemaa, N.: MUSCLE-VCD-2007: a live benchmark for video copy detection (2007), http://www-rocq.inria.fr/imedia/civr-bench/
Manjunath, B.S., Ohm, J.-R., Vasudevan, V.V., Yamada, A.: Color and texture descriptors. IEEE Transactions on Circuits and Systems for Video Technology 11(6), 703–715 (2001)
Micó, L., Oncina, J.: A constant average time algorithm to allow insertions in the LAESA fast nearest neighbour search index. In: Proc. of the Int. Conf. on Pattern Recognition (ICPR 2010), pp. 3911–3914. IEEE (2010)
Micó, M.L., Oncina, J., Vidal, E.: A new version of the nearest-neighbour approximating and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements. Pattern Recognition Letters 15(1), 9–17 (1994)
Skopal, T., Lokoč, J., Bustos, B.: D-cache: Universal distance cache for metric access methods. IEEE Transactions on Knowledge and Data Engineering 24(5), 868–881 (2012)
Vidal, E.: New formulation and improvements of the nearest-neighbour approximating and eliminating search algorithm (AESA). Pattern Recognition Letters 15(1), 1–7 (1994)
Zezula, P., Amato, G., Dohnal, V., Batko, M.: Similarity Search: The Metric Space Approach (Advances in Database Systems). Springer (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Barrios, J.M., Bustos, B., Skopal, T. (2012). Snake Table: A Dynamic Pivot Table for Streams of k-NN Searches. In: Navarro, G., Pestov, V. (eds) Similarity Search and Applications. SISAP 2012. Lecture Notes in Computer Science, vol 7404. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32153-5_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-32153-5_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32152-8
Online ISBN: 978-3-642-32153-5
eBook Packages: Computer ScienceComputer Science (R0)