Multimodal deep-learning models power interactive video retrieval by ranking keyframes in response to textual queries. Despite these advances, users must still browse ranked candidates manually to locate a target. Keyframe arrangement within the search grid highly affects browsing effectiveness and user efficiency, yet remains underexplored. We report a study with 49 participants evaluating seven keyframe layouts for the Visual Known-Item Search task. Beyond efficiency and accuracy, we relate browsing phenomena, such as overlooks, to layout characteristics. Our results show that a video-grouped layout is the most efficient, while a four-column, rank-preserving grid achieves the highest accuracy. Sorted grids reveal potential and trade-offs, enabling rapid scanning of uninteresting regions but down-ranking relevant targets to less prominent positions, delaying first arrival times and increasing overlooks. These findings motivate hybrid designs that preserve positions of top-ranked items while sorting or grouping the remainder, and offer guidance for searching in grids beyond video retrieval.

In 2026, the Multimedia Modeling conference in Prague hosted the fifteenth edition of the Video Browser Showdown (VBS) competition. Yet, for the first time, two participating systems implemented full-scale interaction logging frameworks, enabling a detailed analysis of the search process beyond traditional score-based evaluation. In this paper, both systems are introduced and described with a focus on their user interactions. To enable compact presentation and analysis of logs, all interaction types are further grouped into more abstract events, forming an interaction taxonomy hierarchy. Finally, we reveal the applied search strategies and analyze which factors drive success and failure. The results reveal a clear dominance of iterative, high-frequency text query reformulation with result set inspection, leveraging the power of modern CLIP-based models across most competition categories. In around 10% of cases, users also relied on advanced system features to achieve good performance at VBS, mostly on challenging homogeneous datasets.

Searching in highly homogeneous video domains is challenging, especially when relying solely on human memory. This difficulty arises because homogeneous content often requires domain-specific vocabulary to describe effectively, and a single text label might fit a substantial subset of the database. This paper investigates supplementing text queries with spatial location information to better address specific search intents—a strategy applicable when users possess strong visual memory of a target object, or have external knowledge of its position. To process this location information effectively, we formally define and evaluate static grid and dynamic segmentation strategies for video frame partitioning. Furthermore, we present a large-scale cognitive user study involving 220 participants, designed to simulate realistic memory constraints of Known-Item Search (KIS) tasks commonly found in interactive retrieval benchmarks. The study utilizes standard working memory interference techniques, comprising a target exposure phase, a distraction period, and subsequent query specification from memory. These queries are then evaluated against the proposed spatial retrieval models to determine how human spatial memory decay impacts retrieval effectiveness. Our results reveal that while dynamic segmentation models achieve the highest theoretical retrieval bounds under perfect conditions, their strict geometric boundaries are severely affected by human memory decay. Consequently, static overlapping grids demonstrate high robustness, outperforming dynamic models under more realistic, memory-driven search constraints. Finally, our experiments show that the observed spatial annotation perturbations can be modeled using a four-dimensional Kernel Density Estimation (KDE) method, enabling the simulation of realistic human memory decay on ideal bounding boxes.

For the seventh time since 2018, the Lifelog Search Challenge (LSC) benchmarked interactive lifelog search systems in a live challenge. The LSC goal is to comparatively evaluate system capabilities to access large multimodal lifelogs comprising hundreds of thousands of records. LSC'24 attracted an unprecedented record number of twenty-one participating teams, where each team proposes innovative ideas implemented to new or already established interactive lifelog retrieval systems. The benchmark was organised in front of a live audience at the LSC workshop at ACM ICMR'24 in Phuket, Thailand. This short paper summarises the LSC workshop setting and presents the participating lifelog search systems.

Deep learning has revolutionized multimedia retrieval, yet effectively searching within large video collections remains a complex challenge. This paper focuses on the design and evaluation of known-item search systems, leveraging the strengths of CLIP-based deep neural networks for ranking. At events like the Video Browser Showdown, these models have shown promise in effectively ranking the video frames. While ranking models can be pre-selected automatically based on a benchmark collection, the selection of an optimal browsing interface, crucial for refining top-ranked items, is complex and heavily influenced by user behavior. Our study addresses this by presenting an eye tracking-based analysis of user interaction with different image grid layouts. This approach offers novel insights into search patterns and user preferences, particularly examining the trade-off between displaying fewer but larger images versus more but smaller images. Our findings reveal a preference for grids with fewer images and detail how image similarity and grid position affect user search behavior. These results not only enhance our understanding of effective video retrieval interface design but also set the stage for future advancements in the field.

Although automatic shot transition detection approaches are already investigated for more than two decades, an effective universal human-level model was not proposed yet. Even for common shot transitions like hard cuts or simple gradual changes, the potential diversity of analyzed video contents may still lead to both false hits and false dismissals. Recently, deep learning-based approaches significantly improved the accuracy of shot transition detection using 3D convolutional architectures and artificially created training data. Nevertheless, one hundred percent accuracy is still an unreachable ideal. In this paper, we share the current version of our deep network TransNet V2 that reaches state-of-the-art performance on respected benchmarks. A trained instance of the model is provided so it can be instantly utilized by the community for a highly efficient analysis of large video archives. Furthermore, the network architecture, as well as our experience with the training process, are detailed, including simple code snippets for convenient usage of the proposed model and visualization of results.

Different task interpretations are a highly undesired element in interactive video retrieval evaluations. When a participating team focuses partially on a wrong goal, the evaluation results might become partially misleading. In this paper, we propose a process for refining known-item and open-set type queries, and preparing the assessors that judge the correctness of submissions to open-set queries. Our findings from recent years reveal that a proper methodology can lead to objective query quality improvements and subjective participant satisfaction with query clarity.

For the sixth time since 2018, the Lifelog Search Challenge (LSC) was organized as a comparative benchmarking exercise for various interactive lifelog search systems. The goal of this international competition is to test system capabilities to access large multimodal lifelogs. LSC’23 attracted twelve participanting teams, each of whom had developed a competitive interactive lifelog retrieval system. The benchmark was organized in front of live audience at the LSC workshop at ACM ICMR’23. As in previous editions, this introductory paper presents the LSC workshop and introduces the participating lifelog search systems.

For the fifth time since 2018, the Lifelog Search Challenge (LSC) facilitated a benchmarking exercise to compare interactive search systems designed for multimodal lifelogs. LSC'22 attracted nine participating research groups who developed interactive lifelog retrieval systems enabling fast and effective access to lifelogs. The systems competed in front of a hybrid audience at the LSC workshop at ACM ICMR'22. This paper presents an introduction to the LSC workshop, the new (larger) dataset used in the competition, and introduces the participating lifelog search systems.

During the last 10 years of Video Browser Showdown (VBS), there were many different approaches tested for known-item search and ad-hoc search tasks. Undoubtedly, teams incorporating state-of-the-art models from the machine learning domain had an advantage over teams focusing just on interactive interfaces. On the other hand, VBS results indicate that effective means of interaction with a search system is still necessary to accomplish challenging search tasks. In this tutorial, we summarize successful deep models tested at the Video Browser Showdown as well as interfaces designed on top of corresponding distance/similarity spaces. Our broad experience with competition organization and evaluation will be presented as well, focusing on promising findings and also challenging problems from the most recent iterations of the Video Browser Showdown.

The retrieval of multimedia content remains a difficult problem where a high accuracy or specificity can often only be achieved interactively, with a user working closely and iteratively with a retrieval system. While there exist several venues for the exchange of insights in the area of information retrieval in general and multimedia retrieval specifically, there is little discussion on such interactive retrieval approaches. The Workshop on Interactive Multimedia Retrieval offers such a venue. Held for the 2nd time in 2022, it attracted a diverse set of contributions, six of which were accepted for presentation. The following provides a brief overview of the workshop itself as well as the contributions of 2022.

The Lifelog Search Challenge (LSC) is an annual benchmarking challenge for comparing approaches to interactive retrieval from multi-modal lifelogs. LSC'21, the fourth challenge, attracted sixteen participants, each of which had developed interactive retrieval systems for large multimodal lifelogs. These interactive retrieval systems participated in a comparative evaluation in front of an online live-audience at the LSC workshop at ACM ICMR'21. This overview presents the motivation for LSC'21, the lifelog dataset used in the competition, and the participating systems.

Despite the fact that automatic content analysis has made remarkable progress over the last decade - mainly due to significant advances in machine learning - interactive video retrieval is still a very challenging problem, with an increasing relevance in practical applications. The Video Browser Showdown (VBS) is an annual evaluation competition that pushes the limits of interactive video retrieval with state-of-the-art tools, tasks, data, and evaluation metrics. In this paper, we analyse the results and outcome of the 8th iteration of the VBS in detail. We first give an overview of the novel and considerably larger V3C1 dataset and the tasks that were performed during VBS 2019. We then go on to describe the search systems of the six international teams in terms of features and performance. And finally, we perform an in-depth analysis of the per-team success ratio and relate this to the search strategies that were applied, the most popular features, and problems that were experienced. A large part of this analysis was conducted based on logs that were collected during the competition itself. This analysis gives further insights into the typical search behavior and differences between expert and novice users. Our evaluation shows that textual search and content browsing are the most important aspects in terms of logged user interactions. Furthermore, we observe a trend towards deep learning based features, especially in the form of labels generated by artificial neural networks. But nevertheless, for some tasks, very specific content-based search features are still being used. We expect these findings to contribute to future improvements of interactive video search systems.

Comprehensive and fair performance evaluation of information retrieval systems represents an essential task for the current information age. Whereas Cranfield-based evaluations with benchmark datasets support development of retrieval models, significant evaluation efforts are required also for user-oriented systems that try to boost performance with an interactive search approach. This article presents findings from the 9th Video Browser Showdown, a competition that focuses on a legitimate comparison of interactive search systems designed for challenging known-item search tasks over a large video collection. During previous installments of the competition, the interactive nature of participating systems was a key feature to satisfy known-item search needs, and this article continues to support this hypothesis. Despite the fact that top-performing systems integrate the most recent deep learning models into their retrieval process, interactive searching remains a necessary component of successful strategies for known-item search tasks. Alongside the description of competition settings, evaluated tasks, participating teams, and overall results, this article presents a detailed analysis of query logs collected by the top three performing systems, SOMHunter, VIRET, and vitrivr. The analysis provides a quantitative insight to the observed performance of the systems and constitutes a new baseline methodology for future events. The results reveal that the top two systems mostly relied on temporal queries before a correct frame was identified. An interaction log analysis complements the result log findings and points to the importance of result set and video browsing approaches. Finally, various outlooks are discussed in order to improve the Video Browser Showdown challenge in the future.

The Lifelog Search Challenge (LSC) is an annual comparative benchmarking activity for comparing approaches to interactive retrieval from multi-modal lifelogs. LSC'20, the third such challenge, attracts fourteen participants with their interactive lifelog retrieval systems. These systems are comparatively evaluated in front of a live-audience at the LSC workshop at ACM ICMR'20 in Dublin, Ireland. This overview motivates the challenge, presents the dataset and system configuration used in the challenge, and briefly presents the participating teams.

Searching for memorized images in large datasets (known-item search) is a challenging task due to a limited effectiveness of retrieval models as well as limited ability of users to formulate suitable queries and choose an appropriate search strategy. A popular option to approach the task is to automatically detect semantic concepts and rely on interactive specification of keywords during the search session. Nonetheless, employed instances of such search models are often set arbitrarily in existing KIS systems as comprehensive evaluations with reals users are time demanding. This paper envisions and investigates an option to simulate keyword queries in a selected "toy'' (yet competitive) keyword search model relying on a deep image classification network. Specifically, two properties of such keyword-based model are experimentally investigated with our known-item search benchmark dataset: which output transformation and ranking models are effective for the utilized classification model and whether there are some options for simulations of keyword queries. In addition to the main objective, the paper inspects also the effect of interactive query reformulations for the considered keyword search model.

In the last decade, the Video Browser Showdown (VBS) became a comparative platform for various interactive video search tools competing in selected video retrieval tasks. However, the participation of new teams with an own, novel tool is prohibitively time-demanding because of the large number and complexity of components required for constructing a video search system from scratch. To partially alleviate this difficulty, we provide an open-source version of the lightweight known-item search system SOMHunter that competed successfully at VBS 2020. The system combines several features for text-based search initialization and browsing of large result sets; in particular a variant of W2VV++ model for text search, temporal queries for targeting sequences of frames, several types of displays including the eponymous self-organizing map view, and a feedback-based approach for maintaining the relevance scores inspired by PICHunter. The minimalistic, easily extensible implementation of SOMHunter should serve as a solid basis for constructing new search systems, thus facilitating easier exploration of new video retrieval ideas.

As reported by respected evaluation campaigns focusing both on automated and interactive video search approaches, deep learning started to dominate the video retrieval area. However, the results are still not satisfactory for many types of search tasks focusing on high recall. To report on this challenging problem, we present two orthogonal task-based performance studies centered around the state-of-the-art W2VV++ query representation learning model for video retrieval. First, an ablation study is presented to investigate which components of the model are effective in two types of benchmark tasks focusing on high recall. Second, interactive search scenarios from the Video Browser Showdown are analyzed for two winning prototype systems implementing a selected variant of the model and providing additional querying and visualization components. The analysis of collected logs demonstrates that even with the state-of-the-art text search video retrieval model, it is still auspicious to integrate users into the search process for task types, where high recall is essential.

The Video Browser Showdown (VBS) has influenced the Multimedia community already for 10 years now. More than 30 unique teams from over 21 countries participated in the VBS since 2012 already. In 2021, we are celebrating the 10th anniversary of VBS, where 17 international teams compete against each other in an unprecedented contest of fast and accurate multimedia retrieval. In this tutorial we discuss the motivation and details of the VBS contest, including its history, rules, evaluation metrics, and achievements for multimedia retrieval. We talk about the properties of specific VBS retrieval systems and their unique characteristics, as well as existing open-source tools that can be used as a starting point for participating for the first time. Participants of this tutorial get a detailed understanding of the VBS and its search systems, and see the latest developments of interactive video retrieval.

Known-item search in large video collections still represents a challenging task for current video retrieval systems that have to rely both on state-of-the-art ranking models and interactive means of retrieval. We present a general overview of the current version of the VIRET tool, an interactive video retrieval system that successfully participated at several international evaluation campaigns. The system is based on multi-modal search and convenient inspection of results. Based on collected query logs of four users controlling instances of the tool at the Video Browser Showdown 2019, we highlight query modification statistics and a list of successful query formulation strategies. We conclude that the VIRET tool represents a competitive reference interactive system for effective known-item search in one thousand hours of video.

We present a tutorial focusing on video retrieval tasks, where state-of-the-art deep learning approaches still benefit from interactive decisions of users. The tutorial covers general introduction to the interactive video retrieval research area, state-of-the-art video retrieval systems, evaluation campaigns and recently observed results. Moreover, a significant part of the tutorial is dedicated to a practical exercise with three selected state-of-the-art systems in the form of an interactive video retrieval competition. Participants of this tutorial will gain a practical experience and also a general insight of the interactive video retrieval topic, which is a good start to focus their research on unsolved challenges in this area.

Searching for one particular scene in a large video collection (known-item search) represents a challenging task for video retrieval systems. According to the recent results reached at evaluation campaigns, even respected approaches based on machine learning do not help to solve the task easily in many cases. Hence, in addition to effective automatic multimedia annotation and embedding, interactive search is recommended as well. This paper presents a comprehensive description of an interactive video retrieval framework VIRET that successfully participated at several recent evaluation campaigns. Utilized video analysis, feature extraction and retrieval models are detailed as well as several experiments evaluating effectiveness of selected system components. The results of the prototype at the Video Browser Showdown 2019 are highlighted in connection with an analysis of collected query logs. We conclude that the framework comprise a set of effective and efficient models for most of the evaluated known-item search tasks in 1000 hours of video and could serve as a baseline reference approach. The analysis also reveals that the result presentation interface needs improvements for better performance of future VIRET prototypes.

This work summarizes the findings of the 7th iteration of the Video Browser Showdown (VBS) competition organized as a workshop at the 24th International Conference on Multimedia Modeling in Bangkok. The competition focuses on video retrieval scenarios in which the searched scenes were either previously observed or described by another person (i.e., an example shot is not available). During the event, nine teams competed with their video retrieval tools in providing access to a shared video collection with 600 hours of video content. Evaluation objectives, rules, scoring, tasks, and all participating tools are described in the article. In addition, we provide some insights into how the different teams interacted with their video browsers, which was made possible by a novel interaction logging mechanism introduced for this iteration of the VBS. The results collected at the VBS evaluation server confirm that searching for one particular scene in the collection when given a limited time is still a challenging task for many of the approaches that were showcased during the event. Given only a short textual description, finding the correct scene is even harder. In ad hoc search with multiple relevant scenes, the tools were mostly able to find at least one scene, whereas recall was the issue for many teams. The logs also reveal that even though recent exciting advances in machine learning narrow the classical semantic gap problem, user-centric interfaces are still required to mediate access to specific content. Finally, open challenges and lessons learned are presented for future VBS events.

In this tutorial we discuss interactive video search tools and methods, review their need in the age of deep learning, and explore video and multimedia search challenges and their role as evaluation benchmarks in the field of multimedia information retrieval. We cover three different campaigns (TRECVID, Video Browser Showdown, and the Lifelog Search Challenge), discuss their goals and rules, and present their achieved findings over the last half-decade. Moreover, we talk about datasets, tasks, evaluation procedures, and examples of interactive video search tools, as well as how they evolved over the years. Participants of this tutorial will be able to gain collective insights from all three challenges and use them for focusing their research efforts on outstanding problems that still remain unsolved in this area.

The last decade has seen innovations that make video recording, manipulation, storage, and sharing easier than ever before, thus impacting many areas of life. New video retrieval scenarios emerged as well, which challenge the state-of-the-art video retrieval approaches. Despite recent advances in content analysis, video retrieval can still benefit from involving the human user in the loop. We present our experience with a class of interactive video retrieval scenarios and our methodology to stimulate the evolution of new interactive video retrieval approaches. More specifically, the video browser showdown evaluation campaign is thoroughly analyzed, focusing on the years 2015-2017. Evaluation scenarios, objectives, and metrics are presented, complemented by the results of the annual evaluations. The results reveal promising interactive video retrieval techniques adopted by the most successful tools and confirm assumptions about the different complexity of various types of interactive retrieval scenarios. A comparison of the interactive retrieval tools with automatic approaches (including fully automatic and manual query formulation) participating in the TRECVID 2016 ad hoc video search task is discussed. Finally, based on the results of data analysis, a substantial revision of the evaluation methodology for the following years of the video browser showdown is provided.

In this demo paper, we present a prototype web application of a product search engine of a fashion e-shop. Although e-shop products consist of full-text description, relational attributes (e.g., price, type, size, color, etc.) as well as visual information (product photo), traditional search engines in e-shops only provide full-text and relational attributes for product filtering. In our retrieval model, we incorporate also the visual information into the search by extracting visual-semantic features using deep convolutional neural networks. Furthermore, visual exploration of the product space using the visual-semantic features (multi-example queries) is used to dynamically discover latent visual attributes that could enhance the original relational schema by fuzzy attributes (e.g., a floral pattern in product). In the demo, we show how these latent attributes could be used to recommend the user preferred products and even outfits (e.g., shoes, bag, jacket) that fit a certain visual style.

Interactive video retrieval tools developed over the past few years are emerging as powerful alternatives to automatic retrieval approaches by giving the user more control as well as more responsibilities. Current research tries to identify the best combinations of image, audio and text features that combined with innovative UI design maximize the tools performance. We present the last installment of the Video Browser Showdown 2015 which was held in conjunction with the International Conference on MultiMedia Modeling 2015 (MMM 2015) and has the stated aim of pushing for a better integration of the user into the search process. The setup of the competition including the used dataset and the presented tasks as well as the participating tools will be introduced . The performance of those tools will be thoroughly presented and analyzed. Interesting highlights will be marked and some predictions regarding the research focus within the field for the near future will be made.

In this demo paper, we present a video retrieval and browsing tool inspired by the natural human ability to memorize visual stimuli of color regions in video frames. Our tool utilizes feature signatures that can be used to represent both significant color regions in the key-frames and simple query sketches. As recently shown at the video browser showdown, such simple representation enables both effective end efficient interactive retrieval and browsing in video.

In this demo paper, we focus on the dynamic multimedia exploration techniques which are an intuitive, effective and entertaining way to present a pre-selected subset of a multimedia database to the users. More specifically, we present an exploration schema employing a similarity model based on SIFT descriptors that can be used to explore image database according to regions in the images. We also provide a simple mechanism to reduce the number of nonrelevant SIFT descriptors in the query image. The reduction of SIFTs in the query image improves the speed and fluency of the exploration process as demonstrated in our demo application.

In this paper, we present the vision of the usage of an object-based video data storage format for similarity search. The efficient (fast) and effective (accurate) search in video streams is an ongoing and still unsolved problem. Using an object-based format of multimedia data, all the information that is needed to answer queries is already available in a machine accessible format. This way, the process of creating (video) descriptors as well as the similarity search becomes easier, because the data is already organized in a manner that allows fast access to specific information. To demonstrate the concept of similarity search process using the object-based 3D video format, we present experiments conducted on generated clouds of points (an abstraction of 3D video data).

We present an image meta-search engine that allows content-based exploration of the results obtained from various sources (mostly based on keyword query). The online feature extraction and the particle physics model are the two key features of our demo application that shows very promising results.

The caching of accessed disk pages has been successfully used for decades in database technology, resulting in effective amortization of I/O operations needed within a stream of query or update requests. However, in modern complex databases, like multimedia databases, the I/O cost becomes a minor performance factor. In particular, metric access methods (MAMs), used for similarity search in complex unstructured data, have been designed to minimize rather the number of distance computations than I/O cost (when indexing or querying). Inspired by I/O caching in traditional databases, in this paper we introduce the idea of distance caching for usage with MAMs—a novel approach to streamline similarity search. As a result, we present the D-cache, a main-memory data structure which can be easily implemented into any MAM, in order to spare the distance computations spent by queries/updates. In particular, we have modified two state-of-the-art MAMs to make use of D-cache—the M-tree and Pivot tables. Moreover, we present the D-file, an index-free MAM based on simple sequential search augmented by D-cache. The experimental evaluation shows that performance gain achieved due to D-cache is significant for all the MAMs, especially for the D-file.

The Signature Quadratic Form Distance on feature signatures represents a flexible distance-based similarity model for effective content-based multimedia retrieval. Although metric indexing approaches are able to speed up query processing by two orders of magnitude, their applicability to large-scale multimedia databases containing billions of images is still a challenging issue. In this paper, we propose the utilization of GPUs for efficient query processing with the Signature Quadratic Form Distance. We show how to process multiple distance computations in parallel and demonstrate efficient query processing by comparing many-core GPU with multi-core CPU implementations.

The quadratic form distance (QFD) has been utilized as an effective similarity function in multimedia retrieval, in particular, when a histogram representation of objects is used. Unlike the widely used Euclidean distance, the QFD allows to arbitrarily correlate the histogram bins (dimensions), allowing thus to better model the similarity between histograms. However, unlike Euclidean distance, which is of linear time complexity, the QFD requires quadratic time to evaluate the similarity of two objects. In consequence, indexing and querying a database under QFD are expensive operations. In this paper we show that, given static correlations between dimensions, the QFD space can be transformed into an equivalent Euclidean space. Thus, the overall complexity of indexing and searching in the QFD similarity model can be reduced qualitatively. Besides the theoretical time complexity analysis of our approach applied to several metric access methods, in experimental evaluation we show the real-time speedup on a real-world image database.

The Signature Quadratic Form Distance has been introduced as an adaptive similarity measure coping with flexible content representations of various multimedia data. Although the Signature Quadratic Form Distance has shown good retrieval performance with respect to their qualities of effectiveness and efficiency, its applicability to index structures remains a challenging issue due to its dynamic nature. In this paper, we investigate the indexability of the Signature Quadratic Form Distance regarding metric access methods. We show how the distance's inherent parameters determine the indexability and analyze the relationship between effectiveness and efficiency on numerous image databases.

The Earth Mover's Distance is a well-known distance measure employed in various domains, especially for content-based retrieval in multimedia databases. However, the distance evaluation is a considerably expensive task and thus for large multimedia databases, efficient query processing becomes a challenging problem. In this paper, we introduce a parameterized version of the Earth Mover's Distance that can be used by database experts to change the distance distribution in the derived distance space in order to improve the indexability. We empirically show, that we can significantly improve the indexability of the distance space and that we can tune the retrieval quality by adapting the parameterized Earth Mover's Distance.

The signature quadratic form distance has been introduced as an adaptive similarity measure coping with flexible content representations of multimedia data. While this distance has shown high retrieval quality, its high computational complexity underscores the need for efficient search methods. Recent research has shown that a huge improvement in search efficiency is achieved when using metric indexing. In this paper, we analyze the applicability of Ptolemaic indexing to the signature quadratic form distance. We show that it is a Ptolemaic metric and present an application of Ptolemaic pivot tables to image databases, resolving queries nearly four times as fast as the state-of-the-art metric solution, and up to 300 times as fast as sequential scan.

The pivot tables are a popular metric access method, primarily designed as a main-memory index structure. It has been many times proven that pivot tables are very efficient in terms of distance computations, hence, when assuming a computationally expensive distance function. However, for cheaper distance functions and/or huge datasets exceeding the capacity of the main memory, the classic pivot tables become inefficient. The situation is dramatically changing with the rise of solid state disks that decrease the seek times, so we can now efficiently access also small fragments of data stored in the secondary memory. In this paper, we propose a persistent variant of pivot tables, the clustered pivot tables, focusing on minimizing I/O cost when accessing small data blocks (a few kilobytes). The clustered pivot tables employs a preprocessing method utilizing the M-tree in the role of clustering technique and an original heuristic for I/O-optimized kNN query processing. In the experiments we empirically show that our proposed method significantly reduces the number of necessary I/O operations during query processing.

We have generalized a method for tandem mass spectra interpretation, based on the parameterized Hausdorff distance dHP. Instead of just peptides (short pieces of proteins), in this paper we describe the interpretation of whole protein sequences. For this purpose, we employ the recently introduced NM-tree to index the database of hypothetical mass spectra for exact or fast approximate search. The NM-tree combines the M-tree with the TriGen algorithm in a way that allows to dynamically control the retrieval precision at query time. A scheme for protein sequences identification using the NM-tree is proposed.