Typology
operator:
and / or
Language
operator:
and / or
Date
operator:
and / or
Rights
operator:
and / or
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: 27th Italian Symposium on Advanced Database Systems, 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: 27th Italian Symposium on Advanced Database Systems, Castiglione della Pescaia, Italy, 16-19/06/2019
See at:
ceur-ws.org 
| ISTI Repository | CNR ExploRA
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.Source: International Conference on Similarity Search and Applications, pp. 233–246, Newark, NJ, USA, 2-4/10/2019
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.Source: International Conference on Similarity Search and Applications, pp. 233–246, Newark, NJ, USA, 2-4/10/2019
DOI: 10.1007/978-3-030-32047-8_21
Metrics:
See at:
dspace.stir.ac.uk | ISTI Repository | doi.org 
| link.springer.com | CNR ExploRA
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.Source: ADBIS 2018 - 22nd European Conference on Advances in Databases and Information Systems, pp. 127–141, Budapest, Ungheria, 2-5 September 2018
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.Source: ADBIS 2018 - 22nd European Conference on Advances in Databases and Information Systems, pp. 127–141, Budapest, Ungheria, 2-5 September 2018
DOI: 10.1007/978-3-319-98398-1_9
Metrics:
See at:
ISTI Repository | doi.org | link.springer.com | CNR ExploRA
2018
Doctoral thesis
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 | ISTI Repository | CNR ExploRA
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 (Oxf.) 101 (2021). doi:10.1016/j.is.2021.101808
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 (Oxf.) 101 (2021). doi:10.1016/j.is.2021.101808
DOI: 10.1016/j.is.2021.101808
Metrics:
See at:
ISTI Repository | ISTI Repository | www.sciencedirect.com | CNR ExploRA
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 B. T., Lokoc J., Leibetseder A., Mejzlik F., Peska L., Rossetto L., Schall K., Schoeffmann K., Schuldt H., Spiess F., Tran L. D., 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 Print 11 (2022). doi:10.1007/s13735-021-00225-2
DOI: 10.1007/s13735-021-00225-2
Project(s): AI4Media
Metrics:
Heller S., Gsteiger V., Bailer W., Gurrin C., Jonsson B. T., Lokoc J., Leibetseder A., Mejzlik F., Peska L., Rossetto L., Schall K., Schoeffmann K., Schuldt H., Spiess F., Tran L. D., 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 Print 11 (2022). doi:10.1007/s13735-021-00225-2
DOI: 10.1007/s13735-021-00225-2
Project(s): AI4Media
Metrics:
See at:
ISTI Repository | ISTI Repository | link.springer.com | CNR ExploRA
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.Source: MMM 2022 - 28th International Conference on Multi Media Modeling, pp. 193–204, Phu Quoc, Vietnam, 06-10/06/2022
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.Source: MMM 2022 - 28th International Conference on Multi Media Modeling, pp. 193–204, Phu Quoc, Vietnam, 06-10/06/2022
DOI: 10.1007/978-3-030-98358-1_16
Project(s): AI4Media
Metrics:
See at:
ISTI Repository | doi.org | link.springer.com | CNR ExploRA
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: SEBD 2022 - 30th Italian Symposium on Advanced Database Systems, 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: SEBD 2022 - 30th Italian Symposium on Advanced Database Systems, pp. 415–426, Tirrenia (PI), Italia, 19-22/06/2022
See at:
ceur-ws.org | ISTI Repository | ISTI Repository | CNR ExploRA
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.Source: SISAP 2022 - 15th International Conference on Similarity Search and Applications, pp. 104–117, Bologna, Italy, 7-9/10/2022
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.Source: SISAP 2022 - 15th International Conference on Similarity Search and Applications, pp. 104–117, Bologna, Italy, 7-9/10/2022
DOI: 10.1007/978-3-031-17849-8_9
Project(s): AI4Media
Metrics:
See at:
ISTI Repository | link.springer.com | CNR ExploRA
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.Source: SISAP 2017 - Similarity Search and Applications. 10th International Conference, pp. 96–109, Munich, Germany, 4-6 October 2017
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.Source: SISAP 2017 - Similarity Search and Applications. 10th International Conference, pp. 96–109, Munich, Germany, 4-6 October 2017
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 | ISTI Repository | doi.org | doi.org | link.springer.com | CNR ExploRA
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.Source: International Conference on Similarity Search and Applications, pp. 265–272, Newark, NJ, USA, 2-4/10/2019
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.Source: International Conference on Similarity Search and Applications, pp. 265–272, Newark, NJ, USA, 2-4/10/2019
DOI: 10.1007/978-3-030-32047-8_23
Metrics:
See at:
Univerzitní repozitář Masarykovy univerzity | ISTI Repository | doi.org | link.springer.com | CNR ExploRA
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.Source: Similarity Search and Applications, pp. v–vi. New York: Springer Science and Business Media, 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.Source: Similarity Search and Applications, pp. v–vi. New York: Springer Science and Business Media, 2020
DOI: 10.1007/978-3-030-60936-8
Metrics:
See at:
link.springer.com | ISTI Repository | link.springer.com | link.springer.com | CNR ExploRA
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 O. S., 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 (2023). doi:10.1007/s00530-023-01143-5
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 O. S., 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 (2023). doi:10.1007/s00530-023-01143-5
DOI: 10.1007/s00530-023-01143-5
Project(s): AI4Media
, XRECO Metrics:
See at:
ISTI Repository | ZENODO | link.springer.com | CNR ExploRA
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.Source: SISAP 2014 - 7th International Conference on Similarity Search and Applications, pp. 37–49, Los Cabos, Mexico, 29-31/10/2014
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.Source: SISAP 2014 - 7th International Conference on Similarity Search and Applications, pp. 37–49, Los Cabos, Mexico, 29-31/10/2014
DOI: 10.1007/978-3-319-11988-5_4
Metrics:
See at:
ISTI Repository | doi.org | link.springer.com | CNR ExploRA
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.Source: EAGLE 2014 - First EAGLE International Conference, pp. 117–131, Parigi, Francia, 29-30 September - 1 October 2014
Project(s): EAGLE
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.Source: EAGLE 2014 - First EAGLE International Conference, pp. 117–131, Parigi, Francia, 29-30 September - 1 October 2014
Project(s): EAGLE
See at:
www.eagle-network.eu | CNR ExploRA
2014
Conference article
Restricted
Aggregating local descriptors for epigraphs recognition
Amato G., Falchi F., Rabitti F., Vadicamo L.
In this paper, we consider the task of recognizing epigraphs in images such as photos taken using mobile devices. Given a set of 17,155 photos related to 14,560 epigraphs, we used a k-NearestNeighbor approach in order to perform the recognition. The contribution of this work is in evaluating 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 SIFT descriptors is the best choice for this task.Source: The Fourth International Conference on Digital Presentation and Preservation of Cultural and Scientific Heritage, pp. 49–58, Veliko Tarnovo, Bulgaria, 18-21 September 2014
Project(s): EAGLE
Amato G., Falchi F., Rabitti F., Vadicamo L.
In this paper, we consider the task of recognizing epigraphs in images such as photos taken using mobile devices. Given a set of 17,155 photos related to 14,560 epigraphs, we used a k-NearestNeighbor approach in order to perform the recognition. The contribution of this work is in evaluating 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 SIFT descriptors is the best choice for this task.Source: The Fourth International Conference on Digital Presentation and Preservation of Cultural and Scientific Heritage, pp. 49–58, Veliko Tarnovo, Bulgaria, 18-21 September 2014
Project(s): EAGLE
See at:
www.ceeol.com | CNR ExploRA
2015
Conference article
Open Access
Searching the EAGLE epigraphic material through image recognition via a mobile device
Bolettieri P., Casarosa V., Falchi F., Vadicamo L., Martineau P., Orlandi S., Santucci R.
This demonstration paper describes the mobile application developed by the EAGLE project to increase the use and visibility of its epigraphic material. The EAGLE project (European network of Ancient Greek and Latin Epigraphy) is gathering a comprehensive collection of inscriptions (about 80 % of the surviving material) and making it accessible through a user-friendly portal, which supports searching and browsing of the epigraphic material. In order to increase the usefulness and visibility of its content, EAGLE has developed also a mobile application to enable tourists and scholars to obtain detailed information about the inscriptions they are looking at by taking pictures with their smartphones and sending them to the EAGLE portal for recognition. In this demonstration paper we describe the EAGLE mobile application and give an outline of its features and its architecture.Source: Similarity Search and Applications. 8th International Conference, pp. 351–354, Glasgow, UK, 12-14/10/2015
DOI: 10.1007/978-3-319-25087-8_35
Project(s): EAGLE
Metrics:
Bolettieri P., Casarosa V., Falchi F., Vadicamo L., Martineau P., Orlandi S., Santucci R.
This demonstration paper describes the mobile application developed by the EAGLE project to increase the use and visibility of its epigraphic material. The EAGLE project (European network of Ancient Greek and Latin Epigraphy) is gathering a comprehensive collection of inscriptions (about 80 % of the surviving material) and making it accessible through a user-friendly portal, which supports searching and browsing of the epigraphic material. In order to increase the usefulness and visibility of its content, EAGLE has developed also a mobile application to enable tourists and scholars to obtain detailed information about the inscriptions they are looking at by taking pictures with their smartphones and sending them to the EAGLE portal for recognition. In this demonstration paper we describe the EAGLE mobile application and give an outline of its features and its architecture.Source: Similarity Search and Applications. 8th International Conference, pp. 351–354, Glasgow, UK, 12-14/10/2015
DOI: 10.1007/978-3-319-25087-8_35
Project(s): EAGLE
Metrics:
See at:
ISTI Repository | doi.org | link.springer.com | CNR ExploRA
2016
Journal article
Unknown
Sistema di riconoscimento delle immagini e mobile app
Amato G., Bolettieri P., Falchi F., Vadicamo L.
In this paper, we present a system for visually retrieving ancient inscriptions, developed in the context of the ongoing Europeana network of Ancient Greek and Latin Epigraphy (EAGLE) EU Project. The system allows the user in front of an inscription (e.g, in a museum, street, archaeological site) or watching a reproduction (e.g., in a book, from a monitor), to automatically recognize the inscription and obtain information about it just using a smart-phone or a tablet. The experimental results show that the Vector of Locally Aggregated Descriptors is a promising encoding strategy for performing visual recognition in this specific context.Source: Forma urbis XXI (2016): 22–25.
Project(s): EAGLE
Amato G., Bolettieri P., Falchi F., Vadicamo L.
In this paper, we present a system for visually retrieving ancient inscriptions, developed in the context of the ongoing Europeana network of Ancient Greek and Latin Epigraphy (EAGLE) EU Project. The system allows the user in front of an inscription (e.g, in a museum, street, archaeological site) or watching a reproduction (e.g., in a book, from a monitor), to automatically recognize the inscription and obtain information about it just using a smart-phone or a tablet. The experimental results show that the Vector of Locally Aggregated Descriptors is a promising encoding strategy for performing visual recognition in this specific context.Source: Forma urbis XXI (2016): 22–25.
Project(s): EAGLE
See at: CNR ExploRA
2016
Conference article
Open Access
How effective are aggregation methods on binary features?
Amato G., Falchi F., Vadicamo L
During the last decade, various local features have been proposed and used to support Content Based Image Retrieval and object recognition tasks. Local features allow to effectively match local structures between images, but the cost of extraction and pairwise comparison of the local descriptors becomes a bottleneck when mobile devices and/or large database are used. Two major directions have been followed to improve efficiency of local features based approaches. On one hand, the cost of extracting, representing and matching local visual descriptors has been reduced by defining binary local features. On the other hand, methods for quantizing or aggregating local features have been proposed to scale up image matching on very large scale. In this paper, we performed an extensive comparison of the state-of-the-art aggregation methods applied to ORB binary descriptors. Our results show that the use of aggregation methods on binary local features is generally effective even if, as expected, there is a loss of performance compared to the same approaches applied to non-binary features. However, aggregations of binary feature represent a worthwhile option when one need to use devices with very low CPU and memory resources, as mobile and wearable devices.Source: International Conference on Computer Vision Theory and Applications, pp. 556–573, Roma, Italy, 27-29 February 2016
DOI: 10.5220/0005719905660573
Project(s): EAGLE
Metrics:
Amato G., Falchi F., Vadicamo L
During the last decade, various local features have been proposed and used to support Content Based Image Retrieval and object recognition tasks. Local features allow to effectively match local structures between images, but the cost of extraction and pairwise comparison of the local descriptors becomes a bottleneck when mobile devices and/or large database are used. Two major directions have been followed to improve efficiency of local features based approaches. On one hand, the cost of extracting, representing and matching local visual descriptors has been reduced by defining binary local features. On the other hand, methods for quantizing or aggregating local features have been proposed to scale up image matching on very large scale. In this paper, we performed an extensive comparison of the state-of-the-art aggregation methods applied to ORB binary descriptors. Our results show that the use of aggregation methods on binary local features is generally effective even if, as expected, there is a loss of performance compared to the same approaches applied to non-binary features. However, aggregations of binary feature represent a worthwhile option when one need to use devices with very low CPU and memory resources, as mobile and wearable devices.Source: International Conference on Computer Vision Theory and Applications, pp. 556–573, Roma, Italy, 27-29 February 2016
DOI: 10.5220/0005719905660573
Project(s): EAGLE
Metrics:
See at:
doi.org | ISTI Repository | www.scitepress.org | CNR ExploRA
2017
Journal article
Open Access
Hilbert exclusion: improved metric search through finite isometric embeddings
Connor R., Cardillo F. A., Vadicamo L., Rabitti F.
Most research into similarity search in metric spaces relies on the triangle inequality property. This property allows the space to be arranged according to relative distances to avoid searching some subspaces. We show that many common metric spaces, notably including those using Euclidean and Jensen-Shannon distances, also have a stronger property, sometimes called the four-point property: In essence, these spaces allow an isometric embedding of any four points in three-dimensional Euclidean space, as well as any three points in two-dimensional Euclidean space. In fact, we show that any space that is isometrically embeddable in Hilbert space has the stronger property. This property gives stronger geometric guarantees, and one in particular, which we name the Hilbert Exclusion property, allows any indexing mechanism which uses hyperplane partitioning to perform better. One outcome of this observation is that a number of state-of-the-art indexing mechanisms over high-dimensional spaces can be easily refined to give a significant increase in performance; furthermore, the improvement given is greater in higher dimensions. This therefore leads to a significant improvement in the cost of metric search in these spaces.Source: ACM transactions on information systems 35 (2017): 17–27. doi:10.1145/3001583
DOI: 10.1145/3001583
DOI: 10.48550/arxiv.1604.08640
Metrics:
Connor R., Cardillo F. A., Vadicamo L., Rabitti F.
Most research into similarity search in metric spaces relies on the triangle inequality property. This property allows the space to be arranged according to relative distances to avoid searching some subspaces. We show that many common metric spaces, notably including those using Euclidean and Jensen-Shannon distances, also have a stronger property, sometimes called the four-point property: In essence, these spaces allow an isometric embedding of any four points in three-dimensional Euclidean space, as well as any three points in two-dimensional Euclidean space. In fact, we show that any space that is isometrically embeddable in Hilbert space has the stronger property. This property gives stronger geometric guarantees, and one in particular, which we name the Hilbert Exclusion property, allows any indexing mechanism which uses hyperplane partitioning to perform better. One outcome of this observation is that a number of state-of-the-art indexing mechanisms over high-dimensional spaces can be easily refined to give a significant increase in performance; furthermore, the improvement given is greater in higher dimensions. This therefore leads to a significant improvement in the cost of metric search in these spaces.Source: ACM transactions on information systems 35 (2017): 17–27. doi:10.1145/3001583
DOI: 10.1145/3001583
DOI: 10.48550/arxiv.1604.08640
Metrics:
See at:
arXiv.org e-Print Archive | ISTI Repository | ACM Transactions on Information Systems | doi.acm.org | ACM Transactions on Information Systems | doi.org | CNR ExploRA