2019
Conference article
Open Access
Modelling string structure in vector spaces
Connor R, Dearle A, Vadicamo L
Searching for similar strings is an important and frequent database task both in terms of human interactions and in absolute worldwide CPU utilisation. A wealth of metric functions for string comparison exist. However, with respect to the wide range of classification and other techniques known within vector spaces, such metrics allow only a very restricted range of techniques. To counter this restriction, various strategies have been used for mapping string spaces into vector spaces, approximating the string distances within the mapped space and therefore allowing vector space techniques to be used. In previous work we have developed a novel technique for mapping metric spaces into vector spaces, which can therefore be applied for this purpose. In this paper we evaluate this technique in the context of string spaces, and compare it to other published techniques for mapping strings to vectors. We use a publicly available English lexicon as our experimental data set, and test two different string metrics over it for each vector mapping. We find that our novel technique considerably outperforms previously used technique in preserving the actual distance.Source: CEUR WORKSHOP PROCEEDINGS, vol. 2400. Castiglione della Pescaia, Italy, 16-19/06/2019
Connor R, Dearle A, Vadicamo L
Searching for similar strings is an important and frequent database task both in terms of human interactions and in absolute worldwide CPU utilisation. A wealth of metric functions for string comparison exist. However, with respect to the wide range of classification and other techniques known within vector spaces, such metrics allow only a very restricted range of techniques. To counter this restriction, various strategies have been used for mapping string spaces into vector spaces, approximating the string distances within the mapped space and therefore allowing vector space techniques to be used. In previous work we have developed a novel technique for mapping metric spaces into vector spaces, which can therefore be applied for this purpose. In this paper we evaluate this technique in the context of string spaces, and compare it to other published techniques for mapping strings to vectors. We use a publicly available English lexicon as our experimental data set, and test two different string metrics over it for each vector mapping. We find that our novel technique considerably outperforms previously used technique in preserving the actual distance.Source: CEUR WORKSHOP PROCEEDINGS, vol. 2400. Castiglione della Pescaia, Italy, 16-19/06/2019
See at:
ceur-ws.org 
| CNR IRIS | ISTI Repository | CNR IRIS 
2019
Conference article
Open Access
Query Filtering with Low-Dimensional Local Embeddings
Chavez E, Connor R, Vadicamo L
The concept of local pivoting is to partition a metric space so that each element in the space is associated with precisely one of a fixed set of reference objects or pivots. The idea is that each object of the data set is associated with the reference object that is best suited to filter that particular object if it is not relevant to a query, maximising the probability of excluding it from a search. The notion does not in itself lead to a scalable search mechanism, but instead gives a good chance of exclusion based on a tiny memory footprint and a fast calculation. It is therefore most useful in contexts where main memory is at a premium, or in conjunction with another, scalable, mechanism. In this paper we apply similar reasoning to metric spaces which possess the four-point property, which notably include Euclidean, Cosine, Triangular, Jensen-Shannon, and Quadratic Form. In this case, each element of the space can be associated with two reference objects, and a four-point lower-bound property is used instead of the simple triangle inequality. The probability of exclusion is strictly greater than with simple local pivoting; the space required per object and the calculation are again tiny in relative terms. We show that the resulting mechanism can be very effective. A consequence of using the four-point property is that, for m reference points, there are (Formula Presented) pivot pairs to choose from, giving a very good chance of a good selection being available from a small number of distance calculations. Finding the best pair has a quadratic cost with the number of references; however, we provide experimental evidence that good heuristics exist. Finally, we show how the resulting mechanism can be integrated with a more scalable technique to provide a very significant performance improvement, for a very small overhead in build-time and memory cost.DOI: 10.1007/978-3-030-32047-8_21
Metrics:
Chavez E, Connor R, Vadicamo L
The concept of local pivoting is to partition a metric space so that each element in the space is associated with precisely one of a fixed set of reference objects or pivots. The idea is that each object of the data set is associated with the reference object that is best suited to filter that particular object if it is not relevant to a query, maximising the probability of excluding it from a search. The notion does not in itself lead to a scalable search mechanism, but instead gives a good chance of exclusion based on a tiny memory footprint and a fast calculation. It is therefore most useful in contexts where main memory is at a premium, or in conjunction with another, scalable, mechanism. In this paper we apply similar reasoning to metric spaces which possess the four-point property, which notably include Euclidean, Cosine, Triangular, Jensen-Shannon, and Quadratic Form. In this case, each element of the space can be associated with two reference objects, and a four-point lower-bound property is used instead of the simple triangle inequality. The probability of exclusion is strictly greater than with simple local pivoting; the space required per object and the calculation are again tiny in relative terms. We show that the resulting mechanism can be very effective. A consequence of using the four-point property is that, for m reference points, there are (Formula Presented) pivot pairs to choose from, giving a very good chance of a good selection being available from a small number of distance calculations. Finding the best pair has a quadratic cost with the number of references; however, we provide experimental evidence that good heuristics exist. Finally, we show how the resulting mechanism can be integrated with a more scalable technique to provide a very significant performance improvement, for a very small overhead in build-time and memory cost.DOI: 10.1007/978-3-030-32047-8_21
Metrics:
See at:
dspace.stir.ac.uk | CNR IRIS | link.springer.com | ISTI Repository | doi.org | CNR IRIS | CNR IRIS
2018
Conference article
Open Access
Selecting sketches for similarity search
Mic V, Novak D, Vadicamo L, Zezula P
Techniques of the Hamming embedding, producing bit string sketches, have been recently successfully applied to speed up similarity search. Sketches are usually compared by the Hamming distance, and applied to filter out non-relevant objects during the query evaluation. As several sketching techniques exist and each can produce sketches with different lengths, it is hard to select a proper configuration for a particular dataset. We assume that the (dis)similarity of objects is expressed by an arbitrary metric function, and we propose a way to efficiently estimate the quality of sketches using just a small sample set of data. Our approach is based on a probabilistic analysis of sketches which describes how separated are objects after projection to the Hamming space.DOI: 10.1007/978-3-319-98398-1_9
Metrics:
Mic V, Novak D, Vadicamo L, Zezula P
Techniques of the Hamming embedding, producing bit string sketches, have been recently successfully applied to speed up similarity search. Sketches are usually compared by the Hamming distance, and applied to filter out non-relevant objects during the query evaluation. As several sketching techniques exist and each can produce sketches with different lengths, it is hard to select a proper configuration for a particular dataset. We assume that the (dis)similarity of objects is expressed by an arbitrary metric function, and we propose a way to efficiently estimate the quality of sketches using just a small sample set of data. Our approach is based on a probabilistic analysis of sketches which describes how separated are objects after projection to the Hamming space.DOI: 10.1007/978-3-319-98398-1_9
Metrics:
See at:
CNR IRIS | link.springer.com | ISTI Repository | doi.org | CNR IRIS | CNR IRIS
2018
Other
Open Access
Enhancing content-based image retrieval using aggregation of binary features, deep learning, and supermetric search
Vadicamo L
The millions of images shared every day on social media is just a tip of the iceberg of the current phenomenon of visual data explosion, which places a great demand on scalable Content-Based Image Retrieval (CBIR) systems. CBIR allows organizing and searching image collections on the basis of image visual contents, that is without using text or other metadata. The problem of content-based search is addressed in this thesis by investigating and proposing efficient and effective methods that support three fundamental stages of a CBIR system, namely the numerical representation of the image visual content (feature extraction), the processing/indexing of the image features, and the query by-example search. Concerning the image representation we investigate and experimentally compare Convolutional Neural Network (CNN) features, methods for aggregating local features, and their combination. We show that very high effectiveness is achieved combining CNN features and aggregation methods; moreover, in order to improve the efficiency we investigate the use of the aggregation methods on the top of binary local features. In particular, we propose the BMM-FV which allows encoding a set of binary vectors into a single descriptor. An extensive experimental evaluation on benchmark datasets shows that our BMM-FV outperforms other methods for aggregating binary local features and achieves high retrieval performance when combined with the CNN features. Secondly, we propose an efficient and effective technique, called Deep Permutation, to index deep features (such as CNN features) using a permutation-based approach. Moreover, we propose the Blockwise Surrogate Text Representation to represent and index compound metric objects, including the VLAD image descriptors, using an off-the-shelf text search engine. Finally, we address the image search task in the general context of similarity search in metric space, which is a framework suitable for a large number of applications and data types. Most metric indexing and searching mechanisms rely on the triangle inequality, which allows deriving bounds on the distance between data objects. The distance bounds are used to efficiently exclude partition of the data that do not contain solutions to a given query. We reread foundations of metric search from a geometrical point of view starting from the observation that the triangle inequality is equivalent to a discrete geometric condition defined in term of finite isometric embeddings into Euclidean spaces. We show that there exists a large class of metric spaces, the supermetric ones, meeting the four-point property that is a property stronger than the triangle inequality. Moreover, we show that many supermetric spaces commonly used in applications have a further property called n-point property. The main outcome of our study is showing how these geometric properties can be used to improve the similarity search in supermetric spaces by 1) deriving distance bounds that are tighter than that relied on the triangle inequality and, thus, allowing better space pruning; 2) defining novel partitioning and indexing mechanisms; 3) proposing a promising approach to embed a supermetric space into a finite-dimensional Euclidean space, which turns out to have implications not only in the similarity search context but also in other applicative tasks such, as the dimensionality reduction. We prove the validity of our approaches both theoretically and experimentally.
Vadicamo L
The millions of images shared every day on social media is just a tip of the iceberg of the current phenomenon of visual data explosion, which places a great demand on scalable Content-Based Image Retrieval (CBIR) systems. CBIR allows organizing and searching image collections on the basis of image visual contents, that is without using text or other metadata. The problem of content-based search is addressed in this thesis by investigating and proposing efficient and effective methods that support three fundamental stages of a CBIR system, namely the numerical representation of the image visual content (feature extraction), the processing/indexing of the image features, and the query by-example search. Concerning the image representation we investigate and experimentally compare Convolutional Neural Network (CNN) features, methods for aggregating local features, and their combination. We show that very high effectiveness is achieved combining CNN features and aggregation methods; moreover, in order to improve the efficiency we investigate the use of the aggregation methods on the top of binary local features. In particular, we propose the BMM-FV which allows encoding a set of binary vectors into a single descriptor. An extensive experimental evaluation on benchmark datasets shows that our BMM-FV outperforms other methods for aggregating binary local features and achieves high retrieval performance when combined with the CNN features. Secondly, we propose an efficient and effective technique, called Deep Permutation, to index deep features (such as CNN features) using a permutation-based approach. Moreover, we propose the Blockwise Surrogate Text Representation to represent and index compound metric objects, including the VLAD image descriptors, using an off-the-shelf text search engine. Finally, we address the image search task in the general context of similarity search in metric space, which is a framework suitable for a large number of applications and data types. Most metric indexing and searching mechanisms rely on the triangle inequality, which allows deriving bounds on the distance between data objects. The distance bounds are used to efficiently exclude partition of the data that do not contain solutions to a given query. We reread foundations of metric search from a geometrical point of view starting from the observation that the triangle inequality is equivalent to a discrete geometric condition defined in term of finite isometric embeddings into Euclidean spaces. We show that there exists a large class of metric spaces, the supermetric ones, meeting the four-point property that is a property stronger than the triangle inequality. Moreover, we show that many supermetric spaces commonly used in applications have a further property called n-point property. The main outcome of our study is showing how these geometric properties can be used to improve the similarity search in supermetric spaces by 1) deriving distance bounds that are tighter than that relied on the triangle inequality and, thus, allowing better space pruning; 2) defining novel partitioning and indexing mechanisms; 3) proposing a promising approach to embed a supermetric space into a finite-dimensional Euclidean space, which turns out to have implications not only in the similarity search context but also in other applicative tasks such, as the dimensionality reduction. We prove the validity of our approaches both theoretically and experimentally.
See at:
etd.adm.unipi.it | CNR IRIS | ISTI Repository | CNR IRIS
2021
Journal article
Open Access
Query filtering using two-dimensional local embeddings
Vadicamo L, Connor R, Chávez E
In high dimensional data sets, exact indexes are ineffective for proximity queries, and a sequential scan over the entire data set is unavoidable. Accepting this, here we present a new approach employing two-dimensional embeddings. Each database element is mapped to the XY plane using the four-point property. The caveat is that the mapping is local: in other words, each object is mapped using a different mapping. The idea is that each element of the data is associated with a pair of reference objects that is well-suited to filter that particular object, in cases where it is not relevant to a query. This maximises the probability of excluding that object from a search. At query time, a query is compared with a pool of reference objects which allow its mapping to all the planes used by data objects. Then, for each query/object pair, a lower bound of the actual distance is obtained. The technique can be applied to any metric space that possesses the four-point property, therefore including Euclidean, Cosine, Triangular, Jensen-Shannon, and Quadratic Form distances. Our experiments show that for all the data sets tested, of varying dimensionality, our approach can filter more objects than a standard metric indexing approach. For low dimensional data this does not make a good search mechanism in its own right, as it does not scale with the size of the data: that is, its cost is linear with respect to the data size. However, we also show that it can be added as a post-filter to other mechanisms, increasing efficiency with little extra cost in space or time. For high-dimensional data, we show related approximate techniques which, we believe, give the best known compromise for speeding up the essential sequential scan. The potential uses of our filtering technique include pure GPU searching, taking advantage of the tiny memory footprint of the mapping.Source: INFORMATION SYSTEMS, vol. 101
DOI: 10.1016/j.is.2021.101808
Metrics:
Vadicamo L, Connor R, Chávez E
In high dimensional data sets, exact indexes are ineffective for proximity queries, and a sequential scan over the entire data set is unavoidable. Accepting this, here we present a new approach employing two-dimensional embeddings. Each database element is mapped to the XY plane using the four-point property. The caveat is that the mapping is local: in other words, each object is mapped using a different mapping. The idea is that each element of the data is associated with a pair of reference objects that is well-suited to filter that particular object, in cases where it is not relevant to a query. This maximises the probability of excluding that object from a search. At query time, a query is compared with a pool of reference objects which allow its mapping to all the planes used by data objects. Then, for each query/object pair, a lower bound of the actual distance is obtained. The technique can be applied to any metric space that possesses the four-point property, therefore including Euclidean, Cosine, Triangular, Jensen-Shannon, and Quadratic Form distances. Our experiments show that for all the data sets tested, of varying dimensionality, our approach can filter more objects than a standard metric indexing approach. For low dimensional data this does not make a good search mechanism in its own right, as it does not scale with the size of the data: that is, its cost is linear with respect to the data size. However, we also show that it can be added as a post-filter to other mechanisms, increasing efficiency with little extra cost in space or time. For high-dimensional data, we show related approximate techniques which, we believe, give the best known compromise for speeding up the essential sequential scan. The potential uses of our filtering technique include pure GPU searching, taking advantage of the tiny memory footprint of the mapping.Source: INFORMATION SYSTEMS, vol. 101
DOI: 10.1016/j.is.2021.101808
Metrics:
See at:
CNR IRIS | ISTI Repository | ISTI Repository | www.sciencedirect.com | CNR IRIS | CNR IRIS | CNR IRIS
2022
Journal article
Open Access
Interactive video retrieval evaluation at a distance: comparing sixteen interactive video search systems in a remote setting at the 10th Video Browser Showdown
Heller S, Gsteiger V, Bailer W, Gurrin C, Jonsson Bt, Lokoc J, Leibetseder A, Mejzlik F, Peska L, Rossetto L, Schall K, Schoeffmann K, Schuldt H, Spiess F, Tran Ld, Vadicamo L, Vesely P, Vrochidis S, Wu J
The Video Browser Showdown addresses difficult video search challenges through an annual interactive evaluation campaign attracting research teams focusing on interactive video retrieval. The campaign aims to provide insights into the performance of participating interactive video retrieval systems, tested by selected search tasks on large video collections. For the first time in its ten year history, the Video Browser Showdown 2021 was organized in a fully remote setting and hosted a record number of sixteen scoring systems. In this paper, we describe the competition setting, tasks and results and give an overview of state-of-the-art methods used by the competing systems. By looking at query result logs provided by ten systems, we analyze differences in retrieval model performances and browsing times before a correct submission. Through advances in data gathering methodology and tools, we provide a comprehensive analysis of ad-hoc video search tasks, discuss results, task design and methodological challenges. We highlight that almost all top performing systems utilize some sort of joint embedding for text-image retrieval and enable specification of temporal context in queries for known-item search. Whereas a combination of these techniques drive the currently top performing systems, we identify several future challenges for interactive video search engines and the Video Browser Showdown competition itself.Source: INTERNATIONAL JOURNAL OF MULTIMEDIA INFORMATION RETRIEVAL, vol. 11 (issue 1)
DOI: 10.1007/s13735-021-00225-2
Project(s): AI4Media
Metrics:
Heller S, Gsteiger V, Bailer W, Gurrin C, Jonsson Bt, Lokoc J, Leibetseder A, Mejzlik F, Peska L, Rossetto L, Schall K, Schoeffmann K, Schuldt H, Spiess F, Tran Ld, Vadicamo L, Vesely P, Vrochidis S, Wu J
The Video Browser Showdown addresses difficult video search challenges through an annual interactive evaluation campaign attracting research teams focusing on interactive video retrieval. The campaign aims to provide insights into the performance of participating interactive video retrieval systems, tested by selected search tasks on large video collections. For the first time in its ten year history, the Video Browser Showdown 2021 was organized in a fully remote setting and hosted a record number of sixteen scoring systems. In this paper, we describe the competition setting, tasks and results and give an overview of state-of-the-art methods used by the competing systems. By looking at query result logs provided by ten systems, we analyze differences in retrieval model performances and browsing times before a correct submission. Through advances in data gathering methodology and tools, we provide a comprehensive analysis of ad-hoc video search tasks, discuss results, task design and methodological challenges. We highlight that almost all top performing systems utilize some sort of joint embedding for text-image retrieval and enable specification of temporal context in queries for known-item search. Whereas a combination of these techniques drive the currently top performing systems, we identify several future challenges for interactive video search engines and the Video Browser Showdown competition itself.Source: INTERNATIONAL JOURNAL OF MULTIMEDIA INFORMATION RETRIEVAL, vol. 11 (issue 1)
DOI: 10.1007/s13735-021-00225-2
Project(s): AI4Media
Metrics:
See at:
CNR IRIS | link.springer.com | ISTI Repository | ISTI Repository | CNR IRIS | CNR IRIS | CNR IRIS
2022
Conference article
Open Access
A task category space for user-centric comparative multimedia search evaluations
Lokoc J, Bailer W, Barthel K U, Gurrin C, Heller S, Jónsson B Þ, Peska L, Rossetto L, Schoeffmann K, Vadicamo L, Vrochidis S, Wu J
In the last decade, user-centric video search competitions have facilitated the evolution of interactive video search systems. So far, these competitions focused on a small number of search task categories, with few attempts to change task category configurations. Based on our extensive experience with interactive video search contests, we have analyzed the spectrum of possible task categories and propose a list of individual axes that define a large space of possible task categories. Using this concept of category space, new user-centric video search competitions can be designed to benchmark video search systems from different perspectives. We further analyse the three task categories considered so far at the Video Browser Showdown and discuss possible (but sometimes challenging) shifts within the task category space.DOI: 10.1007/978-3-030-98358-1_16
Project(s): AI4Media
Metrics:
Lokoc J, Bailer W, Barthel K U, Gurrin C, Heller S, Jónsson B Þ, Peska L, Rossetto L, Schoeffmann K, Vadicamo L, Vrochidis S, Wu J
In the last decade, user-centric video search competitions have facilitated the evolution of interactive video search systems. So far, these competitions focused on a small number of search task categories, with few attempts to change task category configurations. Based on our extensive experience with interactive video search contests, we have analyzed the spectrum of possible task categories and propose a list of individual axes that define a large space of possible task categories. Using this concept of category space, new user-centric video search competitions can be designed to benchmark video search systems from different perspectives. We further analyse the three task categories considered so far at the Video Browser Showdown and discuss possible (but sometimes challenging) shifts within the task category space.DOI: 10.1007/978-3-030-98358-1_16
Project(s): AI4Media
Metrics:
See at:
CNR IRIS | link.springer.com | ISTI Repository | doi.org | CNR IRIS | CNR IRIS
2022
Conference article
Open Access
Investigating binary partition power in metric query
Connor R, Dearle A, Vadicamo L
It is generally understood that, as dimensionality increases, the minimum cost of metric query tends from O(log n) to O (n) in both space and time, where n is the size of the data set. With low dimensionality, the former is easy to achieve; with very high dimensionality, the latter is inevitable. We previously described BitPart as a novel mechanism suitable for performing exact metric search in "high(er)" dimensions. The essential tradeoff of BitPart is that its space cost is linear with respect to the size of the data, but the actual space required for each object may be small as log2 n bits, which allows even very large data sets to be queried using only main memory. Potentially the time cost still scales with O (log n). Together these attributes give exact search which outperforms indexing structures if dimensionality is within a certain range. In this article, we reiterate the design of BitPart in this context. The novel contribution is an indepth examination of what the notion of "high(er)" means in practical terms. To do this we introduce the notion of exclusion power, and show its application to some generated data sets across different dimensions.Source: CEUR WORKSHOP PROCEEDINGS, pp. 415-426. Tirrenia (PI), Italia, 19-22/06/2022
Connor R, Dearle A, Vadicamo L
It is generally understood that, as dimensionality increases, the minimum cost of metric query tends from O(log n) to O (n) in both space and time, where n is the size of the data set. With low dimensionality, the former is easy to achieve; with very high dimensionality, the latter is inevitable. We previously described BitPart as a novel mechanism suitable for performing exact metric search in "high(er)" dimensions. The essential tradeoff of BitPart is that its space cost is linear with respect to the size of the data, but the actual space required for each object may be small as log2 n bits, which allows even very large data sets to be queried using only main memory. Potentially the time cost still scales with O (log n). Together these attributes give exact search which outperforms indexing structures if dimensionality is within a certain range. In this article, we reiterate the design of BitPart in this context. The novel contribution is an indepth examination of what the notion of "high(er)" means in practical terms. To do this we introduce the notion of exclusion power, and show its application to some generated data sets across different dimensions.Source: CEUR WORKSHOP PROCEEDINGS, pp. 415-426. Tirrenia (PI), Italia, 19-22/06/2022
See at:
ceur-ws.org | CNR IRIS | ISTI Repository | ISTI Repository | CNR IRIS | CNR IRIS
2022
Conference article
Open Access
On the expected exclusion power of binary partitions for metric search
Vadicamo L, Dearle A, Connor R
The entire history and, we dare say, future of similarity search is governed by the underlying notion of partition. A partition is an equivalence relation defined over the space, therefore each element of the space is contained within precisely one of the equivalence classes of the partition. All attempts to search a finite space efficiently, whether exactly or approximately, rely on some set of principles which imply that if the query is within one equivalence class, then one or more other classes either cannot, or probably do not, contain any of its solutions. In most early research, partitions relied only on the metric postulates, and logarithmic search time could be obtained on low dimensional spaces. In these cases, it was straightforward to identify multiple partitions, each of which gave a relatively high probability of identifying subsets of the space which could not contain solutions. Over time the datasets being searched have become more complex, leading to higher dimensional spaces. It is now understood that even an approximate search in a very high-dimensional space is destined to require O(n) time and space. Almost entirely missing from the research literature however is any analysis of exactly when this effect takes over. In this paper, we make a start on tackling this important issue. Using a quantitative approach, we aim to shed some light on the notion of the exclusion power of partitions, in an attempt to better understand their nature with respect to increasing dimensionality.DOI: 10.1007/978-3-031-17849-8_9
Project(s): AI4Media
Metrics:
Vadicamo L, Dearle A, Connor R
The entire history and, we dare say, future of similarity search is governed by the underlying notion of partition. A partition is an equivalence relation defined over the space, therefore each element of the space is contained within precisely one of the equivalence classes of the partition. All attempts to search a finite space efficiently, whether exactly or approximately, rely on some set of principles which imply that if the query is within one equivalence class, then one or more other classes either cannot, or probably do not, contain any of its solutions. In most early research, partitions relied only on the metric postulates, and logarithmic search time could be obtained on low dimensional spaces. In these cases, it was straightforward to identify multiple partitions, each of which gave a relatively high probability of identifying subsets of the space which could not contain solutions. Over time the datasets being searched have become more complex, leading to higher dimensional spaces. It is now understood that even an approximate search in a very high-dimensional space is destined to require O(n) time and space. Almost entirely missing from the research literature however is any analysis of exactly when this effect takes over. In this paper, we make a start on tackling this important issue. Using a quantitative approach, we aim to shed some light on the notion of the exclusion power of partitions, in an attempt to better understand their nature with respect to increasing dimensionality.DOI: 10.1007/978-3-031-17849-8_9
Project(s): AI4Media
Metrics:
See at:
CNR IRIS | link.springer.com | ISTI Repository | CNR IRIS | CNR IRIS
2024
Conference article
Open Access
Multimedia Information Retrieval in XR
Arnold R., Bailer W., Gasser R., Jónsson B. P., Khan O. S., Schuldt H., Spiess F., Vadicamo L.
The way we create, consume and interact with multimedia content has changed significantly in recent years with the advent of affordable recording devices and easy sharing and access in the form of mobile phones. With the imminent wave of affordable devices that enable mixed reality experiences and the large variety of devices on the market, interaction with multimedia content is expected to continue to evolve rapidly. This will also drastically affect the entire area of multimedia information retrieval in eXtended Reality (XR), for instance by novel ways to express user needs in VR, result presentation that takes the specific capabilities of XR devices into account, and/or result feedback. This tutorial on Multimedia Retrieval in XR discusses and demonstrates existing solutions and highlights key challenges in this evolving field.DOI: 10.1145/3664647.3689176
Project(s): SUN, XReco
Metrics:
Arnold R., Bailer W., Gasser R., Jónsson B. P., Khan O. S., Schuldt H., Spiess F., Vadicamo L.
The way we create, consume and interact with multimedia content has changed significantly in recent years with the advent of affordable recording devices and easy sharing and access in the form of mobile phones. With the imminent wave of affordable devices that enable mixed reality experiences and the large variety of devices on the market, interaction with multimedia content is expected to continue to evolve rapidly. This will also drastically affect the entire area of multimedia information retrieval in eXtended Reality (XR), for instance by novel ways to express user needs in VR, result presentation that takes the specific capabilities of XR devices into account, and/or result feedback. This tutorial on Multimedia Retrieval in XR discusses and demonstrates existing solutions and highlights key challenges in this evolving field.DOI: 10.1145/3664647.3689176
Project(s): SUN
, XReco Metrics:
See at:
dl.acm.org | CNR IRIS | doi.org | CNR IRIS | CNR IRIS
2024
Journal article
Open Access
Correlations of cross-entropy loss in Machine Learning
Connor R., Dearle A., Claydon B., Vadicamo L.
Cross-entropy loss is crucial in training many deep neural networks. In this context, we show a number of novel and strong correlations among various related divergence functions. In particular, we demonstrate that, in some circumstances, (a) cross-entropy is almost perfectly correlated with the little-known triangular divergence, and (b) cross-entropy is strongly correlated with the Euclidean distance over the logits from which the softmax is derived. The consequences of these observations are as follows. First, triangular divergence may be used as a cheaper alternative to cross-entropy. Second, logits can be used as features in a Euclidean space which is strongly synergistic with the classification process. This justifies the use of Euclidean distance over logits as a measure of similarity, in cases where the network is trained using softmax and cross-entropy. We establish these correlations via empirical observation, supported by a mathematical explanation encompassing a number of strongly related divergence functions.Source: ENTROPY, vol. 26 (issue 6)
DOI: 10.3390/e26060491
Metrics:
Connor R., Dearle A., Claydon B., Vadicamo L.
Cross-entropy loss is crucial in training many deep neural networks. In this context, we show a number of novel and strong correlations among various related divergence functions. In particular, we demonstrate that, in some circumstances, (a) cross-entropy is almost perfectly correlated with the little-known triangular divergence, and (b) cross-entropy is strongly correlated with the Euclidean distance over the logits from which the softmax is derived. The consequences of these observations are as follows. First, triangular divergence may be used as a cheaper alternative to cross-entropy. Second, logits can be used as features in a Euclidean space which is strongly synergistic with the classification process. This justifies the use of Euclidean distance over logits as a measure of similarity, in cases where the network is trained using softmax and cross-entropy. We establish these correlations via empirical observation, supported by a mathematical explanation encompassing a number of strongly related divergence functions.Source: ENTROPY, vol. 26 (issue 6)
DOI: 10.3390/e26060491
Metrics:
See at:
Entropy | Entropy | St Andrews Research Repository | IRIS Cnr | St Andrews Research Repository | GitHub | CNR IRIS
2024
Conference article
Open Access
Demonstrating the efficacy of polyadic queries
Claydon B., Connor R., Dearle A., Vadicamo L.
Similarity search is normally defined to be the task of iden- tifying those objects, from a large collection, that are most similar to a further single object presented as a query. Using polyadic queries, a small set of objects are presented to the system, with the intent of finding those objects most similar to all elements of the query set. A few scenarios have previously demonstrated the usefulness of this notion. For example, we may be searching for images similar to a red balloon over a lake. With a single query, it is impossible to tell if the intent is to search for other im- ages of balloons over lakes, or for other red balloons in any background. If instead we could present a system with a few different images of bal- loons, all of which are either all red, or all over lakes, the similarity search engine may be able to respond more appropriately. In this paper we demonstrate software which permits the user to provide explicit feedback by selecting the best few results from an intermediate set which are best suited to their original information need. A polyadic query can be formed from this set, which should give better results with a minimum of user interaction.Source: LECTURE NOTES IN COMPUTER SCIENCE, vol. 15268, pp. 49-56. Providence, USA, 4-6/11/2024
DOI: 10.1007/978-3-031-75823-2_4
Project(s): 2022-2026 ADR UK Programme, MUCES -- a MUltimedia platform for Content Enrichment and Search in audiovisual archives
Metrics:
Claydon B., Connor R., Dearle A., Vadicamo L.
Similarity search is normally defined to be the task of iden- tifying those objects, from a large collection, that are most similar to a further single object presented as a query. Using polyadic queries, a small set of objects are presented to the system, with the intent of finding those objects most similar to all elements of the query set. A few scenarios have previously demonstrated the usefulness of this notion. For example, we may be searching for images similar to a red balloon over a lake. With a single query, it is impossible to tell if the intent is to search for other im- ages of balloons over lakes, or for other red balloons in any background. If instead we could present a system with a few different images of bal- loons, all of which are either all red, or all over lakes, the similarity search engine may be able to respond more appropriately. In this paper we demonstrate software which permits the user to provide explicit feedback by selecting the best few results from an intermediate set which are best suited to their original information need. A polyadic query can be formed from this set, which should give better results with a minimum of user interaction.Source: LECTURE NOTES IN COMPUTER SCIENCE, vol. 15268, pp. 49-56. Providence, USA, 4-6/11/2024
DOI: 10.1007/978-3-031-75823-2_4
Project(s): 2022-2026 ADR UK Programme, MUCES -- a MUltimedia platform for Content Enrichment and Search in audiovisual archives
Metrics:
See at:
CNR IRIS | link.springer.com | doi.org | CNR IRIS | CNR IRIS
2025
Conference article
Open Access
Comparative analysis of relevance feedback techniques for image retrieval
Vadicamo L., Scotti F., Dearle A., Connor R.
Relevance feedback mechanisms have garnered significant attention in content-based image and video retrieval thanks to their effectiveness in refining search results to better meet user information needs. This paper provides a comprehensive comparative analysis of four techniques: Rocchio, PicHunter, Polyadic Query, and linear Support Vector Machines, representing diverse strategies encompassing query vector modification, relevance probability estimation, adaptive similarity metrics, and classifier learning. We conducted experiments within an interactive image retrieval system, with varying amounts of user feedback: full feedback, limited positive feedback, and mixed feedback. In particular, we introduce novel enhanced versions of PicHunter and Polyadic search incorporating negative feedback. Our findings highlight the benefits of integrating both positive and negative examples, demonstrating significant performance improvements. Overall, SVM and our improved PicHunter outperformed the other approaches for ad-hoc search, especially in cases in which the feedback process is iterated several times.Source: LECTURE NOTES IN COMPUTER SCIENCE, vol. 15520 - Proceedings, Part I, pp. 206-219. Nara, Japan, 8-10/01/2025
DOI: 10.1007/978-981-96-2054-8_16
Project(s): 2022-2026 ADR UK Programme, a MUltimedia platform for Content Enrichment and Search in audiovisual archive project
Metrics:
Vadicamo L., Scotti F., Dearle A., Connor R.
Relevance feedback mechanisms have garnered significant attention in content-based image and video retrieval thanks to their effectiveness in refining search results to better meet user information needs. This paper provides a comprehensive comparative analysis of four techniques: Rocchio, PicHunter, Polyadic Query, and linear Support Vector Machines, representing diverse strategies encompassing query vector modification, relevance probability estimation, adaptive similarity metrics, and classifier learning. We conducted experiments within an interactive image retrieval system, with varying amounts of user feedback: full feedback, limited positive feedback, and mixed feedback. In particular, we introduce novel enhanced versions of PicHunter and Polyadic search incorporating negative feedback. Our findings highlight the benefits of integrating both positive and negative examples, demonstrating significant performance improvements. Overall, SVM and our improved PicHunter outperformed the other approaches for ad-hoc search, especially in cases in which the feedback process is iterated several times.Source: LECTURE NOTES IN COMPUTER SCIENCE, vol. 15520 - Proceedings, Part I, pp. 206-219. Nara, Japan, 8-10/01/2025
DOI: 10.1007/978-981-96-2054-8_16
Project(s): 2022-2026 ADR UK Programme, a MUltimedia platform for Content Enrichment and Search in audiovisual archive project
Metrics:
See at:
CNR IRIS | link.springer.com | CNR IRIS | CNR IRIS
2024
Journal article
Open Access
nSimplex Zen: a novel dimensionality reduction for euclidean and Hilbert spaces
Connor R., Vadicamo L.
Dimensionality reduction techniques map values from a high dimensional space to one with a lower dimension. The result is a space which requires less physical memory and has a faster distance calculation. These techniques are widely used where required properties of the reduced-dimension space give an acceptable accuracy with respect to the original space. Many such transforms have been described. They have been classified in two main groups: linear and topological. Linear methods such as Principal Component Analysis (PCA) and Random Projection (RP) define matrix-based transforms into a lower dimension of Euclidean space. Topological methods such as Multidimensional Scaling (MDS) attempt to preserve higher-level aspects such as the nearest-neighbour relation, and some may be applied to non-Euclidean spaces. Here, we introduce nSimplex Zen, a novel topological method of reducing dimensionality. Like MDS, it relies only upon pairwise distances measured in the original space. The use of distances, rather than coordinates, allows the technique to be applied to both Euclidean and other Hilbert spaces, including those governed by Cosine, Jensen–Shannon and Quadratic Form distances. We show that in almost all cases, due to geometric properties of high-dimensional spaces, our new technique gives better properties than others, especially with reduction to very low dimensions.Source: ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA, vol. 18 (issue 6), pp. 1-44
DOI: 10.1145/3647642
Project(s): AI4Media, National Centre for HPC, Big Data and Quantum Computing
Metrics:
Connor R., Vadicamo L.
Dimensionality reduction techniques map values from a high dimensional space to one with a lower dimension. The result is a space which requires less physical memory and has a faster distance calculation. These techniques are widely used where required properties of the reduced-dimension space give an acceptable accuracy with respect to the original space. Many such transforms have been described. They have been classified in two main groups: linear and topological. Linear methods such as Principal Component Analysis (PCA) and Random Projection (RP) define matrix-based transforms into a lower dimension of Euclidean space. Topological methods such as Multidimensional Scaling (MDS) attempt to preserve higher-level aspects such as the nearest-neighbour relation, and some may be applied to non-Euclidean spaces. Here, we introduce nSimplex Zen, a novel topological method of reducing dimensionality. Like MDS, it relies only upon pairwise distances measured in the original space. The use of distances, rather than coordinates, allows the technique to be applied to both Euclidean and other Hilbert spaces, including those governed by Cosine, Jensen–Shannon and Quadratic Form distances. We show that in almost all cases, due to geometric properties of high-dimensional spaces, our new technique gives better properties than others, especially with reduction to very low dimensions.Source: ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA, vol. 18 (issue 6), pp. 1-44
DOI: 10.1145/3647642
Project(s): AI4Media
, National Centre for HPC, Big Data and Quantum ComputingMetrics:
See at:
dl.acm.org | CNR IRIS | CNR IRIS | CNR IRIS
2017
Conference article
Open Access
High-dimensional simplexes for supermetric search
Connor R, Vadicamo L, Rabitti F
In a metric space, triangle inequality implies that, for any three objects, a triangle with edge lengths corresponding to their pairwise distances can be formed. The n-point property is a generalisation of this where, for any (n+1) objects in the space, there exists an n-dimensional simplex whose edge lengths correspond to the distances among the objects. In general, metric spaces do not have this property; however in 1953, Blumenthal showed that any semi-metric space which is isometrically embeddable in a Hilbert space also has the n-point property. We have previously called such spaces supermetric spaces, and have shown that many metric spaces are also supermetric, including Euclidean, Cosine, Jensen-Shannon and Triangular spaces of any dimension. Here we show how such simplexes can be constructed from only their edge lengths, and we show how the geometry of the simplexes can be used to determine lower and upper bounds on unknown distances within the original space. By increasing the number of dimensions, these bounds converge to the true distance. Finally we show that for any Hilbert-embeddable space, it is possible to construct Euclidean spaces of arbitrary dimensions, from which these lower and upper bounds of the original space can be determined. These spaces may be much cheaper to query than the original. For similarity search, the engineering tradeoffs are good: we show significant reductions in data size and metric cost with little loss of accuracy, leading to a significant overall improvement in exact search performance.DOI: 10.1007/978-3-319-68474-1_7
DOI: 10.48550/arxiv.1707.08370
Metrics:
Connor R, Vadicamo L, Rabitti F
In a metric space, triangle inequality implies that, for any three objects, a triangle with edge lengths corresponding to their pairwise distances can be formed. The n-point property is a generalisation of this where, for any (n+1) objects in the space, there exists an n-dimensional simplex whose edge lengths correspond to the distances among the objects. In general, metric spaces do not have this property; however in 1953, Blumenthal showed that any semi-metric space which is isometrically embeddable in a Hilbert space also has the n-point property. We have previously called such spaces supermetric spaces, and have shown that many metric spaces are also supermetric, including Euclidean, Cosine, Jensen-Shannon and Triangular spaces of any dimension. Here we show how such simplexes can be constructed from only their edge lengths, and we show how the geometry of the simplexes can be used to determine lower and upper bounds on unknown distances within the original space. By increasing the number of dimensions, these bounds converge to the true distance. Finally we show that for any Hilbert-embeddable space, it is possible to construct Euclidean spaces of arbitrary dimensions, from which these lower and upper bounds of the original space can be determined. These spaces may be much cheaper to query than the original. For similarity search, the engineering tradeoffs are good: we show significant reductions in data size and metric cost with little loss of accuracy, leading to a significant overall improvement in exact search performance.DOI: 10.1007/978-3-319-68474-1_7
DOI: 10.48550/arxiv.1707.08370
Metrics:
See at:
arXiv.org e-Print Archive | dspace.stir.ac.uk | CNR IRIS | link.springer.com | ISTI Repository | doi.org | doi.org | CNR IRIS | CNR IRIS
2019
Conference article
Open Access
Metric Embedding into the Hamming Space with the n-Simplex Projection
Vadicamo L, Mic V, Falchi F, Zezula P
Transformations of data objects into the Hamming space are often exploited to speed-up the similarity search in metric spaces. Techniques applicable in generic metric spaces require expensive learning, e.g., selection of pivoting objects. However, when searching in common Euclidean space, the best performance is usually achieved by transformations specifically designed for this space. We propose a novel transformation technique that provides a good trade-off between the applicability and the quality of the space approximation. It uses the n-Simplex projection to transform metric objects into a low-dimensional Euclidean space, and then transform this space to the Hamming space. We compare our approach theoretically and experimentally with several techniques of the metric embedding into the Hamming space. We focus on the applicability, learning cost, and the quality of search space approximation.DOI: 10.1007/978-3-030-32047-8_23
Metrics:
Vadicamo L, Mic V, Falchi F, Zezula P
Transformations of data objects into the Hamming space are often exploited to speed-up the similarity search in metric spaces. Techniques applicable in generic metric spaces require expensive learning, e.g., selection of pivoting objects. However, when searching in common Euclidean space, the best performance is usually achieved by transformations specifically designed for this space. We propose a novel transformation technique that provides a good trade-off between the applicability and the quality of the space approximation. It uses the n-Simplex projection to transform metric objects into a low-dimensional Euclidean space, and then transform this space to the Hamming space. We compare our approach theoretically and experimentally with several techniques of the metric embedding into the Hamming space. We focus on the applicability, learning cost, and the quality of search space approximation.DOI: 10.1007/978-3-030-32047-8_23
Metrics:
See at:
CNR IRIS | Univerzitní repozitář Masarykovy univerzity | link.springer.com | ISTI Repository | doi.org | CNR IRIS | CNR IRIS
2020
Contribution to book
Open Access
Preface - SISAP 2020
Satoh S, Vadicamo L, Zimek A, Carrara F, Bartolini I, Aumüller M, Jónsson B Þór, Pagh R
Preface of Volume 12440 LNCS,2020, Pages v-vi, 13th International Conference on Similarity Search and Applications, SISAP 2020.DOI: 10.1007/978-3-030-60936-8
Metrics:
Satoh S, Vadicamo L, Zimek A, Carrara F, Bartolini I, Aumüller M, Jónsson B Þór, Pagh R
Preface of Volume 12440 LNCS,2020, Pages v-vi, 13th International Conference on Similarity Search and Applications, SISAP 2020.DOI: 10.1007/978-3-030-60936-8
Metrics:
See at:
CNR IRIS | link.springer.com | ISTI Repository | CNR IRIS | link.springer.com | link.springer.com
2023
Journal article
Open Access
Interactive video retrieval in the age of effective joint embedding deep models: lessons from the 11th VBS
Lokoc J, Andreadis S, Bailer W, Duane A, Gurrin C, Ma Z, Messina N, Nguyen T N, Peska L, Rossetto L, Sauter L, Schall K, Schoeffmann K, Khan Os, Spiess F, Vadicamo L, Vrochidis S
This paper presents findings of the eleventh Video Browser Showdown competition, where sixteen teams competed in known-item and ad-hoc search tasks. Many of the teams utilized state-of-the-art video retrieval approaches that demonstrated high effectiveness in challenging search scenarios. In this paper, a broad survey of all utilized approaches is presented in connection with an analysis of the performance of participating teams. Specifically, both high-level performance indicators are presented with overall statistics as well as in-depth analysis of the performance of selected tools implementing result set logging. The analysis reveals evidence that the CLIP model represents a versatile tool for cross-modal video retrieval when combined with interactive search capabilities. Furthermore, the analysis investigates the effect of different users and text query properties on the performance in search tasks. Last but not least, lessons learned from search task preparation are presented, and a new direction for ad-hoc search based tasks at Video Browser Showdown is introduced.Source: MULTIMEDIA SYSTEMS
DOI: 10.1007/s00530-023-01143-5
Project(s): AI4Media, XRECO
Metrics:
Lokoc J, Andreadis S, Bailer W, Duane A, Gurrin C, Ma Z, Messina N, Nguyen T N, Peska L, Rossetto L, Sauter L, Schall K, Schoeffmann K, Khan Os, Spiess F, Vadicamo L, Vrochidis S
This paper presents findings of the eleventh Video Browser Showdown competition, where sixteen teams competed in known-item and ad-hoc search tasks. Many of the teams utilized state-of-the-art video retrieval approaches that demonstrated high effectiveness in challenging search scenarios. In this paper, a broad survey of all utilized approaches is presented in connection with an analysis of the performance of participating teams. Specifically, both high-level performance indicators are presented with overall statistics as well as in-depth analysis of the performance of selected tools implementing result set logging. The analysis reveals evidence that the CLIP model represents a versatile tool for cross-modal video retrieval when combined with interactive search capabilities. Furthermore, the analysis investigates the effect of different users and text query properties on the performance in search tasks. Last but not least, lessons learned from search task preparation are presented, and a new direction for ad-hoc search based tasks at Video Browser Showdown is introduced.Source: MULTIMEDIA SYSTEMS
DOI: 10.1007/s00530-023-01143-5
Project(s): AI4Media
, XRECO Metrics:
See at:
CNR IRIS | link.springer.com | ISTI Repository | ZENODO | CNR IRIS | CNR IRIS
2014
Conference article
Open Access
Some theoretical and experimental observations on permutation spaces and similarity search
Amato G, Falchi F, Rabitti F, Vadicamo L
Permutation based approaches represent data objects as ordered lists of predefined reference objects. Similarity queries are executed by searching for data objects whose permutation representation is similar to the query one. Various permutation-based indexes have been recently proposed. They typically allow high efficiency with acceptable effectiveness. Moreover, various parameters can be set in order to find an optimal trade-off between quality of results and costs. In this paper we studied the permutation space without referring to any particular index structure focusing on both theoretical and experimental aspects. We used both synthetic and real-word datasets for our experiments. The results of this work are relevant in both developing and setting parameters of permutation-based similarity searching approaches.DOI: 10.1007/978-3-319-11988-5_4
Metrics:
Amato G, Falchi F, Rabitti F, Vadicamo L
Permutation based approaches represent data objects as ordered lists of predefined reference objects. Similarity queries are executed by searching for data objects whose permutation representation is similar to the query one. Various permutation-based indexes have been recently proposed. They typically allow high efficiency with acceptable effectiveness. Moreover, various parameters can be set in order to find an optimal trade-off between quality of results and costs. In this paper we studied the permutation space without referring to any particular index structure focusing on both theoretical and experimental aspects. We used both synthetic and real-word datasets for our experiments. The results of this work are relevant in both developing and setting parameters of permutation-based similarity searching approaches.DOI: 10.1007/978-3-319-11988-5_4
Metrics:
See at:
CNR IRIS | link.springer.com | ISTI Repository | doi.org | CNR IRIS | CNR IRIS
2014
Conference article
Open Access
Inscriptions visual recognition. A comparison of state-of-the-art object recognition approaches
Amato G, Falchi F, Rabitti F, Vadicamo L
In this paper, we consider the task of recognizing inscriptions in images such as photos taken using mobile devices. Given a set of 17,155 photos related to 14,560 inscriptions, we used a ð'~-NearestNeighbor approach in order to perform the recognition. The contribution of this work is in comparing state-of-the-art visual object recognition techniques in this specific context. The experimental results conducted show that Vector of Locally Aggregated Descriptors obtained aggregating Scale Invariant Feature Transform descriptors is the best choice for this task.Project(s): Europeana network of Ancient Greek and Latin Epigraphy
Amato G, Falchi F, Rabitti F, Vadicamo L
In this paper, we consider the task of recognizing inscriptions in images such as photos taken using mobile devices. Given a set of 17,155 photos related to 14,560 inscriptions, we used a ð'~-NearestNeighbor approach in order to perform the recognition. The contribution of this work is in comparing state-of-the-art visual object recognition techniques in this specific context. The experimental results conducted show that Vector of Locally Aggregated Descriptors obtained aggregating Scale Invariant Feature Transform descriptors is the best choice for this task.Project(s): Europeana network of Ancient Greek and Latin Epigraphy
See at:
CNR IRIS | www.eagle-network.eu | CNR IRIS