Maria Sinziana Astefanoaei
email: m.s.astefanoaei@sms.ed.ac.uk

Paul Cesaretti
email: paul.cesaretti@qc.cuny.edu

Panagiota Katsikouli
email: citi.panagiota.katsikouli@inria.fr

Mayank Goswami
email: mayank.goswami@qc.cuny.edu

Rik Sarkar
email: rsarkar@inf.ed.ac.uk

Multi-resolution sketches and locality sensitive hashing for fast trajectory processing

Keywords: Data compression, • Networks → Location based services, • Information systems → Global positioning systems, Location, distance estimation, nearest neighbours search, clustering

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

INTRODUCTION

Location analytics is a fundamental aspect of insights from GPS, sensor and mobile phone data, with applications in various domains ranging from social sciences, communication networks to smart cities and transport. Eective analysis depends on fast response to basic queries, for example, nding the nearest neighbor (or all near neighbors) of a given trajectory. Ability to eciently update the query database -e.g., inserting a new trajectory or adding new points to an existing trajectory -helps one to handle streams of trajectory data continuously updated in real time.

Trajectories are usually compared using Hausdor distance, Fréchet distance, or the dynamic time warping (DTW) distance [START_REF] Sakoe | Dynamic programming algorithm optimization for spoken word recognition[END_REF]. The last two are most popular as they incorporate the intrinsic sequential nature of the trajectories in the comparison. However, these distances are computationally challenging to apply to large datasets. Dynamic programming algorithms to compute Fréchet and DTW between two trajectories of length m require O(m 2 ) time per comparison, which makes them prohibitive in large datasets.

Nearest neighbor searching on points in the exact version require either linear query time or space exponential in the dimension d, popularly referred to as the curse of dimensionality. Recently it was proven [START_REF] Alman | Probabilistic polynomials and hamming nearest neighbors[END_REF] that a query time sublinear in n for the batched Hamming nearest neighbor problem would refute the Strong Exponential Time Hypothesis (SETH). With such barriers, researchers turned to approximate nearest neighbor search. Formally, a c-approximate nearest neighbor algorithm will return an item whose distance to the query is at most c times the true nearest neighbor of the query item. Indyk and Motwani [START_REF] Indyk | Approximate nearest neighbors: Towards removing the curse of dimensionality[END_REF] were the rst to develop Locality sensitive hashing (LSH) for this approximation problem, and it was subsequently improved upon in various works to obtain a query time sublinear in n, and polynomial dependence in d in all parameters (see for example: [START_REF] Andoni | Optimal data-dependent hashing for approximate near neighbors[END_REF][START_REF] Charikar | Similarity estimation techniques from rounding algorithms[END_REF][START_REF] Gionis | Similarity search in high dimensions via hashing[END_REF][START_REF] Indyk | On approximate nearest neighbors under lâĹđ norm[END_REF][START_REF] Panigrahy | Entropy based nearest neighbor search in high dimensions[END_REF]). The main idea in LSH is to construct a hash function that ensures that similar items are usually hashed to the same buckets, while dissimilar items are hashed to dierent buckets.

However, unlike point datasets, where one can exploit the bounded doubling dimension of the underlying metric space [START_REF] Arya | Space-time tradeos for proximity searching in doubling spaces[END_REF][START_REF] Backurs | Constant-distortion embeddings of hausdor metrics into constant-dimensional l_p spaces[END_REF], compressing trajectory data while preserving these distances is dicult in general: the space of trajectories under Fréchet distance does not have a bounded doubling dimension and does not easily admit a low dimensional embedding [START_REF] Driemel | Clustering time series under the fréachet distance[END_REF].

LSH for trajectories. Indyk [START_REF] Indyk | Approximate nearest neighbor algorithms for fréchet distance via product metrics[END_REF] describes a version of locality sensitive hashing for product spaces that apply to Fréchet distances. However, this approach has an immense space requirement, which makes it impractical in GPS datasets. A recent work by Driemel and Silvestri [START_REF] Driemel | Locality-Sensitive Hashing of Curves[END_REF] gives simpler mechanisms for locality sensitive hashing of trajectories. This method works by snapping the vertices of trajectories to grids, so that trajectories with Fréchet distance much smaller than the grid size are likely to snap to the same vertices. The vertex order on the grid then serves as a locality sensitive hash.

Apart from near neighbor queries, other important research problems in trajectory datasets include quickly estimating the distance between two trajectories in the dataset, clustering trajectories, or detecting whether one trajectory is similar to a sub-trajectory of another, etc. The above works do not focus on such problems. Furthermore, it is highly desirable to obtain a data structure that can support fast insertions of new trajectories into the dataset, and also one where the user can specify a desired degree of detail.

Our contributions. We devise a hierarchy of sketches for trajectories, that not only perform the basic tasks of locality sensitive hashing and near neighbor search, but can also be used to directly estimate distances between trajectories, cluster trajectories, detect subtrajectories, etc. Our sketches and hash families have the added advantage of being simpler than existing techniques.

The structure of the sketch is as follows: we deploy a random set of disks in the plane, and for each trajectory, test its intersection with these disks. Our basic sketch is simply a bit vector representing the intersection of the trajectory with these disks. This bit vector can act as a simple locality sensitive hash with provable probability guarantee. The main insight is that when disks are deployed randomly, similar trajectories are likely to intersect a similar set of disks. A simple measure of distance using this sketch is the Hamming distance giving the number of bits where two sketches dier. The ordered version of this sketch is a sequence representing the order in which the trajectory enters and exits the disks. These ideas are shown in Figure 1. Measures such as edit distance can be used here to nd how similar two sketches are. In the hierarchic version, we deploy disks of a dierent size at each level of the hierarchy, with the "highest" level consisting of the largest disks. In real data analysis, our scales of interest, and therefore the size of the hierarchy are bounded by the application and the platform. For example, GPS localization measurements have errors up to a few meters, and thus closeness of GPS data is not signicant at scales smaller than this size L. Similarly, beyond a certain distance, such as hundreds of kilometers, data points can simply be treated as far, since applications such as near neighbor search are not useful beyond such distances -let's call it this upper bound U .

We make use of these bounds to get theoretically rigorous results of practical importance. With trajectories d distance apart localized in a region of area A we can show the following:

• there is a constant factor approximation of the distance be- Experimental results. Experimental results on two real datasets show that the distance metric based on the basic unordered sketch is strongly correlated with Hausdor distance, and the distance based on the ordered sketch is correlated with Fréchet and DTW distances. The correlations hold even when a large proportion of the data is missing, for example due to sensing/communication failure or lack of resources. The sketch-based distances can be computed orders of magnitude faster than Hausdor, Fréchet , or DTW.

We found that a at structure -about 50 disks of 2 km radius gives good practical results. Observe that with bit vector size of 50, Hamming distance or matching of hash can be made extremely fast. We used this feature for data pruning in nearest neighbor search. Using the sketch, we identied trajectories of same or similar sketch for comparison, and discarded everything else. Then applied Hausdor and Fréchet distance computation on the small selected set. The sketch achieved a pruning ratio of about 80% (fraction of discarded items), while achieving accuracy of 80% -where the true nearest neighbor was found in the selected set. As a result of the high pruning ratio, on large datasets, this process runs an order of magnitude faster.

In other experiments we studied the eect of size and number of disks used. We also computed the error in distance to the nearest neighbor in the multi-resolution version of the sketch and found this to be usually low.

The rest of the paper is organized as follows. In Section 2 we present related works. In Section 3 we describe the type of queries that we are considering. In Sections 4 and 5 we describe our sketches and prove that they provide an LSH family (thus solving the near neighbor problems). In Section 6 we describe the MRTS (Multi Resolution Trajectory Sketch) data structure and show how to handle insertions, distance estimation, classication and clustering queries. Section 7 contains our detailed experimental results. ) [START_REF] Alt | Computing the fréchet distance between two polygonal curves[END_REF][START_REF] Sakoe | Dynamic programming algorithm optimization for spoken word recognition[END_REF]. Recent results show that assuming strong exponential time hypothesis, strongly subquadratic time algorithms are impossible [START_REF] Bringmann | Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless seth fails[END_REF] for Fréchet . Thus, in datasets of n trajectories. simple near neighbor search will run in O(nm 2 ) time. Indyk's approach to LSH using product metrics [START_REF] Indyk | Approximate nearest neighbor algorithms for fréchet distance via product metrics[END_REF] ) storage, where X is the domain in question -loosely, the area A of the region containing the trajectories. This large data structure to be constructed and stored, and the resultant query time polynomial in m are the main challenges of using this method in GPS datasets with large m.

RELATED WORKS

The recent work by Dreimel and Silvestri [START_REF] Driemel | Locality-Sensitive Hashing of Curves[END_REF] uses more intuitive methods to achieve locality sensitive hashing for Fréchet and DTW. The rst strategy proposed is to snap trajectories to a grid placed with a random translation. The hash of a trajectory in this system is given by the sequence of vertices its snapped version traverses. For two trajectories P and Q, the probability of having identical hash depends on how the grid cell size compares to length m and the Fréchet distance d F (P, Q). In the plane, the probability of identical hash can be shown to be

✓ 1 4md F (P, Q) ◆
. In this scheme, it is possible to construct an LSH with approximation factor linear in m for parameters suitably chosen for a pair of trajectories. A dierent scheme in [START_REF] Driemel | Locality-Sensitive Hashing of Curves[END_REF] proposes to apply a xed sequence of random perturbations to the vertices of a trajectory P before snapping them to nearest grid points. The query undergoes a dierent perturbation per vertex before snapping. This scheme achieves a constant approximation factor, but the probability of hashes matching for two similar trajectories can be shown only to be more than ⇡ 2 4m , which is impractically small for datasets with long GPS trajectories. Since this scheme is meant mainly for answering near neighbor queries, it does not provide answers to various other types of queries one may be interested in, e.g., quickly estimating the distance between two trajectories, clustering, subtrajectory detection, etc. Other works in managing large trajectory datasets include methods of simplication, where the goal is to construct an approximate curve that is close to the original. The Douglas-Peucker algorithm [START_REF] Douglas | Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[END_REF] is possibly the most popular algorithm of this type, which works well in many practical cases. A recent work uses topological persistence to simplify trajectories online, and nd the signicant turns at dierent resolutions [START_REF] Katsikouli | Persistence based online signal and trajectory simplication for mobile devices[END_REF]. Compact sketches based on topology of the domain have been developed in [START_REF] Ghosh | Topological signatures for fast mobility analysis[END_REF]. These methods treat trajectories individually, and do not provide any guarantees on distance computation or search in datasets. The power of large cluster computers has been exploited in [START_REF] Xie | Distributed trajectory similarity search[END_REF] by developing indexing for segmented trajectories. In-network mining for popular subtrajectories is considered in [START_REF] Katsikouli | Distributed mining of popular paths in road networks[END_REF].

In contrast to these works, our focus was to speedup trajectory processing by building highly compressed summaries. This enabled us to rapidly estimate distances between trajectories and prune large fractions of data when searching for similar trajectories.

PROBLEM DESCRIPTION AND BACKGROUND

We let A denote the area of the region (typically a square or a rectangle) of interest that contains all the trajectory data. Let n denote the number of trajectories in the dataset. When comparing two trajectories, we will use the term "distance between them" to mean either the Hausdor or the Fréchet distance (dened in Section 3.1). We dene a trajectory T of length m as a sequence of ordered embedded vertices T = { 0 , 1 , . . . m }. We do not include other information than the order of the vertices, so essentially we treat trajectories as curves. The discrete representation simplies the application of algorithms directly to the data without need for interpolation.

We assume an upper bound U and a lower bound L on the distances of interest. This means that we only care about the actual distance between a pair of trajectories if their distance is between L and U . For other pairs of trajectories, i.e., trajectories that are farther than U apart or within L of each other , we just want to detect if this happens. We partition the interval [L, U ] into subintervals, depending on the degree of detail desired by the user.

Let a be a user-specied constant larger than 1 (otherwise we set a = 2) and let l = log a (U /L). Dene r i = U /a i for i 2 {0, . . . ,l }. Thus r 0 = U , and the r i 's decrease geometrically until r l = L. These r i will serve as partitions of [L, U ] -the smaller the r i , the greater the accuracy.

Let T be the query trajectory. We provide a data structure that performs the following operations eciently: We now describe the proposed distance measures on the space of trajectories and the concept of LSH.

Preliminaries: distance measures and locality sensitive hashing

Distance Measures. As one baseline to compare trajectories, we use the Hausdor distance, which can be dened as the maximum of distances from vertices on one trajectory to the nearest vertex on the other trajectory. For the following denitions we consider two trajectories

T 1 = {u 1 , u 2 , . . . u m 1 } and T 2 = { 1 , 2 , . . . m 2 },
H (T 1 ,T 2 ) = max{max u 2T 1 min 2T 2 d(u, ), max 2T 2 min u 2T 1 d(u, )}.

The complexity of computing Hausdor distance between the two trajectories is

O((m 1 + m 2 ) log (m 1 + m 2 )) [4], using Voronoi diagrams.
The Fréchet distance is another common distance measure, and it is generally believed to be more appropriate for comparing curves in a plane [START_REF] Alt | Approximate matching of polygonal shapes[END_REF]. To dene it we use the concept of traversal (as in [START_REF] Driemel | Locality-Sensitive Hashing of Curves[END_REF]): Denition 3.2 (Traversal). Given two trajectories T 1 ,T 2 , of sizes m 1 , m 2 respectively, a traversal = {(i 1 , j 1 ), (i 2 , j 2 ), • • • , (i l , j l )} is a sequence of pairs of indices referring to a pairing of vertices from the two curves with the properties:

(1) i 1 = 1, j 1 = 1, i l = m 1 and j l = m 2 (2) 8(i k , j k ) 2 : (i k+1 i k ) 2 {0, 1} ^(j k +1 j k ) 2 {0, 1} (3) 8(i k , j k ) 2 : (i k+1 i k ) + (j k +1 j k ) 1.
Denition 3.3 (Discrete Fréchet distance). Let T be the set of all traversals between two trajectories T 1 and T 2 . The discrete Fréchet distance F (T 1 ,T 2 ) between them is:

F (T 1 ,T 2 ) = min 2T max (i k , j k )2 ku i k j k k.
Locality-sensitive hashing. Solutions for approximate nearest neighbours often employ Locality-sensitive hashing (LSH) algorithms which ensure that the probability of two objects to be attributed to the same hash is high for similar objects and low for substantially dierent objects. A family of hash functions is a collection of mappings that are dened on the same sets (the set of all objects, which is of arbitrary size, and a set of xed size).

Denition 3.4 (Locality-sensitive families). Let d be a distance measure dened on two trajectories T 1 and T 2 . Given the values

r > 0, c < 1, 0  p 1 , p 2  1 with p 1 > p 2 , a family H of hash functions is (r , cr, p 1 , p 2 )-sensitive if for every f 2 H : (1) if d(T 1 ,T 2 )  r , then Pr (f (T 1 ) = f (T 2 )) p 1 ; (2) if d(T 1 ,T 2 ) cr , then Pr (f (T 1 ) = f (T 2 ))  p 2 .
A (r , cr, p 1 , p 2 )-sensitive family of hash functions is useful when the collision probabilities p 1 , p 2 satisfy p 1 > p 2 . The LSH families we derive in this paper have p 2 = 0.

LSH families and the near-neighbor problem

Given a (r , cr, p 1 , p 2 )-sensitive hashing family, there is a standard framework for solving (c, r )-near neighbor queries. Using this framework, one can also solve the c-approximate nearest neighbor queries. We briey describe it here, and refer the reader to more comprehensive descriptions [START_REF] Driemel | Locality-Sensitive Hashing of Curves[END_REF][START_REF] Indyk | Approximate nearest neighbors: Towards removing the curse of dimensionality[END_REF] for details. First, we construct a new family H 0 of hash functions by concatenating `= max{1, log p 2 1/n} hash functions. This decreases the collision probability to at most 1/n. We then choose k = (1/p 1 ) hash functions from the family H 0 , and insert each trajectory into k hash tables. This completes the preprocessing phase. Once the query arrives, we search among all trajectories that collide with the query in the k hash tables, and compute the distance of the query trajectory to such trajectories. We can stop as soon as a trajectory within cr distance is found, or in the reporting version, report all trajectories within cr . The space and query time of such a data structure is governed by the parameter = log p 1 /log p 2 . The space used is O(n 1+ + nm) and the query time is O((m log m)n ) for Hausdor distance and O(m 2 n ) for Fréchet distance.

For the LSH families we derive in this paper, p 2 = 0, i.e., far away trajectories never hash to the same bucket. In this case, the query time is O(m). These query times are for the algorithm to work with a constant probability. To get (c, r )-near neighbors with probability at least 1 1/n, we can repeat the above process log n times, leading to an extra logarithmic overhead in the space and query time. Given a data structure to solve the (c, r )-near neighbor problem, one can use the concept of ring trees as described by Indyk and Motwani [START_REF] Indyk | Approximate nearest neighbors: Towards removing the curse of dimensionality[END_REF] to solve the c-approximate nearest neighbor problem.

COMPACT SKETCHES AND LSH FOR NEAR NEIGHBORS

We propose a simple strategy that allows us to build LSH schemes for Hausdor, Fréchet and DTW distances. The sketches are based on randomly deploying disks on a map and considering their intersections with trajectories. We then dene metrics on these sketches that are related to the distances between the corresponding trajectories.

Binary sketches for Hausdor distance

Our approach is based on the observation that if two trajectories T 1 ,T 2 are such that the Hausdor distance H (T 1 ,T 2 ) is small, then they both go through approximately the same neighbourhoods on the map. Fix a radius r > 0, and let D = (A/r 2 ). We dene our sketch S(T ) of a trajectory T as the record of its intersection with D random disks on a map: Denition 4.1 ((D, r )-Binary Sketch). The Binary Sketch of a trajectory T is the binary vector S D,r (T ) = e 1 . . . e D of length D, dened in terms of a set of D random but xed disks of radius r . The vector element e i = 1 if the disk i intersects trajectory T , otherwise it is 0.

We dene the measure of distance between the sketches as the number of bits that are dierent: In other words, this is the L 1 norm of the binary dierence of the two vectors and it represents the number of disks that intersect exactly one of the trajectories.

4.1.1 Data structures to speed up sketch computation. Let T be a trajectory of length m. In O(mD) time we can test each disk for every point in the trajectory, and retrieve the set of disks intersected by the trajectory, i.e., the position of 1s in the sketch vector. However, when D is large (recall that D = (A/r 2 )), we can actually do better.

Notice that for a given point p on the trajectory, we want to quickly determine which of the D disks of radius r contain p. This is essentially a range searching problem: Let Q denote the centers of the D disks, and B denote a ball of radius r around p. A circular range query for B determines which points in Q lie inside B. The disks corresponding to those points are exactly those that contain p (the center of B). Using known range searching data structures from computational geometry [START_REF] Aggarwal | Solving query-retrieval problems by compacting voronoi diagrams[END_REF][START_REF] Matousek | Reporting points in halfspaces[END_REF] Computing the binary sketch distance. For large r such that D = O(m), one can compute the Hamming distance between sketches of length D in the straightforward manner. For small r , D is larger than the number of disks intersected by the trajectory (which will never be more than m, but could be signicantly smaller), resulting in sparse bit vectors. When D is large enough that the vectors are very sparse, we do not store the entire sketch but just the indices of the disks intersected by the trajectory. Assume that no trajectory intersects more than I disks, where I << D, and I = O(m). Then we can actually compute the binary sketch distance in O(I log I ) time using a set intersection query, where the two sets are the sets of disks intersected by each trajectory. Thus, computing the distance takes at most O(min(D, m log m)) time, and is typically signicantly smaller; e.g. for uniformly sampled trajectories, this can be done in O((m/r ) log(m/r )) time.

(1) If H (T 1 ,T 2 ) < 2r c then P(S(T 1 ) = S(T 2 )) > 1 8 r 2 Dm cA (2) If H (T 1 ,T 2 ) > 2r then P(S(T 1 ) = S(T 2 )) = 0.
In order to prove the theorem, we need a geometric lemma.

L 4.5. The probability that a randomly placed disk separates two vertices at distance h is bounded by 4 rh/A. P. The disk separates the vertices when the center lies in the symmetric dierence of the disks of radius r centered at the two vertices. Let us call this the symmetric dierence area. This is shown pictorially in Figure 2.

2: Symmetric dierence area: A disk of radius r separates the two vertices if and only if its center lies in the symmetric dierence of disks at those vertices given by the shaded area. This area is bounded by 4 rh. Thus the probability that a particular disk x separates the vertices, is at most 4 rh/A. ⇤ Proof of Theorem 4.4. (1) For every u 2 T 1 there is a 2 T 2 such that d(u, )  H (T 1 ,T 2 ) = H , and vice versa. Let us refer to this set of pairs as the closest pairs. Any disk of radius r that contains u but not any vertex from T 2 , must also not contain , and therefore must have its center in the symmetric dierence area for u and . This applies for all closest pairs. Thus, any disk i such that d 1 i , d 2 i must lie in the symmetric dierence of at least one closest pair. There are m closest pairs and any closest pair is separated by a distance at most H . By union bound, the probability that the center of a disk is in a symmetric dierence area is bounded by (4 mrH )/A. Substituting H < 2r /c gives the desired bound. To prove (2), we note that if the trajectories are more than 2r away then no disk can contain a point from each trajectory, and hence the sketches cannot be the same.

Observe that setting D = (A/r 2 ) and c = O(m) gives us a constant probability of collision, and thus by the standard framework of (c, r )-near neighbor data structure, we obtain the desired space and query bounds.

Ordered sketches for Fréchet distance

As opposed to Hausdor, the Fréchet distance between trajectories takes into account the ordering of the vertices. Therefore, we propose sketches that maintain the order of the intersections with the disks. Denition 4.6 (Ordered Sketch). Let T be a trajectory and D the set of disks spread on the map. We dene by the Ordered Sketch the sequence of indices of the disks that T enters and exits.

Figure 1 shows a trajectory a passing through disks 1, 2, 3, 4. The trajectory rst enters disk 1, exits 1, enters disk 2, enters disk 3 and so on.

We dene a measure of distance (dissimilarity) and also a measure of similarity between two ordered sketches, and therefore, between their corresponding trajectories. These will help us answer distance related queries when we describe our Multi Resolution Trajectory Sketch (MRTS) data structure. Denition 4.7 ((D, r )-Ordered Sketch Distance). The Ordered Sketch Distance between two trajectoriesT 1 ,T 2 is the edit distance between their (D, r ) Ordered Sketches. That is, the number of insertions, deletions and substitutions required to transform one ordered sketch into another. Denition 4.8 ((D, r )-LCS measure). The LCSM (Longest Common Subsequence Measure) between two trajectories T 1 ,T 2 is the length of the LCS between their (D, r ) Ordered sketches.

4.2.1

Ordered sketches provide an LSH family. We rst nd the probability of collision of two trajectories in terms of their Fréchet distance.

L 4.9. Given two curves T 1 ,T 2 with m 1 , m 2 vertices, m = min(m 1 , m 2 ) and D disks of radius r the probability that they hash to the same sequence is bounded by:

P(OS(T 1 ) = OS(T 2 )) 1 4 rDm A F (T 1 ,T 2 ).
P. Suppose the trajectories do not hash to the same sequence. From Lemma 3 in [START_REF] Driemel | Locality-Sensitive Hashing of Curves[END_REF] we know that an optimal traversal T will separate the trajectories in at most m components, each of them a star. Intuitively a star component has one vertex on one trajectory (traversal is static on this curve), and some vertices on the other trajectory (where the traversal is happening). We consider E k to be the event that a disk separates a pair of vertices in the component k.

Since the component is a star, there must exist vertex such that is connected to all other vertices in the component. All the lengths are less than F (T 1 ,T 2 ). The probability that any pair is separated is less than 4 rF (T 1 ,T 2 )/A (this is just the symmetric dierence areasimilar to what we had before). There are at most m components in the traversal and D disks, therefore, by union bound, the probability that the hashes dier is bounded by 4 r Dm A F (T 1 ,T 2 ).

⇤

This provides us with the following locality sensitive hash family.

T 4.10. Let T 1 ,T 2 be two trajectories of lengths m 1 , m 2 , intersecting at least one disk. Let A be the area of the region, r the radius of the disk, D the number of disks, m = min(m 1 , m 2 ) and c a constant. Then the following are true:

(1) If F (T 1 ,T 2 ) < 2r c then P(OS(T 1 ) = OS(T 2 )) > 1 8 r 2 Dm cA (2) If F (T 1 ,T 2 ) > 2r then P(OS(T 1 ) = OS(T 2 )) = 0.
P. The second part is apparent as there is no disk which intersects both trajectories. For the rst part we use Lemma 4.9. ⇤

Summary of LSH and near neighbor results

We have shown how the binary sketches and the ordered sketches provide a locality sensitive hash family for the Hausdor and the Fréchet distances, respectively. In both families, setting the number of disks D = (A/r 2 ) and c = O(m) gives us a constant collision probability of nearby trajectories, and we have zero collision probability for far-away trajectories. From the framework described in Section 3.2, we obtain that T 4.11. There exists a data structure using binary and ordered sketches, that takes space O(n) memory words, and returns an O(m) approximation (in the Hausdor metric using the binary sketch, and in the Fréchet metric using the ordered sketch) to the (1) (c, r )-near neighbor problem in O(m log n) time.

(2) c-approximate nearest neighbor problem in O(m log 2 n) time.

Now we turn to the other kinds of queries, and the data structure we use to solve them.

MRTS: MULTI RESOLUTION TRAJECTORY SKETCH

In this section we describe the MRTS (Multi Resolution Trajectory Sketch), a layered data structure that we will use to solve distance estimation, classication, clustering and subtrajectory detection queries.

Description

Recall that U and L are upper and lower bounds on the degree of detail desired by the user, and r i = U /a i for 0  i  h, with l = log a (U /L) and r l = L. Dene D i = (A/r 2 i ) for 0  i  l. Our layered data structure has l layers, denoted by

L i , 0  i  l. Layer L i stores (1)
The binary sketches of all the n trajectories, for D i random disks of radius r i each. When D i = (m), we store the set of disks intersecting a trajectory as opposed to the bit vector of length D i . (2) The ordered sketches of all the n trajectories, for D i random disks of radius r i each. (3) In addition, there are forward and backward pointers between a trajectory in the dataset and its corresponding sketches at each layer. Each sketch also stores a counter with the number of trajectories pointing to it.

Insertions. When a new trajectory T is to be inserted in the dataset, we use the data structure referred to in Observation 4. ) log(U /L) + k) time, where k is the total number of disks intersecting the trajectory.

Space. Any point p on a trajectory T lies in O(1) out of the D i disks for every i. This is because D i is the number of disks required to cover the region A and the disks are deployed uniformly at random in the domain. Thus the sketch of T on layer i requires at most O(m) space, and so in total the sketches for the trajectory T in the entire MRTS data structure uses O(ml) space. Since there are n trajectories, O 5.2. The MRTS uses at most O(nm log(U /L)) words of memory in space.

Notice that O(nm) words of space are required to store the dataset. Moreover, the bound above is pessimistic in the sense that we do not consider the fact that for densely sampled trajectories, many points of the trajectory will lie in the same disk. In fact, one can show that for uniformly sampled trajectories, O(r ) points lie in a disk of radius r . This reduces the space usage of our data structure to O( nm L log(U /L)) memory words.

MRTS and distance queries

Now we show how to handle other types of queries mentioned in our problem description. For the sake of brevity, we will restrict ourselves to the Fréchet case, which is arguably harder than the Hausdor case, and more interesting. We point out that all of our results generalize to the Hausdor case with the same (or better) bounds. However, before we describe our query procedure, we need some geometric lemmas.

L 5.3. Consider two disks of radius r , and let h be the distance between their centers. Let A dif denote the area of their symmetric dierence (see Figure 2). Then 1) if h > 2r , A dif = 2 r 2 , and 2) if h  2r , A dif 2rh. P. Part 1) is obvious, as the disks are disjoint. For part 2), the area of the symmetric "lens", or the intersection of the two disks, is given by 2r 2 cos 1 (h/2r ) (h/2) p 4r 2 h 2 . The area of the symmetric dierence is therefore

A dif = 2( r 2 2r 2 cos 1 (h/2r ) + (h/2) p 4r 2 h 2 ) = 2r 2 ( 2( /2 (h/2r ) O((h/2r ) 3 ))) + (h/2r ) p 1 (h/2r ) 2 2r 2 (h/r + O((h/2r ) 3 ) 2rh.
⇤ This gives us the following crucial observation: O 5.4. Let T 1 and T 2 be two trajectories such that their Fréchet distance is F . Then the probability that a randomly chosen disk of radius r intersects one trajectory but not the other is at least 2rF /A. This is because if we look at the component realizing the Fréchet distance (the maximum length of the leash), there must be a pair of vertices u 2 T 1 and 2 T 2 that are F apart. A disk separates these two vertices with probability equal to the measure of their symmetric dierence area, which by the above lemma is at least 2rF /A.

Lastly, we show that the ordered sketches already provide an upper bound on the Fréchet distance. L 5.5. Let T 1 and T 2 be two trajectories with Fréchet distance F . Consider their ordered sketches with D disks of radius r , and assume all vertices overlap at least one disk. If the ordered Sketches coincide, then F < 2r .

P. If the ordered sketches coincide then for every vertex in T 1 there is at least one vertex in T 2 such that the distance between them is lower than 2r , because they should both belong to the same set of disks. There is a traversal that groups every pair of such vertices, giving a cost of at most 2r . This means than an optimal traversal has a lower cost, therefore the Fréchet distance is less than 2r . ⇤ 5.2.1 erying the MRTS. We now describe how we query the MRTS for dierent kinds of queries.

Distance Estimation. Given the indices of two trajectories T 1 and T 2 in the dataset, we want to approximate the Fréchet distance between them. Note that precomputing the distance of a newly inserted trajectory to all the existing trajectories in the dataset trivially solves this problem in O(1) time, but the cost is the high insertion time, at least O(m 2 n). The MRTS has low insertion time, and is still exible enough to answer such queries faster.

Let us consider the optimal traversal of the two trajectories that realizes their Fréchet distance F . As observed, this traversal can be broken down into at most m components, each of which is a star. In some of these components the distance is O(F ), whereas in others it is signicantly lower. Let k be the number of components in which the maximum distance between the vertices of the component (the center of the star and the other vertices on the second trajectory) is (F ). We will rst estimate the product kF .

The main reason in estimating kF is that the symmetric dierence area of the two trajectories depends linearly on k. If k = 1, then the two trajectories travel very close together until they reach this component; in this case the area of the symmetric dierence is O(rF ). On the other extreme, two trajectories could be traveling at a constant distance F from each other (thus giving the same Fréchet distance between the trajectories), but the area of the symmetric dierence is O(rFk).

Let `i denote the fraction of disks on layer i that intersect one trajectory but not the other. Clearly, `i is an unbiased estimator for the symmetric dierence area (for disks of radius r i ). We compute A dif = Õ h i=1 `i A/r i , and let Est k F = A dif /h. We can show that this is an unbiased estimator of the true value of kF , and by increasing the number of disks at each layer, we can get higher concentration for this estimator. The expected value of `i on the other hand equals O(r i kF /A), as the probability that one disk separates the two trajectories equals r i kF /A.

Query Algorithm: Report r j , where j is the smallest value of i such that `i r i EST k F /A.

We conjecture that this value of r j reported is a constant factor approximation of the Fréchet distance between the trajectories. Note that if one just wants an upper bound, the r i corresponding to the last layer i such that S i 1 = S i 2 (the sketches coincide) gives us an upper bound,as by Lemma 5.5, we know that the Fréchet distance between the two trajectories is at most 2r i , since the sketches coincide.

This procedure requires us to examine the sketches at all levels in the worst case, requiring O(min(m, log(U /L) log(A/d 2)) time. To get an upper bound we can stop at the rst layer where we discover the sketches are dierent.

Classication/clustering. Our classication procedure is simple: for a given interval [r i+1 , r i ], we dene the set P i to be all the trajectories that have the same sketch on layer i of the MRTS as the query trajectory.

Using the pointers, we can report the trajectories in P i , or, if one just needs the count, we can read the counter value of the bucket corresponding to the sketch of the query trajectory. Running this procedure for all 1  i  l gives us the partition of the dataset. Procedures such as [START_REF] Mirzasoleiman | Distributed submodular maximization[END_REF] can be used to select representative elements as centers for exemplar based clustering. Clustering of trajectories can be applied to anonymize locations traces [START_REF] Zeng | Mobile r-gather: Distributed and geographic clustering for location anonymity[END_REF].

Subtrajectory Detection. Given the query "Is trajectory T 1 r i -close to a subtrajectory of T 2 ?", we rst insert T 1 and T 2 in the MRTS if they haven't been inserted yet. Then we locate the sketches of T 1 and T 2 on layer i 1. We compute the LCS between these sketches, and answer yes if the sketch for T 1 appears as a subsequence, and no otherwise. To get accurate results with high probability, we can increase the number of disks on layer i 1, and take the majority answer.

EXPERIMENTS

We tested the performance of binary and ordered sketches on two real datasets. The experiments show that:

• there is a correlation between the proposed distace measures and Hausdor (strong correlation), Fréchet and DTW (Section 6.1);

• the correlation holds even with a small number of disks or with incomplete data (Sections 6.1, 6.3);

• the sketches achieve high pruning ratio with good accuracy, less storage space and better running time in nearest neighbours queries (Sections 6.2, 6.4, 6.5).

We ran all experiments on both the CRAWDAD dataset of taxis in Rome [START_REF] Bracciale | CRAWDAD dataset roma/taxi (v. 2014-07-17[END_REF] and the ECML/PKDD dataset of Taxi Trajectories in Porto [START_REF]Ecml/pkdd porto taxi data[END_REF].

Data preparation. The ECML/PKDD (Porto) dataset describes the mobility of 442 taxis driving in the city of Porto (Portugal) for 1 year and is composed of 1.7 million datapoints. The GPS locations (latitude, longitude) are recorded every 15 seconds with mobile data terminals installed in the vehicles. Each trajectory represents a complete taxi trip taken by a passenger. The lengths vary from 1km to 15km. We randomly selected 1000 trajectories in a 5km ⇥ 10km area of the map.

The CRAWDAD (Rome) dataset [START_REF] Bracciale | CRAWDAD dataset roma/taxi (v. 2014-07-17[END_REF] contains the GPS locations of 320 taxi drivers working in the city centre of Rome (Italy). Each trace is for one driver for one day at about 7 second intervals, giving roughly 22 million datapoints. To obtain trajectories similar to individual trips, as in the Porto dataset, we split each trajectory into trips, such that the length of each is at most a 3 times the distance between source and destination. This gives trajectories with lengths roughly between 2km and 5km. We randomly selected 1000 trajectories in a 7km ⇥ 2km area of the map.

Choice of parameters.

For all experiments with a xed number of disks we picked uniformly at random 50 disks of radius 2km. In general, the choice of radius depends on the scale of the problem. Suppose we consider two 1km trajectories to be close if their distance is less than 10m. We choose enough disks to cover the map. Based on results in Section 4, we want to maximise 1 8 r 2 c while 2r c = 10m. For r = 2km, the probability 1 8 r 2 c becomes 0.75, which is a lower bound for the probability that the sketches are the same when the trajectories are less than 10m apart.

Experimental setup. The experiments were implemented in Python 3.4.9 and ran on an Intel Core i5-4570 CPU @ 3.20GHz ⇥ 4 processor. Time comparisons were done by running 20 parallel jobs.

Correlation with Hausdor, Fréchet and DTW

We checked how the proposed distance measures compare to Hausdor, Fréchet and DTW. We grouped the possible values in 30 bins and show in the plots the median value (white line) and the 5-95, 10-90, and 25-75 percentiles (the shaded areas). We see that the sketch distance measure bears a clear correlation to the traditional measures. For Hausdor the correlation is high (⇡ 0.8). For Fréchet and DTW, while the correlation is lower, there is a clear distinction between close and distant trajectories, showing the utility of locality sensitive hashes.

6.1.1 Eect of radius and number of disks. This correlation naturally raises a question of how it is inuenced by parameters such as the number and radii of disks. Figure 4 shows the eect of disk radius; each subplot corresponds to results with a xed number of disks and a varying radius between 500m and 4km. The shaded area corresponds to the 5 to 95 percentiles based on 30 trials. For each trial we computed the Pearson correlation coecient between our distance measure and Hausdor distance.

In Figure 4(a) a radius size of around 2.5km achieves the maximum correlation, beyond which the disks become less discriminatory and the correlation decreases. We also observe that too small a radius does not perform as well -to use a smaller radius we would need to consider more disks.

The correlation also increases with the number of disks. A higher number also assures low variability in performance between trials. Even with a low number, such as 10, we get a good correlation of ⇡ 0.7 or more as long as the radius is in the right range (1.5km-3km). Beyond a certain number, increasing the number of disks does not improve performance. For a good correlation we need to choose enough disks to get a cover of the map, but having more disks oers a more ne grained distance measure at the cost of greater storage and computation, as we discuss in relation to nearest neighbours queries in Section 6.2.

Nearest neighbour search

For a variable number of disks (10, 30, 50) and xed r = 2km, we computed the nearest neighbour for each trajectory in the dataset using Hausdor and Fréchet distances. To prune the search space using our sketches we selected only those trajectories that had sketch distance equal to 0, 1, 2 etc. We measured in what proportion of cases the true nearest neighour is in the remaining set (accuracy), and how large the eliminated set is compared to the total dataset (pruning ratio). In Figure 5 we show how the pruning ratio changes with accuracy.

There is little variation in the accuracy for a specic number of disks. Interestingly, changing the number of disks does not inuence the results too much for nearest neighbor search with LSH; with a small number we can achieve a high pruning ratio and high accuracy. However, larger number of disks provides better resolution when using the sketches as an estimate of distance.

Figures 5 show that accuracy can be as high as about 80% at a pruning ratio of over 80% for both Hausdor and Fréchet distances, even with a small number of disks. Thus, this method allows us to restrict our attention to a small fraction of the trajectories and still obtain the correct nearest neighbor in most cases.

Multiresolution trajectory sketches. In Figure 4 we show how the distance error to the nearest neighbour changes with the dierent number of layers in the multiresolution sketches. We considered 1, 5, 7, 10 and 15 layers. At the rst level the disks have radius r = 2km; this decreases by a factor = 0.1 at each level. The number of disks at level i is given by A/r 2 i log(A/r 2 i ), where r i is radius at level i. To nd the nearest neighbours given a query trajectory we compare the sketches at every layer, starting from the top, and only advance to the next one if the sketches match. When we reach the last layer, the set of the remaining trajectories is searched for the nearest neighbour. The dierence in distance between the true nearest neighbour and the one we found gives the error. Figure 4 shows the CDF of the error.

At the rst level the number of disks is low [START_REF] Driemel | Clustering time series under the fréachet distance[END_REF]. Performance increases quickly with the number of layers. In practice, the performance can be further improved by checking for approximate matches between sketches instead of exact matches (corresponding to distance 0).

Robustness to data loss and privacy of locations

Trajectory data can be subject to sensing errors and noise and often has missing data. In other cases, a lower frequency of location sampling is preferred to maintain the user's privacy in between check-ins [START_REF] Niedermayer | Probabilistic nearest neighbor queries on uncertain moving object trajectories[END_REF]. The disk distance performs well even when large parts of the trajectories are missing. Interestingly, when only 10% of the datapoints in each trajectory are retained, the disk distance is still highly correlated with the Hausdor distance, as can be seen in Figure 3 (d). In this experiment we computed the disk distance on only a 10% sample of the location points in each trajectory, and plotted against their true initial Hausdor distance.

Beyond the natural robustness to unreliable sensing, this result implies eciency of storage and computations as only a small random sample needs to be stored for useful comparison.

Time eciency

We compared the running times of our method using pruning with Hausdor, Fréchet and DTW when computing distance matrices. In the rst experiment shown in Figure 6 (a) we used the standard Hausdor implementation between point sets and computed the time for sampled sets of up to 1000 trajectories. Using the Douglas-Peucker algorithm to rst simplify the trajectories did not bring a large improvement in the computation time. The time taken to compute all pairwise sketch distances is more than 5 times faster than computing Hausdor distance for 1000 trajectories. This also includes the preprocessing time of picking the disks and computing the sketches.

For the second experiment in Figure 6 (b) we computed Fréchet and DTW distances eciently with Python libraries. The results show that the sketch distance computation is 2 times faster than Fréchet for 1000 trajectories when using 50 disks -enough to get a 90% accuracy for nearest neighbours search with 80% pruning ratio, as can be seen in Figure 5.

Comparison with existing LSH method

We compared the performance of the ordered sketches with the grid-based sketches proposed by Driemel and Silvestri [START_REF] Driemel | Locality-Sensitive Hashing of Curves[END_REF]. In their work the hashes are constructed in the following way:

• consider a grid that covers all trajectories;

• each vertex in the trajectory is replaced by the closest node in the grid;

• from the resulting sequence of nodes the consecutive duplicates are removed. In experiments we considered various sizes of grids, ranging from 100m to 15km. For every size s we built a grid that covers the map, where the distance between any two nodes is equal to s. We denote the number of resulting nodes by n grid . To compare with our proposed method, we deployed n grid /2 disks of diameter s. Notice that we are using the ordered sketches (not the xed size binary sketches) because the grid approach gives a LHSs scheme for Fréchet . Two ordered sketches are considered the same if the edit distance is at most 2. Figure 7 shows the results: the two methods perform approximately the same in terms of pruning ratio and accuracy (slightly better for the disks version), but the sizes of our sketches are almost half the size of the grid sketches.

Figure 1 :

 1 Figure 1: Trajectory skteches with respect to randomly deployed disks. Similar trajectories like a and b are likely to pass through same set/seqence of disks. For trajectory a, the basic unordered sketch is 111100, the ordered sketch recording entry and exists is 1, 2, 3, 2, 4, 3, 4 . . . .

  tween them in time O(min(m, log(U /d) log(A/d 2 ))) • a new trajectory can be inserted into the sketch database in O(m log(A/L 2 )) time • an O(m) approximation to the nearest neighbor query can be computed in O(m log 2 n) time.

  Distances between curves are challenging to compute. For inputs of length m, Fréchet distance F (•) and DTW distance DTW (•) can be computed in O(m 2

  achieves an approximation of O(log m + log log n) and nearest neighbor query time of O(m O (1) log n) using O(|X | p m (m p m n) 2

( 1 ) 4 )

 14 (c, r )-near Neighbor queries: if there exists a trajectory in the dataset within distance r , return a trajectory in the dataset that is within cr of T . Our methods allow a linear approximation c = O(m) answer with high probability in O(m log n) time.(2) c-approximate nearest neighbor queries: return a trajectory whose distance to T is within c times the distance of T to its nearest trajectory in the dataset. We can answer the c-approximate nearest neighbor queries in O(m log 2 n) time. (3) Clustering/classication: we can partition the dataset of n trajectories into P 1 , • • • , P l , where trajectories in the set P i are within r i and at least r i+1 away from the query trajectory T . The entire partitioning takes O(l min(m, log(A/L 2 ))) time. To compute only P i for a given i, our data structure takes O(min(m, log(A/L 2 ))) time. (Distance estimation: Given another trajectory T 0 , we can compute a constant factor approximation of the distance d between T and T 0 in O(min(m, log(U /L) log(A/d 2 )) time, where A is the area of the region where the trajectories are deployed. (5) Subtrajectory detection: Given another trajectory T 0 , we can identify if it is similar to a subtrajectory of trajectory T in time O((min(m, log(A/L 2 ))) 2 ). Notice that a subcurve of a curve may have a large Fréchet or Hausdor distance to the original curve, and so such queries are not merely distance queries. (6) Finally, the data structure handles fast insertions of trajectories to the dataset. Inserting a new trajectory of length m into our data structure takes O(m log(A/L 2 ) log(U /L)) time (Lemma 5.1).

Denition 4 . 2 (

 42 (D, r )-Binary Sketch Distance). The Binary Sketch Distance between two trajectories T 1 ,T 2 is the Hamming distance between their (D, r )-Binary Sketches. That is, the number of indices with dierent entries: d D,r (T 1 ,T 2 ) = {i : e 1 i , e 2 i } .

O 4 . 3 .

 43 , this can be accomplished in O(log D + k) time, where k is the number of disks containing p. In summary: Given a set of D disks of radius r and a trajectory T of length m, the set of k disks that intersect T can be computed in O(m log D + k) time.

4. 1 . 2

 12 Binary sketches provide an LSH family.

T 4 . 4 .

 44 Let T 1 ,T 2 be two trajectories of lengths m 1 and m 2 respectively, intersecting at least one disk. Let m = min(m 1 , m 2 ) and c > 1 a constant. Then the following are true:

3 .

 3 Computing the sketch on layer i requires O(m log D i + k i ) time, where k i is the number of disks of radius r i that intersect T . Since D i  D l , overall, this costs us at most O(m log D l l + k), where k is the total number of disks intersecting T . Plugging in the values of D l and l, we get L 5.1. A new trajectory T can be inserted into MRTS in O(m log(A/L 2

  Figures 3 (a), (b), (c), (e), (f) show the results for the Porto and Rome dataseta. For each pair of trajectories we compute the distance: with the binary unordered sketches for Hausdor and with the ordered version for Fréchet and DTW.

Figure 3 :

 3 Figure 3: Correlation of binary and ordered sketch distances with Hausdor, Fréchet , and DTW for the Porto and Rome datasets (the 5-95, 10-90, and 25-75 percentiles).

Figure 4 :Figure 5 :

 45 Figure 4: (a) Correlation coecient with Hausdor distance depending on the disk radius and the number of disks. Variance decreases when increasing the number of disks. (b) CDF of the Hausdor distance error between true and found nearest neighbours. With more layers the error decreases.

Figure 6 :

 6 Figure 6: Better performance in terms of running time.

Figure 7 :

 7 Figure 7: Better performance in terms of (a) accuracy and (b) storage size.

Table 1 :

 1 ,T 2 ) Hausdor distance between trajectories T 1 and T2 F (T 1 ,T 2 )Frechet distance between trajectories T 1 and T 2 Table of notations Denition 3.1 (Hausdor distance). The Hausdor distance between T 1 and T 2 is:

	Symbol	Description
	T	trajectory (sequence of GPS locations)
	m	length of trajectory
	n	number of trajectories
	A	area of the map
	H (T 1 D	number of disks
	r	radius of a disk
	binary sketch OS D,r (T ), OS(T ) ordered sketch S D,r (T ), S(T ) d D,r distance between sketches (binary or ordered)
	U, L	upper and lower bounds on the degree of detail
	`number of layers
	L i	layer i
	D i	number of disks on layer i
	r i	radius of disks on layer i
	A dif	area of the symmetric dierence
	EST k F	estimator of kF

of length (number of vertices) m 1 and m 2 , respectively.

CONCLUSION

We presented a randomized sketching scheme to compactly represent trajectories, and established its eectiveness in both theory and practice of trajectory processing. Planar networks and trajectories are common in robotics, biological systems and many other domains. Adaptation of this basic randomized scheme in these areas remain to be investigated, as well as in trajectories embedded in higher dimensions.


Carmela D'avino
email: c.davino@uel.ac.uk

Banking regulation and the changing geography of off-balance sheet activities

Keywords: US banks, interest rate swaps, derivatives regulation. JEL: F33, G15, G21

This paper investigates whether the substitute compliance framework under the new US regime for over-the-counter derivatives has stimulated regulatory arbitrage. Results point to increased post-regulatory concentration in exposure in those countries in which US banks comply with local derivative regulation.

Introduction

In the light of the global nature of derivative markets, the regulatory framework for Over-The-Counter (OTC) swaps, contained in the Dodd-Frank Act (DFA), sets forth an extraterritorial applicability to foreign transactions involving US financial institutions. Enacted by the Commodity Futures Trading Commission (CFTC) in 2013, the Interpretive Guidance on cross-border swaps regulations allows foreign branches of US banks to comply with local regulation via a substitute compliance framework in a number of jurisdictions with broadly comparable provisions1 .

This paper, focusing on the largest segment of swaps markets, that is, Interest Rate Swaps (IRS), investigates whether substitute compliance has resulted in regulatory arbitrage by foreign branches of US banks, tilting the playing field in favor of those countries in which the framework is available. Lagged implementation timing and/or marginally less stringent regulation in those jurisdictions where substitute compliance is available may indeed cause an increase in geographical concentration of swaps trading in favor of these latter [START_REF] Artamonov | Cross-border application of OTC derivatives rules: revisiting the substituted compliance approach[END_REF] 2 .

Evidence on the implications of the DFA on swap markets is limited in the literature and focuses mainly on market liquidity [START_REF] Benos | Centralized trading, transparency and interest rate swap market liquidity: evidence from the implementation of the Dodd-Frank Act[END_REF][START_REF] Loon | Does Dodd-Frank affect OTC transaction costs and liquidity? vidence from real-time D trade re orts[END_REF]. This research is a first attempt to explore whether the DFA has stimulated cross-border regulatory arbitrage by US banks 3 .

The investigation is based on a novel dataset encompassing IRS positions of foreign branches of US banks aggregated over by host-country, contained in the Foreign Branch Report of Condition available from the Federal Financial Institutions Examination Council (FFIEC030). Data is available quarterly for 23 countries over the period 2001q1-2015q3. Geographical shifts in favor of locations in which regulatory equivalence is available to EU banks featuring an analogous extraterritorial reach are also accounted for 4 . The IRS exposure of US banks may indeed increase in countries susceptible to witness a surge in the presence of their main competitors and counterparties, that is, EU banks, resulting from a parallel attempt to circumvent domestic regulation.

Table 1 reports post-guidance growth rates of IRS exposure of branches of US banks in selected countries. Exposure in jurisdictions with substitute compliance/equivalence for either/both US or/and EU banks have increased with notable exception of Japan featuring fully-implemented and stricter regulation (FSB, 2014).

Empirical analysis

The baseline model is:

(

is the ratio of IRS (notional amounts) to assets of branches located in host-country i, i=1,…,23.

accounts for host country groupings, captured by s dummies, s=1,…,S allowing to assess geographical shifts either away from those locations with tighter regulations, such as European countries and Japan, or towards those jurisdictions in which substitute compliance/equivalence is available. European countries are captured by the dummy Europe; a dummy is also used for England. DUSnoEU contains countries, other than European, in which substitute compliance is available to branches of US banks. DEU identifies those locations, other than the US, in which regulatory equivalence is available to EU banks5 . Country dummies are also considered without Japan in the following identifiers: DUSnoJP and DEUnoJP. See Table 2 for details. 2015q3). is a fixed-effect that captures unobserved host-country specific variables, such as differences in regulatory environment. Fixed-time period dummies are also included in the regression (unreported) to account for common time-varying effects on IRS exposures across the panel.

X i,t contains k=1,...,K control variables. The choice of the location of IRS trading of branches may not be necessarily driven by local economic conditions as counterparties are often located in third countries. Albeit a given jurisdiction's macroeconomic stability and favourable regulation can stimulate local off-balance sheet activities, financial markets depth, sophistication and openness can also explain the locational choice of IRS trading. Financial openness (Openness it ) is proxied by host location i's cross-border assets plus liabilities vis-àvis reporting banks as a share of host county's GDP. Outstanding derivative positions on resident counterparties as a share of GDP (derivatives it ) proxy for local financial development and sophistication. Inflation rates proxy for macroeconomic stability in i (inflation it ) and the log of assets of branches in i (size it ) controls for the relative importance of on-balance sheet activities. IRS exposure of banks arises primarily from market-making/dealing and interest rate risk management. Interest rate risk at the host-country level capturing the latter is proxied by the absolute value of one minus the loans-to-deposit ratio (IRrisk).

Results

Table 3 presents the regression estimates of (1) for different specifications. The coefficient of Europe*TrUS in column (1) shows that in the US post-regulation era the IRS exposure of foreign branches of US banks in Europe has declined 6.5% more than in other locations. This fall is particularly important for branches located in England whose IRS exposure was 22% lower than elsewhere over the same period, as reported in column (2).

Specifications in columns (3)-(8) capture those locations in which a framework of substitute compliance/equivalence is available to either US and/or EU banks. Column (4) considers exclusively the pre-guidance period (i.e. TrUS=0) in order to test whether IRS exposure of US banks had not been growing at a faster rate before 2014 in those countries in which substitute compliance was available. Column (8) considers the marginal effects on IRS exposure in the subgroup of countries, other than Japan, in which both US and European banks can rely on local derivative regulations, i.e. in Australia, Hong Kong and Canada.

The estimated coefficients of the different country interaction dummies in specifications ( 3)-( 8) are all positive and strongly significant. However, when comparing preand post-guidance increase in IRS exposure in those countries with substitute compliance in relation to other foreign locations (DUSnoEU definition, columns 3 and 4), post-guidance levels were significantly higher. Overall, evidence points to a more pronounced, i.e. when compared to other locations, post-regulatory increase in IRS exposure of branches of US banks located in those countries in which substitute compliance/equivalence is either available to them or to branches of EU banks. This geographical shift is particularly important in those countries, other than Japan, in which equivalence is available to EU banks, as reported in column ( 7), in which IRS exposure has increased 9% more than elsewhere since early 2014. This evidence suggests a swift response of US banks to move a large part of their off-balance sheet activities to those countries more susceptible to accommodate a higher volume of swap trading by their major competitors and counterparties. The subset of jurisdictions, other than Japan, in which branches of both EU and US banks can comply with local OTC regulation depict the highest post-guidance increase in IRS exposure: about 9.4% higher than elsewhere (column 8).

The estimated coefficients of the control variables reveal that macroeconomic stability is an important determinant of the location of IRS exposure by foreign branches of US banks. The negative and strongly significant coefficient of on-balance sheet assets (in logs), i.e. size i,t , uncovers a geographical polarization of on and off-balance sheet activities of branches of US banks. The nonsignificant coefficient of IRrisk reflects the fact that IRS exposure is largely due to dealing and market-making rather than to insure from the interest rate risk that arises from local activities.

Conclusions

The 2007-09 global financial crisis has uncovered the potential threats to domestic financial stability posed by excessive risk taken by foreign offices of global banks. The extraterritorial clause contained in the OTC swaps regulation, set out in the DFA, reflects the intent of US regulators to prevent further large scale bailouts such as that of American International Group in 2008 caused by the excessive swaps exposure by its London office. While the new regulatory framework aims to discourage geographical concentration of risk by US banks, loopholes arising from substitute compliance frameworks available for US banks may create new geographical hubs for swaps trading. The findings in this paper point to significant relocation of IRS exposure of branches of US global banks away from traditional locations, such as England, and in favor of those countries in which US and/or EU banks can comply with local OTC derivatives market regulation. This evidence points to the existence of loopholes in international regulatory systems arising from technical nuances. IRriski,t -0.000 (0.000) -0.000 (0.000) -0.000 (0.000) -0.000 (0.000) -0.000 (0.000) -0.000 (0.000) -0.000 (0.000) -0.000 (0.000)

Table 1 : IRS exposure by host country, % 2014-2015

 1

		%	Substitute Compliance/Equivalence?
	Australia	12	US,EU
	Canada	42	US,EU
	England	-19	US
	Hong Kong	36	US,EU
	Japan	-25	US,EU
	Singapore	32	EU
	South Korea	18	EU
	South Africa	6	EU
	Switzerland	63	US,EU
	Taiwan	-37
	Bahamas	-48
	Thailand	-3
	China	-20
	Philippines	-16
	Source: FFIEC030.

Table 2 : Country dummies

 2 , c=US,EU are time dummy variables, capturing the timing of the extraterritorial applicability of derivative regulation in the US (2014q1-2015q3) and in the EU (2014q4-

	Europe	DUSnoEU	DUSnoJP	DEU	DEUnoJP
	Italy	Australia	Australia	Australia	Australia
	Belgium	Hong Kong Hong Kong Hong Kong	Hong Kong
	England	Canada	Canada	Canada	Canada
	Germany Japan	Italy	Japan	Singapore
	France		Belgium	Singapore	Republic of Korea
			England	Republic of Korea South Africa
			Germany	South Africa
			France
	TR c

  This Table reports the estimates of panel regressions over the period 2000q2-2015q3. Robust standard errors in parentheses. ***,**,* refer to 1%, 5% and 10% significance levels, respectively.

	Host country fixed effect	x	x	x	x	x	x	x	x
	Fixed time dummy	x	x	x	x	x	x	x	x
	Observations	1426	1426	1426	1242	1426	1426	1426	1426
	R 2	0.794	0.804	0.793	0.818	0.797	0.794	0.801	0.797
	Adjusted R 2	0.781	0.791	0.779	0.806	0.783	0.781	0.788	0.783
	Notes:

Applicable from December-end

2013, the interpretative guidance is a not-binding policy statement indicating intentions of forthcoming legislation. The CFTC establishes regulatory comparability of foreign jurisdictions.2 See FSB (2014) for cross-country progress in OTC reforms.3 Research on cross-border regulatory arbitrage by banks is well-documented[START_REF] Acharya | International alignment of financial sector regulation[END_REF][START_REF] Carbo-Valverde | Regulatory arbitrage in crossborder banking mergers within the EU[END_REF][START_REF] Houston | Regulatory arbitrage and international bank flows[END_REF]).4 See the European Market Infrastructure Regulation.

Including those countries granted equivalence by the European Commission in both 2014 and 2015.


Olivier Jourdan

Alexander A Kokhanovsky

John P Burrows

Calibration of SCIAMACHY Using AATSR Top-of-Atmosphere Reflectance Over a Hurricane

Keywords: satellite instrumentation, calibration, AATSR, MERIS, SCIAMACHY

come

Introduction : Overview of SCIAMACHY calibration issue

The SCAnning Imaging Absorption spectroMeter for Atmospheric ChartographY (SCIAMACHY) is a moderate resolution imaging spectrometer [START_REF] Bovensmann | SCIAMACHY: Mission objectives and measurement modes[END_REF] onboard ENVISAT. It is designed to measure the scattered and reflected spectral radiance in nadir and limb geometry, the spectral radiance transmitted through the atmosphere (solar and lunar occultation geometry) and the extraterrestrial solar irradiance and the lunar radiance. It was launched on orbit on March 1 st , 2002. Measurements are expected to continue for at least another four years (till 2010). Data are recorded at moderate spectral resolution (0.2-1.5nm) in a spectral range of 240-1750 nm divided in 6 channels as well as in two smaller spectral regions corresponding to 1940-2040nm and 2265-2380nm. In the nadir mode, the spatial resolution is between 30x30 km 2 and 30x240 km 2 . Accordingly, SCIAMACHY's main objective is focused on the accurate measurements of trace gases in the terrestrial atmosphere. As most SCIAMACHY retrieval algorithms rely on studies of the depths of gaseous absorption bands of backscattered solar light (Borell et al., 2004), the accurate calibration of the instrument is not of primary importance. However, for the retrieval of the atmospheric optical thickness (OT) from space, an accurate calibration is essential. Indeed, for optically thin atmospheric layers, radiative transfer calculations show that the optical thickness is directly proportional to the top-of-atmosphere (TOA) reflectance. Therefore, calibration errors of, for example 25%, will produce in turn the same range of error for OT (for optically thin layers). The uncertainties in the forward model can increase the error even further or make the retrievals impossible (e.g., the aerosol TOA reflectance can become a negative number after removal of a well-defined molecular scattering contribution).

Numerous studies have been performed related to SCIAMACHY calibration, both reanalyzing ground data collected before launch of ENVISAT [START_REF] Noël | Determination of correction factors for SCIAMACHY radiances and irradiances[END_REF] and also using the comparison with the MEdium Resolution Imaging Spectrometer (MERIS) TOA reflectances [START_REF] Acarreta | Calibration comparison between SCIAMACHY and MERIS onboard ENVISAT[END_REF]Kokhanovsky et al., 2006a;[START_REF] Von Hoyningen-Huene | Validation of SCIAMACHY top-of-atmosphere reflectance for aerosol remote sensing using MERIS L1 data[END_REF].

MERIS is a 68.5  field-of-view pushbroom imaging spectrometer that measures the solar radiation reflected by the Earth, at a ground spatial resolution of 300m, in 15 spectral bands, programmable in width and position, in the visible and near infra-red.

MERIS allows global coverage of the Earth in 3 days. The reduced resolution mode (RRM) of MERIS has a spatial resolution of 1040m across track and 1160m along track.

Measurements are performed in nadir geometry in 15 narrow channels with an average spectral width of 10nm [START_REF] Bezy | MERIS -a new generation of ocean-colour sensor onboard ENVISAT[END_REF][START_REF] Von Hoyningen-Huene | Validation of SCIAMACHY top-of-atmosphere reflectance for aerosol remote sensing using MERIS L1 data[END_REF] 1 . Moreover, [START_REF] Delwart | MERIS 1st year: early calibration results[END_REF] showed that the calibration error of MERIS was below 4%.

The analysis performed by several groups confirmed that TOA reflectances measured by SCIAMACHY are too low as compared to MERIS measurements. Previous works emphasized that SCIAMACHY calibration errors vary from 10 to 25% depending on the channel and the ground reflectance conditions (see among others, [START_REF] Kerridge | Intercomparison of MIPAS and SCIAMACHY L1 and L2 products with GOME and AATSR[END_REF]Latter et al., 2003;Acaretta and Stammes, 2005;[START_REF] Noël | Determination of correction factors for SCIAMACHY radiances and irradiances[END_REF][START_REF] Von Hoyningen-Huene | Validation of SCIAMACHY top-of-atmosphere reflectance for aerosol remote sensing using MERIS L1 data[END_REF]. Although there are physical grounds behind the possible changes of the error with the wavelength (e.g., due to the spectral reflectance of films and coatings on the optics of an instrument), the calibration factors should not depend on the surface 1 More specifically, the channels are centered on the following wavelengths : 412.5nm(10nm), 442.5nm(10nm), 490nm(10nm), 510nm(10nm), 560nm(10nm), 620nm(10nm), 665nm(10nm), 681.3nm(7.5nm), 708.8nm(10nm), 753.8nm(7.5nm), 760.6nm (3.8nm), 778.8nm(15nm), 865nm (20nm), 885nm(10nm), 900nm (10nm) where the width of the correspondent channel is given in brackets.

reflection. However, comparisons between SCIAMACHY and MERIS measurements showed that significant differences of reflectances were encountered between these two instruments depending on the surface type. The biases were always found to be larger for underlying water surfaces. In particular, [START_REF] Acarreta | Calibration comparison between SCIAMACHY and MERIS onboard ENVISAT[END_REF] found that the difference with MERIS was only of 15% over land but 25% over ocean for the 885nm wavelength. We believe that such an estimation of the calibration error is more reliable over an ocean surface because the surface contribution is less important at 885nm for ocean compared to that of the land. It also should be pointed out that the bi-directional properties of the surface and its horizontal inhomogeneity may influence the main assumption of a vicarious calibration:

( ) R R r dr     (1)
for sensors having significantly different spatial resolutions. In Eq. ( 1), R is the reflectance measured by a sensor having a coarse spatial resolution ( 2 ~2000 in the case of SCIAMACHY) km and  

R r

 is the reflectance measured by an instrument with a high spatial resolution (e.g., 2 ~1km as in the case of MERIS) at the point characterized by the two dimensional radius-vector r  . Furthermore, the violation of Eq. ( 1) can be also due to discrepancies in observation angles of instruments under comparison. Under condition that Eq. ( 1) holds, results of [START_REF] Acarreta | Calibration comparison between SCIAMACHY and MERIS onboard ENVISAT[END_REF] assert that the calibration factor indeed depends on the ground scene, being systematically smaller for bright surfaces (in the 442-885nm wavelength range). On the other hand, as we mentioned above, due to the linearity of detectors, the bias between MERIS and SCIAMACHY calibration factors shouldn't depend significantly of the scene studied. It points out that the relationship presented in Eq. ( 1) does not hold for all cases.

Therefore, it is more adequate to perform a calibration study over a homogeneous surface or to use wavelengths where the surface contribution is low.

In order to address further the SCIAMACHY calibration issue, we have performed the vicarious calibration of SCIAMACHY over a hurricane with an underlying ocean surface, using yet another optical instrument on ENVISAT, namely the Advanced Along Track Scanning Radiometer (AATSR). This is considered in the next section.

Vicarious calibration of SCIAMACHY using AATSR TOA reflectance

AATSR, along with MERIS and SCIAMACHY, is part of the atmospheric payload onboard ENVISAT. AATSR employs a dual view where each scene is viewed at nadir and at a forward angle of 55°. Its field of view covers a 512km width curved swath centered at nadir and the ground pixel size is 1x1km 2 at the center of the nadir scan. The spectral information of the sensor is divided in three thermal infrared channels centered at 3.7µm, 11µm and 12 µm and four visible/near infrared channels (20-nm width except for a channel 60 nm wide centered at 1.6 µm) centered at 0.55 µm, 0.67µm, 0.87 µm and 1.6 µm. According to SCIAMACHY spectral resolution, these four channels can directly be exploited for TOA reflectances comparison between SCIAMACHY and AATSR.

Additionally, the calibration error of AATSR is small and comparable with that of MERIS.

The differences in MERIS-AATSR TOA reflectances are close to +3% for wavelengths at 0.55 µm, and 0.87 µm, and below 1% at 0.665 µm [START_REF] Smith | Intercalibration of AATSR and MERIS reflectances[END_REF].

Considering the calibration issues stated earlier, we chose to make a comparison of AATSR-SCIAMACHY reflectances over a scene with an underlying ocean surface that mainly encompasses optical thick cloud fields. In particular, this case study was conducted over Hurricane Isabel (orbit 08094 of ENVISAT, 17.09.2003, 14:50UTC) with a center located at (72W, 30N) (Fig. 1). One can refer to our previous work (Kokhanovsky et al., 2006b) for further details on the selected scene. SCIAMACHY Level 1 productsversion 5 wereused in this work.

The AATSR-SCIAMACHY reflectances intercomparison methodology follows the same procedure as the one proposed by [START_REF] Acarreta | Calibration comparison between SCIAMACHY and MERIS onboard ENVISAT[END_REF]. First, the four visible/near infrared AATSR channels (0.55µm, 0.67µm, 0.87 µm and 1.6 µm), which are within SCIAMACHY spectral range, were selected. Then, in order to compare L1

AATSR nadir products with L1 SCIAMACHY products, spectrally averaged nadir reflectances are calculated for SCIAMACHY at each AATSR visible/near infrared spectral channels by integrating over AATSR filter response function. The shape of the AATSR slit function was chosen as a rectangular one. We believe that the choice of such a shape will not introduce significant errors compared to the real AATSR filter response function as [START_REF] Acarreta | Calibration comparison between SCIAMACHY and MERIS onboard ENVISAT[END_REF] found that the effect of the MERIS slit function was negligible on the change of the calibration factors. Additionally, the spectral dependence of the reflection function of cloudy scenes is negligible due to the large size of scatterers. The final step consisted in collocating 1x1km 2 AATSR pixels within each 30x60km 2 SCIAMACHY pixels on the basis of their longitude and latitude coordinates.

Additionally, in this study, only SCIAMACHY pixels corresponding to a cloud fraction greater than 99% were selected. This pixel selection was based on a threshold technique of the SCIAMACHY and AATSR TOA reflectances at 0.87µm. An AATSR pixel within a given SCIAMACHY pixel has been considered as completely cloudy if the reflection function at 0.87µm of both instruments exceeded the threshold value of 0.2 [START_REF] Kokhanovsky | Optical properties of a hurricane[END_REF]. In turn, the number of AATSR cloudy pixels within the SCIAMACHY pixel gives an estimation of the cloud cover of the SCIAMACHY pixel. The pixels fulfilling these criteria were used to investigate the possibility to establish linear relationships between SCIAMACHY and AATSR reflectances and therefore perform a calibration study.

We believe that a scene containing a hurricane structure is a good choice for the vicarious calibration of SCIAMACHY, not only because the levels of backscattered light intensity on SCIAMACHY detectors are quite large and variable, but also due to the relative homogeneity of the spectral TOA reflection function (RF). Additionally, the RF of the thick clouds under study is only slightly dependant on the observation angles and wavelengths. This reduces the possible influence of the observation geometry and the spectral instrument sensitivity function on the calibration coefficient. The possible effects of the surface inhomogeneity and the lower troposphere also significantly diminish for this case.

The results of the AATSR-SCIAMACHY reflectances intercomparison are presented in terms of linear regression plots displayed for four wavelengths in Figs. 2345.

It follows from the analysis of Figs. [START_REF] Acarreta | Calibration comparison between SCIAMACHY and MERIS onboard ENVISAT[END_REF][START_REF] Von Hoyningen-Huene | Validation of SCIAMACHY top-of-atmosphere reflectance for aerosol remote sensing using MERIS L1 data[END_REF]. Results for calibration coefficients obtained using the comparison of SCIAMACHY measurements with those of POLDER instrument (see http://smsc.cnes.fr/POLDER/ for the description of the instrument) have been presented by Tilstra and Stammes (2006). They are also given in Table 1. The calibration coefficients found are consistent with previous findings reported by [START_REF] Acarreta | Calibration comparison between SCIAMACHY and MERIS onboard ENVISAT[END_REF] obtained using MERIS.

It follows that C generally increases with the wavelength except the case at 1600nm, where the calibration error is at minimum (C=1.1). The similar trend is seen in the analysis of ground SCIAMACHY calibration data as reported by [START_REF] Noël | Determination of correction factors for SCIAMACHY radiances and irradiances[END_REF] 2 (doted points on Fig. 6). This behavior was also found by von Hoyningen-Huene et al. ( 2006), who determined, using MERIS observations, values of C equal to 1.10, 1.12, 1.21 for SCIAMACHY channels 3 (394-620nm), 4(604-805), and 5(785-1050), respectively. (except highly oscillating results at the edge of SCIAMACHY channels) will be used in the next version of SCIAMACHY Processor (the version 6.0, S. Noël, private communication). In this way, after this re-calibration is achieved, MERIS and SCIAMACHY will have very similar reflectances at 442 and 510nm. The reflectance of SCIAMACHY for other wavelengths will also come closer to the results obtained by other instruments. However, except at 1600nm, the SCIAMACHY reflectances will remain on average smaller than those of MERIS and AATSR.

In a previous work, [START_REF] Kerridge | Intercomparison of MIPAS and SCIAMACHY L1 and L2 products with GOME and AATSR[END_REF] compared SCIAMACHY and AATSR reflectances for several heterogeneous ground scenes. In total, five scenes were analyzed and both SCIAMACHY and AATSR reflectances were averaged over larger scenes of 480*512km 2 . They found calibration coefficients equal to 1.13 (at 550nm), 1.10 (at 670nm), and 1.19 (at 870nm). The coefficient found at 870nm is in agreement with the one reported by us and also to that obtained using MERIS (see Table 1). The coefficients at smaller wavelengths are smaller than the ones we found but remain closer to those corresponding to average coefficients obtained from MERIS observations. This could be explained by the fact that coefficients reported by [START_REF] Kerridge | Intercomparison of MIPAS and SCIAMACHY L1 and L2 products with GOME and AATSR[END_REF] and also by [START_REF] Acarreta | Calibration comparison between SCIAMACHY and MERIS onboard ENVISAT[END_REF] correspond to highly heterogeneous scenes (e.g., water, vegetation, clouds). Our results characterize a somehow more homogeneous scene encompassing a hurricane. However our results still remain comparable with MERIS observations over water surfaces. Yet another possible reason of differences could come from the fact that previous AATSR-SCIAMACHY calibration studies were limited to scenes with lower reflectivity compared to the case studied in this paper. Latter et al. (2003) found that the calibration coefficients are 1.15 (at 550nm), 1.05 (at 670nm), 1.24(at 870nm), and 1.13 (at 1600nm). They have also used AATSR for SCIAMACHY calibration based on the analysis of three complete orbits. However, instead of averaging AATSR pixels to the SCIAMACHY 30*60km 2 scenes, much larger ground scenes were selected.

Conclusions

We confirm that the current version of SCIAMACHY Processor (5.0)

underestimates the TOA reflectance. The comparison of SCIAMACHY with AATSR measurements over a hurricane points out an underestimation of TOA reflectances by SCIAMACHY of 21%, 19%, 23%, and 10% at 550, 670, 870, and 1600nm, respectively, which is generally consistent with findings of [START_REF] Acarreta | Calibration comparison between SCIAMACHY and MERIS onboard ENVISAT[END_REF] using MERIS. [START_REF] Kerridge | Intercomparison of MIPAS and SCIAMACHY L1 and L2 products with GOME and AATSR[END_REF] used a similar approach as described in this paper and found calibration differences for SCIAMACHY around 13% (550nm), 10%(670nm), and 19%(870nm) as compared to AATSR with a small variability depending on the scene studied. Latter et al. (2003) reported the values of 15% (550nm), 5%(670nm), 24%(870nm), and 13%(1600nm) comparing AATSR and SCIAMACHY collocated measurements. The discrepancies of calibration constants reported by different authors could be due to the differences in the ground scenes and versions of processors used.

Although there is a discrepancy with respect to the derived value of the SCIAMACHY calibration constants by different remote sensing groups, the underestimation of SCIAMACHY TOA reflectances can be considered as a well established fact now.

Therefore, we conclude that it is of importance to introduce the next version of error of 4% [START_REF] Delwart | MERIS 1st year: early calibration results[END_REF]. The difference in calibrations of MERIS and AATSR are smaller than 3% with the overestimation by AATSR [START_REF] Smith | Intercalibration of AATSR and MERIS reflectances[END_REF].

Figure 6

 6 Figure 6 displays the spectral dependence of SCIAMACHY calibration factors obtained from measurements carried out at ground before launch of ENVISAT (open circles) and derived from MERIS (full black squares), AATSR (open triangles), and

Fig. 1

 1 Fig. 1 Browse image of Hurricane Isabel as seen by AATSR.

Fig. 2

 2 Fig.2 Correlation between AATSR and SCIAMACHY reflectances at 550nm.

Fig. 4

 4 Fig.4The same as in Fig.3except at 870nm.

Fig. 5

 5 Fig.5The same as in Fig.2except at 1600nm.

  Fig.1

  compared to the one reported by[START_REF] Acarreta | Calibration comparison between SCIAMACHY and MERIS onboard ENVISAT[END_REF] are presented in Table1. It ensues from this table that MERIS and AATSR give comparable calibration coefficients with respect to SCIAMACHY. We chose not to report the offset in our table because it represents a low reflectance value and can be neglected. This is confirmed by other independent calibration studies

	which is in close agreement with the value	1.25 C 	reported by Acarreta and Stammes
	(2005) at 885nm for MERIS measurements over ocean.		Results of the vicarious
	calibration using AATSR
	2-5, that AATSR reflectances (R aatsr ) and
	SCIAMACHY reflectances (R scia ) are almost perfectly correlated with a correlation
	coefficient larger than 98%. The least square fit error is close to 0.01 for each wavelength
	and the offset has a maximum value of 0.004 indicating that overall the fit is acceptable.
	However, scia R are lower by 21% at 550nm, 19% at 670nm, 23% at 870nm, and 10% at
	1600nm as compared to aatsr R . This is close to earlier MERIS-based findings reported
	above. Moreover, the calibration coefficient	aatsr C R 	/	scia R	at 870nm is equal to 1.23

Table 1 .

 1 The values of the calibration coefficient C averaged for different ground scenes ,

	 nm	C	Reference
	442	1.13	Acarreta and Stammes (2005) (ocean:1.18)
	443	1.12	Tilstra and Stammes (2006) (POLDER)
	490	1.13	Tilstra and Stammes (2006) (POLDER)
	510	1.13	Acarreta and Stammes (2005) (ocean:1.17)
	550	1.21	this work
	565	1.14	Tilstra and Stammes (2006) (POLDER)
	665	1.15	Acarreta and Stammes (2005) (ocean:1.19)
	670	1.19	this work
	708	1.18	Acarreta and Stammes (2005) (ocean: 1.21)
	765	1.16	Tilstra and Stammes (2006) (POLDER)
	870	1.23	this work
	885	1.21	Acarreta and Stammes (2005) (ocean:1.25)
	910	1.21	Tilstra and Stammes (2006) (POLDER)
	1600	1.10	this work

Refer to the following web page for further details : http://www.iup.physik.uni-bremen.de/sciamachy/SCIA_CAL/rad_cal.html and also Fig.6

Acknowledgements

This work has been supported by Alexander von Humboldt Foundation and DFG Project BU-688-2. Authors are grateful to B. Latter, R. Neil, S. Noël, D. L. Smith, P. Stammes, and W. von Hoyningen-Huene for a number of discussions related to the calibration issues of AATSR, MERIS, and SCIAMACHY.

retrievals from SCIAMACHY measurements.

Clearly, because ENVISAT is planned to be in operation at least till 2010, more calibration efforts for SCIAMACHY will be needed in future (e.g., using Moon as a light source for calibration). This new re-calibration may remove small -scale oscillations present in the latest version of the calibration curve given in Fig. 6.