Local intrinsic dimensionality (LID) provides insight into the behavior of individual training points in deep neural networks, with applications including adversarial detection, prevention of dimensional collapse in self-supervised learning, and identification of untruthful responses from large language models (LLMs). In such contexts, efficient LID estimation has depended on the use of mini-batches, due to the high cost of computing neighborhoods in latent space. However, estimation with respect to small subsets of the training data usually reflects the dimensionality of the global manifold structure rather than the intended local distribution around each point. In this paper, we propose the Nearest Distance Cache (NDC), a method that improves the locality of LID estimation by reusing nearest-neighbor distances observed in past mini-batches. This strategy faces two key challenges: representations evolve over time, and limited memory prevents storing all past distances. To address these, NDC maintains a compact cache of nearest distances per example and uses window-based change detection to discard outdated samples affected by distributional drift. We also evaluate NDC on two tasks: an autoencoder trained on synthetic data with known ground-truth LID, and a ResNet trained on CIFAR-10. Results show that NDC captures local properties of deep representations not revealed by single mini-batch estimates.

Transversely to all multimedia research, the methods and tools are often shared by several MM topics and applications. M4MM aims to foster discussion around fundamental methodologies and tools that are used in various multimedia research topics. To that aim, the technical program of the workshop consists of two keynote speakers, on complementary and very relevant methods and tools for MM, as well as four technical papers. The complete M4MM'22 workshop proceedings are available at: https://dl.acm.org/doi/proceedings/10.1145/3552487

In this study we extract the deep features and investigate the compression of the Mg II k spectral line profiles observed in quiet Sun regions by NASA's IRIS satellite. The data set of line profiles used for the analysis was obtained on April 20th, 2020, at the center of the solar disc, and contains almost 300,000 individual Mg II k line profiles after data cleaning. The data are separated into train and test subsets. The train subset was used to train the autoencoder of the varying embedding layer size. The early stopping criterion was implemented on the test subset to prevent the model from overfitting. Our results indicate that it is possible to compress the spectral line profiles more than 27 times (which corresponds to the reduction of the data dimensionality from 110 to 4) while having a 4 DN (Data Number) average reconstruction error, which is comparable to the variations in the line continuum. The mean squared error and the reconstruction error of even statistical moments sharply decrease when the dimensionality of the embedding layer increases from 1 to 4 and almost stop decreasing for higher numbers. The observed occasional improvements in training for values higher than 4 indicate that a better compact embedding may potentially be obtained if other training strategies and longer training times are used. The features learned for the critical four-dimensional case can be interpreted. In particular, three of these four features mainly control the line width, line asymmetry, and line dip formation respectively. The presented results are the first attempt to obtain a compact embedding for spectroscopic line profiles and confirm the value of this approach, in particular for feature extraction, data compression, and denoising.

The South African research community has strong individual interests in pattern recognition and machine learning, but to date has had limited interactions with the worldwide multimedia research community. In an attempt to redress this, this workshop aims to introduce a selection of South African researchers to the multimedia community, and expose the multimedia community to a range of multimedia-related work, primarily from South Africa.

This article presents an efficient and totally unsupervised content-based similarity search method for multimedia data objects represented by high-dimensional feature vectors. The assumption is that the similarity measure is applicable to feature vectors of arbitrary length. During the offline process, different sets of features are selected by a generalized version of the Laplacian Score in an unsupervised way for individual data objects in the database. Online retrieval is performed by ranking the query object in the feature spaces of candidate objects. Those candidates for which the query object is ranked highly are selected as the query results. The ranking scheme is incorporated into an automated query expansion framework to further improve the semantic quality of the search result. Extensive experiments were conducted on several datasets to show the capability of the proposed method in boosting effectiveness without losing efficiency.

In the U.S., 80% of Medicare spending is for managing patients with multiple coexisting conditions. Predicting potentially correlated diseases for an individual patient and correlated disease progression paths are both important research tasks. For example, obese patients are at an increased risk for developing type-2 diabetes and hypertension. This correlation is called comorbidity relationship. Discovering the comorbidity relationships is complex and difficult due to the limited access to Electronic Health Records by privacy laws. In this paper, we present a framework called Social Data-based Prediction of Incidence and Trajectory to predict potential risks for medical conditions as well as its progression trajectory to identify the comorbidity path. The framework utilizes patients' publicly available social media data and presents a collaborative prediction model to predict the ranked list of potential comorbidity incidences, and a trajectory prediction model to reveal different paths of condition progression. The experimental results show that our framework is able to predict future conditions for online patients with a coverage value of 48% and 75% for a top-20 and a top-100 ranked list, respectively. For risk trajectory prediction, our framework is able to reveal each potential progression trajectory between any two conditions and infer the confidence of the future trajectory, given any observed condition. The predicted trajectories are validated with existing comorbidity relations from the medical literature.

Numerous applications in different fields, such as spatial databases, multimedia databases, data mining, and recommender systems, may benefit from efficient and effective aggregate similarity search, also known as aggregate nearest neighbor (AggNN) search. Given a group of query objects Q, the goal of AggNN is to retrieve the k most similar objects from the database, where the underlying similarity measure is defined as an aggregation (usually sum or max) of the distances between the retrieved objects and every query object in Q. Recently, the problem was generalized so as to retrieve the k objects which are most similar to a fixed proportion of the elements of Q. This variant of aggregate similarity search is referred to as “flexible AggNN”, or FANN. In this work, we propose two approximation algorithms, one for the sum variant of FANN, and the other for the max variant. Extensive experiments are provided showing that, relative to state-of-the-art approaches (both exact and approximate), our algorithms produce query results with good accuracy, while at the same time being very efficient.

Neighborhood graphs are an essential component of many established methods for content-based image retrieval and automated image annotation. The performance of such methods relies heavily on the semantic quality of the graphs, which can be measured as the proportion of neighbors sharing the same class label as their query images. In this paper, we propose a new framework for the efficient construction of K-nearest neighbor (K-NN) graphs based on nearest-neighbor descent (NN-Descent), in which selective sparsification of object feature vectors is interleaved with neighborhood refinement operations in an effort to improve the semantic quality of the result. A local variant of the Laplacian Score is used to identify noisy features with respect to individual images, whose values are then set to 0 (the global mean value after standardization). We show through extensive experiments that our graph construction method is able to increase the proportion of semantically-related images over unrelated images within the neighbor sets.

With more and more multimedia content made available on the Internet, music information retrieval is becoming a critical but challenging research topic, especially for real-time online search of similar songs from websites. In this paper we study how to quickly and reliably retrieve relevant songs from a large-scale dataset of music audio tracks according to melody similarity. Our contributions are two-fold: (i) Compact and accurate representation of audio tracks by exploiting music semantics. Chord progressions are recognized from audio signals based on trained music rules, and the recognition accuracy is improved by multi-probing. A concise chord progression histogram (CPH) is computed from each audio track as a mid-level feature, which retains the discriminative capability in describing audio content. (ii) Efficient organization of audio tracks according to their CPHs by using only one locality sensitive hash table with a tree-structure. A set of dominant chord progressions of each song is used as the hash key. Average degradation of ranks is further defined to estimate the similarity of two songs in terms of their dominant chord progressions, and used to control the number of probing in the retrieval stage. Experimental results on a large dataset with 74,055 music audio tracks confirm the scalability of the proposed retrieval algorithm. Compared to state-of-the-art methods, our algorithm improves the accuracy of summarization and indexing, and makes a further step towards the optimal performance determined by an exhaustive sequence comparison.

The practicality of large-scale image indexing and querying methods depends crucially upon the availability of semantic information. The manual tagging of images with semantic information is in general very labor intensive, and existing methods for automated image annotation may not always yield accurate results. The aim of this paper is to reduce to a minimum the amount of human intervention required in the semantic annotation of images, while preserving a high degree of accuracy. Ideally, only one copy of each object of interest would be labeled manually, and the labels would then be propagated automatically to all other occurrences of the objects in the database. To this end, we propose an influence propagation strategy, SW-KProp , that requires no human intervention beyond the initial labeling of a subset of the images. SW-KProp distributes semantic information within a similarity graph defined on all images in the database: each image iteratively transmits its current label information to its neighbors, and then readjusts its own label according to the combined influences of its neighbors. SW-KProp influence propagation can be efficiently performed by means of matrix computations, provided that pairwise similarities of images are available. We also propose a variant of SW-KProp which enhances the quality of the similarity graph by selecting a reduced feature set for each prelabeled image and rebuilding its neighborhood. The performances of the SW-KProp method and its variant were evaluated against several competing methods on classification tasks for three image datasets: a handwritten digit dataset, a face dataset and a web image dataset. For the digit images, SW-KProp and its variant performed consistently better than the other methods tested. For the face and web images, SW-KProp outperformed its competitors for the case when the number of prelabeled images was relatively small. The performance was seen to improve significantly when the feature selection strategy was applied.

In data mining applications such as subspace clustering or feature selection, changes to the underlying feature set can require the reconstruction of search indices to support fundamental data mining tasks. For such situations, multi-step search approaches have been proposed that can accommodate changes in the underlying similarity measure without the need to rebuild the index. In this paper, we present a heuristic multi-step search algorithm that utilizes a measure of intrinsic dimension, the generalized expansion dimension (GED), as the basis of its search termination condition. Compared to the current state-of-the-art method, experimental results show that our heuristic approach is able to obtain significant improvements in both the number of candidates and the running time, while losing very little in the accuracy of the query results.

Accurate and compact representation of music signals is a key component of large-scale content-based music applications such as music content management and near duplicate audio detection. This problem is not well solved yet despite many research efforts in this field. In this paper, we suggest mid-level summarization of music signals based on chord progressions. More specially, in our proposed algorithm, chord progressions are recognized from music signals based on a supervised learning model, and recognition accuracy is improved by locally probing n-best candidates. By investigating the properties of chord progressions, we further calculate a histogram from the probed chord progressions as a summary of the music signal. We show that the chord progression-based summarization is a powerful feature descriptor for representing harmonic progressions and tonal structures of music signals. The proposed algorithm is evaluated with content-based music retrieval as a typical application. The experimental results on a dataset with more than 70,000 songs confirm that our algorithm can effectively improve summarization accuracy of musical audio contents and retrieval performance, and enhance music retrieval applications on large-scale audio databases.

This paper presents the prototype of a personal photo album manager that we build over three years. It integrates state of the art techniques of both database systems and computer vision to propose to publishers a privacy preserving sharable photo album manager where the publisher decides what each user is allowed to see. In addition, the photo album manager provides tools for an easy semantic annotation, classification and querying of the images.

The aim of this paper is to reduce to a minimum the level of human intervention in the semantic annotation process of images. Ideally, only one copy of each object of interest would be labeled manually, and the labels would then be propagated automatically to all other occurrences of the objects in the database. To that end, we propose a neighbor-based influence propagation approach KProp which builds a voting model and propagates the knowledge associated to some objects to similar objects. We show that KProp can perform efficiently through matrix computations and achieve better performance with fewer labeled examples per object.

The future of multimedia community depends on how the community effectively and efficiently recruits, nurtures and retains young talents. Students tends to decide on their majors based on job opportunities and the main question in every student mind while finishing a degree is "which jobs are out there for me?" In this panel, we have gathered people from both academia and industry to discuss job opportunities and career perceptive. The panel will try to basically answer two main questions: (1) Which are the jobs for the fresh graduates of our community? (2) What are the carrier paths in both academia and industry?

The Recognition by Components(RBC) is a theory in Psychology introduced by Biederman in the late 80s, by which humans perceive scenes through simple 3D objects with regular shapes such as spheres, cubes, cylinders, cones, or wedges, called Geons (geometric ions). Extracting geons from 2D images is a very challenging task as it requires a good segmentation and the recognition of the 3D geons in a 2D space. In this paper, we propose a novel approach for extracting 2D geons from 2D images. The process is composed of three major parts: image preprocessing which includes image background removal and segmentation, arc-geon detection, and polygon-geon detection. We also propose a general procedure for matching the extracted 2D geons to given models for object recognition. Experiment results show that our approach is competitive compared to existing object recognition methodologies in general.

Novel applications such as recommender systems, uncertain databases, and multimedia databases are designed to process similarity queries that produce ranked lists of objects as their results. Similarity queries typically result in disk access latency and incur a substantial computational cost. In this paper, we propose an 'active caching' technique for similarity queries that is capable of synthesizing query results from cached information even when the required result list is not explicitly stored in the cache. Our solution, the Cache Estimated Significance (CES) model, is based on shared-neighbor similarity measures, which assess the strength of the relationship between two objects as a function of the number of other objects in the common intersection of their neighborhoods. The proposed method is general in that it does not require that the features be drawn from a metric space, nor does it require that the partial orders induced by the similarity measure be monotonic. Experimental results on real data sets show a substantial cache hit rate when compared with traditional caching approaches.

In this paper we propose PARINET, a new access method to efficiently retrieve the trajectories of objects moving in networks. The structure of PARINET is based on a combination of graph partitioning and a set of composite B+-tree local indexes. PARINET is designed for historical data and relies on the distribution of the data over the network as for historical data, the data distribution is known in advance. Because the network can be modeled using graphs, the partitioning of the trajectory data is based on graph partitioning theory and can be tuned for a given query load. The data in each partition is indexed on the time component using B+-trees. We study different types of queries, and provide an optimal configuration for several scenarios. PARINET can easily be integrated into any RDBMS, which is an essential asset particularly for industrial or commercial applications. The experimental evaluation under an off-the-shelf DBMS shows that PARINET is robust. It also significantly outperforms both MON-tree and another R-tree based access method which are the reference indexing techniques for in-network trajectory databases.

In order to improve the reliability and the scalability of content-based retrieval of variant audio tracks from large music databases, we suggest a new multi-stage LSH scheme that consists in (i) extracting compact but accurate representations from audio tracks by exploiting the LSH idea to summarize audio tracks, and (ii) adequately organizing the resulting representations in LSH tables, retaining almost the same accuracy as an exact kNN retrieval. In the first stage, we use major bins of successive chroma features to calculate a multi-probe histogram (MPH) that is concise but retains the information about local temporal correlations. In the second stage, based on the order statistics (OS) of the MPH, we propose a new LSH scheme, OS-LSH, to organize and probe the histograms. The representation and organization of the audio tracks are storage efficient and support robust and scalable retrieval. Extensive experiments over a large dataset with 30,000 real audio tracks confirm the effectiveness and efficiency of the proposed scheme.

In this paper we study the problem of detecting and grouping multi-variant audio tracks in large audio datasets. To address this issue, a fast and reliable retrieval method is necessary. But reliability requires elaborate representations of audio content, which challenges fast retrieval by similarity from a large audio database. To find a better tradeoff between retrieval quality and efficiency, we put forward an approach relying on local summarization and multi-level Locality-Sensitive Hashing (LSH). More precisely, each audio track is divided into multiple Continuously Correlated Periods (CCP) of variable length according to spectral similarity. The description for each CCP is calculated based on its Weighted Mean Chroma (WMC). A track is thus represented as a sequence of WMCs. Then, an adapted two-level LSH is employed for efficiently delineating a narrow relevant search region. The "coarse" hashing level restricts search to items having a non-negligible similarity to the query. The subsequent, "refined" level only returns items showing a much higher similarity. Experimental evaluations performed on a real multi-variant audio dataset confirm that our approach supports fast and reliable retrieval of audio track variants.

Recommender systems aim to substantially reduce information overload by suggesting lists of similar items that users may find interesting.Caching has been a useful technique for reducing stress on limited resources and improving response time. In this paper, we propose an 'active caching' technique for recommender systems based on a partial order approach that not only benefits from popularity and temporal locality, but also exploits spatial locality. This approach allows the processing of answers to neighboring non-cached queries in addition to the reporting of cached query results. Test results for several data sets and recommendation techniques show substantial improvement in the cache hit ratio and computational costs, while achieving reasonable recall rates.

We develop a content-based audio COver Song IdeNtification (COSIN) system to detect/group cover songs.The COSIN takes music audio content as input and performs similarity searching to locate variants of the input (i.e., cover versions). Identified cover songs are returned in the rank order according to their similarity to the input.The COSIN also incorporates a set of tools to evaluate retrieval performance so researchers can explore different retrieval schemes and parameters (e.g. recall, precision).The COSIN utilizes a suite of techniques to detect cover songs including: Pitch + Dynamic Programming (DP), Chroma + DP, and Semantic Feature Summarization (SFS) + Hash-Based Approximate Matching (HBAM). Demonstration system shows that COSIN is a very potential music content retrieval tool. Running some music retrieval schemes on COSIN platform, recent experiments with SFS + LSH Variants demonstrate a nicely balanced efficiency (search speed) v. performance (search accuracy) tradeoff.

The recent proliferation of XML-based standards and technologies for managing data on the Web demonstrates the need for effective and efficient management of tree-structured data. Querying tree-structured data is a challenging issue due to the diversity of the structural aspect in the same or in different trees. In this paper, we show how to evaluate queries on tree-structured data, called value trees. The formulation of these queries does not depend on the structure of a particular value tree. Our approach exploits semantic information provided by dimension graphs. Dimension graphs are semantically rich constructs that abstract the structural information of the value trees. We show how dimension graphs can be used to query efficiently value trees in the presence of structural differences and irregularities. Value trees and their dimension graphs are represented as XML documents. We present a method for transforming queries to XPath expressions to be evaluated on the XML documents. We also provide conditions for identifying strongly and weakly unsatisfiable queries. Finally, we conducted various experiments to compare our method for evaluating queries with one that does not exploit dimension graphs. Our results demonstrate the superiority of our approach.

An important consideration in similarity-based retrieval of moving object trajectories is the definition of a distance function. The existing distance functions are usually sensitive to noise, shifts and scaling of data that commonly occur due to sensor failures, errors in detection techniques, disturbance signals, and different sampling rates. Cleaning data to eliminate these is not always possible. In this paper, we introduce a novel distance function, Edit Distance on Real sequence (EDR) which is robust against these data imperfections. Analysis and comparison of EDR with other popular distance functions, such as Euclidean distance, Dynamic Time Warping (DTW), Edit distance with Real Penalty (ERP), and Longest Common Subsequences (LCSS), indicate that EDR is more robust than Euclidean distance, DTW and ERP, and it is on average 50% more accurate than LCSS. We also develop three pruning techniques to improve the retrieval efficiency of EDR and show that these techniques can be combined effectively in a search, increasing the pruning power significantly. The experimental results confirm the superior efficiency of the combined methods.

Many analytical or computational applications especially legacy systems create documents and display screens in response to user queries "dynamically" or in "real time". These "virtual documents" do not exist in advance and thus hypermedia features must be generated "just in time" - automatically and dynamically. Additionally the hypermedia features may have to cause target documents to be generated or re-generated. This paper focuses on the specific challenges faced in hypermedia support for virtual documents of dynamic hypermedia functionality dynamic regeneration and dynamic anchor re-identification and re-location. It presents a prototype called JHE (Just-in-time Hypermedia Engine) to support just-in-time hypermedia across third party applications with dynamic content and discusses issues prompted by this research.

This work addresses the challenge of extracting structure in educational and training media based on the type of material that is presented during lectures and training sessions. The narrative structure that arises out of a use of different types of presentation content such as slides, web pages, and white board writings is useful in segmenting an educational video for easy content access and nonlinear browsing of the material presented. Automatically detecting sections of videos as delineated by the use of supplementary teaching/instructional visual aids allows for structuralizing educational video with high level of semantics, and provides a concise means for organizing learning content according to the needs of different users in e-learning scenarios. Experiments on the videos from classrooms show encouraging results with discriminating different narrative sections in the proposed presented-material based video structuralization scheme.

In recent years, a lot of research effort has been dedicated to the management of quality of service (QoS), mainly in the fields of telecommunication networks and multimedia systems. Emerging applications such as electronic commerce, health-care applications, digital publishing or data mining also have requirements regarding the quality of service, the cost of service, the quality of data to be delivered, the accuracy and precision of the retrieved data. These examples show the need to consider the concept of QoS from a broader perspective, requiring the collaboration of all the distributed system components involved. In this paper, we propose an approach to integrate user-defined QoS requirements, together with the dynamic properties of the system components involved, into a distributed query processing environment. We then propose a query optimization strategy in which multiple goals may be considered with separate cost models. Furthermore, we discuss some experiment results confirming the effectiveness of our approach.

In the DISIMA system, an image is composed of salient objects that are regions of interest in the image. A salient object has some syntactic properties (shape, color, textures) on which some similarity searches are defined. In addition, a global multi-precision image similarity based on multi-scale color histograms allows similarity queries on images and sub-images.

Most image database prototypes and products focus mainly on similarity searches over syntactic features of images. DISIMA aims at providing querying on both syntactic and semantic features of images. The content of an image is viewed as a set of salient objects (regions of interest). Salient objects are organized into two levels: physical salient objects that store syntactic features and logical salient objects that give the semantics. DISIMA integrates a declarative query language (MOQL) and a visual query language (VisualMOQL).

No abstract available.

Spatial joins are join operations that involve spatial data types and operators. Spatial access methods are often used to speed up the computation of spatial joins. This paper addresses the issue of benchmarking spatial join operations. For this purpose, we first present a WWW-based benchmark generator to produce sets of rectangles. Using a Web browser, experimenters can specify the number of rectangles in a sample, as well as the statistical distributions of their sizes, shapes, and locations. Second, using the generator and a well-defined set of statistical models we define several tests to compare the performance of three spatial join algorithms: nested loop, scan-and-index, and synchronized tree traversal. We also added two real-life data sets from the Sequoia 2000 storage benchmark. Our results show that the relative performance of the different techniques mainly depends on the selectivity factor of the join predicate. All of the statistical models and algorithms are available on the Web, which allows for easy verification and modification of our experiments.