Loïc Paulevé
email: loic.pauleve@ens-cachan.org

Hervé Jégou
email: herve.jegou@inria.fr

Laurent Amsaleg
email: laurent.amsaleg@irisa.fr

Locality sensitive hashing: a comparison of hash function types and querying mechanisms

It is well known that high-dimensional nearest-neighbor retrieval is very expensive. Dramatic performance gains are obtained using approximate search schemes, such as the popular Locality-Sensitive Hashing (LSH). Several extensions have been proposed to address the limitations of this algorithm, in particular, by choosing more appropriate hash functions to better partition the vector space. All the proposed extensions, however, rely on a structured quantizer for hashing, poorly fitting real data sets, limiting its performance in practice. In this paper, we compare several families of space hashing functions in a real setup, namely when searching for high-dimension SIFT descriptors. The comparison of random projections, lattice quantizers, k-means and hierarchical k-means reveal that unstructured quantizer significantly improves the accuracy of LSH, as it closely fits the data in the feature space.

We then compare two querying mechanisms introduced in the literature with the one originally proposed in LSH, and discuss their respective merits and limitations.

Introduction

Nearest neighbor search is inherently expensive due to the curse of dimensionality [START_REF] Böhm | Searching in highdimensional spaces: Index structures for improving the performance of multimedia databases[END_REF][START_REF] Beyer | When is "nearest neighbor" meaningful?[END_REF]. This operation is required by many pattern recognition applications. In image retrieval or object recognition, the numerous descriptors of an image have to be matched with those of a descriptor dataset (direct matching) or a codebook (in bagof-features approaches). Approximate nearest-neighbor (ANN) algorithms are an interesting way of dramatically improving the search speed, and are often a necessity. Several ad hoc approaches have been proposed for vector quantization (see Gray and Neuhoff, 1998, for references), when finding the exact nearest neighbor is not mandatory as long as the reconstruction error is limited. More specific ANN approaches performing content-based image retrieval using local descriptors have been proposed [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Lejsek | Scalability of local image descriptors: a comparative study[END_REF]. Overall, one of the most popular ANN algorithms is the Euclidean Locality-Sensitive Hashing (E2LSH) [START_REF] Datar | Locality-sensitive hashing scheme based on p-stable distributions[END_REF][START_REF] Shakhnarovich | Nearest-Neighbor Methods in Learning and Vision: Theory and Practice[END_REF]. LSH has been successfully used in several multimedia applications [START_REF] Ke | Efficient near-duplicate detection and sub-image retrieval[END_REF][START_REF] Shakhnarovich | Nearest-Neighbor Methods in Learning and Vision: Theory and Practice[END_REF][START_REF] Matei | Rapid object indexing using locality sensitive hashing and joint 3D-signature space estimation[END_REF].

Space hashing functions are the core element of LSH. Several types of hash functions have recently been proposed to improve the performance of E2LSH, including the Leech lattices [START_REF] Shakhnarovich | Nearest-Neighbor Methods in Learning and Vision: Theory and Practice[END_REF] and E8 lattices (Jégou et al., 2008a), which offer strong quantization properties, and spherical hash functions [START_REF] Terasawa | Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere[END_REF] for unit-norm vectors. These structured partitions of the vector space are regular, i.e., the size of the regions are of equal size, regardless the density of the vectors. Their advantage over the original algorithm is that they exploit the vectorial structure of the Euclidean space, offering a partitioning of the space which is better for the Euclidean metric than the separable partitioning implicitly used in E2LSH.

One of the key problems when using such a regular partitioning is the lack of adaptation to real data. In particular the underlying vector distribution is not taken into account. Besides, simple algorithms such as a k-means quantizer have been shown to provide excellent vector search performance in the context of image and video search, in particular when used in the so-called Video-Google framework of [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF], where the descriptors are represented by their quantized indexes. This framework was shown to be equivalent to an approximate nearest neighbor search combined with a voting scheme in [START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF]. However, to our knowledge this k-means based partitioning has never been evaluated in the LSH framework, where multiple hash functions reduce the probability that a vector is missed, similar to what is done when using randomized trees [START_REF] Muja | Fast approximate nearest neighbors with automatic algorithm configuration[END_REF].

The first contribution of this paper is to analyze the individual performance of different types of hash functions on real data. For this purpose, we introduce the performance metrics, as the one usually proposed for LSH, namely the "ε-sensitivity", does not properly reflect objective function used in practice. For the data, we focus on the established SIFT descriptor [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], which is now the standard for image local description. Typical applications of this descriptor are image retrieval [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF][START_REF] Nistér | Scalable recognition with a vocabulary tree[END_REF][START_REF] Jégou | Hamming embedding and weak geometric consistency for large scale image search[END_REF], stitching [START_REF] Brown | Automatic panoramic image stitching using invariant features[END_REF] and object classification [START_REF] Zhang | Local features and kernels for classification of texture and object categories: A comprehensive study[END_REF]. Our analysis reveal that the k-means quantizer, i.e., an unstructured quantizer learned on a vector training set, behaves significantly better than the hash functions used in the literature, at the cost of an increased pre-processing cost. Note that several approximate versions of k-means have been proposed to improve the efficiency of pre-processing the query. We analyze the performance of one of the popular hierarchical k-means [START_REF] Nistér | Scalable recognition with a vocabulary tree[END_REF] in this context.

Second, inspired by state of the art methods that have proved to increase the quality of the results returned by the original LSH scheme, we propose two variants of the k-means approach offering different trade-offs in terms of memory usage, efficiency and accuracy. The relevance of these variants are shown to depend on the database size. The first one, multi-probe LSH [START_REF] Lv | Multi-probe LSH: Efficient indexing for high-dimensional similarity search[END_REF], decreases the query pre-processing cost. It is therefore of interest for datasets of limited size. The second variant, query-adaptive LSH (Jégou et al., 2008a), improves the expected quality of the returned vectors at the cost of increased pre-processing. It is of particular interest when the number of vectors is huge. In that case, the query preparation cost is negligible compared to that of post-processing the vectors returned by the indexing structure.

This paper is organized as follows. Section 2 briefly describes the LSH algorithm, the evaluation criteria used to measure the performance of ANN algorithms in terms of efficiency, accuracy and memory usage, and presents the dataset used in all performance experiments. An evaluation of individual hash functions is proposed in Section 3. We finally present the full k-means LSH algorithm in Section 4, and the two variants for the querying mechanism.

Background

This section first briefly presents the background material for LSH that is required to understand the remainder of this paper. We then detail the metrics we are using to discuss the performance of all approaches. We finally present the dataset derived from real data that is used to perform the experiments.

Locality sensitive hashing

Indexing d-dimensional descriptors with the Euclidean version E2LSH of LSH [START_REF] Shakhnarovich | Nearest-Neighbor Methods in Learning and Vision: Theory and Practice[END_REF] proceeds as follows. The n vectors of the dataset to index are first projected onto a set of m directions characterized by the d-dimensional vectors (a i ) 1≤i≤m of norm 1. Each direction a i is randomly drawn from an isotropic random generator.

The n descriptors are projected using m hash functions, one per a i . The projections of the descriptor x are defined as

h i (x) = x|a i -b i w , ( 1
)
where w is the quantization step chosen according to the data (see [START_REF] Shakhnarovich | Nearest-Neighbor Methods in Learning and Vision: Theory and Practice[END_REF]). The offset b i is uniformly generated in the interval [0, w) and the inner product x|a i is the projected value of the vector onto the direction a i .

The m hash functions define a set H = {h i } 1≤i≤m of scalar hashing functions. To improve the hashing discriminative power, a second level of hash functions, based on H, is defined. This level is formed by a family of l functions constructed by concatenating several functions from H. Hence, each function g i of this family is defined as

g j = (h j,1 , . . . , h j,d * ), (2)
where the functions h j,i are randomly chosen from H. Note that this hash function can be seen as a quantizer performed on a subspace of dimension d * . At this point, a vector x is indexed by a set of l vector of integers

g j (x) = (h j,1 (x), • • • , h j,d * (x)) ∈ Z k .
The next step stores the vector identifier within the cell associated with this vector value g j (x). Note additional steps aiming at avoiding the collision in hash-buckets of distant vectors are performed, but can be ignored for the remainder of this paper, see [START_REF] Shakhnarovich | Nearest-Neighbor Methods in Learning and Vision: Theory and Practice[END_REF] for details.

At run time, the query vector q is also projected onto each random line, producing a set of l integer vectors {g 1 (q), • • • , g l (q)}. From that set, l buckets are determined. The identifiers of all the vectors from the database lying in these buckets make the result short-list. The nearest neighbor of q is found by performing an exact search (L 2 ) within this short-list, though one might prefer using another criterion to adapt a specific problem, as done in [START_REF] Casey | Fast recognition of remixed music audio[END_REF]. For large datasets, this last step is the bottleneck in the algorithm. However, in practice, even the first steps of E2LSH can be costly, depending on the parameter settings, in particular on l.

Performance Metrics

LSH and its derivatives [START_REF] Gionis | Similarity search in high dimension via hashing[END_REF][START_REF] Terasawa | Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere[END_REF][START_REF] Andoni | Near-optimal hashing algorithms for near neighbor problem in high dimensions[END_REF] are usually evaluated using the so-called "ε-sensitivity", which gives a intrinsic theoretical performance of the hash functions. However, for real data and applications, this measure does not reflect the objective which is of interest in practice: how costly will be the query, and how likely will the true nearest neighbor of the query point be in the result? Hereafter, we address these practical concerns through the use of the following metrics:

Accuracy: recall

Measuring the quality of the results returned by ANN approaches is central. In this paper, we will be measuring the impact of various hashing policies and querying mechanisms on the accuracy of the result.

To have a simple, reproducible and objective baseline, we solely measure the accuracy of the result by checking whether the nearest neighbor of each query point is in the short-list or not. This measure then corresponds to the probability that the nearest neighbor is found if an exhaustive distance calculation is performed on the elements of the short-list. From an application point of view, it corresponds for instance to the case where we want to assign a SIFT descriptor to a visual word, as done in [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF].

The recall of the nearest neighbor retrieval process is measured, on average, by aggregating this observation (0 or 1) over a large number of queries. Note that instead, we could have performed a k-nn retrieval for each query. Sticking to the nearest neighbor avoids choosing an arbitrary value for k.

Search complexity

Finding out how costly an ANN approach is has major practical consequences for real world applications. Therefore, it is key to measure the overall complexity of the retrieval process in terms of resource consumption. The LSH algorithm, regardless of the hashing options, has two major phases, each having a different cost:

• Phase 1: Query preparation cost. With LSH, some processing of the query vector q must take place before the search can probe the index. The query descriptor must be hashed into a series of l values. These values identify the hash-buckets that the algorithm will subsequently analyze in detail. Depending on the hash function type, the cost of hashing operations may vary significantly. It is a function of the number of inner products and/or comparisons with database vectors to perform in order to eventually get the l values. That query preparation cost is denoted by qpc and is given in Section 3 for several hash function types.

• Phase 2: Short-list processing cost: selectivity. Depending on the density of the space nearby q, the number of vectors found in the l hash-buckets may vary significantly. For a given q, we can observe the selectivity of the query, denoted by sel.

Definition: The selectivity sel is the fraction of the data collection that is returned in the short-list, on average, by the algorithm.

In other words, multiplying the selectivity by the number of indexed vectors gives the expected number of elements returned as potential nearest neighbors by the algorithm. The number of memory cells to read and the cost of processing the short-list are both a linear function of the short-list length, hence of sel.

In the standard LSH algorithm, it is possible to estimate this selectivity from the probability mass function of hash values, as discussed later in the subsection 3.5.

If exhaustive distance calculation is performed on the shortlist returned by LSH, the overall cost for retrieving the ANN of a query vector is expressed as

ocost = sel × n × d + qpc. ( 3
)
An interesting measure is the acceleration factor ac over exhaustive search, which is given by

ac = n × d ocost = 1 sel + qpc n×d .
(4)

For very large vector collections, the selectivity term is likely to dominate the query preparation cost in this equation, as hashbuckets tends to contain many vectors. This is the rationale for using the selectivity as the main measurement.

Memory usage

The complexity of the search also includes usage of the main memory. In this paper, we assume that the complete LSH data structure fits in main memory. Depending on the strategy for hashing the vectors, more or less main memory is needed. As the memory occupation has a direct impact on the scalability of search systems, it is worth noticing that in LSH, this memory usage is proportional to the number of hash functions considered and to the number of database vectors:

memory usage = O(l × n).
(5)

The number of hash functions used in LSH will hence be used as the main measurement of the memory usage.

Dataset

Our vector dataset is extracted from the publicly available INRIA Holidays dataset1 , which is composed of high-definition real Holiday photos. There are many series of images with a large variety of scene types (natural, man-made, water and fire effects, etc). Each series contains somehow visually similar images, differing however due to various rotations, viewpoint and illumination changes of the same scenes taken by the photographers.

These images have been described using the SIFT descriptor [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], for which retrieving the nearest neighbors is a very computationally-demanding task. SIFT descriptors have been obtained on these images using the affine co-variant features extractor from [START_REF] Mikolajczyk | Scale and affine invariant interest point detectors[END_REF]. When using the standard parameters of the literature, the dimensionality of SIFT descriptors is d = 128.

The descriptor collection used in this paper is a subsample of 1 million descriptors randomly picked from the descriptors of the image dataset. We also randomly picked 10,000 descriptors used as queries, and another set of 1 million vectors extracted from a distinct image dataset (downloaded from Flickr) for the methods requiring a learning stage. Finally, we ran exact searches using the Euclidean distance to get the true nearest neighbor of each of these query descriptors. This ground-truth will be the one against which ANN searches will be compared.

Hash function evaluation

This section first discusses the key design principles behind four types of hash functions and the key parameters that matter for evaluating their performance in the context of LSH. We first recall the original design, where hash functions are based on random projections. Following recent literature [START_REF] Andoni | Near-optimal hashing algorithms for near neighbor problem in high dimensions[END_REF]Jégou et al., 2008a), we then describe highdimensional lattices used for spatial hashing. These two types of hash functions belong to the family of structured quantizers, and therefore do not capture the peculiarities of the data collection's distribution in space. To contrast with these approaches, we then discuss the salient features of a k-means unstructured quantizer for hashing, as well as one if its popular tree-based variant. Overall, choosing a hash function in LSH amounts to modifying the definition of g introduced in Section 2.1.

Enunciated these design methods, we then move to evaluate how each type of hash function performs on the real data collection introduced above. The performance is evaluated for a single hash function. This accurately reflects the intrinsic properties of each hash function, while avoiding to introduce the parameter l (number of distinct hash functions).

Random projection based

The foundations of the hash functions used in the original E2LSH approach have been presented in Section 2.1. Overall, the eventual quantization of the data space is the result of a product of unbounded scalar quantizers.

The key parameters influencing the performance of each E2LSH hash function are:

• the quantization step w ;

• the number d * of components used in the second-level hash functions g j .

As the parameters b i and m are provided to improve the diversity between different hash functions, they are arbitrarily fixed, as we only evaluate the performance of a single hash function. The values chosen for these parameters do not noticeably impact the selectivty, though large values of m linearly impacts the query preparation cost. This one remains low for this structured hashing method.

Hashing with lattices

Lattices have been extensively studied in mathematics and physics. They were also shown to be of high interest in quantization [START_REF] Gray | Quantization[END_REF]Conway and Sloane, 1982b). For a uniform distribution, they give better performance than scalar quantizers [START_REF] Gray | Quantization[END_REF]. Moreover, finding the nearest lattice point of a vector can be performed with an algebraic method [START_REF] Agrell | Closest point search in lattices[END_REF]. This is referred to as decoding, due to its application in compression.

A lattice is a discrete subset of R d ′ defined by a set of vectors of the form

{x = u 1 a 1 + • • • + u d a d |u 1 , • • • , u d ∈ Z} (6)
where

a 1 , • • • , a d are linearly independent vectors of R d ′ , d ′ ≥ d. Hence, denoting by A = [a 1 • • • a d ]
the matrix whose columns are the vectors a j , the lattice is the set of vectors spanned by Au when u ∈ Z d . With this notation, a point of a lattice is uniquely identified by the integer vector u.

Lattices offer a regular infinite structure. The Voronoi region around each lattice points has identical shape and volume (denoted by V) and is called the fundamental region.

By using lattice-based hashing, we aim at exploiting their spatial consistency: any two points decoded to the same lattice point are separated by a bounded distance, which depends only on the lattice definition. Moreover, the maximum distance between points inside a single lattice cell tends to be identical for some particular lattices. In the rest of this paper, we refer to this phenomenon as the vectorial gain.

Vectorial gain is strongly related to the density of lattices. The density of a lattice is the ratio between the volume V of the fundamental region and the volume of its inscribed sphere. Basically, considering Euclidean lattices, the closer to 1 the density, the closer to a sphere the fundamental region, and the greater the vectorial gain. Figure 1 illustrates the vectorial gain for two 2-d lattices having fundamental region of identical volume. In other terms, if L 2 (x, y) is the Euclidean distance between x and y, and V a (respectively V b ) is the closed domain of vectors belonging to the region depicted on Figure 1

(a) (re- spectively Figure 1(b)), then: max x a ∈V a ,y a ∈V a L 2 (x a , y a ) ≫ max x b ∈V b ,y b ∈V b L 2 (x b , y b ) (7)
where x a ∈V a dx a = x b ∈V b dx b (i.e., for identical volumes). In this paper, we will focus on some particular lattices for which fast decoding algorithms are known. These algorithms take advantage of the simplicity of the lattice definition. We briefly introduce the lattices D d , D + d and A d . More details can be found in Conway et al. (1987, chap. 4).

• Lattice D d is the subset of vectors of Z d having an even sum of the components:

D d = {(x 1 , • • • , x d ) ∈ Z d : d i=1 x i even}, d ≥ 3 . (8)
• Lattice D + d is the union of the lattice D d with the lattice D d translated by adding 1 2 to each coordinate of lattice points. That translation is denoted by 1 2 + D d .

D + d = D d ∪ ( 1 2 + D d ) . (9)
When d = 8, this lattice is also known as E 8 , which offers the best quantization performance for uniform 8dimensional vectors.

• Lattice A d is the subset of vectors of Z d+1 living on the d-dimensional hyper-plane where the sum of the components is null:

A d = {(x 0 , x 1 , • • • , x d ) ∈ Z d+1 : d i=0 x i = 0} . (10)
A vector q belonging to R d can be mapped to its d + 1dimensional coordinates by multiplying it on the right by the n lines × n + 1 columns matrix:

              -1 1 0 • • • 0 0 0 -1 1 • • • 0 0 • • • • • • • • 0 0 0 • • • -1 1               . ( 11
)
For these lattices, finding the nearest lattice point of a given query vector is done in a number of steps that is linear with its dimension (Conway and Sloane, 1982a).

The main parameters of a lattice hash function are:

• the scale parameter w, which is similar to the quantization step for random projections ;

• the number d * of components used.

Hashing the data collection using a lattice asks first to randomly pick d * components among the original d dimensionsthe natural axes are preserved. Then, given w, the appropriate lattice point is assigned to each database vector. The index therefore groups all vectors with the same lattice point identifier into a single bucket.

Remark:

The Leech lattice used in [START_REF] Shakhnarovich | Nearest-Neighbor Methods in Learning and Vision: Theory and Practice[END_REF] has not been considered here for two reasons. First, it is defined for d * = 24 only, failing to provide any flexibility when optimizing the choice of d * for performance. Second, its decoding requires significantly more operations compared to the others lattices: 3595 operations per lattice point [START_REF] Vardy | Maximum likelihood decoding of the leech lattice[END_REF]).2

k-means vector quantizer

Up to now, we have only considered structured quantizers which do not take into account the underlying statistics of the data, except by the choice of the parameters w and d * . To address this problem, we propose to use an unstructured quantizer learned on a representative set of the vectors to index. Formally, an unstructured quantizer g is defined as a function

R → [1, . . . , k] x → g(x) = arg min i=1..k L 2 (x, c(i)) ( 12
)
mapping an input vector x to a cell index g(x). The integer k is the number of possible values of g(x). The vectors c(i), 1 ≤ i ≤ k are called centroids and suffice to define the quantizer.

To construct a good unstructured quantizer, a nice choice is to use the popular k-means clustering algorithm. In that case, k corresponds to the number of clusters. This algorithm minimizes3 the overall distortion of reconstructing a given vector of the learning set using its nearest centroid from the codebook, hence exploiting the underlying distribution of the vectors. Doing so, the potential of vector quantization is fully beneficial since it is able to exploit the vectorial gain. Note that, by contrast to the structured quantizers, there is no random selection of the vector components. Hence, the hashing dimension d * is equal to the vector dimension d, as the quantizer is learned directly on the vector space.

However, learning a k-means quantizer may take a long time when k is large. In practice, bounding the number of iterations improves the learning stage without significantly impacting the results. In the following, we have set the maximum number of iterations to 20 for SIFT descriptors, as higher values provide comparable results.

Hierarchical k-means

Approximate variants of the k-means quantizer and the corresponding centroid assignment have been proposed [START_REF] Nistér | Scalable recognition with a vocabulary tree[END_REF][START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] to reduce both the learning stage and the query preparation costs. We evaluate the hierarchical k-means (HKM) of [START_REF] Nistér | Scalable recognition with a vocabulary tree[END_REF], which is one of the most popular approach.

The method consists of computing a k-means with k relatively small, and to recursively computes a k-means for the internal nodes until obtaining a pre-defined tree height. This produces a balanced tree structure, where each internal node is connected to a fixed number of centroids. The search is performed top-down by recursively finding the nearest centroid until a leaf is reached. The method uses two parameters:

• the height h t of the tree ;

• the branching factor b f . The total number of centroids (leaves) is then obtained as (b f ) h t .

Remark: The method used in [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] relies on randomized trees. This method was improved in [START_REF] Muja | Fast approximate nearest neighbors with automatic algorithm configuration[END_REF] by automatic tuning of the parameters. The method was shown to outperform HKM, leading to results comparable to that of standard k-means. Therefore, the results we give here for the k-means give a good approximation of the selectivity/recall tradeoff that the package of [START_REF] Muja | Fast approximate nearest neighbors with automatic algorithm configuration[END_REF] would provide, with a lower query preparation cost, however.

Experiments and discussion

Figure 2 gives the evaluation of the different types of hash function introduced in this section. For both random projection and lattices, the two parameters w and d * are optimized. Figure 2 only presents the optimal ones, which are obtained as follows. Given a couple of parameters w and d * , we compute the nearest neighbor recall at a given selectivity. This process is repeated for a set of varying couples of parameters, resulting in a set of tuples associating a selectivity to a nearest neighbor recall. Points plotted on the curves belong to the roof of the convex hull of these numbers. Therefore, a point on the figure corresponds to an optimal parameter setting, the one that gives the best performance obtained for a given selectivity.

For the k-means hash function, only one parameter has to be fixed: the number of centroids k, which gives the trade-off between recall and selectivity. This simpler parametrization is an advantage in practice. HKM is parametrized by two quantities: the branching factor b f and the height h t of the k-means tree. We evaluate the extremal cases, i.e., :

• a fixed height (h t = 2, 3) with a varying branching factor

• and a binary tree (b f = 2) with a varying tree height.

Vectorial gain

Figure 2 clearly shows that the lattice quantizers provide significantly better results than random projections, due to the vectorial gain. These results confirm that the random projections used in E2LSH are unable to exploit the spatial consistency. Note that this phenomenon was underlined in [START_REF] Andoni | Near-optimal hashing algorithms for near neighbor problem in high dimensions[END_REF]Jégou et al., 2008a). However, by contrast to these works, the lattices we are evaluating are more flexible, as they are defined for any value of d * . In particular, the lattice E 8 used in (Jégou et al., 2008a) is a special case of the D + lattice.

Figure 2 also shows that the various types of lattice perform differently. We observe an improvement of the nearest neighbor recall with lattices D and D + compared to random projections whereas lattice A gives similar performance. The density of D + is known to be twice the density of D. In high dimensions, the density of A is small compared to that of D. Overall, density clearly affects the performance of lattices. However, density is not the only crucial parameter. The shape of the fundamental region and its orientation may also be influential, depending on the distribution of the dataset.

Before discussing the performance of the unstructured quantizers evaluated in this paper and shown on Figure 2, it is necessary to put some emphasis on the behavior of quantization mechanisms with respect to the distribution of data and the resulting cardinality in Voronoi cells.

Structured vs unstructured quantizers

Hashing with lattices intrinsically defines Voronoi cells that all have the same size, that of the fundamental region. This is not relevant for many types of high-dimensional data, as some regions of the space are quite populated, while most are void. This is illustrated by Figure 3, which shows how well the kmeans is able to fit the data distribution. Figure 3 depicts the Voronoi diagram associated with the different hash functions introduced in this section, and consider two standard distributions. The dimensions d = d * = 2 are chosen for the sake of presentation.

As mentionned above, by construction the structured quantizers (see Figures 3(a) and 3(b)) introduced above lead to Voronoi cells of equal sizes. This property is not desirable in the LSH context, because the number of retrieved points is too high in dense regions and too small in regions yielding small vector density.

Considering the k-means quantizer in Figure 3(c), we first observe that for a uniform distribution, the shape of the cells is close to the one of the A 2 lattice, which is optimal for this distribution. But k-means is better for other distributions, as the variable volume of the cells adapts to the data distribution, as illustrated for a Gaussian distribution in Figure 3(d). The cell size clearly depends on the vector density. Another observation is that k-means exploits the prior on the bounds of the data, which is not the case of the A 2 lattice, whose optimality is satisfied only in the unrealistic setup of unbounded uniform vectors.

As a result, for structured quantizers, the cell population is very unbalanced, as shown by Figure 4. This phenomenon penalizes the selectivity of the LSH algorithm. In contrast to these quantizers, the k-means hash function exploits both the vectorial gain and the empirical probability density function pro- vided by the learning set. Because the Voronoi cells are quite balanced, the variance of the number of vectors returned for a query is small compared to that of structured quantizers.

Turning back to Figure 2, one can clearly observe the better performance of the k-means hash function design in terms of the trade-off between recall and selectivity. For the sake of fairness, the codebook (i.e., the centroids) has been learned on a distinct set: k-means being an unsupervised learning algorithm, learning the quantizer on the set of data would overestimate the quality of the algorithm for a new set of vectors. The improvement obtained by using this hash function construction method is very significant: the selectivity is about two order of magnitude smaller for the same recall.

Although HKM is also learned to fit the data, it is inferior to k-means, due to poorer quantization quality. The lower the branching factor is, the closer the results are compared to those of k-means. The two extremal cases depicts in Fig. 2, i.e., 1) a fixed tree height of 2 with varying branching factor and 2) the binary tree (b f = 2) delimits the regions in which all other settings lie. As expected, the performance of HKM in terms of selectivity/recall is the inverse of the one in terms of the query preparation cost. Therefore, considering Equation 3, the tradeoff between b f and h t appears to be a function of the vector dataset size.

Query preparation cost

Table 1 shows the complexity of the query preparation cost qpc associated with the different hash functions we have introduced. Note that this table reflects the typical complexity in terms of the number of operations. It could clearly be refined by considering the respective costs of these knowing the architecture on which the hashing is performed.

Lattices are the most efficient quantizers, even compared with random projections. Using the k-means hash function is slower than using random projection for typical parameters. HKM is a good compromise, as it offers a relatively low query preparation cost while adapting to the data.

hash function query preparation cost random projection (E2LSH

) m × d + d * × l lattice D d * d * × l lattice D + d * d * × l lattice A d * d * × l k-means k × d × l HKM b f × h t × l
Table 1: Query preparation cost associated with the different hash functions.

Querying mechanisms

In this section, we detail how the k-means approach is used to build a complete LSH system, and analyze the corresponding search results. The resulting algorithm is referred to as KLSH in the following. We then build upon KLSH by proposing and evaluating more sophisticated strategies, somehow similar in spirit to those recently introduced in the literature, namely multiprobing and query adaptive querying.

KLSH

Indexing d-dimensional descriptors with KLSH proceeds as follows. First, it is necessary to generate l different k-means clustering using the same learning set of vectors. This diversity is obtained by varying initializations4 of the k-means. Note that it is very unlikely that these different k-means gives the same solution for k high enough, as the algorithm converges to a local minimum only. Once these l codebooks are generated, each one being represented by its centroids {c j,1 , . . . , c j,k }, all the vectors to index are read sequentially. A vector to index is assigned to the nearest centroid found in one codebook. All codebooks are used in turn for doing the l assignments for this vector before moving to the next vector to index. Note this mechanism replaces the standard E2LSH H and g j hash functions from Section 2.

At search time, the nearest centroid for each of the l kmeans codebooks is found for the query descriptor. The database vectors assigned to these same centroids are then concatenated in the short-list, as depicted by Algorithm 1. From this point, the standard LSH algorithm takes on for processing the short list.

The results for KLSH are displayed Figure 5. One can see that using a limited number of hash functions is sufficient to achieve high recall. A higher number of centroids leads to the best trade-off between search quality and selectivity. However, as indicated section 2.2, the selectivity measures the asymptotic behavior for large datasets, for which the cost of this qpc stage is negligible compared to that of treating the set of vectors returned by the algorithm.

For small datasets, the selectivity does not solely reflect the "practical" behavior of the algorithm, as it does not take into Algorithm 1 -KLSH, search procedure Input: query vector q Output: short-list sl sl = ∅ for j = 1 to l do // find the nearest centroid of q from codebook j: i * = arg min account qpc. For KLSH, the overall cost is:

ocost = sel × n × d + k × l × d. ( 13
)
The acceleration factor therefore becomes:

ac = 1 sel + k×l n . (14)
Figure 6 shows the acceleration factor obtained for a dataset of one million vectors, assuming that a full distance calculation is performed on the short-list. This factor accurately represents the true gain of using the ANN algorithm when the vectors are stored in main memory. Unlike what observed for asymptotically large datasets, for which the selectivity is dominant, one can observe that there is an optimal value of the quantizer size obtained for k = 512. It offers the best trade-off between the query preparation cost and the post-processing of the vectors. Note that this optimum depends on the database size: the larger the database, the larger should be the number of centroids.

As a final comment, in order to reduce the query preparation cost for small databases, a approximate k-means quantizer could advantageously replace the standard k-means, as done in [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF]. Such quantizers assign vectors to cell indexes in logarithmic time with respect to the number of cells k, against linear time for standard k-means. This significantly reduces the query preparation cost, which is especially useful for small datasets. Algorithm 2 -Multi-probe KLSH, search procedure Input: query vector q Output: short-list sl sl = ∅ for j = 1 to l do // find the m p nearest centroids of q from codebook j:

(i * 1 , . . . , i * m ) = m p -arg min i=1,...,k L 2 (q, c j,i ) sl = sl ∪ i * =i * 1 ,...,i * m {x ∈ cluster(c j,i * )} end for

Multi-probe KLSH

Various strategies have been proposed in the litterature to increase the quality of the results returned by the original LSH approach. One series of mechanisms extending LSH uses a socalled multi-probe approach. In this case, at query time, several buckets per hash function are retrieved, instead of one (see [START_REF] Lv | Multi-probe LSH: Efficient indexing for high-dimensional similarity search[END_REF] and [START_REF] Joly | A posteriori multi-probe locality sensitive hashing[END_REF]). Probing multiple times the index increases the scope of the search, which, in turn, increases both recall and precision.

Originally designed for structured quantizers, this multiprobe approach can equally be applied to our unstructured scheme with the hope of also improving precision and recall. For the k-means hash functions, multi-probing can be achieved as follows. Having fixed the number m p of buckets that we want to retrieve, for each of the l hash function, we select the m p closest centroids of the unstructured quantizer g j = {c j,1 , . . . , c j,k }. Algorithm 2 briefly presents the procedure.

The vectors associated with the selected m p buckets are then returned for the l hash functions. Note that choosing m p = 1 is equivalent to using the basic KLSH approach. The total number of buckets retrieved is l × m p . Therefore, for a fixed number of buckets, the number of hash functions is reduced by a factor m p . The memory usage and the query preparation cost are thus divided by this factor.

Figure 7 shows the results obtained when using l = 1 and varying values of m p , i.e. for a single hash function. The re- sults are reasonably good, especially considering the very low memory usage associated with this variant. However, comparing Figures 5 and7, the recall is lower for the same selectivity. This is not surprising, as in KLSH, the vectors which are returned are localized in the same cell, whereas the multi-probe variant returns some vectors that are not assigned to the same centroid.

For small datasets, for which the query preparation cost is not negligible, this multi-probe variant is of interest. This is the case for our one million vectors dataset: Figure 8 shows the better performance of the multi-probe algorithm compared to the standard querying mechanism (compare to Figure 6). This acceleration factor compares favorably against state-ofthe-art methods of the literature. In a similar experimental setup (dataset of 1 million SIFT descriptors), [START_REF] Muja | Fast approximate nearest neighbors with automatic algorithm configuration[END_REF] reports, for a recall of 0.90, an acceleration factor lower than 100, comparable to our results but for a higher memory usage: the multi-probe KLSH structure only uses 4 bytes per descriptor for m p = 1.

Query-adaptive KLSH

While multi-probing is one direction for improving the quality of the original structured LSH scheme, other directions exist, like the query-adaptive LSH by Jégou et al. (2008a). In a nutshell, this method adapts its behavior because it picks from a large pool of existing random hash-functions the ones that are the most likely to return the nearest neighbors, on a per-query basis.

As it enhances result quality, this principle can be applied to our unstructured approach. Here, instead of using a single k-means per hash function, it is possible to maintain a poll of independent k-means. At query time, the best k-means can be selected for each hash-function, increasing the likelyhood of finding good neighbors.

Before developping the query-Adaptive KLSH, we must describe the original query-adaptive LSH to facilitate the understanding of the remainder. Query-Adaptive LSH as described in Jégou et al. (2008a) proceeds as follows (this is also summarized in Algorithm 3):

• The method defines a pool l of hash functions, with l larger than in standard LSH.

• For a given query vector, a relevance criterion λ j is computed for each hash function g j . This criterion is used to identify the hash functions that are most likely to return the nearest neighbor(s).

• Only the buckets associated with the p most relevant hash functions are visited, with5 p ≤ l.

The relevance criterion proposed in (Jégou et al., 2008a) corresponds, for the E 8 lattice, to the distance between the query point and the center of the Voronoi cell. We use the same criterion for our KLSH variant. For the query vector q, λ is defined as λ(g j ) = min i=1,...,k L 2 q, c j,i .

It turns out that this criterion is a byproduct of finding the nearest centroid. Therefore, for a fixed number l of hash functions, the pre-processing cost is the same as in the regular querying method of KLSH. These values are obtained to select the p best hash function as p-arg min j=1,...,l λ(g j ).

(

) 16
The selection process is illustrated by the toy example of Figure 9, which depicts a structure comprising l = 4 k-means hash functions. Intuitively, one can see that the location of a descriptor x in the cell has a strong impact on the probability that its nearest neighbor is hashed in the same bucket. On this example, only the second clustering ( j = 2) puts the query vector and its nearest neighbor in the same cell. Figure 10: Query-adaptive KLSH: performance when using a single hash function among of pool of l hash functions, l=1,2, 3,5,10,20,25,50,100. For a given number k of clusters, the selectivity is very stable and close to 1/d: 0.0085 for k=128, 0.0021 for k=512, 0.00055 for k=2048 and 0.00014 for k=8192.

j = 1 j = 2 j = 3 j = 4
In order for the query-adaptive KLSH to have interesting properties, one should use a large number l of hash functions. This yields two limitations for this variant:

• the memory required to store the hash tables is increased;

• the query preparation cost is higher, which means that this variant is interesting only for very large datasets, for which the dominant cost is the processing of the vectors returned by the algorithm.

The selection of the best hash functions is not time consuming since the relevance criterion is obtained as a by-product of the vector quantization for the different hash functions. However, this variant is of interest if we use more hash functions than in regular LSH, hence in practice its query preparation cost is higher. For a reasonable number of hash functions and a large dataset, the bottleneck of this query adaptive variant is the last step of the "exact" LSH algorithm. This is true only when the Algorithm 3 -Query-adaptive KLSH, search procedure Input: query vector q Output: short-list sl sl = ∅ // select the p hash functions minimizing λ(g j (q)):

( j 1 , . . . , j p ) = p-arg min j=1,...,l λ(g j (q)) for j ∈ ( j 1 , . . . , j p ) do // find the nearest centroid of q from codebook j: i * = arg min i=1,...,k L 2 (q, c j,i ) sl = sl ∪ {x ∈ cluster(c j,i * )} end for dominant cost is the processing cost of the search for the exact nearest neighbors within the short-list obtained by parsing the buckets. This is not the case in our experiments on one million vectors, in which the acceleration factor obtained for this variant is not as good as those of KLSH and multi-probe KLSH.

Figure 10 gives the selectivity obtained, using only one voting hash function (p = 1), for varying sizes l of the set of hash functions. Unsurprisingly, the larger l, the better the results. However, most of the gain is attained by using a limited number of hash functions. For this dataset, choosing l = 10 seems a reasonable choice. Now, using several voting hash functions, i.e., for p > 1, one can observe in Figure 11 that the query-adaptive mechanism significantly outperforms KLSH in terms of the trade-off between selectivity and efficiency. In this experiment the size of the pool is fixed to l = 100. However, on our "small" dataset of one million descriptors, this variant is not interesting for this large number of hash functions: the cost of the query preparation stage (k × l × d) is too high with respect to the postprocessing stage of calculating the distances on the short-list. This contradictory result stems from the indicator: the selectivity is an interesting complexity measurement for large datasets only, for which the query preparation cost is negligible compared to that of processing the vectors returned by the algorithm.

Discussion 4.4.1. Off-line processing and parametrization

One of the drawbacks of k-means hash functions over structured quantizers is the cost of creating the quantizer. This is especially true for the query-adaptive variant, where the number l of hash functions may be high. However, in many applications, this is no a critical point, as this clustering is performed off-line. Moreover, this is somewhat balanced by the fact that KLSH admits a simpler optimization procedure to find the optimal parametrization, as we only have to optimize the parameter k, against two parameters w and d * for the structured quantizer. Finally, approximate k-means reduces the cost of both the learning stage and the query preparation. It is therefore not surprising that the emerging state-of-the-art ANN methods, e.g., [START_REF] Muja | Fast approximate nearest neighbors with automatic algorithm configuration[END_REF], relies on such partitioning methods.

Which querying mechanism should we use?

It appears that each of the querying mechanism proposed in this section may be the best, depending on the context: dataset size, vector properties and resource constraints. The less memorydemanding method is the multi-probe version. For very large datasets and with no memory constraint, query-adaptive KLSH gives the highest recall for a fixed selectivity. If, for the fine verification, the vectors are read from a low-efficiency storage device, e.g., a mechanical hard drive, then the query-adaptive version is also the best, as in that case the bottleneck is to read the vectors from the disk. As a general observation, multiprobe and query adaptive KLSH offer opposite properties is terms of selectivity, memory usage and query preparation cost. The "regular" KLSH is in between, offering a trade-off between these parameters. Overall, the three methods are interesting, but for different operating points.

Conclusion

In this paper, we have focused on the design of the hash functions and the querying mechanisms used in conjunction with the popular LSH algorithm. First, confirming some results of the literature in a real application scenario, we have shown that using lattices as stronger quantizers significantly improve the results compared to the random projections used in the Euclidean version of LSH. Second, we have underlined the limitations of structured quantizers, and show that using unstructured quantizers as a hash functions offer better performance, because it is able to take into account the distribution of the data. The results obtained by k-means LSH are appealing: very high recall is obtained by using only a limited number of hash functions. The speed-up over exhaustive distance calculation is typically greater than 100 on a one million vector dataset for a reasonable recall. Finally, we have adapted and evaluated two recent variants of the literature, namely multi-probe LSH and query-adaptive LSH, which offer different trade-offs in terms of memory usage, complexity and recall.

Figure 1 :

 1 Figure 1: Fundamental regions obtained using random projections (a) and the lattice A 2 (b). The disparity of distances between the furthest possible points in each region dramatically reduces with dense lattices. This illustrates the vectorial gain.

Figure 2 :

 2 Figure 2: Evaluation of the different types of hash functions on the SIFT dataset.

Figure 3 :

 3 Figure 3: Voronoi regions associated with random projections (a), lattice A 2 (b) and a k-means quantizer (c,d).

Figure 4 :

 4 Figure 4: Population of cells by decreasing order for different lattices and kmeans.

Figure 5 :

 5 Figure 5: Performance LSH with k-means hash functions for a varying number l of hash functions.

Figure 6 :

 6 Figure 6: Acceleration factor of LSH over exhaustive search. Both the query preparation cost and the final distance calculation are included.

Figure 7 :

 7 Figure 7: Multi-probe KLSH for a single hash function (l = 1) and varying numbers of visited cells m p .

Figure 8 :

 8 Figure 8: Multi-probe KLSH: Acceleration factor of LSH over exhaustive search.

Figure 9 :

 9 Figure9: Toy example: hash function selection process in query-adaptive KLSH. The length of the segment between the query vector (circled) and its nearest centroid corresponds to the relevance criterion λ j ( j = 1..4). Here, for p = 1, the second hash function ( j = 2) is used and returns the correct nearest neighbor (squared).

Figure 11 :

 11 Figure11: Query adaptive KLSH: performance for a fixed pool of l = 100 k-means hash functions and a varying number p of selected hash functions.

http://lear.inrialpes.fr/people/jegou/data.php

Note, however, that this number is small compared to what is needed for unstructured quantizers.

This minimization only ensures to find a local minimum.

This is done by modifying the seed when randomly selecting the initial centroids from the learning set.

For p = l, the algorithm is equivalent to the KLSH.

Acknowledgements

The authors would like to thank the Quaero project for its financial support.


E H M Camara

P Breuil
email: pbreuil@emse.fr

D Briand

N F De Rooij

C Pijolat

A MICRO GAS PRECONCENTRATOR WITH IMPROVED PERFORMANCE FOR POLLUTION MONITORING AND EXPLOSIVES DETECTION

Keywords: Gas preconcentrator, Micro-channel, Porous silicon, Carbon nanotubes, Adsorbent

This paper presents the optimization of a micro gas preconcentrator based on a micro-channel in porous and non-porous silicon filled with an adequate adsorbent. This micro gas preconcentrator is both applicable in the fields of atmospheric pollution monitoring (Volatil Organic Compounds-VOCs) and explosives detection (nitroaromatic compounds). Different designs of micro-devices and adsorbent materials have been investigated since these two parameters are of importance in the performances of the microdevice. The optimization of the device and its operation were driven by its future application in outdoor environments. Parameters such as the preconcentration factor, cycle time and the influence of the humidity were considered along the optimization process. As a result of this study, a preconcentrator with a total cycle time of 10 minutes and the use of single wall carbon nanotubes (SWCNTs) as adsorbent exhibits a good preconcentration factor for VOCs with a limited influence of the humidity. The benefits of using porous silicon to modify the gas desorption kinetics are also investigated.

INTRODUCTION

In miniaturization of physical analysis methods, preconcentration appears as the essential element for improving both the sensitivity and the selectivity of these devices . Thus, micro-preconcentrators find [START_REF] Lewis | Recent Advancements in the Gas-Phase MicroChemLab[END_REF][START_REF] Gràcia | Sub-ppm gas sensor detection via spiral micro-preconcentrator[END_REF][START_REF] Ruiz | Membrane-suspended microgrid as a gas preconcentrator for chromatographic applications[END_REF][START_REF] Voiculescu | Micropreconcentrator for enhanced trace detection of explosives and chemical agents[END_REF][START_REF] Zheng | Single-walled carbon nanotube paper as a sorbent for organic vapour preconcentration[END_REF] their applications in various systems for gas analysis such as solid phase micro gas chromatography (μ-GC) [START_REF] Tian | Multiple-Stage Microfabricated Preconcentrator-Focuser for Micro Gas Chromatography System[END_REF][START_REF] Serrano | A micro gas chromatograph for high-speed determinations of explosive vapors[END_REF][START_REF] Lu | First-generation hybrid MEMS gas chromatograph[END_REF][START_REF] Ohira | Micro gas analyzers for environmental and medical applications[END_REF][START_REF] Zellers | Determination of complex vapor mixtures in ambient air with a wireless microanalytical system : vision, progress, and homeland security applications[END_REF] , ion mobility spectrometry (IMS) and electronic nose (E-nose) . [START_REF] Gabelica | Intérêt de la spectrométrie de mobilité ionique pour l'étude de la conformation et des assemblages non-covalents de biomolécules[END_REF][START_REF] Borsdorf | Ion Mobility Spectrometry: Principles and Applications[END_REF][START_REF] Martin | Microfabricated vapor preconcentrator for portable ion mobility spectroscopy[END_REF] [ [START_REF] Persaud | Analysis of discrimination mechanisms in the mammalian olfactory system using a model nose[END_REF][START_REF] Xu | A solid trap and thermal desorption system with application to a medical Electronic Nose[END_REF][START_REF] Bender | Development of a preconcentration unit for a SAW sensor micro array and its use for indoor air quality monitoring[END_REF][START_REF] Cho | Two-step preconcentration for analysis of exhaled gas of human breath with electronic nose[END_REF] The use of detection systems based on the preconcentration is growing since the need to quantify very low concentration is growing up as well as in the field of civil security as in agribusiness and healthcare. For example, in the later, there is a demand of preconcentrators for medical diagnostics as addressed by Mr.

Cho Seong et al and William A. Groves et al . They have analyzed through a preconcentration system, [17] [18] the air exhaled by a patient while knowing that the appearance of some gas molecules in exhaled air is characteristic of the metabolism, thus the state of patient's health. The presence of some of these VOCs is attributed to a definite disease; for example, alkanes, benzene derivatives o-toluidine and aniline are referred to lung cancer, while acetone is linked to diabetes...

In the environmental field, it should be noted that the increasing of industrialization around some major cities causes great vigilance in the monitoring environmental pollution and the prevention of disasters. Each country, through an environmental quality agency, sets tolerance limits for some VOCs. For example, in United States, the threshold for benzene is determined by the U.S. EPA (U.S. Environmental Protection Agency) to 500ppb in ambient air and 5ppb in drinking water . While in France, the limit is set by IFEN [19] (French Institute of Environment) to 10μg/m . These limits continuously being reviewed to lower levers 3 [20] require the implementation of more performing detection equipments with a low detection limit and very short sampling time.

The need to improve both the sensitivity and the selectivity of some detection systems has prompted many laboratories to review the implementation of their gas pre-conditioning system. Thus, systems with preconcentrators filled with a hydrophobic adsorbent (carbotrap) allowing to reduce the influence of water vapor in the analysis of human exhaled breath. There are also other multiple stages preconcentration techniques based on the difference of desorption temperature between the two preconcentration units to overcome the influence of other interfering gases upon detection as demonstrated by B. Alfeeli et al in [START_REF] Alfeeli | Selective preconcentration by temperature manipulation of cascaded Micro preconcentrators[END_REF] their concept of cascaded micro-preconcentrator.

A new innovative process in the field of micro-preconcentration is the use of porous silicon. Indeed, the use of porous silicon as a binding surface for filing adsorbent appears as a very attractive approach in the development of miniaturized preconcentration because it offers the possibility to deposit by fluidic solution various types of adsorbent while avoiding the problems of overpressure during the experiences.

In our previous study [22 23, 24] , a gas pre-concentrator based on porous silicon micro-channels filled with carbon nanopowders from a fluidic solution has been developed. The present work aims to improve the performance of this device, with new approaches in the design as well as in the choice of adsorbent materials and modes of operation. We have further investigated the contribution of porous silicon in the adsorption and desorption phases since besides the increase of its specific surface area as reported in [26] ,

porous silicon when coupled with the adequate adsorbent can also modify the desorption kinetics of the target gas.

Alternative absorbent materials such as carbon nanotubes and polymers, whose surface areas, poressize distributions, and structures can be varied to serve as conformal adsorbents, were evaluated for the improvement of the performance of the preconcentrator [5] .

The devices in this study have been developed targeting the preconcentration of benzene and nitrobenzene which are representative gases for several types of applications relevant from atmospheric pollution control to explosives detection.

EXPERIMENTAL

Adsorbent Materials

The choice of the adsorbent material is an important factor in the performance of a micro gas preconcentrator. The suitable adsorbent must have a strong affinity with the target gas, a low activation energy of desorption, a large adsorption capacity vis-à-vis of the target gas and finally a good binding of its particles on the preconcentrator substrate in order to avoid an evacuation of the deposited adsorbent under high gas flow which is harmful for the performance of the devices. The activation energy of the adsorbent is symbolized by its desorption temperature; while the adsorption capacity is linked to the specific area.

Therefore, four different adsorbents such as activated carbon, carbon nanotubes (Single Walled Carbon NanoTubes-SWCNTs, Multi Walled Carbon NanoTubes-MWCNTs) and Tenax polymer have been tested for the preconcentration of benzene and nitrobenzene in presence of humidity by using various techniques: BET (Brunauer, Teller and Emmett) method, Thermal Programmed Desorption (TPD) and applying them to micropreconcentrator devices.

The BET method is a volumetric adsorption of gas point by point, which allows obtaining the complete isotherms (adsorption and desorption). These gas adsorption/desorption isotherms (Nitrogen, Argon, Krypton...) will permit the determination of the specific area and the adsorbent texture. The value of the specific area is obtained from the absorption isotherms of a gas at the liquid nitrogen temperature (77K).

TPD technique is often used to discern the different desorption products of a given adsorbent after an adsorption phase. This technique consists in programming the desorption heating rate and selectively measuring the desorption products with a mass spectrometer. In some cases, the adsorption phase can be done in situ and the desorption heating rate is set to 100°C/min in order to make easier the discrimination of the various desorption products.

The carbon adsorbent used in this test has been activated by thermal process. The activation of carbon is an oxidizing reaction in order to release internal porosity created during the carbonization, to expand the pores, to create new micropores and to increase its specific area. This step must be controlled to avoid the total elimination of the carbon structure as the activation at high temperature (up to 900°C) under oxygen can cause the total disappearance of carbon structure. That is why we have done the activation of carbon nanopowder at 500°C during 3 hours in presence of oxygen. All the others adsorbents materials were not activated because this process was not needed due to of their specific area already higher.

Preconcentrator

Micro-devices with different designs have been fabricated (figure 1) by deep reactive ion etching (DRIE) of silicon wafers using a thick photoresist mask. In the case of porous silicon channels, prior to the DRIE, a silicon nitride film is deposited to act as a masking layer during the porous silicon formation. Then, for both types, a 50 nm thick thermal oxide of is grown prior to their sealing with a glass cover by anodic bonding.

The different channels are designed with the necessity of having some pillars or walls within the channels in order to control the powders deposition by fluidic solutions [23, 24] . The neutral microchannel is designed without structures in the internal chamber while the zigzag design with channel system at inlet/outlet, mostly used in this work, is made with "V" shaped structures in order to improve the flow distribution not only during the adsorbent deposition but also during experiments.

The first micro-devices realized at the beginning of this study were made following two depths of etching.

The internal chamber etched at 120µm into the silicon contains parallel channels, either smooth or with the "scales". In order to receive the metallic micro-capillaries of 350μm used as fluidic connectors, the inlet and outlet of the device were etched to a depth of 325µm. But we faced a non-uniform distribution of flow (Figure 1) and overpressure during the experiments, which have been confirmed by some fluidic simulations done under three hypotheses such as:

-The pressure is applied only in the entrance of the microdevice while the outlet is under atmospheric pressure;

-No interaction between the substrate and the fluid except the friction forces;

-And the turbulence effect was not considered in this simulation model.

New micro-components were designed with a uniform depth of 325μm for both the inlet/outlet and the internal chamber in order to compensate the overpressure observed on previous devices during tests. In addition, inlet and outlet were fabricated with a channel system to promote a uniform distribution of fluid unlike the old micro-components. Indeed, the latter did not have this channel system and we observed for them a non-uniform distribution of flow when performing the fluidic simulation developed below.

This improvement in the design of the micro-channels was confirmed by series of simulation devoted to new micro-devices which have pointed, on one hand, an improvement in the distribution of the gas flow with the presence of channel system at the inlet/outlet of the micro-devices (Figure 1) and on other hand, a reduction of pressure losses thanks to the uniform depth of 325μm through all the microchannel in this new design.

Adsorbent deposition

The adsorbent insertion in micro-channels has been realized by two methods. The first one is a deposition using a fluidic solution , and the second one consists to deposit the adsorbent in a paste form before the sealing of the glass cover. The choice of the deposition method is closely related to the adsorbent nature. According to dimension of the metallic capillary used as fluidic connection (220µm of internal diameter), the first deposition method is more suitable for adsorbent materials with a particle size less than 5µm of external diameter. Thus, the activated carbon (100nm of particle size) and carbon nanotubes (CNTs)

were inserted in the microchannels by fluidic solution while Tenax TA was deposited in a paste form before the sealing of the microdevices because of its large particle size close to 250µm. [START_REF] Pijolat | Application of carbon nanopowders for gas micro-preconcentrator[END_REF] These experiments on the fluidic deposition of the adsorbent have shown that the presence of pillars in the preconcentration chamber, particularly in the "zigzag" design, is a key factor to homogenize the distribution of the liquid flow through the entire device and to enhance the carbon deposition. It was observed that the use of porous silicon has increased the quantity of deposited carbon in the micro-channels. In fact, the presence of pores on the surface of the walls constitutes an important asset to get a good binding layer and thus to increase the quantity of adsorbent filled in the micro-channel compared to non-porous silicon [23] .

Once the devices filled with adequate adsorbent material, the fluidic connections are made with metallic capillaries (steel) having 220µm of internal diameter The capillary is filed, partially introduced in the device and then fixed with a ceramic cement in order to not block the connectors during the sealing.

Heating element

In order to have an autonomous component, for either the thermal treatments of the adsorbent materials and the desorption of the trapped gases, a platinum heater is integrated on the backside of the device by screen printing and the electrical connections are made with gold wires pasted on a platinum lacquer. This heating element is used to heat the device at temperatures up to 500°C with a very homogeneous distribution of the temperature considering the good thermal conductivity of the silicon, as it was reported in our previous works .

[ [START_REF] Camara | Micro gas preconcentrator in porous silicon filled with a carbon absorbent[END_REF][START_REF] Pijolat | Application of carbon nanopowders for gas micro-preconcentrator[END_REF] To have a good regulation of temperature, the micro-preconcentrator is suspended in a metallic box (Figure 2).

Optimization of the experimental parameters

Five main parameters are of importance for the optimum operation of a preconcentrator device with a given geometry and filled with a fixed quantity of specific absorbent material: the gas flow rate during the gas adsorption, the gas flow rate during the desorption phases, the heating rate during the gas desorption phase, the duration of the gas adsorption and desorption phases, and the gas volume of the detector.

The miniaturization of such device imposes us a limitation on the gas flow rate, but for preconcentration, high flow rates are preferred during the adsorption in order to increase the desorption peak amplitude for a

given time of adsorption. The adsorption phase flow was set at 167mL/min, which allowed us to inject a significant quantity of pollutant in a short time, while the desorption phase flow was maintained at 33mL/min to avoid an important dilution of the desorbed quantity. Likewise, to avoid a considerable detection volume, the metallic capillary at the outlet of our micro-preconcentrator was directly connected to the inside of the detector through its packaging (Sensor from FIGARO ref. 2620), and the latter was then calibrated in order to correct the influence of the gas flow on the characteristics of its response [23| . Otherwise, some experiments were initially made with a miniaturized sub ppm PID (Photo Ionization Detector, RAE ppb).

Since the maximum of the desorption peak is an increasing function of the heating rate [23] , the preconcentration tests were performed with a heating rate of 160°C/min, which corresponds to the maximum rate that can reach the heating resistance deposited on the backside of the micro-channels. the maximal temperature is 350°C.

Finally, the increase of the adsorption time can lead to an enhancement of the desorption peak amplitude, but in the same time causes a longer preconcentration cycle which for some applications might not be desirable. Therefore, the adsorption and desorption times were maintained constant all through the experiments and lasted for 5 minutes since for these targeted applications as the pollution monitoring, a short preconcentration cycle is more appropriate.

So, it is very difficult to define a preconcentration factor since, for a given preconcentrator, the "amplification" of the concentration is closely related to the duration of the gas adsorption phase, the flowrates during adsorption and desorption phases, and the heating rate. However, we will measure a "practical" preconcentration factor which we defined as the ratio between the maximum of the measured concentration during the desorption phase and the concentration of the injected gas.

RESULTS AND DISCUSSIONS

Specific area measurement

The first tests were especially dedicated to the measurement of the specific area of the selected adsorbent materials namely carbon nanopowder, carbon nanotubes (SWCNTs, MWCNTs) and a polymer (Tenax TA) by nitrogen adsorption using the BET method. These results show that the specific area of the activated carbon nanopowder and the SWCNTs nanotubes are higher than the one of the three other adsorbents (Table 1).

However, a large specific surface does not mean necessarily a large adsorption capacity because the latter is closely related to the degree of affinity between the adsorbent and adsorbed gas. So the best solution is to evaluate the adsorption capacity of these adsorbents towards to benzene and nitrobenzene.

Benzene adsorption

Thermal Programmed Desorption (TPD)

The second series of experiments concerned the evaluation of the adsorption capacity of the adsorbents by TPD technique coupled with a mass spectrometer.

The adsorption capacity for benzene of the four adsorbents has been evaluated in similar conditions and in the presence of humidity obtained by bubbling the gas in a bottle of water at ambient temperature. On the one hand, there is a significant desorption peak of water with the activated carbon nanopowder unlike the three other adsorbents which have a low affinity with water vapor (Figure 3). This result reflects a higher decrease of the adsorption capacity of the activated carbon nanopowder in a presence of water, which is very harmful for the experimentation in ambient air. On the other hand, the benzene desorption peak obtained with the activated carbon nanopowder and SWCNTs is about 5 times higher than the one obtained with MWCNTs and Tenax TA. This demonstrates a strong affinity of these two compounds with benzene since the same adsorbent mass has been used for these TPD experiments (Figure 4, 5 and 6).

However, it should be noted that the temperature of the maximum of the desorption peak amplitude varies with the adsorbent material. It is estimated at about 120, 180, 280 and 490°C respectively for Tenax TA, activated carbon nanopowder, SWCNTs and MWCNTs, respectively. The high desorption temperatures of the MWCNTs manifest an important activation energy of the desorption synonym with a strong link between the adsorbent and adsorbed gas which is bad for the reduction of the power budget and also for the reliability of the device. Therefore, we decided to not use MWCNTs for the following experiments. It should be noted too secondary benzene peaks between 400 and 600°C, probably due to other sites and mechanisms of adsorption-desorption.

TPD experiments performed with carbon nanopowder deposited on porous and nonporous silicon have shown that the benzene kinetics of desorption on carbon is closely linked to the substrate nature on which the carbon is deposited. Indeed, the desorption temperature of benzene adsorbed on carbon deposited on porous silicon substrate (200°C) is about 60°C lower than the one obtained with a non-porous silicon substrate (260°C) (Figure 7).

Experiments with the micro-preconcentrator

Following the conclusions drawn from the previous TPD experiments presented in the sections above, the preconcentration tests have been performed on silicon and porous silicon micro-channels with a "zigzag" design. In order to study in similar conditions the effect of optimized parameters, the quantity of deposited adsorbent on all micro-channels will be equal to about 1mg.

On one hand, the tests of these porous silicon micro-channels with carbon deposition have shown that the porous silicon, besides increasing the quantity of deposited carbon, contributes to the effectiveness of the gas preconcentration by making the desorption easier and thereby reducing the desorption temperature and at last the duration of the preconcentration cycle (Figure 8).

This complete desorption of the couple porous silicon-carbon is, maybe, due to its activation energy of desorption lower than the one for the pair non-porous silicon-carbon. The maximum of concentration obtained during desorption is about 15 ppm corresponding to a "practical" factor of preconcentration (as defined above) of about 60.

On other hand, the preconcentration tests of the non porous silicon micro-channels filled with SWCNTs have shown that the influence of water vapor in the performance of the micro-preconcentrator is lower than the one filled with activated carbon nanopowder, for which the sensor response during the desorption is intensely reduced in presence humidity (Figure 9, 10).

However, it should be noted that the desorption parameters of the non porous silicon micro-channels filled with SWCNTs are not optimum since we have observed a low factor of preconcentration and a spread of its desorption peak, which is synonym of a insufficient both heating rate (160°C/min) and desorption temperature (240°C). Some experiments are underway to optimize the preconcentration characteristics of the device when using SWCNTs.

The other experiments under benzene with SWCNTs and Tenax TA are summarized in the table 2 have shown firstly, the interest of using SWCNTs for reducing of the influence of water vapor during the adsorption phase and secondly, the low desorption temperature when Tenax is used as adsorbent material in opposition of the activated carbon.

Others VOCs with high saturation vapor pressure such as xylene have been tested with our micropreconcentrator and the results are shown in the table 2. They confirm the interest of using Tenax for these typical VOCs. 10

Nitrobenzene adsorption

Thermal Programmed Desorption

These TPD experiments with nitrobenzene adsorption have shown a strong link between the nitrobenzene molecules and carbon nanopowder particles making thereby the desorption more difficult.

Indeed, there is a low desorption of nitrobenzene at 200°C and a high desorption of benzene is observed meaning thus the decomposition of nitrobenzene molecules in benzene at above 300°C (Figure 11). Unlike carbon, the polymer Tenax TA released easily nitrobenzene molecules during the desorption at a temperature below 150°C and no decomposition of the latter is observed since the benzene desorption peak is very small compared to nitrobenzene peak (Figure 12).

Experiments with the micro-preconcentrator

Tests under nitrobenzene realized with a micro-preconcentrator have confirmed that the nitrobenzene molecules are strongly adsorbed on the carbon adsorbent making thus the desorption quasi impossible. As shown in the Figure 13, after a cleaning step at 200°C followed by an injection of 1ppm of nitrobenzene during 120min, no nitrobenzene is desorbed even with a temperature of about 200°C.

In addition, when this experiment has been performed again by heating the micro-preconcentrator until 350°C during one hour, only a small amount of nitrobenzene is desorbed. While the Tenax, after a cleaning step at 150°C followed by an injection of 1ppm of nitrobenzene, a total desorption of the target gas is observed only at 120°C before the end of the heating confirming therefore the TPD observations (Figure 14).

Summary and perspectives

All these tests experimented with our micro-preconcentrator have shown that the efficiency of the latter is closely related not only to the adsorbent material but also to the nature of the micro-preconcentrator substrate on which the test has been done. Therefore, the table 2 summarizes the results obtained with our preconcentration of nitrobenzene with macroprous silicon microchannel filled with carbon adsorbent (symbolized by the question mark) has not been done yet. It will be an interesting test in order to confirm the reduction of the desorption temperature of the nitrobenzene easing thus the use of carbon material for the preconcentration of nitroaromatic gases deriving from explosive compounds.

Another idea now is to reduce the dimension of the microchannel because at the beginning of this project, we opted for a large deposit of adsorbent in the micro-device but over time we realized that for the detection of trace VOCs (concentrations of hundreds of ppb), few milligrams of carbon are efficient to perform these experiences. Therefore, reducing the size of micro-component seems necessary, firstly, to obtain a more compact deposit of the adsorbent promoting interstitial porosity, more uniform distribution of the flow and secondly, to improve the thermal inertia because of its small size (Figure 15).

CONCLUSIONS

The effect of gas preconcentration in micro-channels has been demonstrated following a preliminary optimization of both the microchannel designs and the operating parameters. The use of four different adsorbent materials has been evaluated in a presence or not of relative humidity. To this end, SWCNT appears as adequate adsorbent for preconcentration of benzene in presence of humidity because of its high specific area and adsorption capacity and its low affinity with water vapor. While Tenax TA polymer seems the ideal candidate for the preconcentration of nitrobenzene since the latter is completely desorbed below 150°C.

Another important result of this study is the development of micro-preconcentrator on porous silicon. In fact, the porous aspect of the micro-preconcentrator substrate contributes to increasing the quantity of adsorbent filled by fluid through the micro-device. Besides this, it facilitates the desorption of gas molecules adsorbed on the adsorbent deposited on it by reducing the temperature of desorption of adsorbent-of saturation that are very difficult to be desorbed.

In addition, the adsorption capacity of the microporous silicon itself is not uninteresting since, due to its low desorption temperature, it could probably be directly used as adsorbent material for certain vapors such as nitrobenzene.

Moreover, we are currently studying the preconcentration of VOCs mixture by exploiting the difference of desorption between gases in order to separate their desorption peaks. In this case, the combining of porous silicon and other alternative materials seems an interesting way to improve the performance of our micropreconcentrator.

FIGURES

Figure 1: Velocity cartographies obtained after a CFD simulation with microchannels in neural design without channel system at the inlet/outlet for a flow rate of 20L/h (a) and 40L/h (b) and in neutral (c) and zigzag (d) designs with channel system at the inlet/outlet for a flow rate of 20L/h.

TABLES

Table 1: Specific area and particle size of different adsorbents.

Figure 2 :

 2 Figure 2: Micro-channel in porous silicon filled with carbon with metallic gas capillaries and suspended in metallic box.

Figure 3 :

 3 Figure 3: TPD spectrum of Carbon nanopowder after benzene adsorption.

Figure 4 :

 4 Figure 4: TPD spectrum of Tenax polymer after benzene adsorption.

Figure 5 :

 5 Figure 5: TPD spectrum of SWCNTS after benzene adsorption.

Figure 6 :

 6 Figure 6: TPD spectrum of MWCNTs after benzene adsorption.

Figure 7 :

 7 Figure 7: TPD spectrum of carbon nanopowder deposited on porous and non-porous silicon after benzene adsorption.

Figure 8 :

 8 Figure 8: Comparison of gas sensor response between porous silicon and non porous silicon microchannels filled with carbon nanopowder after an adsorption step of 250ppb and desorption step at 200°C with a heating rate of 160°C/min.

Figure 9 :

 9 Figure 9: Sensor response for a silicon micro-channel filled with activated carbon nanopowder with and without humidity, when exposed to 5min to 250ppb of benzene and desorbed during 5min at a temperature of 200°C.

Figure 10 :

 10 Figure 10: PID response of silicon micro-channel filled with SWCNTs with and without humidity when exposed to 5min to 250ppb of benzene and desorbed at 240°C.

Figure 11 :Figure 12 :

 1112 Figure 11: TPD spectrum of Carbon nanopowder after nitrobenzene adsorption

Figure 13 :

 13 Figure 13: PID response of a silicon micro-channel filled with activated carbon nanopowder when exposed to 120min to 1ppm of nitrobenzene and desorbed at a temperature of 200°C.

Figure 14 :

 14 Figure 14: PID response of a silicon micro-channel filled with Tenax TA when exposed to 45min to 1ppm of nitrobenzene and desorbed a temperature of 140°C.

Figure 15 :

 15 Figure 15: Pressure and velocity cartographies obtained after a CFD simulation at 20 L/h with a new microchannel in neutral design.

2

  multiple stages of preconcentration were developed to reduce both the influence of water vapor and other

	interfering gases such as alcohol derivatives	[17, 21]	. S. M. Cho et al	[17]	have implemented two-stage

Table 2 :

 2 Summary of results obtained with our micro gas preconcentrator according the adsorbent material, the preconcentrator substrate and the target gas. Symbols +++, ++, + and -mean respectively very good, good, medium and bad results

	Adsorbent	Specific area (m 2 /g)	Particle size (µm)
	Carbon nanopowder	99	+/-1	0.1
	Activated carbon nanopowder	490	+/-8	0.1
	SWCNTs	399	+/-5	2
	MWCNTs	21	+/-1	5
	Tenax TA	35	+/-2	250

Table 1 :

 1 Specific area and particle size of different adsorbents.

	Gas
	Adsorbent/Substrate	Benzene	Xylene	Nitrobenzene
	Carbon / Silicon	+ + +	+ +	─
	Carbon / Macroporous silicon	+ + +	+ ++	NA
	SWCNTs / Silicon	+ +	+	─
	SWCNTs /Macroporous silicon	+ + +	+ + +
	Tenax TA / Silicon	+ +	+ +	+ +

Table 2 :

 2 Summary of results obtained with our micro gas preconcentrator according the adsorbent material, the preconcentrator substrate and the target gas, +++, ++, + and -mean respectively very good, good, medium and bad results, .


Computational Statistics, James E. Gentle, April 2009, Statistics andComputing Series, Springer-Verlag, New York, xxi+727 pages, ISBN 978-0-387-98143-7, DOI 10.1007/978-0-387-98144-4, $ 99.00 This book has a very large scope in that, beyond its title, it covers the dual fields of computational statistics and of statistical computing. If only for this reason it thus constitutes a reference text for any statistics course including some degree of computing. The first field, computational statistics, on statistical methods that rely heavily on computational tools ("Computational inference, together with exact inference and asymptotic inference, is an important component of statistical methods"), like the Bayesian analysis of hierarchical models [START_REF] Gelman | Bayesian Data Analysis[END_REF], while the second field covers computational or numerical methods that are used by computational statistics, like the EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm (with discussion)[END_REF]. The latter field being more easily chartered and more operational than conceptual, it may appear to the reader that, paradoxically, Computational Statistics focus more on statistical computing than on computational statistics.

Computational Statistics is structured as a four part treatise:

• Part I: Mathematical and statistical preliminaries The first part of Computational Statistics is, as indicated by its title, a single preliminary chapter containing what Gentle considers as the essentials of mathematics, probability, and statistics for the understanding of the book. A reader unfamiliar with too many topics within this chapter should first consider improving his or her background in the corresponding area! This is a rather large chapter, made of 82 pages, and it offers some usefulness for all readers, not only to signal deficiencies in their background, as noted above, but also to anchor the subsequent developments into the proper formalism. Given this purpose, the few exercises in this chapter are necessarily incomplete but they can be seen as useful reminders. (However, some of those exercises involve simulation tools introduced later in the book and thus should be set aside for future processing). Gentle insists in his preface on the urgency of reading this chapter, even for seasoned statisticians, for fear of missing the "subtle points". (For instance, he stresses the difference between the "form of a mathematical expression and the way the expression should be evaluated in actual practice", illustrating this point with the standard example that solving Ax = b in x does not require computing A -1 .)

As shown by the titles of the chapters therein, the second part of Computational Statistics is truly about the theory of computation, meaning using computers for numerical approximations, with interesting sections about the representation of numbers in computers, about approximation errors, and of course about random number generators. While there exist complete books about everyone of those topics (see, e.g., [START_REF] Fishman | Monte Carlo[END_REF], I appreciate the need for enforcing upon our students' minds those hardware subtleties, especially since they often seem completely unaware of them, despite their advanced computer skills. (I like very much the repeated aphorism "Programming is the best way to learn programming".) This second part of Computational Statistics may thus appear as a self-contained textbook of 250 pages on numerical methods (incl. function approximations by basis functions, resolution of linear and non-linear systems) and on random generators, i.e. it covers the same ground as the set of Gentle's earlier books, Random Number Generation and Monte Carlo Methods (2004) and Numerical Linear Algebra for Applications in Statistics (1998), while Elements of Computational Statistics (2002) looks very much like a shorter entry on the topics treated in Parts III and IV of Computational Statistics. This second part can certainly and seamlessly sustain a whole semester undergraduate course while advanced graduate students can be expected to gain from a self-study of those topics. In my opinion, it is a very coherent part of the book and it constitutes a must-read for all students and researchers engaging into any kind of serious statistical programming. Obviously, some notions are introduced a bit superficially, given the scope of this section (as, for instance, MCMC techniques, in less than six pages), but I came to realise this is the very point of the entire book, namely to provide an entry into "all" necessary topics, along with links to the relevant literature (if often entries in [START_REF] Gentle | Handbook of Computational Statistics-Concepts and Methods[END_REF] for deeper enlightment. As such, I deplore that the ultimate issue of Monte Carlo experiments, whose construction often is a hardship for students, is postponed till the 100 page long appendix. (In my experience, students do not read appendices!)

The third and fourth parts of Computational Statistics cover the major methods of computational statistics, including Monte Carlo methods (I appreciated very much the quote "Monte Carlo methods differ from other methods of numerical analysis in yielding an estimate rather than an approximation"), bootstrap, and randomization, but also non-parametric methods like probability density estimation. Because of this wide scope, Part III is to be understood as an introduction to the tools of the trade. As a result, the depth with which the different topics are processed is variable, and most chapters are rather short even though they try to be allencompassing. Part IV is a description of machine learning techniques, that could well function as a preliminary to [START_REF] Hastie | The Elements of Statistical Learning: Data Mining, Inference, and Prediction[END_REF].

In my opinion, some relevant sections of Part III would have fitted better in Part IV, where they belong. For instance, Chapter 10 on the estimation of functions covers the evaluation of estimators of functions, but postpones the actual construction of those estimators till Chapter 15. Jackknife is introduced on its own in Chapter 12, while the bootstrap is covered in Chapter 13. (I note that bootstrap for non-iid data is dismissed rather quickly, given the current research in the area.) The first sections of Chapter 16 are a valuable entry on clustering and data-analysis tools like PCA, while the final section of this chapter on high dimensions feels slightly out of context. (I also bemoan that the curse of dimensionality is mentioned too late in the book.) Chapter 17 is about dependent data and discuss regression, classification and projection pursuit, but does not cover the existing literature on graphical models and their use in the determination of dependence structures.

In conclusion, Computational Statistics is a very diverse book that can be used as a textbook at several levels of a statistics curriculum, as well as a reference for researchers (even if mostly as an encyclopedic entry towards further and deeper references). The book is well-written, in a lively and personal style. There is no requirement for a specific programming language, algorithms being described in a pseudo-code manner. The R language is introduced in a somewhat dismissive way (R "most serious flaw is usually lack of robustness" since "some [packages] are not of high-quality") and the software BUGS [START_REF] Lunn | WinBUGS -a Bayesian modelling framework: concepts, structure, and extensibility[END_REF] is not mentioned at all. (Some exercises are of the kind "Design and write either a C or a Fortran subroutine", when they should simply ask for a program in any language.) The appendices of Computational Statistics also contain the solutions to some exercises, even though the level of detail is highly variable, ranging from one word ("1") to a whole page (see, e.g., Exercise 11.4). The twenty-some page list of references is preceded by a few pages on currently available journals and webpages. Despite the reservations raised above about some parts of Computational Statistics that would benefit from a deeper coverage, I think this book is a reference book that should appear in the shortlist of any computational statistics/statistical computing graduate course as well as on the shelves of any researcher supporting his or her statistical practice with a significant dose of computing backup.