For decades, the success of the similarity search has been based on detailed quantifications of pairwise similarities of objects. Currently, the search features have become much more precise but also bulkier, and the similarity computations are more time-consuming. We show that nearly no precise similarity quantifications are needed to evaluate the k nearest neighbours ( k NN) queries that dominate real-life applications. Based on the well-known fact that a selection of the most similar alternative out of several options is a much easier task than deciding the absolute similarity scores, we propose the search based on an epistemologically simpler concept of relational similarity. Having arbitrary objects q , o 1 , o 2 from the search domain, the k NN search is solvable just by the ability to choose the more similar object to q out of o 1 , o 2 . To support the filtering efficiency, we also consider a neutral option, i.e., equal similarities of q , o 1 and q , o 2 . We formalise such concept and discuss its advantages with respect to similarity quantifications, namely the efficiency, robustness and scalability with respect to the dataset size. Our pioneering implementation of the relational similarity search for the Euclidean and Cosine spaces demonstrates robust filtering power and efficiency compared to several contemporary techniques.

Sequential pattern mining, which is one of the core tasks in data mining, allows to gain insight into datasets with complex sequential data. As the task is computationally intensive, there are many different approaches that are suitable for various types of data. We explore the possibility of optimising the analysis of sequences based on the characteristic (quickly obtainable) properties of the analysed data. In this paper, we propose five such characteristics and explore the efficiency of three algorithms that are representatives of the three main approaches to sequential pattern mining. We discovered that it is possible to save up to 21% of the search time compared to the best-performing representative. We trained a decision tree model with 87% accuracy of choosing the best algorithm for selected data based on these characteristics.

Digitization of human motion using 2D or 3D skeleton representations offers exciting possibilities for many applications but, at the same time, requires scalable content-based retrieval techniques to make such data reusable. Although a lot of research effort focuses on extracting content-preserving motion features, there is a lack of techniques that support efficient similarity search on a large scale. In this paper, we introduce a new indexing scheme for organizing large collections of spatio-temporal skeleton sequences. Specifically, we apply the motion-word concept to transform skeleton sequences into structured text-like motion documents, and index such documents using an extended inverted-file approach. Over this index, we design a new similarity search algorithm that exploits the properties of the motion-word representation and provides efficient retrieval with a variable level of approximation, possibly reaching constant search costs disregarding the collection size. Experimental results confirm the usefulness of the proposed approach.

With the increasing availability of human motion data captured in the form of 2D/3D skeleton sequences, more complex motion recordings need to be processed. In this paper, we focus on the similarity-based retrieval of motion episodes - medium-sized skeleton sequences that consist of multiple semantic actions and correspond to some logical motion unit (e.g., a figure skating performance). We examine two orthogonal approaches to the episode-matching task: (1) the deep learning approach that is traditionally used for processing short motion actions, and (2) the motion-word technique that transforms skeleton sequences into a text-like representation. Since the second approach is more promising, we propose a two-phase retrieval scheme that combines mature text-processing techniques with application-specific refinement methods. We demonstrate that this solution achieves promising results in both effectiveness and efficiency, and can be further indexed to implement scalable episode retrieval.

Large volumes of RGB video data are recorded and processed every day. One of the embedded data modality within these videos is the information about human motions. Up to now, this information has been almost unfeasible to extract, and thus human-motion understanding research has been mainly limited to 3D skeleton data captured by dedicated hardware only. However, with recent advances in computer vision, it is possible to estimate 2D skeleton sequences from ordinary videos quite accurately. Such 2D skeleton data possess an excellent potential for future motion understanding applications. In this paper, we adopt a state-of-the-art bidirectional LSTM network to analyze the accuracy gap in the expressive power of 2D and 3D skeleton data recorded simultaneously on a high number of 20k human actions. We further examine how the missing depth information and fluctuations in 2D skeleton sizes influence the recognition rate. We also demonstrate the suitability of 2D skeleton data for general daily activity recognition by reporting baselines on the PKU-MMD dataset.

Action recognition is a fundamental operation in 3D human motion analysis. Existing deep learning classifiers achieve a high recognition accuracy if large amounts of training data are provided. However, such data are difficult to obtain in a variety of application scenarios, mainly due to the high costs of motion capture technologies and an absence of suitable actors. In this paper, we propose augmentation techniques to artificially enlarge existing collections of 3D human skeleton sequences. The proposed techniques are especially useful for datasets distinguishing in a high number of classes, each of them characterized by only a limited number of action samples. We experimentally demonstrate that the augmented data help to significantly increase the recognition accuracy even using a standard deep learning architecture.

Motion capture data are digital representations of human movements in form of 3D trajectories of multiple body joints. To understand the captured motions, similarity-based processing and deep learning have already proved to be effective, especially in classifying pre-segmented actions. However, in real-world scenarios motion data are typically captured as long continuous sequences, without explicit knowledge of semantic partitioning. To make such unsegmented data accessible and reusable as required by many applications, there is a strong requirement to analyze, search, annotate and mine them automatically. However, there is currently an absence of datasets and benchmarks to test and compare the capabilities of the developed techniques for continuous motion data processing. In this paper, we introduce a new large-scale LSMB19 dataset consisting of two 3D skeleton sequences of a total length of 54.5 hours. We also define a benchmark on two important multimedia retrieval operations: subsequence search and annotation. Additionally, we exemplify the usability of the benchmark by establishing baseline results for these operations.

Motion capture technologies can digitize human movements into a discrete sequence of 3D skeletons. Such spatio-temporal data have a great application potential in many fields, ranging from computer animation, through security and sports to medicine, but their computerized processing is a difficult problem. The objective of this tutorial is to explain fundamental principles and technologies designed for searching, subsequence matching, classification and action detection in the 3D human motion data. These operations inherently require the concept of similarity to determine the degree of accordance between pairs of 3D skeleton sequences. Such similarity can be modeled using a generic approach of metric space by extracting effective deep features and comparing them by efficient distance functions. The metric-space approach also enables applying traditional index structures to efficiently access large datasets of skeleton sequences. We demonstrate the functionality of selected motion-processing operations by interactive web applications.

Motion capture technologies digitize human movements by tracking 3D positions of specific skeleton joints in time. Such spatio-temporal multimedia data have an enormous application potential in many fields, ranging from computer animation, through security and sports to medicine, but their computerized processing is a difficult problem. In this paper, we focus on an important task of recognition of a user-defined motion, based on a collection of labelled actions known in advance. We utilize current advances in deep feature learning and scalable similarity retrieval to build an effective and efficient k-nearest-neighbor recognition technique for 3D human motion data. The properties of the technique are demonstrated by a web application which allows a user to browse long motion sequences and specify any subsequence as the input for probabilistic recognition based on 130 predefined classes.

This article addresses the problem of matching the most similar data objects to a given query object. We adopt a generic model of similarity that involves the domain of objects and metric distance functions only. We examine the case of a large dataset in a complex data space, which makes this problem inherently difficult. Many indexing and searching approaches have been proposed, but they have often failed to efficiently prune complex search spaces and access large portions of the dataset when evaluating queries. We propose an approach to enhancing the existing search techniques to significantly reduce the number of accessed data objects while preserving the quality of the search results. In particular, we extend each data object with its sketch , a short binary string in Hamming space. These sketches approximate the similarity relationships in the original search space, and we use them to filter out non-relevant objects not pruned by the original search technique. We provide a probabilistic model to tune the parameters of the sketch-based filtering separately for each query object. Experiments conducted with different similarity search techniques and real-life datasets demonstrate that the secondary filtering can speed-up similarity search several times.

An important functionality of current social applications is real-time recommendation, which is responsible for suggesting relevant published data to the users based on their preferences. By representing the users and the published data in a metric space, each user can be recommended with their k nearest neighbors among the published data. We consider the scenario when the relevance of a published data item to a user decreases as the data gets older, i.e., a time-dependent distance function is applied. We define the problem as the continuous time-dependent kNN join and provide a solution to a broad range of time-dependent functions. In addition, we propose a binary sketch-based approximation technique used to speed up the join evaluation by replacing expensive metric distance computations with cheap Hamming distances.

Search-based annotation methods can be used for proposing descriptive keywords to users who need to annotate images e.g. in image stock databases. From the annotation output, users select keywords which they want to assign to the given image. The selected keywords can serve as a relevance feedback for additional annotation refinement. In this paper, we study the possibilities of exploiting the annotation relevance feedback, which is a novel problem that has not been systematically addressed yet. In particular, we focus on the subtask of utilizing the feedback for the retrieval of related annotated images that are subsequently used for mining of candidate keywords. We select three multi-modal search techniques that can be applied to this problem, implement them within a state-of-the-art search-based annotation system, and experimentally evaluate their usefulness for annotation quality improvement.

Motion capture technologies digitize human movements by tracking 3D positions of specific skeleton joints in time. Such spatio-temporal data have an enormous application potential in many fields, ranging from computer animation, through security and sports to medicine, but their computerized processing is a difficult problem. The recorded data can be imprecise, voluminous, and the same movement action can be performed by various subjects in a number of alternatives that can vary in speed, timing or a position in space. This requires employing completely different data-processing paradigms compared to the traditional domains such as attributes, text or images. The objective of this tutorial is to explain fundamental principles and technologies designed for similarity comparison, searching, subsequence matching, classification and action detection in the motion capture data. Specifically, we emphasize the importance of similarity needed to express the degree of accordance between pairs of motion sequences and also discuss the machine-learning approaches able to automatically acquire content-descriptive movement features. We explain how the concept of similarity together with the learned features can be employed for searching similar occurrences of interested actions within a long motion sequence. Assuming a user-provided categorization of example motions, we discuss techniques able to recognize types of specific movement actions and detect such kinds of actions within continuous motion sequences. Selected operations will be demonstrated by on-line web applications.

Current motion-capture technologies produce continuous streams of 3D human joint trajectories. One of the challenges is to automatically annotate such streams of complex spatio-temporal data in real time. In this paper, we propose an efficient approach to label motion stream data in real time with a limited usage of main memory. Based on a set of user-defined motion profiles, each of them specified by multiple representative samples, the currently visible part of an input motion stream is processed by identifying a moderate number of segments of various lengths. These segments are compared to the profiles to measure their similarity. The segments having a high similarity to a given motion profile are annotated with the corresponding label. The proposed approach performs fast, allows profiles to be dynamically changed at runtime, and does not require any learning procedure, in comparison with existing solutions evaluated on real-life data.

Computer-aided analyses of motion capture data require an effective and efficient concept of motion similarity. Traditional methods generally compare motion sequences by applying time-warping techniques to high-dimensional trajectories of joints. An increasing effectiveness of machine-learning techniques, such as deep convolutional neural networks, brings new possibilities for similarity comparison. Inspired by recent advances in neural networks and image processing, we propose new variants of transformation of motion sequences into 2D images. The generated images are used to fine-tune a neural network from which 4,096D features are extracted and compared by a modified Euclidean distance. The proposed concept is not only efficient but also very effective and beats existing methods on a challenging dataset with 130 categories.

The subsequence-matching operation applied to motion capture data searches in long motion sequences to locate their parts that are similar to a query example. An effective and efficient implementation of such operation is valuable to increase reusability and findability of expensively recorded data in the past. This demonstration paper builds on recent advances in the field of motion-data processing and implements them into a single web application that allows users to discover query-similar subsequences. The proposed application does not require any textual annotations nor explicit knowledge of the data and can deal with spatio-temporal variances of human movements. Efficiency and effectiveness can be verified by searching a 12-hour database of motion sequences in real time.

The rapid growth of unstructured data, commonly denoted as the Big Data challenge, requires new technologies that are capable of dealing with complex data objects such as multimedia. In this work, the authors focus on the content-based retrieval approach, which is able to organize such data by exploiting the similarity of data content. In particular, they focus on solutions that are able to combine multiple similarity measures during the query evaluation. The authors introduce a classification of existing approaches and analyze their performance in terms of effectiveness, efficiency, and scalability. Further, they present a novel technique of inherent fusion that combines the efficiency of fast indexed retrieval with the effectiveness of ranking methods. The performance of all discussed methods is evaluated by extensive experiments with user participation.

Abstract The development of motion capturing devices poses new challenges in the exploitation of human‐motion data for various application fields, such as computer animation, visual surveillance, sports, or physical medicine. Recently, a number of approaches dealing with motion data have been proposed, suggesting characteristic motion features to be extracted and compared on the basis of similarity. Unfortunately, almost each approach defines its own set of motion features and comparison methods; thus, it is hard to fairly decide which similarity model is the most suitable for a given kind of human‐motion retrieval application. To cope with this problem, we propose the human motion model evaluator, which is a generic framework for assessing candidate similarity models with respect to the purpose of the target application. The application purpose is specified by a user in form of a representative sample of categorized motion data. Respecting such categorization, the similarity models are assessed from the effectiveness and efficiency points of view using a set of space‐complexity, information‐retrieval, and performance measures. The usability of the framework is demonstrated by case studies of three practical examples of retrieval applications focusing on recognition of actions, detection of similar events, and identification of subjects. Copyright © 2015 John Wiley & Sons, Ltd.

No abstract available.

The current explosion of data accelerated evolution of various content-based indexing techniques that allow to efficiently search in multimedia data such as images. However, index able features must be first extracted from the raw images before the indexing. This necessary step can be very time consuming for large datasets thus parallelization is desirable to speed the process up. In this paper, we experimentally compare two approaches to distribute the task among multiple machines: the Apache Hadoop and the Apache Storm projects.

Effective management of multimedia data is becoming vital for success in the modern era of omnipresent data. Summarization tools, which allow users to quickly get the gist of a given data collection and have proven their usefulness in text domain, are now gaining popularity also in multimedia processing. However, existing algorithms provide visual-only summaries for image collections, which are difficult to index and search. This paper introduces a prototype software tool that automatically creates multi-modal summaries of personal image collections by enriching the visual collage with keyword annotation. The result is presented as a web page that allows users to browse and share the summarized data.

This work targets the problem of search efficiency vs. answer quality of approximate metric-based similarity search. We especially focus on techniques based on recursive Voronoi-like partitioning or, from another perspective, on pivot permutations. These techniques use sets of reference objects (anchors/pivots) to partition the metric space into cells of close data items. Instead of refining the search space by enlarging the anchor set of a single index, we propose to divide a large pivot set into several subsets and build multiple indexes with independent space partitioning; at query time, the overall search costs are also divided among the separate indexes. Our thorough experimental study on three different real datasets uncovers drawbacks of excessive increase of a single pivot set size—such partitioning refinement can be counterproductive beyond a certain number of pivots. Our approach overcomes the root causes of this limitation and increases the answer quality while preserving the search costs. Further, we address the question of robustness of the answer quality, which can be significantly improved by utilization of independent anchor spaces.

The general trend in data management is to outsource data to 3rd party systems that would provide data retrieval as a service. This approach naturally brings privacy concerns about the (potentially sensitive) data. Recently, quite extensive research has been done on privacy-preserving outsourcing of traditional exact-match and keyword search. However, not much attention has been paid to outsourcing of similarity search, which is essential in content-based retrieval in current multimedia, sensor or scientific data. In this paper, the authors propose a scheme of outsourcing similarity search. They define evaluation criteria for these systems with an emphasis on usability, privacy and efficiency in real applications. These criteria can be used as a general guideline for a practical system analysis and we use them to survey and mutually compare existing approaches. As the main result, the authors propose a novel dynamic similarity index EM-Index that works for an arbitrary metric space and ensures data privacy and thus is suitable for search systems outsourced for example in a cloud environment. In comparison with other approaches, the index is fully dynamic (update operations are efficient) and its aim is to transfer as much load from clients to the server as possible.

Unprecedented amounts of digital data are becoming available nowadays, but frequently the data lack some semantic information necessary to effectively organize these resources. For images in particular, textual annotations that represent the semantics are highly desirable. Only a small percentage of images is created with reliable annotations, therefore a lot of effort is being invested into automatic image annotation. In this paper, we address the annotation problem from a general perspective and introduce a new annotation model that is applicable to many text assignment problems. We also provide experimental results from several implemented instances of our model.

The availability of various photo archives and photo sharing systems made similarity searching much more important because the photos are not usually conveniently tagged. So the photos (images) need to be searched by their content. Moreover, it is important not only to compare images with a query holistically but also to locate images that contain the query as their part. The query can be a picture of a person, building, or an abstract object and the task is to retrieve images of the query object but from a different perspective or images capturing a global scene containing the query object. This retrieval is called the sub-image searching. In this paper, we propose an algorithm for retrieving database images by their similarity to and containment of a query. The novelty of it lies in application of a sequence alignment algorithm, which is commonly used in text retrieval. This forms an orthogonal solution to currently used approaches based on inverted files. The proposed algorithm is evaluated on a real-life data set containing photographs where images of logos are searched. It was compared to a state-of-the-art method and the improvement of 20% in average mean precision was obtained.

The recent techniques for approximate similarity search focus on optimizing answer precision/recall and they typically improve the average of these measures over a set of sample queries. However, according to our observation, the recall for particular indexes and queries can fluctuate considerably. In order to stabilize the recall, we propose a query-evaluation model that exploits several variants of the search index. This approach is applicable to a significant subset of current approximate methods with a focus on techniques based purely on metric postulates. Applying this approach to the M-Index structure, we perform extensive measurements on large datasets and we show that this approach has a positive impact on the recall stability and it suppresses the most unsatisfactory cases. Further, the results indicate that the proposed approach can also increase the general average recall for given overall search costs.

We introduce a generic engine for large-scale similarity search and demonstrate it on a set of 100 million Flickr images.

Exploiting the concepts of social networking represents a novel approach to the approximate similarity query processing. We present a metric social network where relations between peers, giving similar results, are established on per-query basis. Based on the universal law of generalization, a new query forwarding algorithm is proposed. The same principle is used to manage query histories of individual peers with the possibility to tune the tradeoff between the extent of the history and the level of the query-answer approximation. All algorithms are tested on real data and real network of computers.

We propose a self-organized and self-adapting system for content-based search in multimedia data. In particular, we build a semantic overlay over an existing peer-to-peer network. The self-organization of the overlay is obtained by using the social-network paradigm. The connections between peers are formed on the basis of a query-answer principle. The knowledge about answers to previous queries is exploited to route queries efficiently. At the same time, a randomized mechanism is used to explore new and unvisited parts of the network. In this way, the self-adaptable and robust system is built. Moreover, the metric space data model is used to achieve extensibility. The proposed concepts are verified on a network consisting of 2,000 peers and indexing 10 million images.

Multi-dimensional data structures are applied in many real index applications, i.e. data mining, indexing multimedia data, indexing of text documents and so on. Many index structures and algorithms have been proposed. There are two major approaches to multi-dimensional indexing: data structures to indexing metric and vector spaces. R-trees, R*-trees and (B)UB-trees are representatives of the vector data structures. These data structures provide efficient processing of many types of queries, i.e. point queries, range queries and so on. As far as the vector data structures are concerned, the range query retrieves all points in defined hyper box in an n-dimensional space. The narrow range query is an important type of the range query. Its processing is inefficient in vector data structures. Moreover, the efficiency decreases as the dimension of the indexed space increases. We depict an application of the signature for more efficient processing of narrow range queries. The approach puts the signature into the multi-dimensional data structures like R-tree or UB-tree but original functionalities are preserved, i.e. the range query algorithm for general range query. The novel data structure is called the signature data structure, e.g., Signature R-tree or Signature UB-tree.

Similarity search structures for metric data typically bound object partitions by ball regions. Since regions can overlap, a relevant issue is to estimate the proximity of regions in order to predict the number of objects in the regions' intersection. This paper analyzes the problem using a probabilistic approach and provides a solution that effectively computes the proximity through realistic heuristics that only require small amounts of auxiliary data. An extensive simulation to validate the technique is provided. An application is developed to demonstrate how the proximity measure can be successfully applied to the approximate similarity search. Search speedup is achieved by ignoring data regions whose proximity to the query region is smaller than a user-defined threshold. This idea is implemented in a metric tree environment for the similarity range and "nearest neighbors" queries. Several measures of efficiency and effectiveness are applied to evaluate proposed approximate search algorithms on real-life data sets. An analytical model is developed to relate proximity parameters and the quality of search. Improvements of two orders of magnitude are achieved for moderately approximated search results. We demonstrate that the precision of proximity measures can significantly influence the quality of approximated algorithms.

We consider the problem of estimating CPU (distance computations) and I/O costs for processing range and k-nearest neighbors queries over metric spaces. Unlike the specific case of vector spaces, where information on data distribution has been exploited to derive cost models for predicting the performance of multi-dimensional access methods, in a generic metric space there is no such a possibility, which makes the problem quite different and requires a novel approach. We insist that the distance distribution of objects can be profitably used to solve the problem, and consequently develop a concrete cost model for the M-tree access method [10]. Our results rely on the assumption that the indexed dataset comes from a metric space which is "homogeneous" enough (in a probabilistic sense) to allow reliable cost estimations even if the distance distribution with respect to a specific query object is unknown. We experimentally validate the model over both real and synthetic datasets, and sho...

Access methods based on signature files can largely benefit from possibilities offered by parallel environments. To this end, an effective declustering strategy that would distribute signatures over a set of parallel independent disks has to be combined with a synergic clustering which is employed to avoid searching the whole signature file while executing a query. This article proposes two parallel signature file organizations, Hamming Filter ( HF ) and Hamming + Filter ( H + F ), whose common declustering strategy is based on error correcting codes , and where clustering is achieved by organizing signatures into fixed-size buckets, each containing signatures sharing the same key value. HF allocates signatures on disks in a static way and works well if a correct relationship holds between the parameters of the code and the size of the file. H + F is a generalization of HF suitable to manage highly dynamic files. It uses a dynamic declustering, obtained through a sequence of codes, and organizes a smooth migration of signatures between disks so that high performance levels are retained regardless of current file size. Theoretical analysis characterizes the best-case, expected, and worst-case behaviors of these organizations. Analytical results are verified by experiments on prototype systems.

We show that performance of some basic methods for the partitioning of signature files, namely Quick Filter and Fixed Prefix, can be easily evaluated by means of a closed formula. The approximation is based on well-known results from probability theory, and, as shown by simulations, introduces no appreciable errors when compared with the exact, cumbersome formulas used so far. Furthermore, we prove that the exact formulas for the two methods coincide. Although this does not imply that the two methods behave in the same way, it sheds light on the way they could be compared.

The retrieval capabilities of the signature file access method have become very attractive for many data processing applications dealing with both formatted and unformatted data. However, performance is still a problem, mainly when large files are used and fast response required. In this paper, a high performance signature file organization is proposed, integrating the latest developments both in storage structure and parallel computing architectures. It combines horizontal and vertical approaches to the signature file fragmentation. In this way, a new, mixed decomposition scheme, particularly suitable for parallel implementation, is achieved. The organization, based on this fragmentation scheme, is called Fragmented Signature File. Performance analysis shows that this organization provides very good and relatively stable performance, covering the full range of possible queries. For the same degree of parallelism, it outperforms any other parallel signature file organization that has been defined so far. The proposed method also has other important advantages concerning processing of dynamic files, adaptability to the number of available processors, load balancing, and, to some extent, fault-tolerant query processing.

The signature file access method has proved to be a convenient indexing technique, in particular for text data Because it can deal with unformatted data, many application domains have shown interest in signature file techniques, e.g., office information systems, statistical and logic databases.We argue that multimedia databases should also take advantage of this method, provided convenient storage structures for organizing signature tiles are available, Our main concern here is the dynamic organization of signatures based on a partitioning paradigm called Quick Filter.A signature file is partitioned by a hashing function and the partitions are orgamzed by linear hashing, Thorough performance evaluation of the new scheme is provided, and it is compared with single-level and multdevel storage structures Results show that quick filter is economical in space and very convenient for applications dealing with large files of dynamic data, and where user queries result in signatures with high weights.These characteristics are particularly interesting for multimedia databases, where integrated access to attributes, text and images must be provided.

A signature file acts as a filtering mechanism to reduce the amount of data that needs to be searched during query evaluation. Even though several techniques for organizing and searching signature files have been proposed in literature, they have serious limitations when applied to multimedia databases, where integrated access methods to text and image content are needed. A new signature technique, called Quick Filter, is proposed in the paper. According to this technique, signatures are divided into partitions, each of which holds signatures sharing the same characteristic key. As a result, it is possible to determine if the signatures in a partition satisfy a query by merely examining the key. Partitions not matching the key need not be searched. This method is based on dynamic hashing since signatures are hashed into partitions according to the keys and the file size, computed algorithmically from the signatures. Implementation of this technique is illustrated using an example and is verified by analytical performance evaluation. The result is a signature technique which satisfies the requirements for access methods in multimedia databases: dynamicity, with respect to insertions and updates, good query processing performance on large databases for high-weight queries.