A metric space M is defined as a pair ( D , d ) of a domain D representing data objects and a pair-wise distance function d : D × D ↦ R that satisfies: ∀ x , y ∈ D , d ( x , y ) ⩾ 0 non-negativity , ∀ x , y ∈ D , d ( x , y ) = d ( y , x ) symmetry , ∀ x , y ∈ D , x = y ⇔ d ( x , y ) = 0 identity, and ∀ x , y , z ∈ D , d ( x , z ) ⩽ d ( x , y ) + d ( y , z ) triangle inequality . The distance function is used to measure similarity between two objects. The shorter the distance is, the more similar the objects are. Consequently, a similarity query can be defined. There are many types of similarity queries (Deepak and Prasad, 2015) but the range and k-nearest neighbour queries are the most important ones. The range query R ( q , r ) specifies all database objects within the distance of r from the query object q ∈ D. In particular, R ( q , r ) = { o | o ∈ X , d ( q , o ) ⩽ r }, where X ⊂ D is the database to search in. In this paper, we primarily focus on k-nearest neighbour query since it is more convenient for users. The user wants to retrieve k most similar objects to q without the need to know details about the distance function d. Formally, k N N ( q ) = A, where | A | = k ∧ ∀ o ∈ A , p ∈ X − A , d ( q , o ) ⩽ d ( q , p ).

To organize a database to answer similarity queries efficiently, many indexing structures have been proposed (Zezula et al., 2005). Their principles are twofold: (i) recursively applied data partitioning/clustering defined by a preselected data object called pivot and a distance threshold, and (ii) effective object filtering using lower-bounds on distance between a database object and a query object. These principles have been firstly surveyed in Chávez et al. (2001).

In this paper, we use the traditional index M-tree (Ciaccia et al., 1997) and a recent technique M-index (Novak et al., 2011). Both of these structures create an internal hierarchy of nodes that partition the data space into many buckets – an elementary object storage. Please refer to Figs. 1 and 2 for principles of their organization. M-tree organizes data objects in compact clusters created in the bottom-up fashion, where each cluster is represented by a pair ( p , r c ) – a pivot and a covering radius, i.e. distance from the pivot to the farthest object in the cluster. On the other hand, M-index applies Voronoi-like partitioning using a predefined set of pivots in the top-down way. In this case, clusters are formed by objects that have the cluster’s pivot as the closest one. On next levels, the objects are reclustered using the other pivots, i.e. eliminating the pivot that formed the current cluster. Buckets of both structures store objects in leaf nodes, as is exampled in the illustration. So we use the terms leaf node and bucket interchangeably.

A kNN-query evaluation algorithm constructs a priority queue of nodes to access and gradually improves a set of candidate objects forming the final query answer when the algorithm finishes. The priority is defined in terms of a lower bound on distance between the node and the query object. So a probability of node to contain relevant data objects is estimated this way. In detail, the algorithm starts with inserting the root node of hierarchy. Then it repeatedly pulls the head of priority queue until the queue is empty. The algorithm terminates immediately, when the pulled head’s lower bound is greater than the distance of current kth neighbour to the query object. If the pulled element represents a leaf node, its corresponding bucket is accessed and all data objects stored there are checked against the query, so query’s answer is updated. If it is a non-leaf node, all its children are inserted into the queue with correct lower bounds estimated. M-tree defines the lower bound for a node ( p , r c ) and a query object q as the distance d ( q , p ) − r c , where r c is the covering radius forming a ball around the pivot p. For further details, we refer the reader to the cited papers where additional M-tree’s node filtering principles as well as the M-index’s approach, which is elaborate too, are described.

We gathered statistics of querying from two demonstration applications.1¹

http://disa.fi.muni.cz/prototype-applications/image-search/.

Figure 3 shows absolute frequencies of individual top-1000 queries that were executed during the applications’ life time. The demo on CoPhIR was launched in Nov. 2008, while the demo on Profiset was made public in June 2015. These power-law like distributions are attributed to the way of presenting an initial search to a new website visitor. In CoPhIR demo, the users are initially provided with a similarity search to a query image randomly picked from a set of 105 preselected images, so there is a high frequency of such queries. In Profiset demo, the initial page contains 30 query images randomly selected from the whole data-set, so any repetition is caused by bookmarking or sharing popular images. There are few such queries only. Figure 4 depicts density of distances among the top-1000 queries, so the reader may observe there are very similar query objects as well as distinct ones in CoPhIR. This proves that the users were also browsing the data collection as was described above. This phenomenon is almost negligible in Profiset, i.e. some similar queries are present but not many. For reference, we also include distance density of the whole data-sets depicted as solid curves in Fig. 4. To sum up, these two query sets form different conditions for our proposal to cope with.

The major drawback of indexing structures in metric spaces is the high amount of overlaps among index substructures (data partitions), which is also supported by not very precise estimation of lower bounds on distances between data objects and a query object. So the kNN-query evaluation algorithm often accesses a large portion of indexing structure’s buckets to obtain precise answer to a query.

The selected indexing structure representatives were populated with 1 million data objects from the CoPhIR data-set and 30NN queries for the top-1000 query objects were evaluated. In Fig. 5, we present the percentage of fully completed queries while constraining the number of accessed buckets. We have tested two configurations for both M-tree and M-index – the capacity of buckets was constrained to 200 and 2,000 objects to have bushier and more compact structures. Table 1 summarizes information about them. To this end, M-index’s building algorithm was initialized with 128 and 512 pivots picked at random from the data-set and the maximum depth of M-index’s internal hierarchy was limited to 8 and 6 for CoPhIR and Profiset, respectively. From the statistics, we can see that M-tree can adapt to data distribution better than M-index and does not create very low occupied buckets, so M-tree is a more compact data structure. However, the kNN evaluation algorithm of M-index can access promising data partitions early, so curve depicting percentage of fully completed queries is increasing more steeply.

The other aspect of indexing structures to study is efficiency, i.e. how many data partitions are accessed to complete a 30NN query. In Fig. 6, we present the number of visits of individual buckets for M-tree and M-index structures after evaluating all top-1000 queries on CoPhIR and Profiset. In particular, we depict visited buckets for precise and approximate 30NN query evaluation with “O” and “X”, respectively. The curve denoted with “+” corresponds to the buckets that contained at least one data object returned in the precise answer. Thus, it forms the minimal requirements to evaluate the queries. The approximate evaluation was terminated after visiting 303 buckets of M-tree (27.5%) and 254 buckets of M-index (2.3%) for CoPhIR, and 1 714 buckets of M-tree (65.9%) and 779 buckets of M-index (3.8%) for Profiset data-set. These thresholds were selected to correspond to the number of visited buckets that contains complete answer of 70% queries. The average precision of approximate queries is 97.5%, for both M-tree and M-index. From the figure, we can see very large inefficiency in navigating to buckets containing relevant data and terminating the search when precise answer is found, i.e. very loose estimated lower bounds on distance between the query object and a data partition. Even though approximate evaluation provides large performance boost, there is still a large number of buckets that do not need to be accessed at all (more than 90%). Once again, the advantage of M-index over M-tree is in navigating to relevant buckets earlier.

The first group of experiments focuses on determining the best setting of d ICI distance measure. We used M-tree with leaf node capacity fixed to 200 only and the other parameters fixed to log base 10 and to power of 2. We studied the progress of fully completed queries at particular number of accessed nodes (buckets). The results are depicted in Fig. 7, where the following approaches were compared: original

– M-tree’s algorithm for precise kNN evaluation (search queue ordered by lower-bound distance = ( d ( q , pivot ) − r covering );

The second group of experiments focuses on precise kNN evaluation and impact of ICI in M-tree’s and M-index’s algorithms. We tested M-tree and M-index with capacity of buckets set to 2000 on both data collections. The test protocol is to take all queries processed by a demo application in a longer period of time and to separate it into training (adapting) and testing sub-sets.

For CoPhIR, we used traffic in the year of 2009 for counting the popularity and queries processed in January, 2010 for performance verification. They consisted of 993 and 1000 query objects, respectively. About 10% queries are in both the sub-sets in common and the remaining 90% are unique. For Profiset, the training set contained traffic from June, 2015 to February, 2016, whereas the testing one consisted of 6-week traffic following the training period. All tests were performed to evaluate precise 30NN queries.

Figure 8 depicts the total percentage of completed queries while the evaluation progresses in terms of accessed buckets. We can observe that ICI can optimize performance substantially for M-tree, because M-tree visits large portion of all buckets to complete all queries (up to 80%). M-index is much more efficient in the lookup of relevant data partitions (about 30% of all buckets) and ICI-base ordering becomes better when at least 85% queries get completed on CoPhIR. Tables 2 and 3 list exact numbers of performance. We can conclude that ICI-optimized queue ordering is able to make more than 20% performance gain for 95% queries completed.

In the previous trials, the period of gathering ICI statistics was long and we focused on viability of it only. Here, we study the performance while sliding the training and testing periods month by month. Since the Profiset demo application has been set up recently, we conduct this experiment on CoPhIR data-set only. Precise kNN queries are tested again, so the consistency of ICI’s impact through series of consequent time frames can be compared. This also corresponds to the scenario closer to possible future applications, where the statistics should be rolled over periodically.

For every run of experiments depicted in Fig. 9, three-month traffic was used as a training data-set. The testing phase on the following-month traffic is executed on two versions of query evaluation algorithm: the original precise kNN and precise kNN with ICI-based ordering. Graphs in the figure depict results of experiments for the thresholds of 50, 80 and 95% queries completed, i.e. the average number of buckets needed to answer 50, 80 and 95% queries completely. The experiments are repeated through 13 consecutive time frames, covering more than a year of traffic. Every two consecutive months shared only 7% queries on average. In Table 4, there are numbers of training and testing queries in individual time periods and their overlap.

Conducted experiments show us considerably uniform improvement achieved by ICI over the original algorithm for precise kNN query. All experiments on M-tree display improvement in query answering greater than 10%. Average improvement for threshold of 95% completed queries is 19.4%. As for M-index, similar results are obtained considering the same threshold: average improvement of 19.2%. M-index’s original kNN algorithm performs better for highly concentrated queries (answer is distributed in few buckets) – M-index completed 50% queries by visiting up to 89 buckets, which is less than 1% of all buckets. However, the other queries can be optimized by ICI ordering, where the overall improvement varies around 10–15%.

One of the challenges associated with the usage of ICI is tuning its parameters as presented in Eq. (1) in Section 5, namely: d norm , pwr and base.

To make our method widely applicable, experiments in this section use values of these parameters derived from statistics of queries, indexing structures and data-sets. As was already mentioned, the parameter d norm plays the role of a vanishing point, where two data items should become irrelevant or dissimilar. Here, we set its value to the average distance between a pair of objects in the data-set, which is 2.526 for CoPhIR and 85.84 for Profiset.

The parameter pwr specifies the relative impact of ICI in comparison with the original distance. In particular, it must be interpreted in two ways: (i) if a data object or partition is closer than d norm , the higher the value of pwr is, the greater the influence of ICI is; (ii) if a data object is further than d norm , the higher the value of pwr is, the smaller the influence of ICI is. The strength of pwr can be correlated to the data-set dimensionality – emphasis on ICI or distance should be and is deduced from the intrinsic dimensionality (iDim) of data (Chávez et al., 2001). For CoPhIR and Profiset data-sets, the value of iDim is 15 and 27, respectively.

Similarly to d norm , base serves mainly a normalization purpose: to reduce logarithmically the impact of nodes and objects with overly-high values of ICI. As the value of ICI corresponds to the number of queries processed, we deduce the value of base from the average number of queries (or average value of ICI) per bucket. Due to the behaviour of logarithmic function, some values are impractical or disallowed, so we should be constrained: base ∈ [ 5 ; 15 ]. The values of base used here are:

To verify such setting, we conducted a group of experiments on CoPhIR and Profiset for approximate kNN query evaluation. The results are presented in Fig. 10. We picked nine thresholds on the number of accessed buckets that correspond to the requirements of index structures to complete 10, 20, 30, 50, 60, 70, 80, 90 and 95% queries precisely. The exact limits on the number of accessed buckets are given as labels of x-axis.

Interpretation of the results obtained is twofold.

First, the difference between the approaches can be read horizontally, i.e. comparing the number of accessed buckets within the same precision. It indicates the possibility to lower the approximation threshold, which results into saving time to evaluate a kNN query. Table 5 gives approximate results of such optimization for kNN precision 90% and 95%. We can see that ICI is very competitive for all setups.

Second, it follows the vertical comparison of results, i.e. the change in precision within the same amount of accessed buckets. Table 6 summarizes the values of precision obtained for both the variants when the original approximation algorithm exceeded 90% and 95% precision, respectively. This demonstrates improvement in precision when ICI is applied.

Finally, the reader shall remember that we increment ICI counters only for first few objects in answer when queries are evaluated approximately. In Algorithm 1, ICI is increased for buckets and their parents covering the portion corresponding to the expected precision. The smaller the required precision is, the fewer buckets get their ICI increased. For example, an estimated precision of 90% on 30NN leads to updating buckets containing the first 27 objects. This certainly requires more analysis, which we plan as the future work.