## 2 Metric Spaces  
In this section, we introduce some basic concepts about metric spaces. Metric spaces have been widely studied to search for objects which are similar to a given query object \(q\). Metric spaces have been used to retrieve objects from databases such as text, images, audio, and video databases. In these cases, queries are represented by objects of the same type as those stored in the database. The work in [14] exemplifies how metric spaces can be used for computational biology to search for DNA and protein sub-sequences. The work in [15] presents an index for fingerprint matching. Metric spaces can also be used to re-order a set of documents [16]. In this case, the metric space distance between the documents is used to diversify the set results. Formally, a _metric space_\((\mathcal{U},\delta)\) comprises a universe of objects \(\mathcal{U}\) and a distance function \(\delta:\mathcal{U}\times\mathcal{U}\rightarrow\mathcal{R}^{+}\), which determines the similarity between any pair of objects [17]. Therefore, the smaller the distance between two objects, the more \"similar\" they are. The definition of the distance function depends on the type of objects being compared. In an \(m\)-dimensional vector space--a particular case of metric space in which every object is represented by a vector of \(m\) coordinates--\(\delta\) could be a distance function of the family \(L_{s}(x,y)=(\sum_{1\leq i\leq m}|x_{i}-y_{i}|^{s})^{\frac{1}{2}}\). For example, \(s=2\) yields the Euclidean distance. For any \(x,y,z\in\mathcal{U}\), the function \(\delta\) holds several properties: non-negativity (\(\delta(x,y)\geq 0\)), reflexivity (\(\delta(x,y)=0\) if \(x=y\)), symmetry (\(\delta(x,y)=\delta(y,x)\)), and the triangle inequality (\(\delta(x,z)\leq\delta(x,y)+\delta(y,z)\)). Some good surveys about metric spaces can be found in [14; 17; 18; 19]. The finite subset \(\mathcal{X}\subseteq\mathcal{U}\), with \(n=|\mathcal{X}|\), defines the database of objects where searches are performed. There are two types of similarity queries: the range query \(R(q,r)\) is the type of query which retrieves all elements that are within distance \(r\) to a query \(q\). This is \(\{x\in\mathcal{X}:\delta(q,x)\leq r\}\), and \(k\)-\(NN\) query, which retrieves the \(k\) closest objects \(x\in\mathcal{X}\) to a query object \(q\)[20]. Metric space search algorithms pre-process the dataset of object \(\mathcal{X}\) to build an index \(\mathcal{I}\). Different indexing algorithms have been proposed in the literature to speed up similarity searches [19]. The idea is to use the triangle inequality during the query search process to discard objects \(x\) that can be proven to be far enough from a given query \(q\) without computing \(\delta(x,q)\). There are two main index categories: clustering and pivoting. Clustering-based indices divide the dataset of objects into groups (called clusters), such that similar objects fall into the same group [14]. Thus, the space is divided into zones that are as compact as possible, usually in a recursive fashion. This technique stores a representative point (\"center\") for each zone plus extra information that permits one to quickly discard the zone at the query time. Pivot-based indices select some objects as pivots and calculate the distance between every other object and each pivot. The resulting index is a data structure that can be seen as a table \(T\) with the pivots in the columns and the object identifiers in the rows, where each cell \(T_{i,j}\) stores the distance between the object \(i\) and the pivot \(j\), as shown in Figure 1. Several algorithms (e.g., [21; 22]) are almost direct implementations of this idea. Essentially, only their extra data structure (e.g., additional memory space is assigned to store pre-computed distances and other relevant information) is used to reduce the cost of finding the candidate objects. A key challenge for pivoting techniques is to determine the number of pivots needed to cover all objects in the working set.