Géraud Le Falher
email: geraud.le-falher@inria.fr

Aristides Gionis
email: aristides.gionis@aalto.fi

Michael Mathioudakis
email: michael.mathioudakis@hiit.fi

Where is the Soho of Rome? * Measures and algorithms for finding similar neighborhoods in cities

Data generated on location-aware social media provide rich information about the places (shopping malls, restaurants, cafés, etc) where citizens spend their time. That information can, in turn, be used to describe city neighborhoods in terms of the activity that takes place therein. For example, the data might reveal that citizens visit one neighborhood mainly for shopping, while another for its dining venues. In this paper, we present a methodology to analyze such data, describe neighborhoods in terms of the activity they host, and discover similar neighborhoods across cities.

Using millions of Foursquare check-ins from cities in Europe and the US, we conduct an extensive study on features and measures that can be used to quantify similarity of city neighborhoods. We find that the earth-mover's distance outperforms other candidate measures in finding similar neighborhoods. Subsequently, using the earth-mover's distance as our measure of choice, we address the issue of computational efficiency: given a neighborhood in one city, how to efficiently retrieve the k most similar neighborhoods in other cities. We propose a similarity-search strategy that yields significant speed improvement over the brute-force search, with minimal loss in accuracy. We conclude with a case study that compares neighborhoods of Paris to neighborhoods of other cities.

Introduction

More and more people live in cities. That fact raises the challenge of making decisions about how to live in an increasingly complex environment (e.g., what neighborhood to live in, or work in, or visit as a tourist). Yet the plethora of data gathered from social networks, smart sensors and mobile devices offers the opportunity to make informed decisions about these issues. In this paper, motivated by the challenge of understanding urban environments, and seizing the opportunities created by geo-enabled social data, we address the problem of comparing neighborhoods in different cities.

The problem we study has applications to recommending locations in a city. Imagine a traveler planning a trip in a new city and deciding the neighborhood in which to book a hotel room: the methods developed in this paper allow to match each neighborhood in the new city with the most similar neighborhood in the traveler's home city, or any other city that the traveler wishes to compare. Such a comparison makes the traveler's choice easier and more intuitive.

Our methods are also applicable in the analysis of cities and urban planning. For instance, when applied to the neighborhoods of one city, our techniques allow to identify neighborhoods that are similar to each other, and thus help us understand the activity that takes place in each area, what are the hubs of different activities, how citizens experience their city, and how they utilize its resources.

Our approach is briefly described as follows. Using geo-enabled data from social-media platforms, we represent each venue with a feature vector, that accurately describes the characteristics and the overall activity of the venue. We then devise similarity measures between venues, as well as between neighborhoods, i.e., sets of venues that are geographically close to each other.

We address these two problems from a metric-learning point of view [START_REF] Bellet | A survey on metric learning for feature vectors and structured data[END_REF]. We experiment with many different distance measures and with algorithms that aim to learn their parameters. To learn the parameters of the distance measures and select the optimal settings, we use ground-truth data, either present in the dataset or gathered from carefully-designed user studies.

The measure that is shown to perform best for the task of finding similar neighborhoods is the earth-mover's distance (EMD) [START_REF] Rubner | A metric for distributions with applications to image databases[END_REF]. EMD is known to be a robust measure-however, it is also expensive to compute. Motivated by this observation, we address the issue of computational efficiency. In particular, given a neighborhood R in one city, we ask how to find the k most similar neighborhood to R in another city (or a set of other cities) under EMD, and without performing brute force computation. We design a pruning strategy that yields significant speed improvement with minimal loss in accuracy.

Our study and our algorithms are based on extensive experimental evaluation in European and US cities, using activity logs gathered from Foursquare, a location-based social network. Yet our study can be enriched by many other types of data, such as transportation, weather, air quality, energy consumption, etc. Such an extension is left for future work. 2 Datasets

Our dataset consists of geo-tagged activity logs from Foursquare. Foursquareis a popular location-based social network that, as of 2015, claims more than 50 million users.1 It enables users to share their current location with friends, rate and review venues they visit, and read reviews of other users. Foursquare users share location information by generating "check-ins" using a dedicated mobile application2 . Each check-in is associated with a web page that contains information about the user, the venue, and other details of the visit. Each venue is also associated with a public web page that contains information about the venue-notably its category such as Food or Nightlife Spot-and aggregates information from user check-ins.

According to Foursquare's privacy policy, check-ins are private information. However, sometimes users opt to share their check-ins via Twitter, a popular micro-blogging platform. We were thus able to obtain Foursquare data by retrieving check-ins from Twitter, between March and July 2014. We focused on 10 US and 10 European cities, chosen for their high activity. In addition, we also used a previously released dataset [START_REF] Cheng | Exploring millions of footprints in location sharing services[END_REF], with Foursquare check-ins generated between September 2010 and January 2011 in these cities. In total, our Foursquare data consists of almost 3 million check-ins, even though none of them took place in August. Details can be found in Table 1, where we focus on the 6 cities on which we carry on our main experimental evaluation.

Exploration

We highlight some high-level patterns we observe in our dataset, as they guide our later choice of features used to describe venues.

First, we cluster the venues in each city by the temporal distribution of associated check-ins during a day. Specifically, for each venue in one city we calculate the fraction of check-ins that occur at different times of the day, using 4-hour-long windows -i.e.

1-5 5-9 9-13 13-17 13-21 21-1 1-5 5-9 9-13 13-17 13-21 21-1 1-5 5-9 9-13 13-17 13-21 21-1 1-5 5-9 9-13 13-17 13-21 21-1 1-5 5-9 9-13 13-17 13-21 21-1 the fraction of check-ins occurring from 1 am to 5 am, from 5 am to 9 am, and so on.

We then perform k-means clustering on the computed distributions for all venues of each city, using k = 5. Figure 1 shows the k = 5 identified centroids with a different color for each city. We observe five clearly-separated clusters of venues in all cities, with clear peaks of activity within a day, that are also remarkably consistent across all cities and thus motivate this choice of k.

Then, we explore the geographic distribution of venues within a city. We observe that venues are not uniformly distributed within the city and that the density of nearby locations is a discriminative feature as well. For instance in Figure 2, we can clearly distinguish venues belonging to the city center from the others.

Finally, we notice that venues differ in the diversity of people who visit them-some having a large number of infrequent visitors, and others a smaller number of dedicated visitors. To quantify the diversity of unique visitors for different venues, we use the measure of user entropy introduced by [START_REF] Cranshaw | Bridging the gap between physical location and online social networks[END_REF]. Intuitively, a higher value of entropy means that check-in activity is shared among a larger number of users. Computing this value for all venues in Paris and Barcelona shows that it is a good descriptor of the "publicness" of a place. Touristic attractions like Sagrada Família and Eiffel Tower exhibit high entropy because they are visited by a large and diverse set of people. On the other hand, work offices and private houses have low entropy.

Data model and problem setting

In this section we introduce the notation and the problem setting we will be working with in the rest of the paper. Cities and venues. We consider a set C of n cities, C = {C 1 , . . . , C n }. Each city contains a set of venues. A venue is a uniquely identified location that can be visited by individuals, like a restaurant, shop or park. We write V (C) to denote the set of venues of the city C ∈ C. We also use V to denote the set of all venues in all cities, i.e., V = C∈C V (C). The description of each venue v ∈ V contains a geographic location loc(v), expressed as a pair of latitude and longitude coordinates. Activities. We consider a set of activities A = {a 1 , . . . , a |A| }, each one corresponding to an instance of user behavior in the cities C. Each activity a j ∈ A is represented by a tuple a j = (type j , u j , loc j , t j , descr j ), where type j is the activity type, u j is a user-id, loc j and t j are the spatio-temporal coordinates of the activity, and descr j provides additional information depending on the type of activity.

Although this framework supports a variety of sources, in this initial study we focus on single type of activities, namely one Foursquare user checking in at a particular location and time. Such check ins are naturally associated with a single venue. Feature vectors. Given the set of activities A associated with venues in V, we extract 30 features and describe each venue v ∈ V with a feature vector f (v) that contains information about associated activities. The features include the total number of checkins at v, the number of unique users, entropy of the check-in distribution, number of likes, and number of visits/check-ins split down by day (weekday/Saturday/Sunday) and time of day (morning/noon/...). Additionally, since venues in a city are typically not considered in isolation, but location and context is very important, some features of the vector f (v) contain information about other venues around v, namely the distribution of the categories of venues around v. Specifically, the features involving the surrounding were computed from all others venues, weighted by a 2D Gaussian of arbitrary radius r = 350 meters. To make our data more reliable, we only consider venues with at least five check-ins by two different users. Comparing venues. Given two venues v i , v j ∈ V with feature vectors f i = f (v i ) and f j = f (v j ), the simplest distance one can define between the two venues is the p-norm between their feature vectors ||f i -f j || p . This simple definition has a number of shortcomings, as it does not account for (i) the different scale of individual features, (ii) different scale due to variations in the cities, (iii) importance of features, and (iv) potential correlations between features. One way to address the first two shortcomings is to ensure that each feature, aggregated at a city level, has mean equal to zero and standard deviation equal to one. To address the other two shortcomings, one well-motivated and principled approach is to consider the Mahalanobis distance

d W (v i , v j ) = ||f i -f j || W = (f i -f j ) T W (f i -f j ), ( 1
)
where W is the inverse of the covariance matrix of the features. Learning a more suitable matrix W , and thus the distance measure between venues, is the first challenge we face.

Objective 1 Learn the matrix W so that the distance measure d W captures best the human perception of similarity between venues.

We approach this problem as a metric-learning problem [START_REF] Bellet | A survey on metric learning for feature vectors and structured data[END_REF], where we learn the matrix W with different methods to maximize consistency with a ground-truth labeling in our data. City neighborhoods. Summarizing our discussion so far, each venue v ∈ V is described by the pair (loc(v), f (v)), where loc(v) and f (v) specify the location of the venue v, and its feature vector, respectively. Now, given a city C ∈ C, we define a neighborhood (or a region) R of the city C as a geographical region (a closed and connected set in the geographical plane). We abuse notation and we write

R ⊆ C to denote that R is a neighborhood of the city C. For a neighborhood R ⊆ C we define V (R) to be the set of venues of C that are contained in R, i.e., V (R) = {v ∈ V | loc(v) ∈ R}.
We also define F (R) to be the set of feature vectors of all the venues in R, that is,

F (R) = {f (v) | loc(v) ∈ R}.
Comparing neighborhoods. Our objective is to define a meaningful distance measure between city neighborhoods. We want two neighborhoods to be similar, if they contain the same kind of venues, and in the same proportion. Thus, given two neighborhoods R i and R j we consider the feature vectors F (R i ) and F (R j ) of the venues contained the two neighborhoods, and we define the distance δ(R i , R j ) between R i and R j by

δ(R i , R j ) = D(F (R i ), F (R j )), (2)
where D is a distance function between sets of feature vectors. Our second objective is stated as follows.

Objective 2 Choose a distance measure δ between city neighborhoods as expressed by Equation (2), i.e., a distance measure D between sets of feature vectors of the venues in the two neighborhoods. The distance measure should capture best the human perception of similarity between city neighborhoods.

In the next section we consider a number of different options for the distance function D, and we discuss our methodology for selecting the best one. Building on the optimal distance measure selected for our objective, we then consider the following city-neighborhood search problem.

Problem 1 We are given a neighborhood R in a city C ∈ C and a subset of target cities C ⊆ C. The goal is to find a small set of neighborhoods {R i } k i=1 in some city C ∈ C so that the distances δ(R, R i ) are minimized.

Two interesting special cases of Problem 1 are (i) C = C, search for the most similar neighborhood in all cities; and (ii) C = {C }, search for the most similar neighborhood in a given city C . The emphasis for Problem 1 is on computational efficiency, and the aim is to improve over brute-force search.

Measures and evaluation methodology

In this section, we describe methods to achieve the two objectives we set above.

Measures to compare venues

We consider the following approaches to compare venues in terms of their feature vectors:

ITML Information Theoretic Metric Learning (ITML) [START_REF] Davis | Information-theoretic metric learning[END_REF] is a metric-learning method that aims to learn the matrix W in Equation ( 1). Its input consists of the feature vectors of venues V , along with class labels. It learns a matrix W so that the following goals are achieved: (i) the distance between two feature vectors of the same class is less than a (low) threshold t low , (ii) the distance of vectors of different class exceeds a (high) threshold t high , and (iii) matrix W is as close to the identity matrix as possible (in order to provide regularization). The two thresholds, t low and t high , are set automatically to the 5 th and 95 th percentiles of all pairwise euclidean distances of the original feature vectors.

We use the category of venues provided by Foursquare3 as the class of each feature vector. To summarize, this method learns a matrix W that places venues of the same category in close distance of each other and venues of different categories at large distance from each other.

LMNN Large Margin Nearest Neighbor (LMNN) is also a metric-learning method that aims to learn matrix W in Equation (1). It accepts the same input as ITML (i.e. feature vectors of venues, classified according to their Foursquare categories), but unlike ITML, it optimizes an unconstrained cost function, defined so that, for the learned matrix W , feature vectors of the same class are as close as possible, while vectors of different class are as far as possible. In our study, we use Gradient Boosted LMNN, a state-of-the-art variant proposed by [START_REF] Kedem | Non-linear metric learning[END_REF].

t-SNE This method embeds feature vectors to a 2-d plane via t-distributed stochastic neighbor embedding (t-SNE), a state-of-the-art dimensionality-reduction method [START_REF] Maaten | Visualizing data using t-SNE[END_REF], and computes the Euclidean distance on the projected space Euclidean Finally, we consider the Euclidean distance in the original space. Note, again, that feature values have been centered and normalized, so that each feature has zero mean and standard deviation equal to one at a city level.

Measures to compare neighborhoods

We proceed with addressing Objective 2, that is, selecting a distance measure between sets of feature vectors, in order to evaluate similarity between city neighborhoods. We consider the following options. 1. Earth mover's distance. EMD is a standard distance for vector sets that measures the total amount of work needed to transform (move) one vector set (total mass) to the other [START_REF] Rubner | A metric for distributions with applications to image databases[END_REF]. In our case, we have two neighborhoods X and Y made of feature vectors X = {x i } n i=1 and Y = {y j } m j=1 . Assuming the distance between two vectors x i and y j is defined by an underlying metric as d i,j , the distance between X and Y is the solution f of a bipartite flow problem formalized by this linear program:

min f i,j d i,j f i,j subject to j f i,j = w xi i f i,j = w yj i,j f i,j = i w xi = j w yj = 1
Each vector is assigned a weight (their sum being 1 in each neighborhood) and f i,j represents the amount of mass we bring from x i to y j The constraints express the requirement to move all the mass from one side to the other while minimizing the total work needed to move it. We find experimentally that uniform weighting gives more accurate results. We experiment with the following variants of EMD: (i) using as the underlying metric the distance learned with ITML (EMD-ITML); (ii) using as the underlying metric the distance learned with LMNN (EMD-LMNN); (iii) using t-SNE as the underlying metric (EMD-t-SNE); (iv) using as the underlying metric the Euclidean distance (EMD-Eucl); (v) using as the underlying metric the Euclidean distance and requiring only a certain fraction of the smaller feature vector set (F (X) or F (Y )) to be matched (EMD-Partial). The rationale of EMD-Partial is to provide more flexibility by allowing for two neighborhoods to have a fraction of venues that are completely different. For the fraction of vectors to match, we used 80% in our experiments. 2. Jensen-Shannon divergence. JSD is a symmetrized and smoothed version of the Kullback-Leibler divergence, a function for measuring distance between distributions. JSD can be computed for multivariate distributions, however, in our setting we have a relatively small number of samples (a typical neighborhood contains around 100 venues, and never more than 700) and a high dimensions (30) so we cannot estimate an accurate joint probability distribution. To account for this problem, we opt for computing the JSD independently for each feature. In particular, we compute JSD 1 (F (i) , G (i) ), where JSD 1 is univariate JSD, while F (i) and G (i) are the distributions of the i-th feature for the vector sets F and G, respectively. We then aggregate over all features by

JSD(F, G) = i θ i • JSD 1 (F (i) , G (i) ), (3)
with i |θ i | = 1. To calibrate θ i , we sample different neighborhoods and label each pair of neighborhoods as "similar" or "not similar." The labeling of the neighborhoods is based on our ground-truth, which we describe shortly. We then compute θ i to maximize the sum of the JSD values over similar pairs minus the sum of JSD values over non similar pairs. 3. Minimum cost matching distance of set centroids. A very simple way to compute a distance between two sets of feature vectors is to compute the centroid of each set and then compute the distance between the two centroids. We extend this simple definition with k centroids. Given a set of feature vectors we perform k-means clustering, and represent the set with k centroids. Then, given two sets of feature vectors, and their corresponding k-set centroids, we compute the distance of a min-cost matching, using the Hungarian algorithms [START_REF] Munkres | Algorithms for the Assignment and Transportation Problems[END_REF]. We experiment with different values of k and report the best results, obtained for k = 3.

Evaluation methodology. We now describe our evaluation process for selecting the best function for measuring distance over feature vector sets. Consider a neighborhood R in a source city C, and a target city C . Assume that we have obtained k ground-truth neighborhoods R 1 , . . . , R k in C , which are the most similar to R. For example, if R is a neighborhood with many offices, companies, and financial services in C, so are neighborhoods R 1 , . . . , R k in C . Given a distance measure δ we want to evaluate, we can then compute the distance δ(F (R), F (R )) for each possible neighborhood R of C and rank all those neighborhoods in order of increasing distance. We can evaluate the quality of this ranking by checking the position that the ground-truth neighborhoods R 1 , . . . , R k appear in the ranking-if appearing at all. The higher we find a match, the better the ranking, and thus, the better the distance measure δ.

Since we do not have any a-priori neighborhood boundaries (and in fact we do not want to use any, since a neighborhood may be defined in a dynamic way, different than what administrative boundaries would give), any subset of venues that corresponds to a closed and connected region is a candidate neighborhood. As there are exponentially many such subsets, we restrict our search to regions of a certain shape. We consider neighborhoods R to be circles (v , r), centered at a venue v and with radius r. We take as v regularly spaced venues in C and r ∈ {200, 275, 350, 425, 500} meters, with the additional constraint that the resulting circle should contain at least 20 venues.

After ranking all possible such circular neighborhoods R in order of increasing distance δ(F (R), F (R )) we remove overlapping neighborhoods (in an Eratosthenessieve way) so that the resulting ranking does not contain overlapping neighborhoods.

To evaluate the resulting ranking, we need a relevance score for each neighborhood R in the ranking with respect to the ground-truth neighborhoods R 1 , . . . , R k . Note that R may not be identical to any of the ground-truth neighborhoods (for one, R is circular, while the ground-truth neighborhoods can have arbitrary shapes) but there may have significant overlap with some of them. To account for such overlap, we define the relevance of each R as the best overlap of R with a ground-truth neighborhood R 1 , . . . , R k , where the overlap is measured using the Jaccard coefficient on the sets of venues of two neighborhoods.

rel(R | R 1 , . . . , R k ) = k max i=1 |V (R ) ∩ V (R i )| |V (R ) ∪ V (R i )| ,
Having assigned a relevance score for each neighborhood R in the ranking, we evaluate the quality of the ranking using discounted cumulative gain (DCG) [START_REF] Sakai | On the reliability of information retrieval metrics based on graded relevance[END_REF]. The gain is a measure of relevance and we accumulate them (or sum them) but discount results that came too far in the ranking according to

DCG = i=1 2 rel(Ri) -1 log 2 (i + 1)
.

Evaluation results. To perform the evaluation described above we need ground-truth information regarding neighborhoods in cities. Since ground truth requires concrete knowledge of a city, we conducted a user study. Our study involved six cities: Barcelona, New York, Paris, Rome, San Francisco, and Washington DC. The participants in the study are international friends and colleagues of ours, who have lived for many years in at least one of those cities. The participants were given textual description of neighborhoods and were asked to mark some neighborhoods in their own city that matched best that description. The descriptions are shown in Table 2. The table also shows matching neighborhoods for Paris, as chosen by the first author of this paper who happens to have lived in that city. The participants provided their answers via a graphical interface. 4 The answers were curated, so that if more than one person provided answers for one city, the answers were merged. To give a better sense of the typical size and shape of these neighborhoods, we present in Figure 3 three of them in Paris and in Barcelona.

Starting with each of the 6 cities as a source city and for each of the 8 query neighborhoods, we compute the most similar neighborhoods in all other cities, using each of the distance measures that we want to evaluate. 5 The results are shown in Table 3. Each row corresponds to a source city. DCG scores are averaged over all target cities and all 8 query neighborhoods.

We see that EMD-Eucl is the best-performing measure, while JSD and EMD-t-SNE perform rather poorly. EMD-LMNN performs only slightly worse than EMD-Eucl. Another observation is that the absolute DCG scores of all measures are relatively low. One reason for the low scores is that many neighborhoods in the ground truth have non-circular shapes (e.g., a long street of luxurious shops). Thus, even if our measures discover an area very close to the ground truth, due to its circular shape it can have low overlap with the ground truth, and low relevance score.

Searching for similar neighborhoods efficiently

We now turn our attention to the efficiency aspects of the neighborhood similaritysearch problem, i.e., the Problem 1 defined in page 7. Following our evaluation from the previous section, we focus on the EMD distance. The brute-force approach to solve this problem is an exhaustive search algorithm, as the one used above for the evaluation of neighborhood distance measures. Namely, given neighborhood R, consider all candidate neighborhoods R of a certain shape (circle, rectangle, or other) in the target city C , evaluate the distance EMD(F (R), F (R )), and return the neighborhood that achieves the smallest distance. In this section, we show how to speedup the search task significantly, with very little loss in accuracy. Our solution relies on the following observation: the EMD between two sets of feature vectors F (R) = F and F (R ) = F is zero, if all feature vectors in F and F coincide. Relaxing this condition, the EMD is small, if for many vectors in F there is some near vector in F . Put differently, when one feature vector in F is far away from all vectors in F , it contributes a large cost to EMD.

Therefore we can reduce the search space by preprocessing all venues in the target city and keeping only those venues whose feature vectors are close to feature vectors of venues in the query neighborhood. The venues kept in this preprocessing step can be used as anchors. We can then look for areas in the target city that are dense in anchor venues, and group them in candidate neighborhoods, for which we calculate the actual EMD.

To see how this idea works, consider Figure 4, where we search in Barcelona to find the neighborhood that is most similar to Pigalle (Paris). Each row in the figure corresponds to one venue v in Pigalle, and contains the ranking of all venues in Barcelona sorted by distance to v. There is a cross (x) in i-th position of the ranking if the i-th ranked venue in Barcelona belongs to the ground truth neighborhood (in this case, el Raval, which we know from our user study). We see that if we restrict ourselves to the 100 nearest neighbors of each venue in the query neighborhood, we recover most of the venues in the ground-truth neighborhood.

Our algorithm works as follows. Starting from the query neighborhood R and target city C (or cities), we obtain the set of k-nearest neighbors N k (v) ⊆ V (C ) for each venue v ∈ V (R). All venues found in at least one k-NN set form the set of anchor venues V A = v∈V (R) N k (v). The set of anchor venues V A is then treated with respect to its geographic coordinates: the dbscan algorithm is applied and areas with low density in anchor venues are discarded. dbscan also produces a clustering of venues, which are treated as candidate neighborhoods. For the candidate neighborhoods the exact EMD is computed. If a candidate neighborhood is too large, the exact EMD is computed for sliding subareas. Finally, to account for misses that may happen during the pruning phase, each area considered is extended by adding to its radius a distance of j × 50 meters, j = 0, . . . , , and the extended area is also treated as a candidate neighborhood. In the end of the process, the algorithm returns the the neighborhood with the smallest distance (or top-m smallest distances).

The two parameters of the algorithm, k and , offer an accuracy vs. efficiency tradeoff. Our experiments in the next Section , as detailed in Section 6, suggest that the algorithm produces very accurate results even for small values of the parameters (which also give the highest efficiency). With respect to k, we found that in our data, k = 50 works very well, as in most cases, this value returns around 50% of the venues in the ground truth, while covering only 33% of the city. With respect to , even = 0 (no extension) works quite well. While the robustness of EMD (and more generally optimal transport based distance) has recently lead to active research about speeding up their computation (e.g. [START_REF] Pele | Fast and robust Earth Mover's Distances[END_REF][START_REF] Cuturi | Sinkhorn Distances: Lightspeed Computation of Optimal Transport[END_REF][START_REF] Tang | Earth mover's distance based similarity search at scale[END_REF], we find that our simple filtering approach is more than adequate for our purposes.

Scalability experiments

In this section we quantify how well our proposed method approximates a bruteforce EMD search. We conduct our performance evaluation on the 203 query triplets (C, R, C ) that were used in the analysis shown in Table 3.

For each of these queries, we execute the brute-force search ; namely, we compute the EMD for all circles (v , r) centered at a venue v of C and with radius r ∈ {200, 275, 350, 425, 500} meters. We also execute the neighborhood similarity-search algorithm, described in the previous section. We compare these two methods in terms of execution time and quality of solution found. In particular, given a query triple (C, R, C ) let R BF be the most similar neighborhood found by the brute force and let R A be the most similar neighborhood found by the approximation method. Let the corresponding closest distances be D BF = EMD(F (R), F (R BF )) and D A = EMD(F (R), F (R A )), respectively. We define the relative distance ρ for that query as

ρ = D A D BF (4)
The smaller is ρ, the better the approximation. We would in fact expect that ρ is greater than 1, as values less than 1 indicate that the approximation method is better than the brute force. However, as the brute force is constrained to circular neighborhoods, it is possible that the approximation method finds better solutions. Removing this constraint from the brute force implies searching over other shape families (rectangles, diamonds, etc.), which will increase its running time even more. Overall, our results show that for the range of parameters we experiment with, the approximation method is much faster than the brute force-in most cases by at least one order of magnitude, while often by two or even three. At the same time the relative distance is very close to 1, often below 1, and rarely above 1.5.

In more detail, we first analyze the effect of , the number of times we extend the initial regions found after clustering, while using k = 50. As increases, more EMD computations are required, but the chances to find a more similar region increase. Indeed, as we see in Figure 5a, the relative distance decreases as increases, while the computation becomes more expensive (Figure 5b). We also note that after = 1, the gain is small, suggesting that the initial regions are already relevant enough.

We perform the same experiment for k ∈ {8, 25, 50, 80, 160} with = 1. As shown in Table 4, the relative distance is very small for all values of k, showing the robustness of the method. At the same time, k does not affect much the running time of the algorithm (results not shown), as the bottleneck is the computation of EMD.

Empirical Study

A natural way to assess our method is to compare its results with randomly selected neighborhoods. In this section, we employ our approximate search algorithm to find matching neighborhoods between cities, compare them with randomly selected ones, and report indicative results.

Specifically, we run approximate search on the 203 query triplets (C, R, C ) that were used to generate Table 3. For each query triplet, we retrieve the list of top k = 5 neighborhoods returned by approximate search, order them by distance to the query neighborhood, and measure their overlap with the ground-truth neighborhoods in target city C . Moreover, for each query triplet, we generate 2000 lists of randomly selected and ordered neighborhoods in C , each of size k = 5. To produce a random list of k = 5 neighborhoods, we first sample a venue from city C , and then select a neighborhood around it of size approximately equal to the query neighborhood, repeating the process k = 5 times.

Subsequently, we measure the overlap of each result list with the corresponding ground-truth neighborhoods in the target city. To measure overlap, we again use the DCG score of result lists against the ground-truth regions.

In Table 5, we report the percentile at which our method's DCG score ranks compared to the random neighborhoods. Higher percentile means that our result lists have higher overlap with ground-truth than more random neighborhoods. In most cases, it performs significantly better than random. Even when we miss completely the ground truth (entries marked with grey font), the same happens with a large fraction or even the majority of the 2000 random lists -which means that the ground truth is intrinsically difficult to recover because of its size or location in the city.

Examples To illustrate the results produced by our method, we present examples of findings, produced by the best-performing measure, EMD-Eucl.

For the first example, we select Bethesda as our query neighborhood. Its location is shown in Figure 6-left . Bethesda is a neighborhood in Washington D.C. and was identified in our user-study as a neighborhood with 'expensive residences' (Table 2). Subsequently, we ask to find the most similar neighborhoods in New York City. The most similar neighborhoods suggested by our method are shown in blue in Figure 6-right ( ), and they coincide with lower-and upper-east-side Manhattan. Note that eastside Manhattan was identified in our user study as the neighborhood with 'expensive residences' ( ), which indeed is an area of high-cost apartments. This is especially encouraging since our Foursquare data does not include any information about price.

For the second example, we submit two queries. As a first query, we select Montmartre, the "touristic and artsy" neighborhood of Paris, famous for the Basilica of the Sacred Heart, which sits on top of the highest point in the city and thus offer a stunning view to million of tourists. Many artists have worked here, such as Monet, van Gogh, Picasso, and Dalí, which matches its bohemian atmosphere. As a second query, we pick the La Ribera district in Barcelona, identified as a "touristic and artsy" in our user study. Indeed, it is a popular place for expats and home to many art boutiques. Subsequently, we ask for the most similar neighborhood in Rome. The most similar neighborhood is Trastevere and is shown in Figure 7. Indeed it is a neighborhood in Rome that is known to match the description of 'touristic and artsy' neighborhood. Furthermore, we observe that besides Trastevere, both queries returned the same areas of Rome, a good indication that the aforementioned neighborhoods share similar features.

Figure 7: Top: the neighborhood query in Barcelona (La Ribera). Bottom: the results in Rome match the ground truth (in orange), both from Barcelona (green) and Paris (blue, the query is showed in blue in Figure 3). Closer to our work, [START_REF] Cranshaw | The livehoods project: Utilizing social media to understand the dynamics of a city[END_REF] analyze 18 million Foursquare check-ins to find so-called livehoods.6 They build a spatial neighbor graph between venues, where edges are weighted by the cosine similarity of the user distribution of two venues, and then perform spectral clustering. Faced with the same difficulty as ours to evaluate their results, they interview residents of Pittsburgh who validate the resulting subdivisions. Another approach was proposed by [START_REF] Zhang | Hoodsquare: Modeling and recommending neighborhoods in location-based social networks[END_REF], also based on Foursquare check-ins. Each venue is assigned a category, a peak activity time, and a binary label: touristic or not. The venues are then clustered along these features, and the city is divided into a regular grid, where grid cells are described by their feature density. Similar cells are then clustered into neighborhoods. With respect to the last two papers, our work makes a number of advances: different notions of similarity between neighborhoods are defined and evaluated, the problem of finding similar neighborhoods in other cities is considered, and the scalability of the search problem is addressed.

In addition to the analysis of static data like check-ins, another line of work takes advantage of dynamic data, such as trajectories. For instance, [START_REF] Giannotti | Unveiling the complexity of human mobility by querying and mining massive trajectory data[END_REF] analyze GPS data in Italian cities to find temporal patterns, which can then be used for detect events or regulate traffic jams. Similarly, [START_REF] Cao | Mining significant semantic locations from GPS data[END_REF] extract "stay points" from car GPS data and assess the significance of each point by the number of visitors, time taken to reach there, and duration of stay. [START_REF] Uddin | Finding regions of interest from trajectory data[END_REF] develop efficient methods to address closely-related tasks. Once the semantics of locations is known, it is still challenging to find frequent patterns efficiently [START_REF] Zhang | Splitter: Mining fine-grained sequential patterns in semantic trajectories[END_REF].

The problem of identifying and characterizing neighborhoods has also been addressed by companies. For instance, research in Flickr has shown that by computing the α-shape of a set of tagged photos, it is possible to recover neighborhood boundaries;7 we remind that the α-shape is a generalization of the convex hull [START_REF] Edelsbrunner | On the shape of a set of points in the plane[END_REF]. Likewise, Airbnb, a social lodging renting website, has recently produced a ranking of cities by hospitality 8 , as well as data-driven characterization of neighborhoods. 9 However, the methods and details for these commercial systems are not publicly available.

Finally we note that our setting is tangentially related to work on spatio-temporal topic modeling. In this line of work, [START_REF] Yin | Geographical topic discovery and comparison[END_REF] address the problem of finding k localized topics and n Gaussian spatial regions. They develop and apply a latent geographical topic analysis framework: each region has a topic distribution and each topic is a multinomial distribution over all possible photos tags. By taking into account user information, such an approach can be used to provide recommendations [START_REF] Kurashima | Geo topic model: Joint modeling of user's activity area and interests for location recommendation[END_REF]. Similar ideas can be applied to finding localized tweets with a hierarchical topic model [START_REF] Ahmed | Hierarchical geographical modeling of user locations from social media posts[END_REF]. The main difference between these works and ours is that they focus on discovering salient regions rather than comparing them with each other. Going beyond words, [START_REF] Doersch | What makes paris look like paris?[END_REF] discover frequent and discriminative patches from Google Street images and use them, among other applications, to retrieve similar buildings across cities.

Conclusion

In this paper, we studied the problem of matching neighborhoods across cities using Foursquare data and considered various measures for their comparison. Evaluating against ground truth data, we found that EMD performs best and presented a method to enhance its running time with minimal loss of accuracy. Finally we illustrated the quality of results obtained by anecdotal evidence.

Although these results are encouraging, they could be extended in various directions:

• Use more data sources to derive more features (for instance photos sharing website, transportation, weather, air quality, energy consumption, demographics, etc).

• Match several (or all) neighborhoods at the same time (but without excessive overlapping) and thus obtain a similarity measure between whole cities.

• Provide a justification for the neighborhoods selected by the algorithms. For instance, design algorithms that provide explanations of the type "These two regions match because people take a lot of photos, go there on weekday from 4pm to 8pm and there are a lot cultural buildings." Another source of information is the resulting flow of EMD: looking at what kind of venues are close to what, and obtain insights from those matches.

Figure 1 :

 1 Figure 1: Results of k-means with k = 5 on the 4-hour-window check-in distribution of venues. Each line in each figure is the centroid of a cluster in a city. We observe that the centroids of the five clusters are almost identical in all cities.

Figure 2 :

 2 Figure 2: Venue density in Paris, computed by a Gaussian kernel.

Figure 3 :

 3 Figure 3: Three neighborhoods selected in Paris (top) and the corresponding annotations from Barcelona (bottom) experts: 16 th arrondissement Montmartre , and Official . The black dots on each map represent the venues of our dataset.

Figure 4 :

 4 Figure 4: Intuition behind our pruning strategy: for two neighborhoods with small EMD, the venues of one neighborhood are in the k-NN set of the venues of the other.

  Box plot of ρ defined in Equation 4 as varies. Values smaller than 1 indicate that the approximation method finds a neighborhood with smaller distance than the brute force. Time speed-up for each query, in descending order. Original brute force searches take between 19 and 2129 seconds. Note the logarithmic scale.

Figure 5 :

 5 Figure 5: Approximation performance.

Figure 6 :

 6 Figure 6: A query in Washington and its result in New-York.

Table 1 :

 1 Number of check-ins and venues per city.

	City	2010 Check-ins 2014 Check-ins Venues
	New York	408 584	369 562	67 363
	San Francisco	104 363	77 294	15 580
	Washington	75 984	80 274	13 168
	Paris	32 952	67 382	17 231
	Barcelona	21 448	44 462	11 351
	Rome	9 364	24 128	7 691
	14 others	643 810	988 671 206 285
	Total	1 296 505	1 651 773 338 669

Table 2 :

 2 Neighborhood description used in user study and corresponding Paris neighborhoods. Participants in the study were asked to identify up to 5 most similar districts in their own city.

	1 Fashion shops, luxurious places	Golden triangle
	2 College & student neighborhood Quartier Latin
	3 Red light district	Pigalle
	4 Touristic and artsy district	Montmartre
	5 Government buildings	Official
	6 LGBT neighborhood	Le Marais
	7 Expensive residences	16 th arrondissement
	8 Parks & leisure	The banks of Seine

Table 3 :

 3 Average score of each metric from a given city. The best metric in each city is highlighted and the last row is the average score over all cities.

	Query	Min cost EMD-EMD-EMD-EMD-JSD EMD-
	Source	matching Eucl LMNN ITML t-SNE	Partial
	Barcelona	.083	.078 .084 .033 .028 .042	.078
	New York	.059	.059 .059 .049 .026 .057	.053
	Paris	.061	.091 .078	.021 .044 .045	.061
	Rome	.024	.042	.039 .055 .038 .021	.029
	San Franc.	.045	.045	.040 .060 .042 .033	.044
	Wash. DC	.043	.034	.038	.035 .026 .033	.038
	Average	.052	.058 .056	.042 .033 .038 .051

Table 4 :

 4 First, second and third quantile of relative distance as k varies.

	k	8	25	50	80	160
	1 0.942 0.940 0.942 0.946 0.944
	2 1.003 0.998 0.994 0.994 0.986
	3 1.093 1.070 1.059 1.067 1.061

Table 5 :

 5 Percentile rank of the result obtained by our method compared with those obtained by chance. Rows refer to the neighborhood types described in target city, abbreviated as follow BR: Barcelona, NY: New York, PR: Paris, RO: Rome, SF: San Francisco and WS: Washington. For instance, the top-left number means that if we look in Barcelona for an area that is similar to the one chosen in New York by our expert to match the "luxurious shops" description, our method's result overlap more with the ground truth than 68.7% of the random samples. "-" denote queries not run due to lack of suitable ground truth. When our result has no overlap at all (in grey), the percentages indicate the fraction of random samples that fail likewise, even though our result is not better.Our work lies within the scope of urban computing, an area of increasing interest. In one line of work, the concentration of social online activity is used to determine interesting geographic regions of cities. For instance,[START_REF] Deng | Conceptualization of place via spatial clustering and co-occurrence analysis[END_REF] use dbscan to cluster Flickr photos, and they exploit tag co-occurrence to characterize the discovered clusters.[START_REF] Rattenbury | Methods for extracting place semantics from Flickr tags[END_REF] also employ spatial methods to discover hotspot regions in San Francisco where certain photo tags appear in burst. Moreover,[START_REF] Wakamiya | Crowd-sourced cartography: Measuring sociocognitive distance for urban areas based on crowd's movement[END_REF] used geolocated data from Twitter to detect sentiment and movement and draw a socio-cognitive map of the Kinki region in Japan.

	neighborhood	Barcelona	New York	Paris
	fashion shops NY PR RO SF WS BC PR RO SF WS BC NY RO SF WS
	& luxury	68.7 89.4 73.2 100.0 53.8 70.1 70.1 70.1 70.1 70.1 98.1 60.0 85.6 93.5 82.8
	colleges	NY PR RO SF WS BC PR RO SF WS BC NY RO SF WS
	& students	45.8 45.8 45.8 -71.7 79.5 94.2 45.9 -45.9 81.8 84.5 81.8 -81.8
	red light	NY PR RO SF WS -91.6 -85.6 69.0	no ground truth for this query	BC NY RO SF WS 93.7 --93.5 78.0
	touristic	NY PR RO SF WS BC PR RO SF WS BC NY RO SF WS
	& artsy	32.4 91.1 13.9 75.1 91.0 90.3 87.9 49.2 49.2 49.2 81.2 81.2 81.2 81.2 81.2
	government	NY PR RO SF WS BC PR RO SF WS BC NY RO SF WS 49.5 99.7 78.8 51.9 99.6 87.2 87.2 87.2 95.0 87.2 74.1 74.1 74.1 77.5 74.1
	LGBT	NY PR RO SF WS BC PR RO SF WS BC NY RO SF WS 75.1 84.0 -79.8 66.1 77.0 95.0 -50.7 60.7 36.9 55.6 -56.8 86.1
	expensive	NY PR RO SF WS BC PR RO SF WS BC NY RO SF WS
	residences	96.2 36.8 8.7 8.7 99.7 95.2 72.8 72.8 72.8 99.8 87.9 87.9 95.6 97.2 87.9
	leisure	NY PR RO SF WS BC PR RO SF WS BC NY RO SF WS 95.2 98.8 95.2 96.4 --81.3 98.2 81.3 --99.6 99.6 99.6 -
	neighborhood	Rome	San Francisco	Washington
	fashion shops BC NY PR SF WS BC NY PR RO WS BC NY PR RO SF
	& luxury	100.0 97.2 99.1 99.2 89.6 78.2 40.5 91.6 58.0 48.7 91.8 95.1 91.8 91.8 91.8
	colleges	BC NY PR SF WS BC NY PR RO WS BC NY PR RO SF
	& students	28.0 28.0 28.0 -28.0 95.6 95.6 95.6 95.6 95.6 39.0 -95.5 50.9 -
	red light	no ground truth for this query	BC NY PR RO WS BC NY PR RO SF 92.2 -95.0 -36.9 51.2 -51.2 -51.2
	touristic	BC NY PR SF WS BC NY PR RO WS BC NY PR RO SF
		83.3 0.4 90.0 70.5 87.6 8.9 9.9 8.9 8.9 74.8 58.9 95.3 89.3 99.5 47.9
	government	BC NY PR SF WS BC NY PR RO WS BC NY PR RO SF 1.1 4.5 11.5 5.9 11.7 73.2 -95.0 73.2 92.5 83.2 -97.0 62.6 46.1
	LGBT	BC NY PR SF WS BC NY PR RO WS BC NY PR RO SF 90.5 90.5 90.5 90.5 90.5 96.9 93.4 76.5 -76.5 88.3 78.6 86.5 -57.6
	expensive	BC NY PR SF WS BC NY PR RO WS BC NY PR RO SF
	residences	82.7 77.3 77.3 77.3 84.2 68.2 68.2 68.2 68.2 73.7 67.3 66.4 73.9 67.0 66.4
	leisure	BC NY PR SF WS BC NY PR RO WS BC NY PR RO SF -50.9 50.9 50.9 --86.5 88.9 86.5 --98.2 98.2 98.2 98.2

According to http://foursquare.com/about.

The Swarm application, http://www.swarmapp.com.

We use the top level of Foursquare's category hierarchy.

http://where-would-you.herokuapp.com/

Note that we experiment with 203 queries instead of

× (6 -1) × 8 = 240, as in a couple of cases (pairs of city -neighborhood description) our study did not yield a ground-truth neighborhood with enough venues inside.

http://livehoods.org/

http://code.flickr.net/2008/10/30/the-shape-of-alpha

http://nerds.airbnb.com/most-hospitable-cities

http://airbnb.com/locations


Isaac Sackey
email: isaac.sackey@hhi-extern.fraunhofer.de

Francesco Da Ros

Member, IEEE Johannes Karl Fischer

Student Member, IEEE Thomas Richter

Mahmoud Jazayerifar

Christophe Peucheret

Fellow, IEEE Klaus Petermann

Colja Schubert

Francesco Da

Kerr Nonlinearity Mitigation: Mid

Keywords: Link Spectral Inversion Versus Digital Backpropagation in 5x28-GBd PDM 16-QAM Signal Transmission Coherent detection, fiber nonlinearity, optical phase conjugation (OPC), quadrature amplitude modulation (QAM), wavelength-division multiplexing (WDM), digital backpropagation (DBP), optical fiber communication. I

come   L'archive ouverte pluridisciplinaire

multiplexing (DWDM) systems, and signal launch powers are increased in order to achieve a guaranteed optical signal-to-noise ratio (OSNR) at the receiver [START_REF] Winzer | Generation and 1200-km transmission of 448-Gb/s ETDM 56-Gbaud PDM 16-QAM using a single I/Q Modulator[END_REF], [START_REF] Essiambre | Capacity limits of optical fiber networks[END_REF]. However, power-dependent nonlinear distortion from the Kerr nonlinearity in the transmission fiber including intra-and inter-channel crosstalk and self-phase modulation degrades the transmitted signal and therefore decreases the transmission reach. It has been reported that higher-order modulation formats are more prone to Kerr nonlinearity distortions and are severely degraded in tightly packed channels [START_REF] Behrens | Nonlinear distortion in transmission of higher order modulation formats[END_REF]. Therefore advanced modulation formats (e.g. [START_REF] Ip | Compensation of dispersion and nonlinear impairments using digital backpropagation[END_REF]-quadrature amplitude modulation, 16-QAM) withstand shorter distance transmission with acceptable degradation compared to less spectrally efficient formats. Moreover, modulation formats with higher symbol rates are easily affected by dispersion-induced distortion, which can interact with nonlinear effects even over short fiber lengths.

In view of these, recent years have witnessed consistent and progressive research studies with the aim to mitigate both chromatic dispersion and Kerr nonlinear distortions in optical communication systems. Some of the reported distortion compensation schemes include digital back propagation (DBP) [START_REF] Ip | Nonlinearity compensation using backpropagation for polarization-multiplexed transmission[END_REF][START_REF] Napoli | Reduced complexity digital back-propagation methods for optical communication systems[END_REF][START_REF] Du | Efficient digital backpropagation for PDM-CO-OFDM optical transmission systems[END_REF], optical phase conjugation (OPC) [START_REF] Jansen | Long-haul DWDM transmission systems employing optical phase conjugation[END_REF][START_REF] Hu | Fiber nonlinearity compensation of an 8-channel WDM PDM-QPSK signal using multiple phase conjugations[END_REF][START_REF] Morshed | Improving performance of optical conjugation by splitting the nonlinear element[END_REF][START_REF] Da Ros | Kerr nonlinearity compensation in a 5x28-GBd PDM 16-QAM WDM system using fiber-based optical phase conjugation[END_REF][START_REF] Watanabe | Exact compensation for both chromatic dispersion and Kerr effect in a transmission fiber using optical phase conjugation[END_REF], all-optical coherent superposition using phase-sensitive amplification [START_REF] Olsson | Linear and nonlinear transmission of 16-QAM Over 105 km phase-sensitive amplified link[END_REF] and the so called "phase-conjugated twin waves" scheme [START_REF] Chen | Experimental demonstration of fiber nonlinearity mitigation using digital phase conjugation[END_REF][START_REF] Liu | Fiber-nonlinearity-tolerant superchannel transmission via nonlinear noise squeezing and generalized phase-conjugated twin waves[END_REF][START_REF] Tian | Demonstration of digital phase-sensitive boosting to extend signal reach for long-haul WDM systems using optical phase-conjugated copy[END_REF].

The DBP algorithm relies on inverting the distortions caused by chromatic dispersion and Kerr nonlinearities digitally by the propagation of the received signal through a virtual link characterized by opposite dispersion and nonlinear coefficient with respect to the fiber link. DBP has been shown to be effective for Kerr nonlinearity mitigation especially for single-channel systems. Due to the computational complexity [START_REF] Ip | Compensation of dispersion and nonlinear impairments using digital backpropagation[END_REF], current research is focused on reduced complexity approaches [START_REF] Napoli | Reduced complexity digital back-propagation methods for optical communication systems[END_REF] as well as on novel methods for digital mitigation of inter-channel nonlinear impairments [START_REF] Liga | On the performance of multichannel digital backpropagation in high-capacity long-haul optical transmission[END_REF], [START_REF] Shtaif | Nonlinear interference noise in WDM systems and approaches for its cancelation[END_REF].

Alternatively, an OPC-based technique provides compensation through mid-link spectral inversion (MLSI). In this scheme, a conjugate of the propagating signal is created at the middle of the transmission link. Propagating the conjugated signal for the remaining half of the link cancels out chromatic dispersion and fiber nonlinear distortions that have been accumulated in the first half of the link.

In [START_REF] Sackey | Kerr nonlinearity mitigation in 5x28-GBd PDM 16-QAM signal transmission over a dispersion-uncompensated link with backward-pumped distributed Raman amplification[END_REF], we experimentally demonstrated the implementation of the MLSI scheme for chromatic and nonlinear distortions cancellation for 50-GHz spaced channels with 5×28-GBd PDM 16-QAM signals in a 400-km dispersion-uncompensated standard single-mode fiber (SSMF) link with backward-pumped distributed Raman pumps. A numerical model using VPItransmissionMaker v8.7 was employed to predict possible transmission reach of up to 2800 km using parameters which have been derived from the experiment.

As both MLSI and DBP are promising techniques, a direct comparison between the two schemes for higher order modulation format is of high interest. Such a comparison has so far only been performed numerically for dispersion-unmanaged SSMF links and non-zero dispersion-shifted fiber (NZ-DSF) links, as well as for a dispersion-managed NZ-DSF link [START_REF] Rafique | Nonlinearity compensation in multi-rate 28 Gbaud WDM systems employing optical and digital techniques under diverse link configurations[END_REF].

In this work, we extend our experimental investigations of Kerr nonlinearity mitigation using MLSI and compare the results with DBP for up to 800-km transmission in a dispersion-managed link employing super-large area (SLA) fiber and inverse dispersion-shifted fiber (IDF) with erbium-doped fiber amplifiers (EDFAs). A dual-pump polarization-independent fiber-based optical parametric amplifier (FOPA) is used as OPC device to provide mid-link spectral inversion of 5×28-GBd PDM 16-QAM signals with 50-GHz spacing. Note that the generated conjugate signal copies in the FOPA are known as idlers. Alternatively, a split-step Fourier method (SSFM) DBP algorithm is employed for the mitigation of the fiber nonlinearities and the Q-factor (obtained from the BER) performance of the two compensation schemes is compared. In this comparison, the standard DBP based on SSFM serves as a reference benchmark for the compensation of intra-channel nonlinear impairments. Both compensation methods outperform direct transmission. However, while the DBP approach provides a better improvement for a single-channel scenario, OPC outperforms the SSFM DBP in WDM systems.

II. EXPERIMENTAL SETUP

The experimental set-up is depicted in Fig. 1. At the transmitter, five C-band external cavity lasers (ECLs) at wavelengths 1549.32 nm, 1549.72 nm, 1550.12 nm, 1550.52 nm and 1550.92 nm (50-GHz channel spacing) were used as continuous-wave (cw) WDM signal sources. All the WDM channels were combined using an optical coupler, and after amplification with an EDFA, the signals were sent to an IQ modulator (IQ Mod). A two-channel 56-GS/s digital-to-analog converter (DAC) was used to drive the IQ Mod. This provided the in-phase and quadrature components of a single-polarization 28-GBd 16-QAM signal. After using a polarization-multiplexing emulator (PolMux) to provide PDM signals to all five WDM channels, the channels were decorrelated. A wavelength-selective switch (WSS) was used to separate all the channels and different lengths of single-mode fiber patch cords were placed in the individual WDM optical paths. This provided a minimum inter-channel delay of 100 symbols [START_REF] Ibrahim | Towards a practical implementation of coherent WDM: analytical, numerical, and experimental studies[END_REF]. An EDFA was used to amplify the channels after combining all five WDM signals with an optical coupler. The out-of-band amplified spontaneous emission (ASE) noise was filtered by using a 3-nm optical band-pass filter (OBPF) and the state-of-polarization of the data was randomized using a polarization scrambler.

The transmission link consists of 80-km dispersion-compensated spans made from SLA and IDF fibers. The specifications of a representative span can be seen in Table 1 in section IV of the paper. An EDFA was used in front of each fiber span to set the signal launch power. After the first half of the link (N spans in link part 1), an EDFA was set to a constant output power of 17 dBm so as to keep the input signal power into the FOPA constant. A 3-nm OBPF was used to suppress the accumulated ASE and the signal was split into two portions with a 3-dB optical coupler. One portion of the signal went through the OPC device whereas the other portion bypassed the OPC device, which is referred to, here, as 'direct' transmission. The design and performance evaluation of the OPC device is discussed in section III. A variable optical attenuator (VOA) in the path without OPC ensured that the same input power was injected to the first EDFA of link part 2 in both scenarios, thereby resulting in the same noise accumulation behavior in the second half of the link. As the OPC provided low-loss operation, the additional attenuation introduced by the VOA in the path without OPC was about 5 dB and it was mainly due to the relatively high loss of the OBPF (5 dB) used to select the idler at the OPC output. Note that a conventional link without OPC would not consist of the interface between the link part 1 and link part 2 in Fig. 1. However, this interface has a negligible effect on the noise performance of the link since as mentioned before, the first EDFA in the interface is set to a large constant output power and the signal level is high during the optical processing in the interface and reduces only to about 2 dBm measured at the input of the first EDFA in link part 2. Therefore, the interface causes a negligible OSNR penalty. An optical switch was used to either select the output of the OPC device (conjugated signal) or the signal which bypassed the OPC device (direct transmission) before launching the selected data into the remaining half of the link (N spans in link part 2).

Detection of the signal or the conjugated copy after transmission over the entire link was performed with a standard polarization-diverse coherent receiver using a local oscillator (LO) with 100-kHz linewidth. The LO was combined with the selected data (either the signal or the conjugated signal) after the transmission link in a 90° optical hybrid. Four balanced photo detectors (BPD) were connected to the hybrid outputs, and a real-time sampling scope (RTO, 40-GS/s sampling rate, 20-GHz bandwidth) was used as analog-to-digital converter (A/D). Offline processing was performed desktop computer including resampling, 90° optical hybrid correction, frequency-offset compensation, blind adaptive time-domain equalization using a constant-modulus algorithm and multi-modulus algorithm, carrier-phase estimation by blind phase search, de-mapping and bit-error counting. Note that, with the exception of the transmission link; the transmitter, the OPC device and the coherent receiver used in this investigation are the same as those used in [START_REF] Sackey | Kerr nonlinearity mitigation in 5x28-GBd PDM 16-QAM signal transmission over a dispersion-uncompensated link with backward-pumped distributed Raman amplification[END_REF].

III. CHARACTERIZATION OF THE OPC DEVICE

The schematic representation of the dual-pump polarization-independent FOPA that was used as the OPC device is shown in Fig. 1. The OPC device consists of two ECLs at wavelengths 1534 nm (25-kHz linewidth) and 1574 nm (100-kHz linewidth), which served as cw pump sources. Two sinusoidal radio frequency (RF) tones at frequencies 69 MHz and 253 MHz were generated by a two-channel arbitrary waveform generator (AWG). The pumps were independently phase-modulated, with a modulation index of 1.44 radian, using the AWG output waveforms via phase modulators (PMs). The PMs were driven in a counter-phasing fashion in order to minimize the transfer of pump phase modulation from the pump to the generated idlers [START_REF] Richter | Parametric amplification and wavelength conversion of singleand dual-polarization DQPSK signals[END_REF], [START_REF] Radic | Selective suppression of idler spectral broadening in two-pump parametric architectures[END_REF]. The pumps were amplified by two EDFAs, filtered and combined with a WDM coupler. OBPFs with 0.8-nm full-width at half maximum bandwidths were used to suppress the out-of-band ASE noise around the pumps. The signal and the pumps were then sent to the highly nonlinear fiber (HNLF) inside the polarization diversity loop via a polarization beam splitter (PBS). Polarization controllers (PCs) in the pump paths were used to equally split the pumps in both propagation directions of the loop. The HNLF length, nonlinear coefficient, zero-dispersion wavelength, dispersion slope, and attenuation were 300 m, 16.3/W/km, 1556.6 nm, 0.019 ps/nm 2 /km, and 1.4 dB/km, respectively. Operating the OPC in an unsaturated regime was essential to avoid signal degradation, thus the VOA at the input of the OPC was set to ensure an appropriate signal power into the HNLF [START_REF] Da Ros | Impact of Gain Saturation on the Parametric Amplification of 16-QAM Signals[END_REF], [START_REF] Sackey | Characterization of a fiber-optical parametric amplifier in a 5×28-GBd 16-QAM DWDM system[END_REF]. Note that, in order to keep the OPC penalty low, a total pump power of 28.2 dBm and a total signal power of -5 dBm (for either single-channel or WDM case) were launched into the diversity loop via the PBS. This provided 5-dB signal on-off gain and 4-dB idler conversion efficiency at the output of the OPC [START_REF] Sackey | Characterization of a fiber-optical parametric amplifier in a 5×28-GBd 16-QAM DWDM system[END_REF], [START_REF] Jazayerifar | Impact of SBS on polarization-insensitive single-pump optical parametric amplifiers based on a diversity loop scheme[END_REF]. Note that a total input signal power of -5 dBm was used only for the back-to-back characterization of the FOPA. For the transmission experiment, however, the input signal power was optimized to 2 dBm. A 4-nm tunable-OBPF was used to filter out the channel(s) of interest at the output of the OPC. The performance evaluation of the OPC device was first carried out in the back-to-back (b2b) configuration without the transmission link.

In order to analyze the transferred pump-phase modulation to the generated idler, a single-channel cw signal at 1550.12 nm was injected together with the pumps into the diversity loop operated in a polarization-independent fashion. The strength of the phase modulation being transferred from the pumps to the idler was monitored via the electrical spectrum of the received idler measured using the RTO. While monitoring the idler spectrum, the phase delay and amplitude parameters of the pump phase modulation tones were adjusted so as to minimize the transferred pump-phase modulation to the idler. Fig. 2(a) shows the electrical spectrum of the received idler and highlight a suppression ratio between the carrier and the modulation tones higher than 35 dB, indicating that only negligible phase modulation is transferred to the idler [START_REF] Richter | Parametric amplification and wavelength conversion of singleand dual-polarization DQPSK signals[END_REF], [START_REF] Sackey | Design and performance evaluation of an OPC device using a dual-pump polarization-independent FOPA[END_REF].

A flat gain-bandwidth profile of the OPC device is desirable for WDM systems. To determine the gain profile, the signal-pump WDM coupler in the setup was temporarily replaced with a 10-dB coupler. The on-off gain was measured with a polarization scrambled cw-signal with its wavelength swept from 1535 nm to 1572 nm. Fig. 2(b) shows the measured gain profile. The wavelengths of the WDM channels were chosen in the flat gain region. In order to minimize the Raman effect, which causes longer wavelengths to experience more gain than shorter wavelengths, the C-band pump power was set ~1.8 dB higher than the L-band pump power. Fig. 2(b) also shows the measured polarization-dependent gain (PDG) of the OPC. Using a zero-span function of the optical spectrum analyzer (OSA) while scrambling the state-of-polarization of a single-channel 28-GBd 16-QAM signal with the PDM emulator bypassed, the PDG was measured for a wavelength sweep from 1542.5 nm to 1565 nm (i.e. within the flat region of the gain profile). The maximum PDG for both signal and idler was found to be below 0.4 dB (indicated by the dashed line).

The on-off gain of the signal as well as the idler conversion efficiency is shown in Fig. 3(a). The spectrum was obtained from an OSA after a 20-dB coupler.

The BER performance as a function of receiver OSNR for both signals and idlers in a WDM scenario is shown in Fig. 3(b). Note that the center channel (ch-3) was used for evaluations in the WDM investigations. It can be seen that, the performances of the signal and idler are very similar. This indicates the effectiveness of the suppression of the pump phase modulation transfer to the idler. It was also noted that the differences in the BER between the WDM channels were insignificant, showing similar performances for all WDM channels [START_REF] Sackey | Design and performance evaluation of an OPC device using a dual-pump polarization-independent FOPA[END_REF] and therefore making the OPC well applicable for WDM transmission system investigations.

IV. DIGITAL BACKPROPAGATION

A non-iterative symmetric SSFM based on coupled nonlinear Schrödinger equations (NLSEs) was employed for the realization of the DBP [START_REF] Napoli | Reduced complexity digital back-propagation methods for optical communication systems[END_REF], [START_REF] Ip | Compensation of dispersion and nonlinear impairments using digital backpropagation[END_REF]. The dispersion-managed fibers were modeled using the measured parameters from the fibers used in the experiment. An example of the specifications of a fiber span is shown in Table 1. Group velocity dispersion of first and second-order were taken into account in the DBP. However, ASE noise from the link EDFAs was not taken into account [START_REF] Ip | Compensation of dispersion and nonlinear impairments using digital backpropagation[END_REF]. Polarization mode dispersion in the link was also not considered.

The SLA and IDF fibers in each span were modeled separately by performing the SSFM on each fiber type. Each fiber was modeled with a number of m steps in the SSFM DBP algorithm. The value of m was optimized on a 480-km transmission scenario under WDM operation. Increasing the number of steps per fiber beyond m = 10 did not yield further improvements. Therefore the number of steps per fiber was kept fixed at m = 10 and corresponds to 10 steps per SLA and 10 steps per IDF. A higher number of steps can improve the DBP performance up to a certain level at the expense of higher complexity and computational effort [START_REF] Napoli | Reduced complexity digital back-propagation methods for optical communication systems[END_REF], [START_REF] Rafique | Nonlinearity compensation in multi-rate 28 Gbaud WDM systems employing optical and digital techniques under diverse link configurations[END_REF].

The SSFM DBP algorithm was performed on the center channel of the received 5×28-GBd PDM 16-QAM signal and the results were compared to those obtained from the OPC operation. Note that two million samples were processed in both OPC measurements and DBP computation.

V. RESULTS AND DISCUSSIONS

A. Single-channel scenario

We initially investigated the nonlinearity compensation performance by using the OPC with a single-channel at 1550.12 nm (center channel in the WDM experiment) over a transmission length of 480 km (i.e. N = 3 spans before and 3 spans after the OPC) and the results were compared with that of the DBP.

The received data of the direct signal transmission was backpropagated in the modeled DBP. It is seen from Fig. 4 that the maximum Q-factor for the case with DBP increases to 11.8 dB (at a launch power of 1 dBm/pol). This indicates an improvement in performance of 0.8-dB compared to the maximum Q-factor for the OPC compensation technique.

The transmission length was then increased to 800 km (i.e. N = 5 spans before and 5 spans after the OPC) and the calculated Q-factors were plotted as a function of the signal launch power per polarization as shown in Fig. 5. It can be seen that direct transmission without any nonlinearity mitigation scheme was not possible with BERs below the hard-decision forward error correction (HD-FEC) threshold of 3.8×10 -3 , corresponding to a Q-factor of 8.5 dB. However, with the implementation of the OPC the maximum Q-factor increased from 8.3 dB to 9.6 dB resulting in a Q-factor improvement of 1.3 dB. Moreover, application of the DBP increased the maximum Q-factor to 10.5 dB. This yields an improvement of the maximum Q-factor improvement of 2.2 dB when compared to the direct signal transmission and is 0.9 dB better than the OPC scheme. The nonlinear threshold is also seen to be increased considerably thanks to the use of the DBP algorithm.

It is observed that the OPC compensation scheme shows poorer performance than the DBP. This can be attributed to the asymmetric power evolution over the entire EDFA-based The signal launch power per polarization into the spans was varied from -6 dBm to +4dBm. At the coherent receiver, the BER for each measurement at a particular signal launch power was evaluated and Fig. 3 shows the Q-factors (derived from BER) for the cases with and without OPC operation. Signal transmission without nonlinear compensation by either OPC or the DBP is here referred to as 'direct' transmission. It is clear from the plot that transmitting the signal without OPC produced a maximum Q-factor of 10 dB (at a launch power of -3 dBm/pol) whereas the implementation of the OPC increased the maximum Q-factor to 11 dB (at a launch power of 0 dBm/pol) thus yielding an improvement of 1 dB (2-dB increase in optimum launch power). It can also be seen from Fig. 4 that the nonlinear threshold increases from a launch power of 0.4 dBm/pol to 3.6 dBm/pol giving a substantial increase of 3.2 dB in the nonlinear threshold. transmission link [START_REF] Jansen | Long-haul DWDM transmission systems employing optical phase conjugation[END_REF], [START_REF] Ip | Compensation of dispersion and nonlinear impairments using digital backpropagation[END_REF]. In addition, locating the OPC exactly in the middle of the link can be very difficult and therefore any asymmetry regarding the position of the OPC will affect the performance [START_REF] Jansen | Long-haul DWDM transmission systems employing optical phase conjugation[END_REF], [START_REF] Watanabe | Exact compensation for both chromatic dispersion and Kerr effect in a transmission fiber using optical phase conjugation[END_REF]. The DBP algorithm, however, does not have such constraints.

HD-FEC

In addition, the generation of an idler at a different wavelength in the OPC scheme can result in a dispersion mismatch between signal and idler which can lead to inefficient distortion compensation. However, in our experiment, the signal/idler residual dispersion mismatch was very low (~0.8 ps/nm over 400 km) since the wavelength separation between signal and idler was only 7.2 nm (signal at 1550.12 nm, idler at 1557.32 nm) and also due to the use of the dispersion-managed link.

B. WDM scenario

Nonlinear distortion mitigation was also considered for a 5-channel WDM scenario. All five WDM channels were propagated over a transmission length of 480 km. The signal launch power per channel per polarization was adjusted from -7 dBm to 0 dBm and the center channel (i.e. at 1550.12 nm) was evaluated in the WDM investigations. The Q-factors were calculated for each launch power from the BERs, as in the single-channel scenario, and were plotted as function of the signal launch powers as shown in Fig. 6. Direct transmission over the link produced a maximum Q-factor of 9.4 dB at a launch power of -5 dBm/ch/pol. With the application of the DBP, the maximum Q-factor improved to 9.9 dB. However, implementation of the OPC increased the maximum Q-factor to 10.1 dB. This indicates an improvement of the maximum Q-factor of 0.7 dB compared to the direct transmission without any compensation scheme. Fig. 6 also shows that OPC increases the nonlinear threshold by 0.8 dB compared to DBP and by 2 dB compared to the direct transmission.

The transmission length was further increased to 800 km and the Q-factor performances for the three cases are shown in Fig. 7. It is clear from Fig. 7 that without the implementation of any nonlinear compensation scheme, the maximum Q-factor obtained from direct transmission was 7.7 dB, well below the HD-FEC threshold. Even though the use of the DBP algorithm improves the maximum Q-factor to 8.2 dB, this is still below the HD-FEC threshold. On the other hand, OPC operation increases the maximum Q-factor to 8.6 dB, which is above the HD-FEC threshold. This implies that the signal transmission over 800 km was only possible with OPC operation with a Q-factor improvement of 0.4 dB compared to DBP.

These results show that, in the WDM scenario, the OPC outperforms the DBP algorithm. The lower performance of the DBP in the WDM scenario is due to the detection bandwidth of the employed coherent reception which was limited to a single WDM channel. It thus compensates for intra-channel distortions but not for inter-channel distortions [START_REF] Savory | Impact of interchannel nonlinearities on a split-step intrachannel nonlinear equalizer[END_REF]. The OPC on the other hand, compensates for both intra-and inter-channel impairments. The same behavior has been observed for a different dispersion-managed link configuration in numerical simulations [START_REF] Rafique | Nonlinearity compensation in multi-rate 28 Gbaud WDM systems employing optical and digital techniques under diverse link configurations[END_REF].

The performance of the OPC might be further improved in the WDM case over the DBP algorithm if the power profile was made more symmetrical with respect to the middle of the transmission link, a condition which is very critical to attain by using only EDFAs [START_REF] Jansen | Long-haul DWDM transmission systems employing optical phase conjugation[END_REF]. We have experimentally investigated fiber nonlinearity mitigation of a five-channel 28-GBd PDM 16-QAM signal in a 50-GHz spaced WDM system. Two nonlinear compensation methods, optical phase conjugation (OPC) based mid-link spectral inversion and digital backpropagation (DBP) were implemented and the results were compared for up to 800-km transmission over dispersion-managed transmission links. The OPC compensation scheme shows an inferior performance compared to DBP in the single-channel case. However, in the WDM scenario over the same link length, the OPC-based compensation scheme outperformed DBP. This is due to the fact that the DBP algorithm can practically compensate for only intra-channel cross-talk, due to receiver bandwidth limitations, whereas the OPC compensates for both inter-and intra-channel impairments. Thus in our experiment, the optical domain signal processing proves to be a better approach than its digital domain counterpart for nonlinearity compensation of WDM signals.

Fig. 1 .

 1 Fig. 1. Experimental setup showing the 5×28-GBd 16-QAM transmitter, the dispersion-managed fiber links (SLA+IDF), the dual-pump polarization-independent FOPA, which is used as OPC device, and the coherent receiver.

Fig. 2 .

 2 Fig. 2. (a) Acquired electrical spectrum from RTO showing suppression of pump phase modulation (b) On-off gain profile and PDG performances of both signal and idler.

Fig. 3 .

 3 Fig. 3. (a) 5-channel WDM spectrum measured after a 20-dB coupler showing the on-off gain, (b) Plot of BER vs OSNR for the WDM scenario showing the performance of the signal and the idler.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Single-channel: plot of Q-factor vs. launch power per polarization over the 480-km transmission link showing the performances for the cases of direct transmission without nonlinearity mitigation, with OPC operation and with SSFM DBP.

Fig. 6 .

 6 Fig. 6. (a) 5-channel WDM: plot of Q-factor vs. launch power per channel per polarization over the 480-km transmission link showing the performances for the cases of direct transmission without nonlinearity mitigation, with OPC operation and with SSFM DBP, (b) x-polarization constellation diagrams at a launch power of -3 dBm/ch/pol over 800 km for the cases (i) direct transmission without any compensation scheme, (ii) with DBP, (iii) with OPC operation, (c) 5-channel WDM: plot of Q-factor vs. launch power per channel per polarization over the 800-km transmission link showing the performances for the cases of direct transmission without nonlinearity mitigation, with OPC operation and with SSFM DBP.

TABLE 1 SPECIFICATIONS

 1

	OF THE DISPERSION-MANAGED FIBER
	(EACH SPAN CONSISTS OF SLA AND IDF FIBERS)
	Parameter (properties at 1550 nm)	SLA	IDF
	Length (km)	55.57	25.68
	Effective area (µm 2 )	107	31
	Loss coefficient (dB/km)	0.186	0.234
	Nonlinear refractive index (×10 -20 m 2 /W)	2.23	2.36
	Dispersion (ps/nm/km)	20.2	-44
	Dispersion slope (ps/nm 2 /km)	0.06	-0.13

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/JLT.2015.2393152, Journal of Lightwave Technology

This work was supported in part by the German Research Foundation (DFG) under grants GR 3774/1-1 and PE 319/26-1; the German Federal Ministry of Education and Research under support code 16BP12310 EUREKA project SASER as well as the Danish Agency for Technology and Production Sciences under project 09-066562. The authors would like to thank OFS Denmark for providing the dispersion-managed fibers.

Author biographies are not included by author request due to space constraints.