Friðrik Herwig Lejsek

Heiðar Ásmundsson

Björn Thór Jónsson

Laurent Amsaleg

Friðrik Heiðar Ásmundsson

Björn Þór Jónsson

Transactional Support for Visual Instance Search

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Visual instance search is the task of retrieving from a database of images the ones that contain an instance of a visual query. It is typically much more challenging than finding images that contain objects of the same category as the object in the query. If the query is an image of a shoe, visual instance search does not try to find images of shoes, which might differ from the query in shape, color or size, but tries to find images of the exact same shoe as the one in the query image.

Industry is very concerned with instance search, as various real world applications require such fine-grained image recognition capabilities. Forensics is a domain of choice, where identifying tiny similar visual elements in images is key to mapping out child abuse networks, or establishing links between various terrorism-related visual materials. Very fine-grained instance search is also involved in some copyright enforcement applications, and others.

Instance search challenges image representations as features extracted from the images must enable fine-grained recognition despite variations in viewpoints, scale, position, illumination, etc. While holistic image representations, where each image is mapped to a single high-dimensional feature vector, are sufficient for coarse-grained similarity retrieval, local features are needed for instance retrieval.

With local features, an image is mapped to a large set of high-dimensional vectors, allowing fine-grained recognition using the multitude of small visual matches between the query instance and the candidate images from the database. Extracting powerful local features from images has been widely studied and many strategies exist to determine (i) where local features should be extracted ( [START_REF] Mikolajczyk | A comparison of affine region detectors[END_REF][START_REF] Nowak | Sampling strategies for bag-of-features image classification[END_REF]), and (ii) what information each local feature should encode ( [START_REF] Mikolajczyk | A performance evaluation of local descriptors[END_REF][START_REF] Bay | Speeded-up robust features (SURF)[END_REF]). All these strategies, however, result in a very large set of local features per image; an instance search system handling a few million images may need to manage a few billion local features. Scalability of the high-dimensional indexing techniques used in the context of instance search is therefore essential. Most state-of-theart high-dimensional indexing solutions assume that the feature vector collection can always fit in memory. Experience from the data management community and from industry shows that this assumption is not valid, as data will eventually outgrow main memory capacity. Furthermore, with SSDs emerging as as viable middle ground between memory and hard disk drives, handling data that extends beyond main memory should be reconsidered.

Image collections grow (often rapidly) as time goes by, and it is important to ensure that the instance search engines probes up-to-date collections. Very few proposals from the literature address dynamicity, however, and most of them can only expand the indexed collection through a complete reconstruction of the index. In the real world, halting a system for re-indexing is not an option; instead, new data items must be dynamically inserted into the index while the system is running. Even the recently proposed Lambda Architecture [START_REF] Marz | Big Data: Principles and best practices of scalable real-time data systems[END_REF], which separates handling of very recent data from older data, requires dynamic consistency of index maintenance for recent data. Furthermore, resisting failures and enforcing durability of the indexed data is very important. Losing the features upon failure or experiencing extended downtime for reconstruction of indices are not acceptable options. Storing the high-dimensional index on disk is thus not only necessary for scalability, but also for the dynamic integrity of the index.

Key Requirements

Based on the discussion above, we have identified the following four key requirements a high-dimensional indexing solution dedicated to enabling scalable identification of similar visual instances must meet:

R1

The index must make efficient use of all available storage resources, main memory, solid-state devices or hard disks. R2 The index must offer stable query processing performance, so that it can be used as a component of an industry-scale processing chain. R3 The index must support dynamic insertion methods so that the indexed collection can grow while concurrent retrievals are performed. R4 The index must support the ACID properties of transactions (Atomicity; Consistency; Isolation; and Durability), which guarantee the integrity of index maintenance, as well as correct recovery in case of system failures.

Most state-of-the-art methods, such as product quantization, focus on compressing data into main memory. Whereas these methods often provide some guarantees on quality, they neither consider updates nor provide guarantees on query processing performance, thus failing with requirements R1 to R4.

We have previously proposed the NV-tree, an approximate high-dimensional indexing method that is designed from a data management perspective and can thus deal with feature collections that outgrow main memory [START_REF] Lejsek | NV-tree: An efficient disk-based index for approximate search in very large high-dimensional collections[END_REF][START_REF] Lejsek | NV-Tree: Nearest neighbours at the billion scale[END_REF]. When there are more image features that can fit in RAM, the NV-tree guarantees using at most a single disk read per index to get the approximate results. By providing a disk-based query performance guarantee for the NV-tree, requirements R1, and R2 above are satisfied.

In [START_REF] Lejsek | NV-tree: An efficient disk-based index for approximate search in very large high-dimensional collections[END_REF], an insertion procedure is described and evaluated for an early version of the NV-tree. Subsequent works, which propose significant improvements to the NV-tree, also discuss dynamic maintenance of the index [START_REF] Lejsek | NV-Tree: Nearest neighbours at the billion scale[END_REF][START_REF] Ólafsson | Dynamic behavior of balanced NV-trees[END_REF]. In order to make the NV-tree a fully transactional dynamic index, we propose transactional index maintenance procedures, and show that the resulting extended NV-tree supports both R3 and R4.

Contributions This article makes the following major contributions to the domain of scalable high-dimensional indexing for visual instance search:

1. We show how to adapt the NV-tree to transactional processing of insertions and deletions, guaranteeing the well-known ACID properties of transactions. 2. We evaluate insertion performance in this transactional setting and show that insertion throughput is excellent: when the index fits in memory, the index can take full advantage, but even in the disk-bound case each insertion requires only a small fraction of a disk write on average.

The technology described in this article is already in use at Videntifier Technologies, one of the main players in the forensics arena with technology deployed at such clients as Interpol. Their search engine targets fine-grained visual instance search as it is used for investigations that, for example, aim to dismantle child abuse networks. The search engine can index and identify very fine-grained details in still images and videos from a collection of 150 thousand hours of video, typically scanning videos at 40x real-time speed, and about 700 hours of video material can be dynamically added to the index every day.

Related Work

Only approximate high-dimensional indexing solutions remain efficient at very large scale. Approximate indexing methods trade quality off for response time, and follow three different major directions. Due to space constraints we outline only the most scalable of these methods here; for more details see [START_REF] Lejsek | Dynamicity and durability in scalable visual instance search[END_REF].

Quantization One line of work is based on indexing data clusters such as the hierarchical k-means decomposition of the data collection: Voronoi cells are created to partition and store the high-dimensional vectors, and the cells are organized as a multi-level tree to facilitate traversal and improve response time [START_REF] Fukunaga | A branch and bound algorithms for computing k-nearest neighbors[END_REF]. Many variants of this basic idea have been proposed (e.g., see [START_REF] Li | Clindex: Clustering for approximate similarity search in high-dimensional spaces[END_REF][START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF][START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF]). One algorithm from this category has been extended to cope with collections of up to 43 billion feature vectors, using distributed processing with "big data" techniques such as Spark [START_REF] Moise | Indexing and searching 100M images with Map-Reduce[END_REF][START_REF] Guðmundsson | Towards engineering a web-scale multimedia service: A case study using Spark[END_REF]. A more sophisticated indexing method, still using data clusters at its core, is called product quantization [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF]. Product quantization decomposes the high-dimensional space into low-dimensional subspaces that are indexed independently. This produces compact code words representing the vectors that, together with an asymmetric approximate distance function, exhibit good performance for a moderate memory footprint. Several variants of product quantization have been published; in particular, Sun et al. [START_REF] Sun | Indexing billions of images for sketch-based retrieval[END_REF] proposed an indexing scheme based on product quantization that uses ten computers to fit in memory the 1.5 billion images collection they index. The inverted multi-index by Babenko and Lempitsky [START_REF] Babenko | The inverted multi-index[END_REF] uses product quantization at its core but achieves a much denser subdivision of the space by using multiple inverted indices. The experiments reported in [START_REF] Babenko | The inverted multi-index[END_REF], using the BIGANN dataset [START_REF] Jégou | Searching in one billion vectors: re-rank with source coding[END_REF] that contains one billion SIFT descriptors, show that the approach can determine short candidate lists with superior recall. They have recently extended their method for deep learning features [START_REF] Babenko | Efficient indexing of billion-scale datasets of deep descriptors[END_REF]. None of these methods have proposed methods to support either dynamic updates or ACID properties of transactions.

Hashing A second line of work developed around the idea of hashing. The earliest notable hashing-based method proposed was Locality Sensitive Hashing (LSH) [START_REF] Datar | Locality-sensitive hashing using stable distributions[END_REF]. Essentially, LSH uses a large number of hashing functions to project the high-dimensional vectors onto segmented random lines. At query time, these hash tables are probed with the query vector, and the candidates from all hash tables are then aggregated to find the true neighbors. The performance of such hashing schemes is highly dependent on the quality of the hashing functions. Hence, many approaches have been proposed to improve hashing [START_REF] Paulevé | Locality sensitive hashing: A comparison of hash function types and querying mechanisms[END_REF][START_REF] Zhang | HashFile: An efficient index structure for multimedia data[END_REF][START_REF] Jin | Complementary projection hashing[END_REF]. As with the quantization-based methods, none of these hashing-based methods support either dynamic updates or ACID properties of transactions.

Tree Structures A third approach is based on the idea of a search tree structure. The NV-tree is one proponent of this group. Fagin et al. [START_REF] Fagin | Efficient similarity search and classification via rank aggregation[END_REF] introduced the concept of median rank aggregation. They project the entire data collection on multiple random lines and index the ranked identifiers of the data points along each line, discarding the actual feature vectors. This ranking turns the high-dimensional vectors into simple sets of values which are inserted to B +trees. These B + -trees are probed at search time, and the nearest neigbors of the query are returned according to their aggregated rankings. The major drawback of that algorithm is the excessive search across the individual B + -trees [START_REF] Fagin | Efficient similarity search and classification via rank aggregation[END_REF].

Tao et al. [START_REF] Tao | Efficient and accurate nearest neighbor and closest pair search in high-dimensional space[END_REF] proposed another method for accessing high-dimensional data based on B + -trees, called the locality sentitive B-tree or LSB-tree. The LSB-tree approach inherits some of the properties of LSH, but in addition projects the hashed points onto a Z-order curve. Quality guarantees can be enforced using multiple LSB-trees in combination, forming an LSB-forest [START_REF] Tao | Efficient and accurate nearest neighbor and closest pair search in high-dimensional space[END_REF].

Muja and Lowe [START_REF] Muja | Scalable nearest neighbor algorithms for high dimensional data[END_REF] proposed, via the FLANN library, a series of highdimensional indexing techniques based on randomized KD-trees, k-means in-dexing and random projections. Another approach in the category of search trees is the Metric tree [START_REF] Uhlmann | Satisfying general proximity/similarity queries with metric trees[END_REF]; a variant named Spill-tree is a tree-structure based on splitting dimensions in a round-robin manner, and introducing (sometimes very significant) overlap in the split dimension to improve retrieval quality [START_REF] Liu | An investigation of practical approximate nearest neighbor algorithms[END_REF].

Many of the tree-based methods are either based on B + -trees, which support dynamic updates and transactions, or have proposed specific methods to address updates. Most of these methods, however, have only been used for relatively small collections. As far as we are aware, this article presents the first study that is considering updates at a scale of a billion features or more, and also the first study to consider transactional properties at this scale.

The NV-tree

The NV-tree [START_REF] Lejsek | NV-tree: An efficient disk-based index for approximate search in very large high-dimensional collections[END_REF][START_REF] Lejsek | NV-Tree: Nearest neighbours at the billion scale[END_REF] is a disk-based high-dimensional index, based upon a combination of projections of data points to lines and partitioning of the projected space. By repeating the process of projecting and partitioning, data is separated into small partitions which can be easily fetched from disk with a single read, and which are likely to contain all the close neighbors in the collection. We briefly describe the NV-tree creation process, its search procedure, its dynamic insert process and and then enumerate some salient properties of the NV-tree.

Index Creation Overall, an NV-tree is a tree index consisting of a hierarchy of small inner nodes, which guide the vector search to the appropriate leaf node, and larger leaf nodes, which contain references to actual vectors. The leaf nodes are further organised into leaf-groups that are disk I/O units, as described below.

When tree construction starts, all vectors from the collection are first projected onto a single projection line through the high-dimensional space ( [START_REF] Lejsek | NV-tree: An efficient disk-based index for approximate search in very large high-dimensional collections[END_REF] discusses projection line selection strategies). The projected values are then partitioned in 4 to 8 partitions based on their position on the projection line. Information about the partitions, such as the partition borders along the projection line, forms the first inner node of the tree-the root of the tree. To build the subsequent levels of the NV-tree, this process of projecting and partitioning is repeated recursively for each and every partition, using a new projection line for each partition, thus creating the hierarchy of smaller and smaller partitions represented by the inner nodes.

At the upper levels of the tree, with large partitions, the partitioning strategy assigns equal distance between partition boundaries at each level of the tree. The partitioning strategy changes when the vectors in the partition fit within 6×6 leaf nodes of 4 KB each. In this case, all the vectors from that partition are partitioned into a leaf-group made of (up to) 6 inner nodes, each containing (up to) 6 leaves. In this leaf-group, partitioning is done according to an equal cardinality criterion (instead of an equal distance criterion). Finally, for each leaf node, projection along a final random line gives the order of the vector identifiers and the ordered identifiers are written to disk. It is important to note that the vectors themselves are not stored; only their identifiers.

Indexing a collection of high-dimensional vectors with an NV-tree thus creates a tree of nodes keeping track of information about projection lines and partition boundaries. All the branches of the tree end with leaf-groups with (up to) 36 leaf nodes, which in turn store the vector identifiers.

Nearest Neighbor Retrieval During query processing, the search first traverses the hierarchy of inner nodes of the NV-tree. At each level of the tree, the query vector is projected to the projection line associated with the current node. The search is then directed to the sub-partition with center-point closest to the projection of the query vector until the search reaches a leaf-group, which is then fully fetched into RAM, possibly causing one single disk I/O. Within that leaf-group, the two nodes with center-point closest to the projection of the query vector are identified. The best two leaves from each of these two nodes are then scanned in order to form the final set of approximate nearest neighbors, with their rank depending on their proximity to the last projection of the query vector. The details of this process can be found in [START_REF] Lejsek | NV-Tree: Nearest neighbours at the billion scale[END_REF].

While the NV-tree is stored on disk, the hierarchy of inner nodes is read into memory once query processing starts, and remains fixed in memory. The larger leaf nodes, on the other hand, are read dynamically into memory as they are referenced. If the NV-tree fits into memory, the leaf nodes remain in memory and disk processing is avoided, but otherwise the buffer manager of the operating system may remove some leaf nodes from memory.

Insertions Insertion to NV-tree leaf nodes proceeds as follows. First, the leaf node where to insert a new vector identifier is identified. The position within that leaf is also determined and the insert is performed if the leaf is not full. As for most dynamic data structures, leaf nodes at index creation time are not filled completely (they are between 50% and 85% full, and about 70% full on average) in order to leave space for such insertions. A filled leaf node must be split in order to provide more storage capacity within the tree. During a split operation, a leaf-group is considered as a unit, and all the features of the leaf-group are re-organized using the same process as during index construction. In particular, when the size of the leaf-group exceeds the capacity of 6×6 leaf nodes, the group is split into 4 to 8 new leaf-groups, depending on the distribution of the features.

During leaf-group re-organization, new projection lines are chosen for internal nodes and the new leaf nodes. As leaf nodes only contain vector identifiers, the vectors must be retrieved from disk for re-projection. In [START_REF] Jónsson | SSD technology enables dynamic maintenance of persistent high-dimensional indexes[END_REF], it is shown that the most efficient option for handling re-projections is to maintain an independent feature database for each NV-tree, organized in the same manner as the leafgroups, to directly read the relevant features.

Properties of NV-trees

The experiments and analysis of [START_REF] Lejsek | NV-Tree: Nearest neighbours at the billion scale[END_REF] show that the NV-tree indexing scheme has the following properties:

-Random Projections and Ranking: The NV-tree uses random projections to turn multi-dimensional vectors into single-dimensional values indexed by B + -trees. Efficient implementations of dynamic B + -trees are well known.

The NV-tree does not fetch full vectors from disk to compute distances. In contrast, ranking is used, which basically amounts to scanning a list. -Single Read Performance Guarantee: As leaf-groups have a fixed size, the NV-tree guarantees query processing time of a single read regardless of the size of the vector collection. Larger collections need deeper NV-trees but the intermediate nodes fit easily in memory and tree traversal cost is negligible. -Compact Data Structure: The NV-tree stores in its index the identifiers of the vectors, not the vectors themselves. This amounts to about 6 bytes of storage per vector on average. The NV-tree is thus a very compact data structure. Compactness is desirable as it maximizes the chances of fitting the tree in memory, thus avoiding disk operations. -Consolidated Result: Random projections produce numerous false positives that can be almost all eliminated by an ensemble approach. Aggregating the results from a few NV-trees, which are built independently over the same collection, dramatically improve result quality.

The NV-tree, however, is not a transactional index. The next section specifies mechanisms to enforce the ACID properties of transactions within the NV-tree.

Transactional NV-tree

Large collections of media objects, and the corresponding collections of highdimensional vectors, are typically dynamic and require efficient insertions. For the typical web-scale application of visual instance search, however, it is safe to assume that (a) updates are made centrally, and (b) that throughput is more important for this update thread than response time. For these applications, it is feasible to batch insertions such that only one insertion thread is running at each time, which simplifies the implementation of the insertion process. Of course, however, insertions and searches must run concurrently. This section focuses on insertions to the NV-tree index. We outline the insertion operation, then describe enforcement of the ACID properties of transactions (Atomicity; Consistency; Isolation; and Durability), and finally consider the correctness and performance of the proposed methods. Note that while deletions will be rare in practice, they can be implemented using techniques very similar to those implementing insertions. We therefore briefly describe the differences for deletions, where appropriate. Updates are implemented as feature deletions followed by feature insertions.

Due to serialization of inserts, two insertion transactions will never conflict, which means that a simple locking mechanism based on tree-traversals is sufficient to enforce isolation. Because insertions are never aborted and they never deadlock, ensuring atomicity is only needed when the system crashes. Furthermore, since at most one insert transaction is running concurrently, enforcing durability is greatly simplified. Finally, since there are no constraints on the vectors, as such, the notion of consistency simply implies that the results always reflect the status after the last committed transaction.

We start by considering isolation and consistency for a single NV-tree. We then consider atomicity and durability, before addressing some practical issues relating to using multiple NV-trees.

Isolation and Consistency Isolation is implemented by adapting a standard locking algorithm from the B + -tree literature [START_REF] Gray | Transaction Processing: Concepts and Techniques[END_REF][START_REF] Srinivasan | Performance of B-tree concurrency control algorithms[END_REF]. A search thread starts by obtaining a read lock on the root of the NV-tree. Before accessing a child node, the thread must obtain a read lock on that node. At that point, the lock on the parent can be released. Finally, the leaf-group selected for retrieval is locked and only released after all necessary identifiers have been retrieved from the leaves. Note that locks are implemented using pthread mutexes; each internal node contains the mutexes for all its children and the leaf-groups are locked as a unit since they are treated as a unit during both retrieval and node splits. As the overhead of obtaining mutexes is low, locking is always activated.

The insertion process uses the same locking mechanism, except that finally an exclusive lock is acquired for the leaf-group, preventing concurrent insertions into that leaf-group, as well as concurrent retrieval from the leaf-group. In the case of a leaf-group split, a new internal node is created pointing to all the newly created leaf-groups; the lock on the original leaf-group is sufficient to protect the modification of the parent node.

Since each query or insertion transaction needs to access multiple trees multiple times, it is necessary, however, to consider the overall interaction between search and insertion transactions. Recall that insertion transactions are serialized; they are therefore assigned with ever-increasing transaction identifiers (TIDs) that are logged with each inserted vector. Isolation is then enforced by omitting from the query result vectors with transaction identifiers larger than that of the last transaction that committed before the search started; this also guarantees consistency of the result.

Deletions are implemented in the same manner as insertions, except that a list of deleted media items is maintained to avoid returning partially deleted items; when all feature vectors from a media item have been deleted, it can be removed from this list.

Atomicity and Durability

For atomicity and durability, we adopt the standard write-ahead logging (WAL) protocol [START_REF] Mohan | ARIES: A transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging[END_REF]. The WAL protocol uses a transaction log (or write-ahead log) which contains sufficient information to recover in case of failures. The WAL protocol has two rules to ensure the correctness of transactions:

1. The log entry for any modification must be written to disk before the modified data is written to disk. 2. All log entries for a transaction must be written to disk before the transaction can be committed.

The first rule-sometimes called the undo rule-ensures that any change written to the disk before it is committed can later be removed from the database, thus supporting atomicity. The second rule-the redo rule-ensures that committed changes can be redone in case of crashes, thus ensuring durability. Each split can result in a large number of disk operations and splits are therefore heavily buffered. It is best for performance to manage multiple log files where log records can be appended independently and in parallel. There is one log file per NV-tree plus a global log file for the correctness of the overall recovery process.

The recovery manager uses regular checkpoints to facilitate efficient recovery. During recovery, the latest checkpoint file is first read and the status at the time of the checkpoint is adopted for the internal nodes, the leaf nodes and the leaf-group DB. Then the split operations are retrieved from the index log file, and those split operations that were performed due to committed transactions are re-played on the internal structure, while other split operations are ignored. At this point, the internal structure is correct, as of the time of the crash, but vectors may be incorrectly included and/or missing. Next, therefore, vectors that belonged to uncommitted transactions, but made it to the leaf nodes of the NVtree are removed; note that no such vectors are ever found in the leaf-group DB, because they are only added to the leaf-group buffer when the transaction is ready to commit and the checkpoint is only written after commit. Finally, the vector collection log file is used to re-insert the committed vectors that did not make it to disk, both to the NV-tree and the leaf-group DB, taking care to avoid re-insertion to the split leaves.

Note that since insertion operations are serialized and do not conflict, the undo and redo phases can be performed in any order. Since vector removal requires moving other vector identifiers in the leaves, however, it makes sense to do that before inserting new identifiers.

Practical Issues with Multiple NV-trees When inserting to multiple NVtrees, each tree should preferably be located on a separate hard drive (as should the log files) so that the full write-back capacity of the disks can be used for the leaf-group DB thread. In order to fully use the capacity of the disks, however, it is important to decouple the insertion process (as well as logging and checkpointing) for each NV-tree. Each NV-tree can thus be inserting from a different transaction, but they must all process the transactions in the same order. Since transactions may progress differently across different trees, more than one uncommitted transaction may have inserted vectors to some trees before a crash. Due to the ordering of transactions, however, the last NV-tree to finish a transaction decides the commit time and transactions will therefore commit in the same order, and all the techniques described above are unaffected by this change. Using decoupling, disk utilization was improved from about 40% up to 75% to 80%, without violating the previously described ACID properties.

Correctness and Recovery Performance Since our techniques are built on standard building blocks from the database literature, which have been shown to enforce the ACID properties, a formal proof of correctness is beyond the scope of this paper. In the following, however, we give a brief outline of how such a proof would be structured.

A sufficient condition for enforcing isolation is serializability. Recall that we assume that insertion transactions stem from a single, serialized thread. Then the only conflicts that can arise are between this single insertion transaction and the (potentially many) retrieval transactions. As we use standard B + -tree locking for the data structure consistency, which is known to enforce serializability, and further ensure that retrieval transactions can only see insertions from transactions that committed before the retrieval started, isolation is fully enforced. And, as discussed above, since there are no constraints on the vectors, isolation is sufficient to enforce consistency for the class of applications considered here.

By definition, the WAL protocol enforces both atomicity and durability. The fact that the log is stored in multiple files does not change this property, as long as sufficient information is stored in the log entries to redo operations in the correct order. As described in detail above, the recovery operations have been carefully ordered to ensure correctness. The proposed method therefore enforces both atomicity and durability.

Proving the correctness of the implementation of our method, on the other hand, is of course extremely difficult, if at all possible. The implementation has been tested very methodically, however, by pausing operations in certain places and crashing the computer; in all cases has recovery been successful. The recovery performance depends on the frequency of the checkpoints, but with reasonable checkpoint frequency the database is always fully recovered within a matter of minutes even with very large collections.

Performance of Index Maintenance

In this section we investigate the performance of dynamic inserts, while guaranteeing ACID properties, as described above. As the index experiences splits upon inserts, it is also important to verify that the evolution of the data structure does not impact the ability of the NV-tree to correctly identify nearest neighbors. We first discuss insertion throughput and then result quality.

This experiment was designed to show the two interesting cases that govern the performance of inserts. In the first case, when the index fits in RAM, inserts are done in memory and later asynchronously pushed to disks, resulting in excellent performance. The second case arises when the index is larger than memory. In this case, loading the affected data pages from disk may be required, which is not only slow but also interferes with writing back updated pages. We therefore expect this second case to show much worse performance.

To illustrate these two cases, we used a machine with only 32GB of main memory. We used a small subset of a very large collection of images from Flickr to first compute 36 million SIFT vectors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], which were indexed with three NV-trees. This is a tiny collection which can be indexed very quickly, and the resulting NV-trees together occupy slightly more than 500MB. We then ran sequences of 1,000 insertion transactions, where each transaction inserted 100,000 new vectors into the three NV-trees, which means that each sequence inserted 100 million new vectors. We then observed the time taken for each sequence to complete. We repeated this process and ran multiple sequences until each NV-tree contained nearly 2.5 billion vectors, occupying about 328 GB each.

Insertion Throughput Figure 1 shows the evolution of the insertion throughput (measured by vectors inserted per second) for the duration of this workload.

In the beginning of this workload, all three NV-trees fit into main memory and the throughput is excellent, around five thousand vectors per second. After running 18 such transactions, thus inserting 1.8 billion vectors, the 3 NV-trees no longer fit in main memory. After that point, Figure 1 clearly shows the insert behavior corresponding to the second case discussed above, where the rate of inserts slows down significantly due to conflicting disk operations. It should be noted, however, that with throughput of 500 vectors per second, each insertion only takes 2 ms, which is significantly less than one disk operation per insertion, even though the descriptors are inserted to three NV-trees simultaneously.

The most important aspect of this experiment is not the reduced performance of inserts after 1.8 billion vectors have been inserted and the index no longer fits in memory; by adding more memory, larger indices can be stored in RAM. Rather it is the fact that even when the collection no longer fits in memory, and must be stored on traditional HDDs, dynamic maintenance of the index is still possible as the insertion throughput degrades gracefully. And, of course, performance of index maintenance could be vastly improved if SSDs were used instead of HDDs.

Evolution of Retrieval Quality To evaluate the query performance of the NV-tree, we borrow the ground truth defined by [START_REF] Lejsek | NV-tree: An efficient disk-based index for approximate search in very large high-dimensional collections[END_REF]. A sequential scan was used to determine the 1,000 nearest neighbors of 500,000 query vectors, all coming from a very large collection of SIFTs. The resulting 500M neighbors were then analysed to identify 248,212 vectors as being meaningful nearest neighbors of the query points (as defined by [START_REF] Beyer | When is "nearest neighbor" meaningful?[END_REF]).

To reuse that workload, we included these 248,212 vectors in the database of 36 million other vectors used previously. Once this database was created, we ran the same 500,000 queries as in [START_REF] Lejsek | NV-tree: An efficient disk-based index for approximate search in very large high-dimensional collections[END_REF] and computed their recall, i.e., we counted how many of these 248,212 ground truth vectors were found. We repeated that same workload after every insertion transaction (of 100 million vectors), to observe how the quality of the answers evolves as the database grows.

Figure 2 plots the recall percentage from the 500,000 queries described above, as the collection grows in size. The figure shows a configuration where the results are aggregated from three NV-trees. As the figure shows, recall drops slowly as the collection grows, which was expected. For comparison, the figure also contains a dashed line indicating the result quality when the NV-trees for the 2.5 billion vectors are constructed from scratch via bulk loading. As the figure shows, the results for the dynamically created NV-trees and the bulk-loaded NV-trees are identical, meaning that dynamicity has no impact on result quality.

Conclusion

Visual instance search is the task of retrieving from a database of images the ones that contain an instance of a visual query. So far, only local image features are powerful enough to support such fine-grained recognition. Recent progress in approximate high-dimensional indexing has resulted in approaches handling several hundred million to a few billion high-dimensional vectors with excellent response times. These methods typically rely on residing in main memory for performance. We argue, however, that data quantity will always win over memory capacity in the long term. Therefore, high-dimensional indexing solutions that are truly concerned with the scalability of the feature collections they manage must address collection sizes beyond RAM capacity and efficiently utilize disks for extending storage.

Furthermore, we argue that scalability is not the only challenge that must be met as high-dimensional indexing methods must also provide dynamicity-the ability to cope with on-line insertions of features into the indexed collection, and durability-the ability to recover from crashes and avoid losing the indexed data if a failure occurs. As far as we know, no nearest neighbor algorithm published so far is able to cope with all three requirements: scale, dynamicity and durability.

In this article, we have extended an existing disk-based high-dimensional index, the NV-tree, such that it enforces the ACID properties of transactions. Experiments show that with our implementation dynamic inserts can be efficiently managed: when the index fits in memory, performance is excellent, but when the index no longer fits in memory, performance degrades very gracefully. Indeed, the technology described in this paper is in use at Videntifier Technologies, one of the main players in the forensics arena, with technology deployed at such clients as Interpol. Their search engine is currently able to index and identify videos (at about 40x real time) from a collection of nearly 150 thou-sand hours of video, and about 700 hours of video material can be dynamically inserted to the index every day.

Fig. 2 .

 2 Fig. 2. Retrieval quality.


Laurent Amsaleg
email: laurent.amsaleg@irisa.fr

Thor Björn

Herwig Jónsson

Lejsek

Björn Þór Jónsson

Herwig Lejsek

Scalability of the NV-tree: Three Experiments

HAL is

Introduction

Visual instance search (VIS) is the task of retrieving from a media collection the items that contain an actual instance of a visual query. Various real world applications require such fine-grained recognition capabilities, including forensics and copyright enforcement. A common theme in these applications is that the media collection is very large, calling for scalable indexing methods.

Due to the fine-grained nature of VIS, this domain will always require many local features for each media item. Query processing will then boil down to running multiple k-NN queries and consolidating the result into a single reply. Currently, SIFT features are the state-of-the-art for the VIS domain when considering extremely large image datasets: hundreds of local features are typically generated for each media item and result consolidation can be done via simple voting schemes. The scalability problem is compounded due to the multiple features generated: a VIS system handling tens of millions of images, for example, may need to manage tens of billions of local features.

At industry scale, VIS applications have the following requirements:

-The visual query typically results in multiple query features. Approximate indexing schemes are thus applicable to VIS applications, and in fact they can often tolerate fairly low recall. -Each k-NN query is actually looking only for very specific features; in the case of copy detection applications typically only one feature. The appropriate quality metric is thus Recall@k. -Due to the scale of the feature collections, data may not fit in memory. The high-dimensional index must thus support disk-based processing. [START_REF] Moise | Indexing and searching 100M images with Map-Reduce[END_REF] Babenko and Lempitsky (2015) [START_REF] Babenko | The inverted multi-index[END_REF] Gudmundsson et al. (2017) [START_REF] Guðmundsson | Towards engineering a web-scale multimedia service: A case study using Spark[END_REF] This Submission (2018) -VIS applications are typically part of a larger pipeline, so query processing costs must be small and, no less importantly, predictable.

In previous work, we have proposed the NV-tree [START_REF] Lejsek | NV-tree: An efficient disk-based index for approximate search in very large high-dimensional collections[END_REF][START_REF] Lejsek | NV-Tree: Nearest neighbours at the billion scale[END_REF], a scalable approximate high-dimensional specifically designed for large-scale VIS applications. The NV-tree builds upon a combination of projections of data points to lines and partitioning of the projected space. By repeating the process of projecting and partitioning, data is separated into small neighborhoods which can be easily fetched from disk with a single read. By construction, the NV-tree thus guarantees query processing cost of at most one disk read per index per query feature.

Fig. 1 shows a summary of all works reported in the literature with collections of at least 1B features. As the figure shows, the NV-tree has already been used for the largest reported single-server installation, with 2.5B features. The only two other systems that have been applied at this scale are Product Quantisation (PQ) [START_REF] Jégou | Searching in one billion vectors: re-rank with source coding[END_REF] and Inverted Multi-Index (IMI) [START_REF] Babenko | The inverted multi-index[END_REF][START_REF] Babenko | The inverted multi-index[END_REF], while only installations based on Hadoop [START_REF] Moise | Indexing and searching 100M images with Map-Reduce[END_REF] and Spark [START_REF] Guðmundsson | Towards engineering a web-scale multimedia service: A case study using Spark[END_REF] have used larger collections. The figure also shows that the largest collections reported in this paper contain 28.5B features; an order of magnitude more than the other single-server approaches have managed.

In this paper, we report on three experiments designed to evaluate the suitability of the NV-tree for VIS applications:

-In Section 3 we report on two image-based VIS benchmarks, embedded within collections of up to 28.5B distracting features, the largest single-server collection reported in the literature. -In Section 4 we report on a single-query benchmark from our previous work, again embedded within collections of up to 28.5B features. -In Section 5 we compare the NV-tree to PQ and IMI using the relatively small SIFT1B benchmark. While this is not a VIS benchmark, we use it because it represents the largest collection used by those systems. We then analyse how PQ and IMI would perform with the 28.5B collection.

The results show that the NV-tree does very well for the large-scale VIS applications. With the small-scale non-VIS benchmark, the NV-tree has better performance but lower result quality. Further, our analysis shows that query processing performance of PQ and IMI would suffer with the 28.5B collection.

The NV-tree is proven technology, already in use at Videntifier Technologies, one of the main players in the forensics arena with technology deployed at such clients as Interpol. Their search engine targets fine-grained VIS for investigations that, e.g., aim to dismantle child abuse networks. The search engine can identify very fine-grained details in still images and videos from a collection of 150 thousand hours of video, typically scanning videos at 40x real-time speed, and while allowing dynamic insertions of about 700 hours of video material every day.

The NV-tree

The NV-tree [START_REF] Lejsek | NV-tree: An efficient disk-based index for approximate search in very large high-dimensional collections[END_REF][START_REF] Lejsek | NV-Tree: Nearest neighbours at the billion scale[END_REF] is a disk-based high-dimensional index. It builds upon a combination of projections of data points to lines and partitioning of the projected space. By repeating the process of projecting and partitioning, data is separated into small partitions which can be easily fetched from disk with a single read, and which are likely to contain all the close neighbors in the collection. We briefly describe the NV-tree creation process, its search procedure, its dynamic insert process and and then enumerate some salient properties of the NV-tree.

Index Creation

Overall, an NV-tree is a tree index consisting of: a) a hierarchy of small inner nodes, which guide the feature search to the appropriate leaf node; and b) larger leaf nodes, which contain references to actual features. The leaf nodes are further organised into leaf-groups that are disk I/O units, as described below.

When tree construction starts, all features from the collection are first projected onto a single projection line through the high-dimensional space ( [START_REF] Lejsek | NV-tree: An efficient disk-based index for approximate search in very large high-dimensional collections[END_REF] discusses projection line selection strategies). The projected values are then partitioned in 4 to 8 partitions based on their position on the projection line. Information about the partitions, such as the partition borders along the projection line, forms the first inner node of the tree-the root of the tree. To build the subsequent levels of the NV-tree, this process of projecting and partitioning is repeated recursively for each and every partition, using a new projection line for each partition, thus creating the hierarchy of smaller and smaller partitions represented by the inner nodes.

At the upper levels of the tree, with large partitions, the partitioning strategy assigns equal distance between partition boundaries at each level of the tree. The partitioning strategy changes when the features in the partition fit within 6×6 leaf nodes of 4 KB each. In this case, all the features from that partition are partitioned into a leaf-group made of (up to) 6 inner nodes, each containing (up to) 6 leaves. In this leaf-group, partitioning is done according to an equal cardinality criterion (instead of an equal distance criterion). Finally, for each leaf node, projection along a final random line gives the order of the feature identifiers and the ordered identifiers are written to disk. It is important to note that the features themselves are not stored; only their identifiers.

Indexing a collection of high-dimensional features with an NV-tree thus creates a tree of nodes keeping track of information about projection lines and partition boundaries. All the branches of the tree end with leaf-groups with (up to) 36 leaf nodes, which in turn store the feature identifiers.

Nearest Neighbor Retrieval

During query processing, the search first traverses the hierarchy of inner nodes of the NV-tree. At each level of the tree, the query feature is projected to the projection line associated with the current node. The search is then directed to the sub-partition with center-point closest to the projection of the query feature until the search reaches a leaf-group, which is then fully fetched into RAM, possibly causing one single disk I/O. Within that leaf-group, the two nodes with center-point closest to the projection of the query feature are identified. The best two leaves from each of these two nodes are then scanned in order to form the final set of approximate nearest neighbors, with their rank depending on their proximity to the last projection of the query feature. The details of this process can be found in [START_REF] Lejsek | NV-Tree: Nearest neighbours at the billion scale[END_REF].

While the NV-tree is stored on disk, the hierarchy of inner nodes is read into memory once query processing starts, and remains fixed in memory. The larger leaf nodes, on the other hand, are read dynamically into memory as they are referenced. If the NV-tree fits into memory, the leaf nodes remain in memory and disk processing is avoided, but otherwise the buffer manager of the operating system may remove some leaf nodes from memory.

Properties of NV-trees

The experiments and analysis of [START_REF] Lejsek | NV-Tree: Nearest neighbours at the billion scale[END_REF] show that the NV-tree indexing scheme has the following properties:

-Scalar Quantization: The NV-tree uses random projections to turn multidimensional features into single-dimensional values indexed by B + -trees. As only feature identifiers are stored, the NV-tree requires 6 bytes per feature. -Single Read Performance Guarantee: In the NV-tree, leaf-groups have a fixed size. Therefore, the NV-tree guarantees query processing time of a single read regardless of the size of the feature collection. Larger collections need deeper NV-trees but intermediate nodes fit easily in memory and tree traversal cost is negligible. -Compact Data Structure: The NV-tree stores in its index the identifiers of the features, not the features themselves. This amounts to about 6 bytes of storage per features on average. The NV-tree is thus a very compact data structure. Compactness is desirable as it maximizes the chances of fitting the tree in memory, thus avoiding disk operations.

-Consolidated Result: Random projections produce numerous false positives that can be almost all eliminated by an ensemble approach. Aggregating the results from a few NV-trees, which are built independently over the same collection, dramatically improve result quality.

3 Experiment 1: Image Benchmarks at Scale

In this first experiment, we have adopted a traditional fine-grained quasi-copy paradigm, implemented using SIFT features. We report on two benchmarks from the literature, embedded in collections of up to 28.5 billion "distracting" features.

The resulting feature collection is so large (3.7 Tera bytes) that no other highdimensional indexing scheme from the litterature could handle it. The NV-tree could therefore not be compared to any other scheme from the litterature. This applies to the results presented in this section, as well as the ones reported in Section 4.

Image Datasets and Ground Truth

The image retrieval benchmarks are the "49k" benchmark [START_REF] Amsaleg | A database perspective on large scale high-dimensional indexing[END_REF] and the "Copydays" benchmark [START_REF] Douze | Evaluation of gist descriptors for web-scale image search[END_REF]. These benchmarks apply predefined image transformations to a particular collection of images to obtain a set of query images. We then "drown" the original images, used to create the transformed quasi-copies, within a large collection of random images which play the role of "distracting" the search. The transformed query images are then evaluated against the indexed collection and the location of the original image in the final result list is noted. When the first image in the ranked result list is the original image, the answer is considered correct; if the first image in the ranked list is not the original image, then the system is said to fail, even if that image turns out to be second in the ranked list.

For each transformation, 100% success means that all the ground truth images were at the top of the corresponding ranked lists in the result set. All pictures used in our experiments were resized such that their longer edge is 512 pixels long. We did this to ensure that the number of SIFT features [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] computed over each image was about one thousand on average. All the original images used to create the quasi-copies of the 49k and Copydays benchmarks were resized accordingly. Queries and their counterparts are therefore consistent with respect to the distracting image collection within which they are drowned.

49k Image Benchmark For this benchmark, one thousand images were randomly selected from Flickr, resulting in a very diverse collection. For each image, the Stirmark software [START_REF] Petitcolas | A public automated web-based evaluation service for watermarking schemes: StirMark benchmark[END_REF] was used to generate 49 different transformations, summarized in [START_REF] Amsaleg | A database perspective on large scale high-dimensional indexing[END_REF]. Overall, this process generates 49,000 quasi-copy query images, hence the name "49k". Note that some of these quasi-copies are quite dissimilar from their original counterpart. For example, the CONV_2 transform tends to be extremely dark, to the point where very few SIFT features can be computed from the transformed images, making this quasi-copy very hard to find. The MEDIAN_9, NOISE_5 and PSNR_50 are also quite different, making the identification of their original counterparts challenging, especially because the SIFT features of the quasi-copies are either at different scales or at different locations in the images, since the visual noise produces very different local DoG extrema. Finally, it is worth noting that crops are inherently challenging since they dramatically reduce the number of SIFT features that can be computed for the quasi-copies, which in turn strongly decreases the number of possible matches. This is a truly difficult instance search problem.

Copydays Image Benchmark This benchmark is a publicly available collection [START_REF] Douze | Evaluation of gist descriptors for web-scale image search[END_REF] used in several publications. We use this benchmark for our experiments because it contains quasi-copies that are more severely distorted than the ones in the 49k benchmark, making the original images much harder to find. Copydays contains 157 original images. Three families of transformations have been applied, as summarized in [START_REF] Douze | Evaluation of gist descriptors for web-scale image search[END_REF], resulting in 3,055 quasi-copies in total. Some of the 229 manual transformations are particularly difficult to find since they generate quasi-copies that are visually extremely different from their original counterparts. For example, Fig. 2 shows two original images along with one strong (manually created) variant.

Distracting Image Collections To evaluate the result quality produced by the NV-tree, we inserted the original images of the 49k and Copydays image sets into a larger set of images randomly downloaded from Flickr between 2009 and 2011. The downloading process rejected images smaller than 100x100 pixels and also used MD5 signatures to reject exact duplicates of any previously downloaded images. We have gathered almost 30 million such images, and we varied the number of distracting images in order to study the impact of collection size on the result quality of the indexing scheme. We report on experiments with three different data collections, all including the original images from the 49k and Copydays image sets, but having a different number of distracting images, resulting in roughly 300M, 3B and 28.5B features (see Table 1).

Result Quality

49k Image Benchmark Fig. 3 shows the result quality when querying three NV-trees with the 49 transformations, varying the distracting image collections. Fig. 3 reads as follows: 100% of the ground truth images are found for 8.16% of the queries when the distracting collection is the 300M set. This means that all 1,000 ground truth images were ranked #1 in the result set for 4 of the 49 transformations. Continuing with the 300M distracting set, then 43 transformations are found from 90% to 100% of the time, or 87.17% of the queries.

Moving to larger distracting sets, 6.12% of the transformations are always found within the 3B set while this percentage goes down to 4.08% with the 28.5B set. In turn, more transformations are found between 90% and 100% of the times as depicted by the large gray area which grows to 91.84% with 3B and 93.88% with 28.5B. Overall, image retrieval works extremely well as almost all the ground truth images are found when queried with images belonging to the 49k image benchmark, with all three distracting collection sizes.

A few comments are in order, however. First, crops are always found, validating instance search. Second, one image variant is almost never found, no matter which distracting image collection is used; this is the "CONV_2" variant, which produces almost completely black images where next to no detail remains. It is common that the computation of the SIFT features on these images produces no features at all, or only one or two features, making the results random. Third, for some transformations, 100% recall is not reached. For example, for the collection that contains 28.5B features, "JPEG_15" gives 98.5%, "RML_10" gives 98.4% and "MEDIAN_9" gives 96.5%. A detailed analysis of the result lists shows that in all these cases, the ground truth images are ranked from #2 (the most frequent situation) to #5. This is an extremely good result, especially because our success criterion-considering only rank #1-is very strict. Copydays Image Benchmark Fig. 4 shows the result quality for the Copydays image benchmark. Overall, the results are excellent for all but the most difficult variants. The NV-tree is able to identify the correct images most of the time, even from quite strongly distorted queries. It is not surprising to observe that quality drops with extremely compressed images (a person can sometimes hardly find any similarity between a JPEG 3% compressed image and its original version) and with some of the strong variants. Note that sometimes such attacked query images create only a handful of features, so there are too few matches for the original to rank #1-it is lost in the noise.

Retrieval Performance

We ran experiments using a Dell r710 machine that has two Intel X5650 2.67 Ghz CPUs. Each CPU has 12 MB of L3 cache that is shared by 6 actual and 6 virtual cores. The RAM consists of 18x8 GB 800 Mhz RDIMMs chips for a total of 144 GB. That machine is connected to a NAS 3070 storage system from NetApp, offering about 100TB of magnetic disk space in a RAID configuration. We ran the experiments using a single core, using three NV-trees which are probed one after the other; no parallelism is enforced in our experiments to simlipfy interpretation of the results. When the three NV-trees fit entirely in main memory, which is the case for the 300M and the 3B collections, answering each query feature is extremely fast. A detailed analysis shows that, on average, 2,500 query features can be processed per second. On average, therefore, identifying 100 near neighbors of a single query feature takes about 0.4 milliseconds per NV-tree. In turn, as there are about 1,000 query features per image, it takes about 400 milliseconds to identify the images that are the most similar to the query image.

When using the 28.5B collection, however, no index fits entirely in main memory. In this case, the system must therefore read data from disks for almost every query feature; as each query feature is likely to access a different part of the index, no main memory buffering policy is effective. Detailed analysis shows that about 50 query features could be processed per second in this case, which is 50 times slower than for the cases where the index fit in RAM. In the case of the 28.5B collection, it is thus possible to return the answer to a single query feature in 22.47 milliseconds on average, while an image takes about 2.25 seconds.

Note that since some queries have very few features while others have more features, the retrieval time varies significantly. As pointed out earlier, however, the construction process of the NV-tree is such that the search requires only a single disk read. Because three NV-trees are used, no more than three disk reads are thus performed per feature search, and only 3,000 features are considered on average, out of the 28.5B, which is about 0.00001% of the collection.

Experiment 2: Single Feature Recall at Scale

This section again analyses the ability of the NV-tree index structure to cope with truly large-scale data collections, reporting results with up to 28.5B features, this time focusing on the recall of single query features.

Experimental Setup

In this experiment, we use the ground truth defined in [START_REF] Lejsek | NV-tree: An efficient disk-based index for approximate search in very large high-dimensional collections[END_REF]. A sequential scan was used to determine the 1,000 nearest neighbors of 500,000 query features, all coming from a collection of 180 million SIFT features. Analyzing the resulting 500M neighbors, we identified 248,212 features as being contrasted enough to be considered the true nearest neighbors of the query features. Contrast here is directly derived from criterion of [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]: a neighbor is considered a true neighbor if it is significantly closer than neighbor number one hundred.

We then embed these 248,212 features within feature sets of varying cardinalities to distract the search. These sets of distracting features have been created by extracting SIFT features from up to 30 million images randomly downloaded from Flickr. The images are ignored here, however, as we focus on individual query features. The resulting distractor sets are shown in Table 2.

This experiment focuses on recall, i.e., how many of these 248,212 ground truth features are found using the original set of 500,000 queries when varying the number of distractors, but we also report on retrieval performance. We are not aware of any other experiment ever published where recall measurements are obtained from searching the nearest neighbors of individual query features lost within 28.5B distracting features.

Quality of Nearest Neighbor Retrieval

Fig. 5 shows the recall for the different distractor collections. The x-axis shows the size of the distractor collections (note the logarithmic scale), while the y-axis shows the impact on recall of using a varying number of NV-trees. Up to three NV-trees were used against all the collections. We also considered using up to six NV-trees to improve recall; as such experiments are complicated and time consuming, however, we used only two moderate size datasets for this purpose. Fig. 5 shows that when using a single NV-tree, recall is relatively low. Close to 54% of the 248,212 truth features are found when they are lost in the 30M collection. This percentage then slowly decreases as the distracting collection grows, to about 38% when challenged by the 28.5B collection.

Using additional indices dramatically improves performance, however. With the 30M collection, recall jumps to 72% with two NV-trees and 79% using three NV-trees. At the other end of the figure, with the 28.5B collection, recall is lower as before but remains remarkably good given the size of the distracting collection: 52% with two NV-trees and 58% with three NV-trees.

Using more than three NV-trees provides a slight recall improvement, but not as dramatic as going from a single NV-tree to two and three. Multiplying the number of NV-trees is therefore not a worthy option, since it increases the pressure on storage and main memory and increases the retrieval cost.

Retrieval Performance

We now turn to the retrieval performance. We ran this experiment on the same system as in the previous experiment, and therefore the retrieval performance was identical. Recall that the main memory of our server was 144 GB, which means that all the leaves of three NV-trees can fit into memory for all collections except the 28.5B collection. When the various indices entirely fit in main memory, answering each query feature is extremely fast, as before: it takes a fraction of a millisecond to process one feature against one NV-tree. When using the 28.5B collection, on the other hand, main memory can not fit even one NV-tree, and the response time is therefore larger, but still only about 22.5 ms per query.

5 Experiment 3: The Small-Scale SIFT1B Benchmark

In this experiment we examine the SIFT1B benchmark, as this is the largest benchmark for which there are results for the primary competitors from the literature: Product Quantization (PQ) [START_REF] Jégou | Searching in one billion vectors: re-rank with source coding[END_REF] and the Inverted Multi-Index (IMI) [START_REF] Babenko | The inverted multi-index[END_REF][START_REF] Babenko | The inverted multi-index[END_REF]. Note, however, that we consider SIFT1B to be a relatively small benchmark. As the NV-tree index was designed primarily for very large collections, this analysis favors its competitors significantly.

Previous work has directly compared the NV-tree to many approaches, including LSH, median rank aggregation and the Spill-Tree, showing that NV-tree significantly outperforms those approaches already at a much smaller scale [START_REF] Lejsek | NV-tree: An efficient disk-based index for approximate search in very large high-dimensional collections[END_REF]. But it is insightful to determine the disk space requirements and expected disk read performance if the more recent state-of-the-art techniques were used to index the 28.5B features used in the previous two experiments. We make this comparison at the end of this section.

Experimental Setup

SIFT1B is a collection of exactly one billion 128-dimensional SIFT features extracted from natural images [START_REF] Jégou | Searching in one billion vectors: re-rank with source coding[END_REF], which is publicly available and has been used in many publications, including [START_REF] Babenko | The inverted multi-index[END_REF]. The dataset comes with pre-calculated ground truth, where the exact 1,000 nearest neighbors for each of the 10,000 queries are provided; these neighbors were identified using a (long!) sequential scan computing euclidean distances. The measure used to compare systems indexing this SIFT1B dataset is the Recall@R, which for varying values of R determines the average rate of queries for which the 1-nearest neighbor is ranked in the top R positions. The SIFT1B data set was indexed by the NV-tree and the queries run. We then compare those results to the results reported in [START_REF] Babenko | The inverted multi-index[END_REF], which were obtained using fairly similar hardware. In our analysis, we focus on the Recall@1 measure, and observe that all collections fit easily in main memory, as we use the same server as before.

Results

Table 3 shows the comparison of the three methods: PQ, IMI, and NV-tree. For IMI, three variants are shown, where the latter apply some additional optimizations [START_REF] Babenko | The inverted multi-index[END_REF]. As the table shows, IMI improves on PQ in all aspects: result quality, features read, and retrieval time. Optimizations to IMI then further improve quality but at a very significant cost of retrieval time. Table 3 also shows that while the NV-tree returns worse results, it performs better, both in terms of features read and retrieval time. By construction, the NV-tree scans contents from exactly four leafs in order to build its result, and was asked to return only k = 1, 000 neighbors from each tree, for a total of 3,000 features scanned. As the NV-tree only stores the identifier of the feature, no reranking is performed after retrieval, unlike IMI and PQ, which may help explain the reduced result quality. Furthermore, unlike the other approaches, only one disk access is required per index even in the large-scale scenario of the following experiment.

This comparison shows that the NV-tree and IMI offer quite different tradeoffs between retrieval performance and quality. IMI requires more work to i) discover which cells to read, ii) read the cells, and iii) post-process the results. At a small scale, however, such as with this small SIFT1B collection, IMI does indeed offer a good trade-off between quality and retrieval time. As the scale of the collections grows, however, this trade-off becomes less and less viable.

Scalability Analysis

It is insightful to determine the disk space requirements and expected disk read performance if PQ and IMI were used to index the 28.5B features used in the previous experiments. PQ uses at least 32 bytes per feature, so indexing 28.5B features would require close to 1TB of memory. Product quantization must scan a substantial number of cells in order to return high quality results-typically 16 cells per query feature, with each cell requiring at least one random disk readwhich amounts to a few hundred thousands points at least; clearly impossible in a disk-based setting.

IMI improves on PQ in a main-memory situation, and can obtain reasonable quality by examining only between 10 thousand and 100 thousand data points. Their most compact proposal uses only 12 bytes per feature (4 for the identifier and 8 bytes for information used for improving quality). With these settings, indexing the 28.5B collection in memory would require at least 320 GB of main memory (ignoring all overheads). In a disk-based setting, however, the key question is how many cells would be read, as each cell requires a random disk read. Unfortunately, [START_REF] Babenko | The inverted multi-index[END_REF] gives no information on the cell size distribution. As they use 2 14 ×2 14 cells, however, each cell would contain on average just over one hundred data points, and 95 cells would need to be read on average to retrieve 10,000 candidates, and about 950 to retrieve 100,000 candidates. Results from [START_REF] Babenko | Efficient indexing of billion-scale datasets of deep descriptors[END_REF] indicated that only about half of these cells are empty, so about 50 cells would need to be read on average to retrieve 10,000 candidates, and almost 500 cells to retrieve 100,000 candidates. Note that we have used the settings for a 1B feature collection in this analysis; it is of course not clear that those settings would yield sufficient result quality with 28.5B features. What is clear, however, is that the response time of IMI would be unacceptable at this scale in an industry setting.

In contrast, as discussed below, while we typically index each collection using three NV-trees, only a single disk read is required per NV-tree and fewer than one thousand feature identifiers are typically considered per tree when constructing the approximate answer, independent of the scale of the collection.

Conclusion

The NV-tree is a scalable approximate high-dimensional indexing method specifically designed for visual instance search (VIS) at large scale. In this paper, we have reported on three experiments designed to evaluate the suitability of the NV-tree for VIS applications. Two of these experiments embed VIS benchmarks from the literature within collections of up to 28.5B high-dimensional features, which is the largest single-server collection reported in the literature. The results show that indeed the NV-tree performs very well for VIS applications over large-scale collections. With the small-scale non-VIS benchmark, the NV-tree has better performance but lower result quality, but our analysis shows that query processing performance of PQ and IMI would suffer with the 28.5B collection.

The NV-tree index is a proven technology, as it is already in use at Videntifier Technologies, one of the main players in the forensics arena with technology deployed at such clients as Interpol. Their search engine targets fine-grained VIS for investigations that, e.g., aim to dismantle child abuse networks. The search engine can identify very fine-grained details in still images and videos

  Liu et al. (2007) [10] Jegou et al. (2011) [7] Lejsek et al. (2011) [9] Sun et al. (2013) [14] Moise et al. (2013)

Fig. 1 .

 1 Fig. 1. The largest experimental collections reported in the literature. Black bars represent results using the NV-tree. Shaded bars represent multi-server configurations.

Fig. 2 .

 2 Fig. 2. Examples from Copydays: (a) and (c) are two original images, while (b) and (d) are two strong variants used as queries. Size ratio is preserved.

Fig. 4 .

 4 Fig. 4. Result quality for CopyDays.

Fig. 5 .

 5 Fig. 5. Recall, varying collection sizes, varying number of NV-trees.

Table 1 .

 1 Distracting image collections used in Experiment 1.

	Collection Images	SIFTs	Disk Size
	300M	334,268	305,443,749 40.3 GB
	3B	2,970,596 3,040,856,472 401 GB
	28.5B	28,969,271 28,484,904,924	3.7 TB

Table 2 .

 2 Distracting feature collections for Experiment 2.

	Collection SIFT Features Feature Collection Size NV-tree Size
	30M	28,799,690	3.8 GB	180 MB
	180M	179,443,881	23.6 GB	1 GB
	300M	305,443,749	40.3 GB	1.9 GB
	2.5B	2,485,568,191	328 GB	14 GB
	3B	3,040,856,472	401 GB	17 GB
	28.5B	28,484,904,924	3.7 TB	162 GB

Table 3 .

 3 Performance Comparison Using SIFT1B. Results for PQ and IMI variants are reproduced from[START_REF] Babenko | The inverted multi-index[END_REF].

		Bytes / Quality	Features Retrieval Index
	Indexing Method	Feature (Recall@1) Read	Time	Size
	NV-tree (3 indices)	18	0.076	3 K	1.2 ms	18 GB
	PQ	12	0.112	∼8 million 155 ms	12 GB
	Multi-Index	12	0.158	10 K	2 ms	13 GB
		12	0.165	100 K	11 ms	13 GB
	-OMulti-D-OADC-Local	12	0.268	10 K	6 ms	15 GB
		12	0.286	100 K	50 ms	15 GB
	-16 bytes per feature &	20	0.421	10 K	7 ms	23 GB
	OMulti-D-OADC-Local	20	0.467	100 K	66 ms	23 GB

from a collection of 150 thousand hours of video, typically scanning videos at 40x real-time speed, and about 700 hours of video material can be dynamically added to the index every day.