Since its introduction in 1997, the M-tree became a respected metric access method (MAM), while remaining, together with its descendants, still the only database-friendly MAM, that is, a dynamic structure persistent in paged index. Although there have been many other MAMs developed over the last decade, most of them require either static or expensive indexing. By contrast, the dynamic M-tree construction allows us to index very large databases in subquadratic time, and simultaneously the index can be maintained up-to-date (i.e., supports arbitrary insertions/deletions). In this article we propose two new techniques improving dynamic insertions in M-tree—the forced reinsertion strategies and so-called hybrid-way leaf selection. Both of the techniques preserve logarithmic asymptotic complexity of a single insertion, while they aim to produce more compact M-tree hierarchies (which leads to faster query processing). In particular, the former technique reuses the well-known principle of forced reinsertions, where the new insertion algorithm tries to re-insert the content of an M-tree leaf that is about to split in order to avoid that split. The latter technique constitutes an efficiency-scalable selection of suitable leaf node wherein a new object has to be inserted. In the experiments we show that the proposed techniques bring a clear improvement (speeding up both indexing and query processing) and also provide a tuning tool for indexing vs. querying efficiency trade-off. Moreover, a combination of the new techniques exhibits a synergic effect resulting in the best strategy for dynamic M-tree construction proposed so far.

The metric space paradigm has recently received attention as an important model of similarity in the area of Bioinformatics. Numerous techniques have been proposed to solve similarity (range or nearest-neighbor) queries on collections of data from metric domains. Though important representatives are outlined, this chapter is not trying to substitute existing comprehensive surveys. The main objective is to explain and prove by experiments that similarity searching is typically an expensive process which does not easily scale to very large volumes of data, thus distributed architectures able to exploit parallelism must be employed. After a review of applications using the metric space approach in the field of Bioinformatics, the chapter provides an overview of methods used for creating index structures able to speedup retrieval. In the metric space approach, only pair-wise distances between objects are quantified, so they represent the level of dissimilarity. The key idea of index structures is to partition the data into subsets so that queries are evaluated without examining entire collections -- minimizing both the number of distance computations and the number of I/O accesses. These objectives are obtained by exploiting the property of metric spaces called the triangle inequality which states that if two objects are near a third object, they cannot be too distant to one another. Unfortunately, computational costs are still high and the linear scalability of single-computer implementations prevents from searching in large and ever growing data files efficiently. For these reasons, we describe very recent parallel and distributed similarity search techniques and study performance of their implementations. Specifically, Section 12.1 presents the metric space approach and its applications in the field of Bioinformatics. Section 12.2 describes some of the most popular centralized disk-based metric indexes. Consequently, Section 12.3 concentrates on parallel and distributed access methods which can deal with data collections that for practical purposes can be arbitrary large, which is typical for Bioinformatics workloads. An experimental evaluation of the presented distributed approaches on real-life data sets is presented in 12.4. The chapter concludes in Section 12.5.

Due to the exponential growth of digital data and its complexity, we need a technique which allows us to search such collections efficiently. A suitable solution is based on the peer-to-peer (P2P) network paradigm and the metric-space model of similarity. When a large volume of data is being inserted, the P2P network must expand to new peers in order to maintain its efficiency. Thus, many peers must be split. During a peer split, the data is halved and one half is migrated to a new peer. In this paper, we study the problem of peer splits and propose a specialized algorithm for speeding it up. In particular, we use the structured P2P network called the M-Chord. Search performance within a single peer is enhanced by the M-tree. In experimental evaluation, we compare the proposed algorithm with several straightforward solutions on a real network organizing 10 million images. Our algorithm provides a significant performance boost.

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.

This prototype implements the idea of social networking in metric spaces. The metric social network is a peer-to-peer network in which users can share their data without the need to send them to a centralized node. Searching in this system is based on the notion of similarity which is modelled using metric spaces. The architecture of the metric social network is formally defined by using acquaintance and friendship relations. The implementation builds on top of the MESSIF framework library.