We present the Permutation Pre x Index (PP-Index), an index data structure that allows to perform e cient approximate similarity search. The PP-Index belongs to the family of the permutationbased indexes, which are based on representing any indexed object with \its view of the surrounding world", i.e., a list of the elements of a set of reference objects sorted by their distance order with respect to the indexed object. In its basic formulation, the PP-Index is strongly biased toward e ciency, treating e ectiveness as a secondary aspect. We show how the e ectiveness can easily reach optimal levels just by adopting two \boosting" strategies: multiple index search and multiple query search. Such strategies have nice parallelization properties that allow to distribute the search process in order to keep high e ciency levels. We study both the e ciency and the e ectiveness properties of the PP-Index. We report experiments on collections of sizes up to one hundred million images, represented in a very high-dimensional similarity space based on the combination of ve MPEG-7 visual descriptors.
E.1 [Data]: Data Structures; H.3.3 [Information Systems]: Information Storage and Retrieval|Search process approximate similarity search, metric space, scalability
The similarity search model [
LSDS-IR Workshop. July 2009. Boston, USA. by their similarity to the query, according to a given distance function d : O O ! R+ (i.e., the closer two objects are, the most similar they are considered). Typically only the k-top ranked objects are returned (k-NN query), or those within a maximum distance value r (range query).
One of the main research topics on similarity search is the study of the scalability of similarity search methods when applied to high-dimensional similarity spaces.
The well known \curse of dimensionality" [
Approximate methods [
In this work we present the Permutation Pre x Index (PPIndex), an approximate similarity search structure belonging to the family of the permutation-based indexes. We describe the PP-Index data structures and algorithms, and test it on data sets containing up to 100 million objects, distributed on a very high-dimensional similarity space. Experiments show that the PP-Index is a very e cient and scalable data structure both at index time and at search time, and it also allows to obtain very good e ectiveness values. The PPIndex has also nice parallelization properties that allow to distribute both the index and the search process in order to further improve e ciency. 2.
The PP-Index belongs to the family of the
permutationbased indexes, a recent family of data structure for
approximate similarity search, which has been independently
introduced by Amato and Savino [
The PP-Index has however a key di erence with respect to previously presented PBIs: as we detail in this section, such PBIs use permutations in order to estimate the real distance order of the indexed objects with respect to a query. The PP-Index instead uses the permutation pre xes in order to quickly retrieve a reasonably-sized set of candidate objects, which are likely to be at close distance to the query object, then leaving to the original distance function the selection of the best elements among the candidates.
For a more detailed review of the most relevant methods
for similarity search in metric spaces we point the reader to
the book of Zezula et al. [
Chavez et al. [
A set of reference objects R = fr0; : : : ; rjRj 1g O is de ned by randomly selecting jRj objects from D. Every object oi 2 D is then represented by oi , consisting of the list of identi ers of reference objects, sorted by their distance with respect to the object oi. More formally, oi is a permutation of h0; : : : ; jRj 1i so that, for 0 < i < jRj it holds either (i) d(oi; r ox (i 1)) < d(oi; r ox (i)), or (ii) d(oi; r ox (i 1)) = d(oi; r ox (i)) and ox (i 1) < ox (i), where ox (x) returns the i-th value of ox .
All the permutations for the index objects are stored in
main memory. Given a query q, all the indexed permutations
are sorted by their similarity with q, using a similarity
measure de ned on permutations. The real distance d between
the query and the objects in the data set is then computed
by selecting the objects from the data set following the order
of similarity of their permutations, until the requested
number of objects is retrieved. An example of similarity measure
on permutations is the Spearman Footrule Distance [
P ( oy ; r)j (1) where P ( ox ; r) returns the position of the reference object r in the permutation assigned to ox .
Chavez et al. do not discuss the applicability of their method to very large data sets, i.e., when the permutations cannot be all kept in main memory.
Amato and Savino [
For each object oi 2 D, they compute the permutation
oi in the same manner as [
One optimization consists in inserting into the inverted lists only the information related to okii , i.e., the part of oi including only the rst ki elements of the permutation, thus reducing by a factor jkRij the size of the index. For example, given jRj = 500 a value of ki = 100 reduces by ve times the number of disk accesses with respect to using full-length permutations, with a negligible loss in accuracy.
Similarly, a value ks is adopted for the query, in order to select only the rst ks elements of q. Given jRj = 500 a value of ks = 50 reduces by ten times the number of disk accesses, also slightly improving the accuracy. 3.
The PP-Index represents each indexed object with a very short permutation pre x.
The PP-Index data structures consists of a pre x tree kept in main memory, indexing the permutation pre xes, and a data storage kept on disk, from which objects are retrieved by sequential disk accesses.
This con guration of data structures is interestingly
similar to the one used by Bawa et al. [
More generally, a key di erence between the PBI model and the LSH model is that the hash functions of the LSH model are solely derived from the similarity measures in use, independently of the way the indexed objects are distributed in the similarity space, while in the SPI model the reference objects provide information about this aspect.
The PP-Index is designed to allow very e cient indexing by performing bulk processing of all the objects indexed. Such bulk processing model is based on the intuitive assumption that the data, in the very large collections the PP-Index is designed for, have a relatively static nature. However, it is easy to provide the PP-Index with update capabilities (see Section 3.6). 3.1
Given a collection of objects D to be indexed, and the similarity measure d, a PP-Index is built by specifying a set of reference objects R, and a permutation pre x length l.
Any object oi 2 D is represented by a permutation pre x woi consisting of the rst l elements of the permutation oi , i.e., woi = loi . Any object oi 2 D is also associated with a data block. A data block boi contains (i) the information required to univocally identify the object oi and (ii) the essential data used by the function d in order to compute the similarity between the object oi and any other object in O.
The pre x tree of the PP-Index is built on all the permutation pre xes generated for the indexed objects. The leaf at the end of a path relative to a permutation pre x w keeps the information required to retrieve the data blocks relative to the objects represented by w from the data storage.
The data storage consists of a le in which all the data blocks are sequentially stored. The order of objects (represented by data blocks) in the data storage is the same as the one produced by performing an ordered visit of the pre x tree. This is a key property of the PP-Index, which allows to use the pre x tree to e ciently access the data storage.
Speci cally, the leaf of the pre x tree relative to permutation pre x w contains two counter values hswtart and hewnd, and two pointer values pswtart and pewnd. The counter values BuildIndex(D; d; R; l) 1 pref ixT ree EmptyPrefixTree() 2 dataStorage EmptyDataStorage() 3 for i 0 to jD 1j 4 do oi GetObject(D; i) 5 dataBlockoi GetDataBlock(oi) 6 poi Append(dataBlockoi ; dataStorage) 7 woi ComputePrefix(oi; R; d; l) 8 hoi i 9 Insert(woi ; hoi ; poi ; pref ixT ree) 10 L ListPointersByOrderedVisit(pref ixT ree) 11 P CreateInvertedList(L) 12 ReorderStorage(dataStorage; P ) 13 CorrectLeafValues(pref ixT ree; dataStorage) 14 index NewIndex(d; R; l; pref ixT ree; dataStorage) 15 return index indicate the ordinal position in the sequence of data blocks in the data storage of the rst and the last data blocks relative to the permutation pre x w. The pointer values indicate instead the byte o set in the data storage where the data blocks are e ectively serialized. In case the data blocks have a xed size s, the p values can be omitted and computed when necessary as pw = hw s.
The data storage implementation must allow, given any two pointers p0 and p00, to sequentially retrieve all the data blocks included between them. 3.2
Figure 1 shows a pseudo-code description of the indexing function for the PP-Index.
The indexing algorithm rst initializes an empty pre x tree in main memory, and an empty le on disk, to be used as the data storage.
The algorithm takes in input an object oi 2 D, for i from 0 to jD 1j, and appends its data block at the current end position pend of the data storage le. Then the algorithm computes, for the object oi, the permutation pre x woi (ComputePrefix), and inserts woi into the pre x tree. The values hoi = i and poi = pend are stored in the leaf of the pre x tree corresponding to permutation pre x woi . When more that one value has to be stored in a leaf, a list is created.
Figure 2 shows an example list of permutation pre xes generated for a set of objects and the data structures resulting from the above discussed rst phase of data indexing.
The successive phase (ReorderStorage) consists in reordering the data blocks in the data storage to satisfy the order constrains described in the previous section. An ordered visit of the pre x tree is made in order to produce a list L of the hoi values stored in the leaves. Thus, the hoi values in the list L are sorted in alphabetical order of the permutation pre xes their relative objects are associated with.
Data blocks in the data storage are reordered following the order of appearance of hoi values in list L. For example, given a list for L = h0; 4; 8; 6; 1; 3; 5; 9; 2; 7i, the data block relative to object o7, identi ed in the list by the value ho7 = 7, has to be moved to the last position in the data storage, since ho7 appears in the last position of the list L (see the values in the leaves of the pre x tree in Figure 2).
To e ciently perform the reordering, the list L is inverted into a list P . The i-th position of the list P indicates the new position in which the i-th element of the data storage has to be moved. For the above example, o0 ... o4 ... o8... o6 ... o1 ... o3 ... o5 ... o9 ... o2 ... o7 ...
Data storage
Figure 3: The nal index data structure.
P = h0; 4; 8; 5; 1; 6; 3; 9; 2; 7i.
Once P is generated the data storage is reordered
accordingly, using an m-way merge sorting method [
In order to obtain the nal index structure, the values in the leaves of the pre x tree have to be updated accordingly to the new data storage (CorrectLeafValues). This is obtained by performing an ordered visit to the pre x tree, the same performed when building the list L, synchronized with a sequential scan of the reordered data storage. The number of elements in the list of a leaf determines the two hstart and hend values that replace such list, and also the number of data blocks to be sequentially read from the data storage, in ordered to determine the pstart and pend values.
Figure 3 shows the nal index data structure. 3.3
The search function is designed to use the index in order to Index characteristics |D|=10, |R||=6, l=3
Permutation prefixes wo0 =<1, 3, 2> wo1 =<2, 3, 0> wo2 =<5, 2, 3> wo3 =<4, 1, 3> wo4 =<1, 3, 2> wo5 =<4, 1, 3> wo6 =<1, 3, 4> wo7 =<5, 2, 3> wo8 =<1, 3, 2> wo9 =<4, 3, 5> e ciently answer to k nearest neighbor queries. The search strategy consists in searching a subtree of the pre x tree that identi es a speci ed number of candidate objects all represented by permutation pre xes having a pre x match with the permutation pre x representing the query.
A k-NN query is composed of the query object q, the k value, and the z value, indicating the minimum number of candidate objects among which the k nearest neighbors have to be selected.
The FindCandidates function determines the smallest subtree of the pre x tree having a pre x match with the permutation pre x wq, i.e., the permutation pre x relative to the query q, and retrieving at least z objects. The function returns two pointers pstart and pend to the positions in the data storage of the data blocks of the rst and the last candidate objects.
The distance of each candidate object with the query is computed, using the distance function d. A heap is used to keep track of the k objects closest to the query. 3.4
In order to reduce the main memory occupation of the prex tree it is possible to simplify its structure without a ecting the quality of results. These are search-speci c optimizations, and a non-optimized version of the pre x tree should be saved for other operations (e.g., update and merge).
A rst optimization consists in pruning any path reaching
a leaf which is composed of only-child, given that this kind
of path does not add relevant information to distinguish
between di erent existing groups in the index. Another
optimization consists in compressing any path of the pre x tree
composed entirely of only-children into a single label [
A PP-Index-speci c optimization, applicable when the z value is hardcoded into the search function, consists in reducing to a single leaf the subtrees of the pre x tree that points to less than z objects, given that none of such subtrees will be ever selected by the search function. 3.5
The \basic" search function described is Section 3.3 is strongly biased toward e ciency, treating e ectiveness as a secondary aspect. The PP-Index allows to easily tune e ectiveness/e ciency trade-o , and e ectiveness can easily reach optimal levels just by adopting the two following \boosting" strategies:
Multiple index : t indexes are built, based on di erent R1 : : : Rt sets of reference objects. This is based on the intuition that di erent reference object sets produce many differently shaped partitions of the similarity space, resulting in a more complete coverage of the area around queries.
A search process the using multiple index strategy can be parallelized by distributing the indexes over multiple machines, or just on di erent processes/CPUs on the same machine, maintaing almost the same performance of the basic search function, with a negligible overhead for merging the t k-NN results, as far as there are enough hardware resources to support the number of indexes involved in the process.
Multiple query : at search time, p additional permutation pre xes from the query permutation pre x wq are generated, by swapping the position of some of its elements. The geometric rationale is that a permutation pre x w0 di ering from another permutation pre x w00 for the swap of two adjacent/near elements identi es an area Vw0 of the similarity space adjacent/near to Vw00 allowing to extend the search process to areas of the search space that are likely to contain relevant objects.
The heuristic we adopt in our experiments for swapping permutation pre x elements consists in sorting all the reference objects pairs appearing in the permutation pre x by their di erence of distance with respect to the query object. Then the swapped permutation pre xes are generated by rst selecting for swap those pairs of identi ers that have the smallest distance di erence.
The multiple query strategy can be parallelized by distributing the queries over di erent processes/CPUs on the machine handling the index structure. 3.6
The PP-Index data structures allows to very e ciently merge indexes built using the same parameters into a single index. The merge functionality supports three operations:
Supporting update operations: it is easy to add update capabilities to an index by maintaining a few additional data structures. Deleted objects are managed using a vector of their identi ers. Newly inserted or modi ed objects are stored in an all-in-memory secondary PP-Index used in conjunction with the main index structure. A periodic merge procedure is used when the secondary index reaches a given memory occupation limit.
Indexing very large collection: the main memory occupation of a pre x tree reaches its maximum during the indexing process, when it has to be entirely kept in memory, while during search, thanks to the optimization methods described in Section 3.4, its size can be reduced by orders of magnitude. This issue is solved building a number of smaller partial indexes and then merging them into the nal index.
Distributing the indexing process: the indexing process of smaller indexes can be distributed of di erent machines, given that the information contained in any smaller index is completely independent of the one contained in the others. Also the merge process can be distributed, if it is performed in a number of steps that involve the creation of intermediate indexes.
The merge process consists in merging the pre x trees of the source indexes into a single pre x tree, i.e., by enumerating, in alphabetical order, all the permutation pre xes contained in the source indexes.
Such enumeration can be easily produced by performing a parallel ordered visit of all the pre x trees being merged. If the pre x trees of the source indexes are saved to the storage using a depth rst visit, the merge process requires only a single read of the serialized pre x trees. Obviously, the new pre x tree is directly serialized on disk during the permutation pre x enumeration process.
In the case of an update process, the identi ers of the deleted objects are used to skip deleted objects during the merge process.
The data storages are merged during the permutation prex enumeration.
The CoPhIR1 [
The information relative to ve MPEG-7 visual
descriptors [
We have randomly selected 100 images from the collection as queries and we have run experiments using the rst million (1M), ten millions (10M), and 100 millions (100M) images from the data set.
We have run experiments on a linear combination of the
ve distance functions for the ve descriptors, using the
weights proposed in [
Descriptor Scalable Color Color Structure
Color Layout
Edge Histogram Homogeneous Texture
Type L1
L1 sum of L2
L1 L1
We have tested a basic con guration based on the use of a single index and the search function described in Section 3.3, i.e., an e ciency-aimed con guration.
We have then tested the use of multiple indexes , on congurations using 2, 4 and 8 indexes, and also the multiple query search strategy by using a total of 2, 4, and 8 multiple queries. We have also tested the combination of the two strategies.
We have applied the index optimization strategies described in Section 3.4 to all the generated indexes.
On the held-out data we have tested various z values, in this paper we report the results obtained for z = 1; 000, which has produced a good trade-o in e ectiveness/e ciency.
The experiments have been run on a desktop machine running Windows XP Professional, equipped with a Intel Pentium Core 2 Quad 2.4 GHz CPU, a single 1 TB Seagate Barracuda 7,200 rpm SATA disk (with 32 MB cache), and 4 GB RAM. The PP-Index has been implemented in c#. All the experiments have been run in a single-threaded application, with a completely sequential execution of the multiple index/query searches.
We have evaluated the e ectiveness of the PP-Index by
adopting a ranking-based measure and a distance-based
measure [
k i=1 k 1 X d(q; Pqk(i)) k d(q; Dqk(i)) 1 (2) (3) where Dq is the list of the elements of D sorted by their distance with respect to q, Dqk is the list of the k closest elements, Pqk is the list returned by the algorithm, and Lqk(i) returns the i-th element of the list L. 4.3
Results jDj 1M 10M 100M indexing pre x tree size time (sec) full comp. 419 7.7 MB 91 kB 4385 53.8 MB 848 kB 45664 354.5 MB 6.5 MB data storage 349 MB 3.4 GB 34 GB l0 2.1 2.7 3.5
Table 2 reports the indexing times for the various data set sizes (jRj = 100), showing the almost perfect linear proportion between indexing time and data set size. With respect to the indexing times we note that: (i) the twelve hours time, required to build the 100M index for the jRj = 100, is in line with the fourteen hours we have measured to build a text search index on the descriptions and the comments associated with the indexed images; (ii) this time refers to a completely sequential indexing process, not leveraging on the parallelization possibilities described in Section 3.6; (iii) we have not explored the possibility of using a similarity search data structure in order to answer l-NN query on the R set necessary to build the permutation pre x.
The table also shows the resulting memory occupation of the pre x tree before and after the application of the compression strategies described in Section 3.4. The values shows how such strategies allows to reduce by orders of magnitude the main memory requirement of the PP-Index (at least by a factor fty in our case) without a ecting the quality of the results.
As expected, the disk occupation is perfectly linear with respect to the data set size, given that the disk data storage contains only a sequential serialization of data blocks (375 bytes each one).
The last column of Table 2 reports the average depth of the leaves of the pre x tree, after the compression. The l0 values show that the l value is not crucial in the de nition of a PP-Index, given that the only requirement is to choose a l value large enough in order to perform a su cient di erentiation of the indexed objects.
The graph of Figure 5 plots the search time with respect to the size of R and the data set size, for k = 100 (single index, single query). For the worst case, with jRj = 100, we have measured an average 0:239 seconds search time on the 100M index, with an average of less than eight thousands candidates retrieved from the data storage (see Table 3). The search time decreases in a direct proportion the decrease of the z0 value, which follows from the more detailed partitioning of objects into the permutation pre x space, determined by the increase of jRj. Even though the z0 value increases as D gets larger, the increase of z0 is largely subproportional to the growth of D: when D grows by a factor 100, z0 increases at worst by a factor 6:6.
A possible issue with the z0 value is that it is not so close the z value, and it has potentially no limits. However, during the experiments the z0 value has never been a critical factor with respect to e ciency: we have not observed any extreme case in which z0 >> z, and the z0 value has never required more than a single read operation from disk to retrieve all the candidate objects (e.g., retrieving 10; 000 data blocks from the data storage involves reading only 3.7 MB from disk). We leave to future works an investigation of the relations of the z value with the other parameters.
Figure 6 shows the e ectiveness of the PP-Index with respect to the size of the R and the data set size, using a single-index/single-query con guration, for k = 100.
E ectiveness values improve with the increase of jRj for the 10M and 100M data sets, while the 1M data set shows the inverse tendency. This con rms the intuition that larger data sets requires a richer permutation pre x space (generated by a larger set R) to better distribute their elements, until a limit is reached and objects became too sparse in the permutation pre x space and the e ectiveness worsen.
The maximum-e ciency (0.210 seconds answer time) conguration of PP-Index has obtained a 18:3% recall and 8:1% RDE on the 100M data set, for k = 100.
Figures 7 and 8 show respectively the e ects on e ectiveness of the multiple index and multiple query strategies, for three k values.
With respect to the multiple index strategy we have measured a great improvement on both measures reaching a 74% recall (four times better than the single-index case) and a 0:7% RDE (eleven times better) for the eight index case.
For the above mentioned eight index con guration we have measured an average 1:72 seconds search time, for a completely sequential search process. The four index con guration allows to reach a 52% recall (67% for k = 10) and just a 2:2% RDE with a sub-second answer time.
It is relevant to note that, given the small memory occupation of the compressed pre x tree, we have been able to simultaneously load eight 100M indexes into the memory, thus practically performing search on an 800 million objects index, though with replicated data, on a single computer.
The multiple query strategy also shows relevant improvements, though of minor entity with respect to the multiple index strategy. This is in part motivated by the fact that many of the queries, generated by permuting the elements of the original query permutation pre x, actually resulted in retrieving the same candidates of other queries2. On the 100M index, for jRj = 1; 000, on the average, 1:92 distinct queries to be e ective in retrieving candidates for the two queries con guration, 3:18 queries for the four queries con guration, and 5:25 queries for the eight queries con guration.
Figure 9 shows the e ectiveness of the combined multiple query and multiple index search strategies, using eight queries and eight indexes, for jRj = 1; 000. We have measured an average search time of 12.45 seconds, for a fully sequential search process. This setup produces almost exact results, with a recall > 97% and a RDE < 0:01%.
We have measured, on the average, a total of 370; 000 data
blocks retrieved from the data storage among the average
44:5 queries being e ectively used to access the data storages
for each original query. Although this z0 value is relatively
high, it just represents the 0:3% of the whole collection. This
is a very low value considering, for example, that Lv et al.
[
It is a hard task to run comparative experiments on novel and very large data sets, such as CoPhIR due to many reasons: (i) lack of previous results on the same data set; (ii) lack of a publicly available implementation for many of the methods involved in the comparison; (iii) when an implementation is available, it is typically not designed to scale 2Such candidates are read only once from the data storage. to very large data sets, but just a proof of concept; (iv) moreover, the implementation is usually designed to take in input only a speci c data type/format, which makes harder to port the application to di erent data types.
For this reasons we have currently limited our comparison
to replicating two experiments that, among the others, are
most closely related to our work: Batko et al. [
Batko et al. [
The PP-Index could achieve a better performance than
[
Amato and Savino [
Replicating [
The maximum recall level obtained in [
We have introduced the PP-Index, an approximate similarity search data structure based on the use of short permutation pre xes. We have described the PP-Index data structures and algorithms, including a number of optimization methods and search strategies aimed at improving the scalability of the index, its e ciency, and its e ectiveness.
The PP-Index has been designed to take advantage of the relatively static nature one could expect from very large collections. However, as we have described, it is easy to support fast update operations.
We have evaluated the PP-Index on a very large and highdimensional data set. Results show that it is both e cient and e ective in performing similarity search, and it scales well to very large data sets.
We have shown how a limited-resources con guration obtains good e ectiveness results in less than a second, and how almost exact results are produced in a relatively short amount of time. The parallel processing capabilities of the PP-Index allow to distribute the search process in order to further improve its e ciency.
The comparison with experimental results published for
two closely related method, which are among the
topperformers on the task, shows that the PP-Index
outperforms the compared methods, both in e ciency and e
ectiveness. Only one [
The PP-Index has been already used to build a performing
similarity search system5 [
There are many aspect of our proposal that are worth to be further investigated. For example, the R set is a crucial element of the PP-Index. We plan to study element selection policies alternative to the random policy, e.g., selecting centroids of clusters of D, or the most frequent queries from a query log.