Miznah Alshammary

Mai Alzamel

Costas Iliopoulos
email: c.iliopoulos@kcl.ac.ukbruce@fastar.org

Richard E Watson

Bruce W Watson

A brief overview of dead-zone pattern matching algorithms

Within the last decades, the dead-zone algorithms have emerged as being highly performant on certain types of data. Such algorithms solve the keyword exact matching problem over strings, though extensions to trees and two-dimensional data have also been devised. In this short paper, we give an overview of such algorithms.

Introduction and related work

In this paper, we present a new family of algorithms solving the single keyword string pattern matching problem. This particular pattern matching problem can be described as follows: given an input string S and a keyword p, find all occurrences of p as a continuous substring of S. The field of string pattern matching is generally well-studied (some thought it to be exhausted by the end of the 1970's), however, it continues to yield new and exciting algorithms, as was seen in annual conferences such as Combinatorial Pattern Matching and Stringology. In [START_REF] Watson | Taxonomies and Toolkits of Regular Language Algorithms[END_REF] (a dissertation by the last author of this paper), a taxonomy of existing algorithms was presented, along with a number of new algorithms. Any given algorithm may have more than one possible derivation, leading to different classifications of the algorithm in a taxonomy 1 . Many of the new derivations can prove to be more than just an educational curiosity, possibly leading to interesting new families of algorithms. This paper presents one such family, with some new algorithms and also some alternative derivations of existing ones. The algorithms presented in this paper have been extended to handle some more complex pattern matching problems, including multiple keyword pattern matching, regular pattern matching and multi-dimensional pattern matching. For some recent examples of this, see [START_REF] Daykin | Three Strategies for the Dead-Zone String Matching Algorithm[END_REF][START_REF] Mauch | Performance assessment of dead-zone single keyword pattern matching[END_REF][START_REF] Watson | Using Correctness-by-Construction to Derive Dead-zone Algorithms[END_REF][START_REF] Watson | A Sequential Recursive Implementation of Dead-Zone Single Keyword Pattern Matching[END_REF].

Mathematical preliminaries

While most of the mathematical notation and definitions used in this paper are is described in detail in [START_REF] Gries | A Logical Approach to Discrete Math[END_REF], here we present some more specific notations. Indexing within strings begins at 0, as in the C and C++ programming languages. We use ranges of integers throughout the paper which are defined by (for integers i and j):

[i, j) = { k | i ≤ k < j } (i, j] = { k | i < k ≤ j } [i, j] = [i, j) ∪ (i, j] (i, j) = [i, j) ∩ (i, j]
In addition, we define a permutation of a set of integers to be a bijective mapping of those integers onto themselves.

The problem and a first algorithm

Before giving the problem specification (in the form of a postcondition to the algorithms), we define a predicate which will make the postcondition and algorithms easier to read. Keyword p (with the restriction that p = ε, where ε is the empty string) is said to match at position j in input string S if p = S j•••j+|p|-1 ; this is restated in the following predicate:

2

The pattern matching problem requires us to compute the set of all matches of keyword p in input string S. We register the matches as the set O (for "output") of all indices j (in S) such that Matches(S, p, j) holds. Definition 3.2 (Single keyword pattern matching problem): Given a common alphabet V , input string S, and pattern keyword p, the problem is defined using postcondition PM :

O = { j | j ∈ [0, |S|) ∧ Matches(S, p, j) }
Note that this postcondition implicitly depends upon S and p, even though we do not make that explicit.

2

We can now present a nondeterministic algorithm which keeps track of the set of possible indices (in S) at which a match might still be found (indices at which we have not yet checked for a match). This set is known as the live zone. Those indices not in the live zone are said to be in the dead zone. This give us our first algorithm (presented in Dijkstra's pseudocode [START_REF] Dijkstra | A discipline of programming[END_REF][START_REF] Cohen | Programming in the 1990s[END_REF][START_REF] Kourie | The Correctness-by-Construction Approach to Programming[END_REF]). The invariant specifies that live and dead are disjoint and account for all indices in S; additionally, any match at an element of dead has already been registered. Thanks to this relationship between live and dead , we could have written the repetition condition live = Ø as dead = [0, |S|), and the j selection condition j ∈ live as j ∈ dead . It should be easy to see that the invariant and the termination condition of the repetition implies the postcondition -yielding a correct algorithm. Note that this algorithm is highly over-specified by keeping both variables live and dead to represent the live and dead zones, respectively. For efficiency, only one of these sets would normally be kept, as is seen in [START_REF] Mauch | Performance assessment of dead-zone single keyword pattern matching[END_REF][START_REF] Watson | Using Correctness-by-Construction to Derive Dead-zone Algorithms[END_REF][START_REF] Watson | A Sequential Recursive Implementation of Dead-Zone Single Keyword Pattern Matching[END_REF]. Some of the rightmost positions in S cannot possibly accommodate matches -no match can be found at any point j ∈ In the next section, give a more deterministic (more realistically implemented) version of the last algorithm.

[|S| -|p| + 1, |S|) since |S j•••|S|-1 | ≤ |S |S|-|p|+1•••|S|-1 | < |p| (the match

A more deterministic algorithm

In the last algorithm, our comparison of p with S j•••j+|p|-1 is embedded within the evaluation of predicate Matches. In this section, we make this comparison explicit. We begin by noting that p = S j•••j+|p|-1 is equivalent to comparing the individual symbols p k of p with the corresponding symbols S j+k of S (for k ∈ [0, |p|)). In fact, we can consider the symbols in any order whatsoever. To determine the order in which they will be considered, we introduce match orders: Definition 4.1 (Match order): We define a match order mo as a permutation on [0, |p|).

2

Using mo, we can restate our match predicate.

Property 4.2 (Predicate Matches): Predicate Matches is restated as

Matches(S, p, j) ≡ (∀ i : i ∈ [0, |p|) : p mo(i) = S j+mo(i) ) 2
This rendition of the predicate will be evaluated by a repetition which uses a new integer variable i to step from 0 to |p| -1, comparing p mo(i) to the corresponding symbol of S. As i increases, the repetition has the following invariant:

(∀ k : k ∈ [0, i) : p mo(k) = S j+mo(k) )
and terminates as early as possible.

In the following algorithm, we use the match order mo, the new repetition and our previous optimization to the initializations of dead and live.

Algorithm 4.3: live, dead := [0, |S| -|p|], [|S| -|p| + 1, |S|); O := Ø; { invariant: live ∪ dead = [0, |S|) ∧ live ∩ dead = Ø ∧ O = { j | j ∈ dead ∧ Matches(S, p, j) } } do live = Ø → let j : j ∈ live; live, dead := live \ {j}, dead ∪ {j}; i := 0; { invariant: (∀ k : k ∈ [0, i) : p mo(k) = S j+mo(k) ) } do i < |p| cand p mo(i) = S j+mo(i) → i := i + 1 od; { postcondition: (∀ k : k ∈ [0, i) : p mo(k) = S j+mo(k) ) ∧ (i < |p| ⇒ p mo(i) = S j+mo(i) ) } if i = |p| → O := O ∪ {j} [] i < |p| → skip f i od{ postcondition: PM } 2
The operator P cand Q appears in the guard of the inner loop of the above algorithm. This operator is similar to conjunction P ∧ Q except that if the first conjunct evaluates to false then the second conjunct is not even evaluated. This proves to be a useful property in cases such as the loop guard since, if the first conjunct (i < |p|) is false (hence i >= |p|, and indeed i = |p|), then the term mo(i) appearing in the second conjunct is not even defined. Note that the implication within the second conjunct of the loop postcondition is derived from the loop guard, forcing the implication operator to be conditional as well (that is, if i < |p| is determined to be false, then p mo(i) = S j+mo(i) is not even evaluated).

Reusing match information

On each iteration of the outer repetition, index j is chosen and eliminated from the live zone in the statement:

live, dead := live \ {j}, dead ∪ {j}
The performance of the algorithm can be improved if we remove more than just j in some of the iterations. To do this, we can use some of the match information, such as i, which indicates how far through mo the match attempt proceeded before finding a mismatching symbol. The information most readily available is the postcondition of the inner repetition:

(∀ k : k ∈ [0, i) : p mo(k) = S j+mo(k) ) ∧ (i < |p| ⇒ p mo(i) = S j+mo(i) )
We denote this postcondition by Result(S, p, i, j). Since this postcondition holds, we may be able to deduce that certain indices in S cannot possibly be the site of a match. It is such indices which we could also remove from the live zone. They are formally characterized as:

{ x | x ∈ [0, |S|) ∧ (Result(S, p, i, j) ⇒ ¬Matches(S, p, x)) } (1)
Determining this set at pattern matching time is inefficient and not easily implemented. We wish to derive a safe approximation of this set which can be precomputed, tabulated and indexed (at pattern matching time) by i. In order to precompute it, the approximation must be independent of j and S. We wish to find a strengthening of the range predicate since this will allow us to still remove a safe set of elements from set live, thanks to the property that, if P ⇒ Q (P is a strengthening of Q, and Q is a weakening of P ), then

{ x | P (x) } ⊆ { x | Q(x) }
As a first step towards this approximation, we can normalize the ideal set (equation (1) above), by subtracting j from each element. The resulting characterization will be more useful for precomputation reasons:

{ x | x ∈ [-j, |S| -j) ∧ (Result(S, p, i, j) ⇒ ¬Matches(S, p, j + x)) }
Note that this still depends upon j, however, it will make some of the derivation steps shown shortly in Section 5.1 easier. Because those steps are rather detailed, they are presented in isolation.

Condensed, the derivation appears as:

(Result(S, p, i, j) ⇒ ¬Matches(S, p, j + x))

⇐ { Section 5.1 } ¬((∀ k : k ∈ [0, i) ∧ mo(k) ∈ [x, |p| + x) : p mo(k) = p mo(k)-x ) ∧ (i < |p| ∧ mo(i) ∈ [x, |p| + x) ⇒ p mo(i) = p mo(i)-x )) ≡ { De Morgan's Law } ¬(∀ k : k ∈ [0, i) ∧ mo(k) ∈ [x, |p| + x) : p mo(k) = p mo(k)-x ) ∨ ¬(i < |p| ∧ mo(i) ∈ [x, |p| + x) ⇒ p mo(i) = p mo(i)-x ) ≡ { De Morgan's Law on the universal quantification } (∃ k : k ∈ [0, i) ∧ mo(k) ∈ [x, |p| + x) : p mo(k) = p mo(k)-x ) ∨ ¬(i < |p| ∧ mo(i) ∈ [x, |p| + x) ⇒ p mo(i) = p mo(i)-x ) ≡ { De Morgan's Law on the implication, which is conditional } (∃ k : k ∈ [0, i) ∧ mo(k) ∈ [x, |p| + x) : p mo(k) = p mo(k)-x ) ∨ (i ≥ |p| ∨ mo(i) ∈ [x, |p| + x) cor p mo(i) = p mo(i)-x ) ≡ { define the predicate Approximation(p, i, x) } Approximation(p, i, x)
Note that we define the predicate Approximation(p, i, x) which depends only on p and i and hence can be precomputed and tabulated. It should be mentioned that this is one of several possible useful strengthenings which could be derived. We could even have used the strongest predicate, false, instead of Approximation(p, i, x). This would yield the empty set, Ø, to be removed from live in addition to j (as in the previous algorithm).

We can derive a smaller range predicate of x for which we have to check if Approximation(p, i, x) holds. Notice that choosing and x such that [x, |p| + x) ∩ [0, |p|) = Ø has two important consequences:

• The range of the quantification in first conjunct of Approximation(p, i, x) is empty (hence this conjunct is true, by the definition of universal quantification with an empty range).

• The range condition of the second conjunct (the 'implicator') is false -hence the whole of the second conjunct is true since false ⇒ P for all predicates P .

With this choice of x, we see that predicate Approximation(p, i, x) always evaluates to false, in which case we need not even consider values of

x such that [x, |p| + x) ∩ [0, |p|) = Ø. As a result, we characterize those x for which [x, |p| + x) ∩ [0, |p|) = Ø as follows: [x, |p| + x) ∩ [0, |p|) = Ø ≡ { for integers u, v, y, z: [u, v) ∩ [y, z) = Ø ≡ (v -1 < y ∨ u > z -1) } ¬(|p| + x -1 < 0 ∨ x > |p| -1) ≡ { arithmetic } ¬(x < 1 -|p| ∨ x > |p| -1) ≡ { De Morgan's Law } x ≥ 1 -|p| ∧ x ≤ |p| -1 ≡ { definition of ranges } x ∈ [1 -|p|, |p| -1]
Clearly we can use the restriction x ∈ [1 -|p|, |p| -1]. Intuitively (and information theoretically), we know that there must be such a range restriction since we can not possibly know from a current match attempt whether or not we will find a match of p in S more than |p| symbols away. Finally we have the following algorithm (in which we have added the additional update of live and dead below the inner repetition). Note that we introduce the set nogood to accumulate the indices for which Approximation(p, i, x) holds. Also note that we renormalize the set nogood by adding j to each of its members and ensuring that it is within the valid range of indices, [0, |S|). Algorithm 5.1:

live, dead := [0, |S| -|p|], [|S| -|p| + 1, |S|); O := Ø; { invariant: live ∪ dead = [0, |S|) ∧ live ∩ dead = Ø ∧ O = { l | l ∈ dead ∧ Matches(S, p, l) } } do live = Ø → let j : j ∈ live; live, dead := live \ {j}, dead ∪ {j}; i := 0; { invariant: (∀ k : k ∈ [0, i) : p mo(k) = S j+mo(k) ) } do i < |p| cand p mo(i) = S j+mo(i) → i := i + 1 od; { postcondition: Result(S, p, i, j) } if i = |p| → O := O ∪ {j} [] i < |p| → skip f i; nogood := ({ x | x ∈ [1 -|p|, |p| -1] ∧ Approximation(p, i , x ) } + j) ∩ [0, |S|); live := live \ nogood ; dead := dead ∪ nogood od{ postcondition: PM } 2

Range predicate strengthening

Here, we present the derivation of a strengthening of the range predicate Result(S, p, i, j) ⇒ ¬Matches(S, p, j + x)

Being more comfortable with weakening steps, we begin with the negation of part of the above range predicate, and proceed by weakening:

¬(Result(S, p, i, j) ⇒ ¬Matches(S, p, j + x)) ≡ { definition of ⇒ }
¬(¬Result(S, p, i, j) ∨ ¬Matches(S, p, j + x))

≡ { De Morgan's Law } Result(S, p, i, j) ∧ Matches(S, p, j + x)) ≡ { definition of Result and Matches } (∀ k : k ∈ [0, i) : p mo(k) = S j+mo(k) ) ∧ (i < |p| ⇒ p mo(i) = S j+mo(i) ) ∧ (∀ k : k ∈ [0, |p|) : p mo(k) = S mo(k)+j+x )
≡ { change range predicate in second quantification and definition of mo }

(∀ k : k ∈ [0, i) : p mo(k) = S j+mo(k) ) ∧ (i < |p| ⇒ p mo(i) = S j+mo(i) ) ∧ (∀ k : mo(k) ∈ [0, |p|) : p mo(k) = S mo(k)+j+x ) ⇒ { change dummy (mo(k ) = mo(k) + x), restrict range } (∀ k : k ∈ [0, i) : p mo(k) = S j+mo(k) ) ∧ (i < |p| ⇒ p mo(i) = S j+mo(i) ) ∧ (∀ k : mo(k ) -x ∈ [0, |p|) : p mo(k )-x = S mo(k )+j ) ≡ { simplify range predicate of second quantification } (∀ k : k ∈ [0, i) : p mo(k) = S j+mo(k) ) ∧ (i < |p| ⇒ p mo(i) = S j+mo(i) ) ∧ (∀ k : mo(k ) ∈ [x, |p| + x) : p mo(k )-x = S mo(k )+j )
⇒ { one-point rule: second conjunct and second quantification }

(∀ k : k ∈ [0, i) : p mo(k) = S j+mo(k) ) ∧ ((i < |p| ∧ mo(i) ∈ [x, |p| + x)) ⇒ p mo(i) = p mo(i)-x ) ∧ (∀ k : mo(k ) ∈ [x, |p| + x) : p mo(k )-x = S mo(k )+j )
⇒ { combine two quantifications and remove dependency on S and transitivity of = }

(∀ k : k ∈ [0, i) ∧ mo(k) ∈ [x, |p| + x) : p mo(k) = p mo(k)-x ) ∧ ((i < |p| ∧ mo(i) ∈ [x, |p| + x)) ⇒ p mo(i) = p mo(i)-x )
6 Choosing j from the live zone

In this section, we discuss strategies for choosing the index j (from the live zone) at which to make a match attempt. In the last algorithm, the way in which j is chosen from set live is nondeterministic. This leads to the situation that live (and, of course, dead ) is fragmented, meaning that an implementation of the algorithm would have to maintain a set of indices for live.

If we can ensure that live is contiguous, then an implementation would only need to keep track of the (one or two) boundary points between live and dead . There are several ways to do this, and we discuss some of them in the following subsections section. Each of these represents a particular policy to be used in the selection of j.

Minimal element -towards the classical Boyer-Moore algorithm

We could use the policy of always taking the minimal element of live. In that case, we can make some simplifications to the algorithm (which, in turn, improve the algorithm's performance):

• We need only store the minimal element of live, instead of sets live and dead . We use live to denote the minimal element.

• The dead zone update could be modified as follows: we will have considered all of the positions to the left of j and so we can ignore the negative elements of the update set:

{ x | x ∈ [1 -|p|, 0) ∧ Approximation(p, i, x) }
Indeed, we can just add the maximal element (which is still contiguously in the update set and greater than j) of the update set to live for the new version of our new update of live and dead .

Depending upon the choice of weakening, and the choice of match order, the above policy yields variants of the classical Boyer-Moore algorithm (see [START_REF] Watson | Taxonomies and Toolkits of Regular Language Algorithms[END_REF][START_REF] Crochemore | Text Algorithms[END_REF][START_REF] Hume | Fast string searching[END_REF]): Algorithm 6.1:

live := 0; O := Ø; do live ≤ |S| -|p| → j := live; live := live + 1; i := 0; { invariant: (∀ k : k ∈ [0, i) : p mo(k) = S j+mo(k) ) } do i < |p| cand p mo(i) = S j+mo(i) → i := i + 1 od; { postcondition: Result(S, p, i, j) } if i = |p| → O := O ∪ {j} [] i < |p| → skip f i; nogood := (MAX x : x ∈ [0, |p| -1] ∧ (∀ h : h ∈ [0, x] : Approximation(p, i, x)) : x); live := live + nogood od{ postcondition: PM } 2 6.

Recursion

We could also devise a recursive version of the algorithm as a procedure. This procedure receives a contiguous range of live indices (live) -initially consisting of the range [0, |S| -|p|].

If the set it receives is empty, the procedure immediately returns. If the set is non-empty, j is chosen so that the resulting dead zone would appear reasonably close to the middle of the current live zone2 . This ensures that we discard as little information as possible from the nogood index set. After the match attempt, the procedure recursively invokes itself twice, with the two reduced live zones on either side of the new dead zone. This yields the following procedure: Naturally, for efficiency reasons, the set live can be represented by its minimal and maximal elements (since it is contiguous). Note that the dead zone need not be contiguous. This recursive algorithm is presented in [START_REF] Watson | A Sequential Recursive Implementation of Dead-Zone Single Keyword Pattern Matching[END_REF], and with benchmarking data in [START_REF] Mauch | Performance assessment of dead-zone single keyword pattern matching[END_REF].

Definition 3 . 1 (

 31 Predicate Matches): We define predicate Matches as Matches(S, p, j) ≡ (p = S j•••j+|p|-1 )

Algorithm 3. 3 :

 3 live, dead := [0, |S|), Ø; O := Ø; { invariant: live ∪ dead = [0, |S|) ∧ live ∩ dead = Ø ∧ O = { j | j ∈ dead ∧ Matches(S, p, j) } } do live = Ø → let j : j ∈ live; live, dead := live \ {j}, dead ∪ {j}; if Matches(S, p, j) → O := O ∪ {j} [] ¬Matches(S, p, j) → skip f i od{ postcondition: PM } 2

  attempt begins too close to the end of S for p to fit). For this reason, we safely change the initializations of live and dead to live, dead := [0, |S| -|p|], [|S| -|p| + 1, |S|)

Algorithm 6. 2 :

 2 proc mat(S, p, live, dead) → { live is contiguous } if live = Ø → skip [] live = Ø → live low := (MIN k : k ∈ live : k); live high := (MAX k : k ∈ live : k); j := (live low + live high -|p|)/2 ; i := 0; { invariant: (∀ k : k ∈ [0, i) : p mo(k) = S j+mo(k) ) } do i < |p| cand p mo(i) = S j+mo(i) → i := i + 1 od; { postcondition: Result(S, p, i, j) } if i = |p| → O := O ∪ {j} [] i < |p| → skip f i; new dead := ({ x | x ∈ [1 -|p|, |p| -1] ∧ Approximation(p, i, x) } + j) ∩ [0,|S|); dead := dead ∪ new dead ; mat(S, p, [live low , (MIN k : k ∈ new dead : k)), dead ); mat(S, p, ((MAX k : k ∈ new dead : k), live high], dead ) f i corp 2 This procedure is used in the algorithm: Algorithm 6.3: O := Ø; mat(S, p, [0, |S| -|p|], [|S| -|p| + 1, |S|)) { postcondition: PM } 2

This is precisely what happened with the Boyer-Moore type algorithms as presented in the dissertation[START_REF] Watson | Taxonomies and Toolkits of Regular Language Algorithms[END_REF].

The algorithm given in this section makes a simple approximation by taking the middle of the live zone it receives, and subtracting |p|/2 .

Conclusions

We have shown that there are still many interesting algorithms to be derived within the field of single keyword pattern matching. The correctness preserving derivation of am entirely new family of such algorithms demonstrates the use of formal methods and the use of predicates, invariants, postconditions and preconditions. It is unlikely that such a family of algorithms could have be devised without the use of formal methods.


Giannis Haralabopoulos

Christian Wagner

Derek Mcauley

Ioannis Anagnostopoulos

Paid crowdsourcing, low income contributors, and subjectivity

Keywords: Crowdsourcing, Demographics, Monetary Rewards, Subjectivity

Scientific projects that require human computation often resort to crowdsourcing. Interested individuals can contribute to a crowdsourcing task, essentially contributing towards the project's goals. To motivate participation and engagement, scientists use a variety of reward mechanisms. The most common motivation, and the one that yields the fastest results, is monetary rewards. By using monetary, scientists address a wider audience to participate in the task. As the payment is below minimum wage for developed economies, users from developing countries are more eager to participate. In subjective tasks, or tasks that cannot be validated through a right or wrong type of validation, monetary incentives could contrast with the much needed quality of submissions. We perform a subjective crowdsourcing task, emotion annotation, and compare the quality of the answers from contributors of varying income levels, based on the Gross Domestic Product. The results indicate a different contribution process between contributors from varying GDP regions. Low income contributors, possibly driven by the monetary incentive, submit low quality answers at a higher pace, while high income contributors provide diverse answers at a slower pace.

Introduction

Crowdsourcing is the process where a number of non expert people collectively perform a task. The task is presented to a wide group of internet users via an online platform and each user provides their unique input. The collection of inputs from the crowd is aggregated to provide information necessary for the task at hand. The users are referred as workers or contributors and the person that requests the crowdsourcing is known as requester.

As more and more requesters create tasks for workers, new tasks must provide incentives for participation. Money is the most common crowdsourcing incentive, and the one that yields the fastest results, but of varying quality [START_REF] Mao | Volunteering versus work for pay: Incentives and tradeoffs in crowdsourcing[END_REF]. Gamification of crowdsourcing tasks, i.e. the use of game elements such as point ladders and rewards, is another way of keeping workers interested and engaged in the task [START_REF] Hamari | Does gamification work?-a literature review of empirical studies on gamification[END_REF].

A crowdsourcing task is split in small micro tasks. Each micro task requires some seconds (on rare occasions minutes) to be completed, therefore the monetary incentive per micro task is usually low. The minimum allowed per micro task is 0.01$ in most crowdsourcing platforms 34 . This results in a low salary per hour, which according to Horton and Chilton [START_REF] Horton | The labor economics of paid crowdsourcing[END_REF], has a median of 1.38$/hour.

Studies have showed that workers from Europe and America provide higher quality contributions than workers from Asia [START_REF] Rogstadius | An assessment of intrinsic and extrinsic motivation on task performance in crowdsourcing markets[END_REF][START_REF] Kazai | The face of quality in crowdsourcing relevance labels: Demographics, personality and labeling accuracy[END_REF]. In addition, it is also shown that per task payment reduces contributor productivity [START_REF] Ikeda | Pay it backward: Per-task payments on crowdsourcing platforms reduce productivity[END_REF] and monetary rewards negatively influence answers quality [START_REF] Acar | Harnessing the creative potential of consumers: money, participation, and creativity in idea crowdsourcing[END_REF]. Considering that Asia's mean GDP per capita is almost 26% of Europe's, less than 14% of North America's5 , and the fact that participation incentives exist due monetary rewards, could there be a link between income and quality of crowdsourcing contributions?

During the analysis of the crowdsourcing results from one of our recent studies [START_REF] Haralabopoulos | Crowdsourcing for Beyond Polarity Sentiment Analysis A Pure Emotion Lexicon[END_REF][START_REF] Haralabopoulos | A Multivalued Emotion Lexicon Created and Evaluated by the Crowd[END_REF], we found evidence of high percentage of spam or dishonest contribution from workers originating from low income countries. Participants that deliver systematically the same contributions were identified as dishonest contributors, with high certainty. We hypothesize that workers from low income countries are mainly motivated by the monetary incentive, rather than the contribution to the crowdsourcing task. The crowdsourcing task, as described in [START_REF] Haralabopoulos | Crowdsourcing for Beyond Polarity Sentiment Analysis A Pure Emotion Lexicon[END_REF][START_REF] Haralabopoulos | A Multivalued Emotion Lexicon Created and Evaluated by the Crowd[END_REF], requires workers to choose from one of the three main classes and then select the most appropriate subclass. As seen in Fig. 1, workers select the appropriate class with a radio button, and unless the class selection is none, a drop-down menu appears that requires a single selection.

The use of fixed radio and drop-down selections, allows the requester to capture and filter out spamming behavior. This type of behavior is easy to capture when a dishonest worker is constantly selecting the same options over and over again, but undetectable if a dishonest user utilizes more elaborate methods of spamming, such as automated mouse movement applications. The inclusion of quality control questions [START_REF] Allahbakhsh | Quality control in crowdsourcing systems: Issues and directions[END_REF], which usually appear at the start of the task, forces workers to adopt a cautious behavior early on the task, and then proceed to provide dishonest contributions at a higher pace. In addition, the nature of a subjective task, such as the emotional annotation of terms, doesn't provide a solid basis for quality control questions that use predefined answers.

a n g e r a n t ic ip a t io n d is g u s t f e a r jo y o t h e r s a d n e s s s u r p r is e t r u s t Subclasses In this subjective crowdsourcing task, each term group was annotated by 6 separate workers, and each worker was not able to annotate more than 1% of the corpus. The subclass distribution of the contributions, as seen in Fig. 2, was comprised of mostly joy annotated term groups. The nine subclasses, visible in Fig. 2 and Fig. 3, represent the eight emotions, while the subclass "other" refers to either intensifiers and negators, or term groups that are not emotion evocative and not intensifying. Ninety and seventy two per cent of workers from countries with GDP income per capita of less than 10K$ annotated term groups exclusively with joy or none. This high annotation percentage in a single subclass, of a random distribution of terms, is strong indication of spam and dishonesty.

Although this behavior was verified manually by the authors at a term level, where we analysed individual terms to determine whether they were evoking any emotion, in large scale crowdsourcing tasks there is no need for manual verification. The probability of annotation workers constantly encountering terms of the same emotion would be extremely low. E.g. if the combined probability of a term group being none or joy was 99%, the probability of encountering six hundred exclusively none or joy term groups would only be 0.2405%. Thus the probability that a worker honestly annotated a diverse corpus of words only with a single emotion is very close to zero.

a n g e r a n t ic ip a t io n d is g u s t f e a r jo y o t h e r s a d n e s s s u r p r is e t r u s t Subclasses

Quality of workers and contributions

The requested task had both a set of test questions, that would say if a term was an intensifier or emotion evoking, and a distribution control of contributions was applied. However, a high number of test questions would appear during the initial stages of the task, something that workers were aware of and could easily exploit. The distribution control worked well on identifying spammers, but it required a minimum number of answers from each worker before excluding workers that constantly annotated a single emotion.

The distribution threshold was set at 40%, which is approximately double the highest occurrence of a single emotion in another similar study [START_REF] Mohammad | Nrc emotion lexicon[END_REF]. After filtering out workers that had more than 40% of their total annotations in a single subclass, we end up with a smoother distribution of annotations, but strictly bound to the threshold. From the total one hundred eighty seven participating workers, only thirty six were identified as eligible based on the 40% filtering process. This in turn, reduced the number of total annotations deemed valid, from more than fifty thousands to less than eleven thousands. The percentage of invalidated annotations and the originating country of the contributors are the basis of our hypothesis.

Testing the Hypothesis

Our hypothesis is that workers from low income countries are motivated from the monetary incentive, rather than contributing to the task. A direct implication of this hypothesis is that monetary incentivised workers provide low quality answers. In order to test this hypothesis we used 1555 term groups as annotated strictly to joy or none, prior to the filtering process, with a majority higher than 80% of the total annotations. Six annotations per term group were required, with the same test questions for workers as before. The task was requested in the same platform, with the exact same settings, but only allowed workers from countries with GDP per capita higher then 30K$ to participate.

In the high income task, workers annotated term groups diversely, and the previously dominant joy emotion is the third most frequently occurring subclass. Additionally, strong majority agreement (over 80%) over joy and none subclasses is lower, with 42 term groups annotated as joy and 181 as none, compared to 1055 and 500 respective term groups of the initial task.

In total group of 112 contributors in the hypothesis group, 32 were flagged as eligible by our 40% single annotation check. A slightly lower eligibility over assessment than the initial task, due to the fact that hypothesis term groups were biased towards joy and none. However, workers annotated term groups in all of the possible subclasses, and only 4% and 36.2% of the term groups were still majorly annotated as joy and none respectively.

None was the most common occurring annotation post-filter, and the only subclass affected by the single annotation check. Its challenging to determine honesty post-annotation with an unsupervised method, more so on a monetary incentivised subjective task.

Conclusion

The results suggest that income is an important factor in crowdsourcing participation. As the particular crowdsourcing task is mainly of subjective nature, the validation of the hypothesis can only be based on the diversity of the provided contributions, compared to the initially single subclass accumulated contributions. In an objective task, quality questions and distribution filtering are sufficient measures to prevent dishonesty. Modern crowdsourcing platforms6 provide ethical rewards and worker demographic pre-screening, empowering requesters and workers alike.

We are studying the subjective aspects of crowdsourcing, and our goal is to address the evaluation of subjective contributions with objective criteria in future publications. Additionally, in purely subjective crowdsourcing tasks, demographics like age, sex, or education levels, should be further studied to better understand crowds performance [START_REF] Pavlick | The language demographics of amazon mechanical turk[END_REF][START_REF] Ross | Who are the crowdworkers?: shifting demographics in mechanical turk[END_REF]. Our preliminary findings are in line with research that suggests voluntary crowdsourcing provides highest quality contributions than paid crowdsourcing [START_REF] Mao | Volunteering versus work for pay: Incentives and tradeoffs in crowdsourcing[END_REF]. Workers participating voluntarily are only motivated by their desire to contribute, which can be supplemented by a range of non monetary incentives to improve engagement. Apart from voluntary participation, a critical mass of honest participators [START_REF] Sharma | Crowdsourcing Critical Success Factor Model: Strategies to harness the collective intelligence of the crowd[END_REF] can function as a selfmaintained filter for dishonesty and spamming in both objective and subjective tasks.

Fig. 1 .

 1 Fig. 1. Micro-task structure

Fig. 2 .

 2 Fig. 2. Subclass distribution (low income levels)

Fig. 3 .

 3 Fig. 3. Subclass distribution in previously joy or other annotated term groups (high income levels)

https://www.figure-eight.com/

https://www.mturk.com/

http://www.imf.org/external/datamapper/NGDPDPC@WEO/OEMDC/ADVEC/WEOWORLD

https://prolific.ac/


Konstantinos Gourzis
email: gourzisk@gmail.com

Georgios Alexandridis
email: gealexandri@aegean.gr

Stelios Gialis
email: stgialis@aegean.gr

George Caridakis

Studying the Spatialities of Short-Term Rentals' Sprawl in the Urban Fabric: The Case of Airbnb in Athens, Greece

Keywords: Airbnb, Gentrification, Housing markets, Spatio-temporal humanities

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The expansion of short-term rental (STR) markets in recent years is a reality that definitely affects living conditions, especially in urban areas. This fact can be attributed to a number of characteristics of STRs, like their ability to take advantage of local landmarks (more than hotels do) because of their capacity to expand in already built-up areas, without the need of specific permits or being subject to land use zoning [START_REF] Gutirrez | The eruption of airbnb in tourist cities: Comparing spatial patterns of hotels and peer-to-peer accommodation in barcelona[END_REF]. This is exceptionally important in the context of urban tourism, a rapidly growing part of the tourism industry, affecting mainly lower-end hotels and those not targeting affluent business travelers [START_REF] Heo | A macroeconomic perspective on airbnbs global presence[END_REF]. The increasing number of STR listings has generated controversies on several issues of regulation, housing markets and various others spatio-temporal effects [START_REF] Slee | What's Yours Is Mine: Against the Sharing Economy[END_REF]. Thus, it calls for urgent research attention based on, among other things, the perspective of humanistic data mining.

Within the STR market, Airbnb3 , an online peer-to-peer (P2P) accommodation platform, holds a prominent share. Airbnb is a global phenomenon; since its emergence in 2007, it has managed to expand to 81 thousand cities across 191 countries, currently counting more than 6 million listings. While linkages between the spatial characteristics of the platform's listings and shifts in the housing market have been studied for a variety of cities, like New York [START_REF] Sheppard | Do airbnb properties affect house prices? Department of Economics Working Papers[END_REF], Boston [START_REF] Horn | Is home sharing driving up rents? evidence from airbnb in boston[END_REF] or even Barcelona [START_REF] Seg | Do short-term rent platforms affect rents? Evidence from Airbnb in Barcelona[END_REF], there has not been, to the best of our knowledge, a thorough study for a south-eastern EU metropolis, like Athens and its neighborhoods.

The main aim of the current research is to tentatively discuss the consolidation of Airbnb in the city of Athens and associate it with several socio-economic aspects in specific city areas. The expansion of STRs is viewed as an outcome of several processes, needs and antinomies; i.e through the lens of transnational capital flows into the housing market of a dynamic city. Departing from an analysis of STRs listings (number, density) within the context of the biggest Greek city, we proceed by relating their expansion with an increase in long-term rental (LTR) prices. Specifically, it is highlighted how STRs might put pressure on other forms of housing, causing rents and property values to rise, as residences become "cash cows" [START_REF] Horn | Is home sharing driving up rents? evidence from airbnb in boston[END_REF] and reinforce gentrification [START_REF] Lee | How airbnb short-term rentals exacerbate los angeles's affordable housing crisis: Analysis and policy recommendations[END_REF].

The spatialities of short-term rentals

At the global scale, the Airbnb "community" sprawls in a heterogeneous fashion [START_REF] Ke | Sharing means renting?: An entire-marketplace analysis of airbnb[END_REF], being mainly used in macro-peripheries where tourism is already a prominent industry, boast dynamic development overall and the population is "technologically savvy" [START_REF] Heo | A macroeconomic perspective on airbnbs global presence[END_REF]. The majority of entries regard entire house renting, indicating that the commercial use of Airbnb is pervasive, rendering the platform a rental marketplace rather than a true sharing economy mediator. This reality is further characterized by the heavy involvement of business operators whose presence is obscured by the use of "front men". In 2017, it was found that almost 70% of all listings globally referred to entire apartments/houses [START_REF] Ke | Sharing means renting?: An entire-marketplace analysis of airbnb[END_REF], while in 2016 almost half of the lodgings researched in 5 global cities referred to traditional holiday businesses [START_REF] Crommelin | Is airbnb a sharing economy superstar? evidence from five global cities[END_REF]. Additionally, Airbnb functions often as a mechanism that allows middle and upper-class homeowners to consolidate their position in expensive housing markets, in addition to being a channel of extra income for the urbanities of lower classes, who experience an exacerbated vulnerability amid conditions of low affordable housing stock and high tourist demand [START_REF] Crommelin | Is airbnb a sharing economy superstar? evidence from five global cities[END_REF].

One of the earliest arguments in favor of Airbnb was that it would disperse the supply of tourism-oriented accommodation, relieving areas receiving heavy visitor flows. Nevertheless, an analysis for Barcelona [START_REF] Sans | Unravelling airbnb: Urban perspectives from Barcelona[END_REF] concluded that Airbnb functions as a force concentrating supply rather than decentralizing it. On top of that, the way listings unravel follows a pattern that derives from a specific sociocultural profile regarding both hosts and guests [START_REF] Sans | Unravelling airbnb: Urban perspectives from Barcelona[END_REF].

Apart from Barcelona, STR listings in Europe show significant concentrations in Paris, London, and Rome. Athens also exhibits high concentrations relative to its population, even though it is not among the European cities with the largest number of Airbnb entries. In the US, most Airbnb activity is located in five specific cities: New York, Los Angeles, San Francisco, Miami and Boston [START_REF] Lane | The sharing economy checks in: An analysis of airbnb in the united states[END_REF].

Specifically, New York holds a prominent position in the relevant literature, boasting an exceptionally consolidated activity of the STR market. At the same time, is shows concrete signs of ongoing dynamism and expansion (followed by San Francisco, Miami, Oakland and Oahu [START_REF] Heo | A macroeconomic perspective on airbnbs global presence[END_REF]) but it also exhibits falling rates of profitability in relation to LTRs. Listings are again mainly located in downtown areas, even though lately they tend to expand to hitherto under-exploited, residential areas [START_REF] Coles | Airbnb usage across new york city neighborhoods: Geographic patterns and regulatory implications[END_REF], resonating with the recent situation in Barcelona as well [START_REF] Gutirrez | The eruption of airbnb in tourist cities: Comparing spatial patterns of hotels and peer-to-peer accommodation in barcelona[END_REF]. In poorer areas, Airbnb seems to be reaffirming its original purpose as a niche sharing economy, with private rooms -which stand for a more casual use of the platform -holding a disproportionate presence [START_REF] Coles | Airbnb usage across new york city neighborhoods: Geographic patterns and regulatory implications[END_REF].

The impact on long-term rentals

The second issue relevant to our research, is the effect of Airbnb and the STR phenomenon in general on housing availability and affordability, specifically on LTR levels. There are arguments postulating against such a linkage, as in many cases the P2P accommodation market is very small in comparison to that of LTRs; the reliance of landlords upon long-term tenants, and the falling rates of STRs [START_REF] Coles | Airbnb usage across new york city neighborhoods: Geographic patterns and regulatory implications[END_REF] could be strong factors towards this direction. Another issue keeping short-term and LTRs' markets afar is the extensive use of housing units that would have remained out of circulation had it not been Airbnb entries; this is particularly the case with entries such as spare rooms, that could not be rented out to regular tenants [START_REF] Barron | The sharing economy and housing affordability: Evidence from airbnb[END_REF]. In some cases, this connection could even be reversed, with STRs causing rents' decrease, due to the overuse of commons by more people and the negative externalities the higher densities in uses and human flows the rise of P2P accommodation brings [START_REF] Sheppard | Do airbnb properties affect house prices? Department of Economics Working Papers[END_REF]. However, there are clear indications linking the STR phenomenon with rents' inflation [START_REF] Sans | Unravelling airbnb: Urban perspectives from Barcelona[END_REF]; the mobilization of tourism-oriented companies, which in many cases spread their investments across multiple geographical localities and pour a large number of listings into the P2P accommodation market, the stagnation of rent levels even amid recessive pressures that would normally cause shrinkage, or more importantly, the multiple cases where cities experience stark rates of rising rents, such as in San Francisco -which, ironically, is the home city of the Airbnb company itself. Most conducted studies conclude that a link between rising rents and STRs expansion is intuitively relevant and "straightforward" [START_REF] Sheppard | Do airbnb properties affect house prices? Department of Economics Working Papers[END_REF].

More specifically, one of the first works that theorized in a systematic way upon the aforementioned connection, identified two mechanisms that distort the housing market and limit the supply of affordable housing [START_REF] Lee | How airbnb short-term rentals exacerbate los angeles's affordable housing crisis: Analysis and policy recommendations[END_REF]. The first refers to the "simple conversion" of houses previously rented out long-term into Airbnb entries year-round. This mechanism generates a relatively insignificant rise in rents citywide, that mainly affects already gentrifying and affluent neighborhoods, as well as the downtown areas where the rental market is tighter. However, the impact of the second mechanism is argued to be more severe, and it refers to cases where landlords decide to turn whole buildings into Airbnb listings [START_REF] Sideris | Mapping the dominance of airbnb in athens: The worlds most popular short-term rental platform and how it is affecting our neighborhoods explained visually[END_REF]. In these instances of "hotelization", the supply of housing is significantly shrunk, spurring displacement and gentrification.

Today, it is widely believed that the link between STRs and rent-inflation is tangible and severely affects contemporary cities [START_REF] Lee | How airbnb short-term rentals exacerbate los angeles's affordable housing crisis: Analysis and policy recommendations[END_REF][START_REF] Wachsmuth | The high cost of short-term rentals in new york city[END_REF]. Empirically, existing research has managed to correlate a specific level of rents inflation to the expansion of STR markets in New York [START_REF] Sheppard | Do airbnb properties affect house prices? Department of Economics Working Papers[END_REF], Boston [START_REF] Horn | Is home sharing driving up rents? evidence from airbnb in boston[END_REF] and Barcelona [START_REF] Seg | Do short-term rent platforms affect rents? Evidence from Airbnb in Barcelona[END_REF]. [START_REF] Barron | The sharing economy and housing affordability: Evidence from airbnb[END_REF] The case of Athens, Greece

Data

Airbnb does not, so far, provide any data on the spread of its platform on the various cities it operates. Therefore, in order to examine its influence, external sources had to be used, like Inside Airbnb4 , a website providing both relevant data dumps and tools for downloading the desired information directly from Airbnb. More specifically, Inside Airbnb collects and publishes data dumps of the listings that appear on the P2P platform for various cities and on various dates (recently, it has been collecting data on an almost monthly basis). Each dump consists of a number of files that provide insight on different aspects of the phenomenon; describing in detail the collected listings, designating when each listing is available for rental on the platform and finally containing the reviews it has received so far.

LTR prices, on the other hand, are provided by RE/MAX [START_REF]Panhellenic survey for property rentals in 2018[END_REF], a private agency conducting surveys on the real estate market in Greece. RE/MAX releases data on LTRs and mean prices per neighborhood, which are conducted on an annual basis and regard the whole domestic market. It should be noted that the spatial boundaries of the neighborhoods in RE/MAX reports are different from the ones Airbnb uses. Fig. 1 shows Athens' neighborhoods as designated in the Airbnb platform. In order to achieve a controlled comparison between the data on short and long-term rentals, the neighborhoods from the private firm have been adapted to the Airbnb neighborhood format (as shown in Fig. 4).

In order to more thoroughly interpret the temporal as well as the spatial effect of STRs on LTRs within the City of Athens, two data dumps that have been obtained in the same month three years apart, were scrutinized (July 17 th , 2015 and July 16 th , 2018). The analysis mainly focused on the available listings. Initially, the number of listings per neighborhood have been examined, along with their relative change between 2015 and 2018 (Tbl. 1). Then, the density (number of listings per km 2 -Fig. 2) and its change throughout the study period have been calculated (Fig. 3). Additionally, the location quotient (LQ), a metric originating from the area of economic development has been computed for all neighborhoods. LQ is related to density and is used to determine the concentration of a characteristic in a particular area with respect to a wider area. In this case, it was defined as the ratio of a neighborhood's density to the overall density of the City of Athens (Tbl. 1).

Apart from the expansion of STRs in terms of magnitude and density, the interrelation between short and long-term rentals has been explored. Specifically, the above results have been compared with the changes in rent prices per neighborhood (Fig. 4), while at the same time it has been accounted for what they might mean for the wider area of Athens. It should also be noted that the Fig. 2. Density (number of listings per km 2 ) across Athens' neighborhoods as of July 16, 2018 followed analyis scheme, based on the spatial comparison of absolute numbers and densities for Airbnb listings, albeit a preliminary one, in in accordance with relevant research [START_REF] Lee | How airbnb short-term rentals exacerbate los angeles's affordable housing crisis: Analysis and policy recommendations[END_REF][START_REF] Wachsmuth | The high cost of short-term rentals in new york city[END_REF].

Discussion

The most obvious observation of our analysis is that Airbnb listings are increasing in skyrocketing rates, following the general trend of the "sharing economy". In the field of daily economic life in Athens, such an increase has come as an outlet for many landlords seeking to increase their earnings, avoid the risks of long-term tenancy (damages, unpaid bills etc.) or even allowing for segments of homeowners to continue living in rapidly appreciating housing markets [START_REF] Rousanoglou | Foreign investor invation in downtown athens[END_REF]. Our analysis reveals that these astonishing expansion tendencies in the STR market are geographically uneven. The overall increase in the number of listings between 2015 and 2018 is above 300% (Tbl. 1), whereas in specific neighborhoods the increments are much sharper. The results are deemed as expected, with central areas presenting the highest numbers, densities of listings and concentration Airbnb follows a multifactorial pattern of expansion; some areas appear exceptionally lucrative to visitors due to their vicinity to important landmarks, others for their central location, being at a walking distance from most entertainment and cultural spots and some for their convenient position within public transport networks. Koukaki-Makrygianni and Thiseio reflect the first case, exhibiting the biggest densities and concentrations (LQs) during the research period, most of the apartments listed offer a direct view on the Acropolis, with the neighborhood being in close distance to the Museums of Acropolis and of Modern Art. Emporiko Trigono-Plaka embodies the second case; a visitor choosing a place there is within the most vibrant part of the city. On the other hand, neighborhoods like Pangrati represent a convenient option, being close to the subway and boasting its own local mix of restaurants and bars, due to gentrifying processes in the recent years.

Airbnb's expansion is also asynchronous; traditionally dynamic areas in the STRs market, such as Emporiko Trigono-Plaka mentioned above, show stagnation signs, with steady rates of density and concentration. The market appears to be expanding outwards, as [START_REF] Seg | Do short-term rent platforms affect rents? Evidence from Airbnb in Barcelona[END_REF] noted for Barcelona as well, with underexploited central and western zones presenting noteworthy changes. The areas around Agios konstandinos-Plateia Vathis and Plateia Attikis show off their dynamism, experiencing sharp increases in STR volume, even if they do not constitute the safest parts of Athens.

In general, online P2P accommodation platforms have unlocked an array of cheaper choices in comparison to the price range in the regular hospitality industry for tourists and visitors alike, accommodating a more authentic experience that simulates a local way of living. Tourism boom in many geographical contexts can be directly attributed to the emergence of such platforms [START_REF] Seg | Do short-term rent platforms affect rents? Evidence from Airbnb in Barcelona[END_REF], be-cause, apart from more affordable choices, they offer an unmatched convenience of booking a room or a house and directly check a wider spectrum of prices and choices. Such choices can be divided into two categories: the cheap and the vibrant, "real-feel" neighborhoods. Plateia Attikis is a peripheral, not expensive neighborhood, with a notably high concentration of Airbnb activity, and the 542% increase in platform entries within the last 3 years is surely eye-catching. The area even though is one of the cheapest options, is close to public transit networks (Attikis Station). Exarcheia, on the other hand, is a neighborhood that attracts an alternative crowd of urban dwellers and the same has started being the case with tourists from abroad. Besides a diverse and vibrant downtown neighborhood, Exarcheia will be part of a forthcoming subway line, drawing the attention of international capital from China, Russia and Israel, which is invested in "ghost hotels" [START_REF] Sideris | Mapping the dominance of airbnb in athens: The worlds most popular short-term rental platform and how it is affecting our neighborhoods explained visually[END_REF]. Such investments can be seen as a logical market response within a context of rampant expanse, with investors and homeowners exploring their options even in areas that, albeit central, had not shown signs of increased activity until recently. Such areas represent a promise of higher yields; leaving the operation of unsafe, informal hotels -hidden as mere listings -aside, the above designate a moving away of Airbnb from the "casual entrepreneurship" of its first years and a formalization of its activities, as the very recent acquisition of HotelTonight by Airbnb has shown.

Lastly, the platform's expansion has been found to be relevant with significant rent hikes, turning housing in Athens less affordable. This is particularly evident in the areas mentioned above for their high Airbnb listings' densities and LQs: Koukaki-Makrygianni, Pangrati and Mouseio-Exarcheia-Neapoli. There -and especially in the first two -the increments are almost 50% within a 3-year span (Fig. 4). More specifically, it has been observed in the data that the said hike in LTR prices is highly correlated to the increased Airbnb activity over the studied period, as measured by three distinct correlation coefficients; the Pearson's r (0.76), the Spearman's ρ (0.74) and the Kendall's τ (0.67).

Overall, the rental market in Athens shows worrying signs of inflation. This reality is attributed to two main reasons; the available for renting housing stock has significantly shrunk and the LTRs receive heavy pressure from the STRs, as the conversion of rented apartments to Airbnb listings constitute an attractive choice for landlords. Furthermore, Airbnb in particular, has been identified in numerous reports and surveys as a crucial factor of reversing the negative climate of the whole Greek real estate market after 2017. At that point,the rental market stopped shrinking and started exhibiting signs of expansion, which are expected to intensify [START_REF]Panhellenic survey for property rentals in 2018[END_REF][START_REF] Antonakakis | Property market annual report 2017 greece[END_REF]. However, we should not attribute such rent increases solely to the negative externalities of the STRs market. We must identify, for the context of Athens, and the "positive cycle" as well [START_REF] Horn | Is home sharing driving up rents? evidence from airbnb in boston[END_REF]; the necessary renovations done to the existing housing stock, in order to be more attractive for the Airbnb users and the emerging array of local businesses that are positively affected by the increased pedestrian traffic (grocery stores, cafes -mainly those offering breakfast -services directed to urban tourists -such as luggage storage places) lead to an overall upgrading of the economic base and physical environment of these areas and to higher rents.

Conclusions

In this work, a preliminary study of the effect of STRs and more specifically those originating from the Airbnb P2P online platform, has been attempted. The increase in the number of listings within the City of Athens and its neighborhoods has been evaluated both quantitatively and qualitatively over a period spanning three years, during which the capital of Greece showed signs of reverting recession and growth, with respect to the real estate market. Emphasis has been placed on the spatial characteristics of the STR phenomenon, in terms of neighborhood density and LQ, with the findings being on a par with similar research studying the dynamics of the city. Additionally, an initial evaluation of the linkages between the spatial characteristics of Airbnb listings and shifts in the housing market has been affirmed, with the observed LTR hikes exhibiting a highly positive correlation with Airbnb expansion, as measured by three distinct correlation coefficients.

The obtained results are very informative and call for a more in-depth analysis of STR development in other dimensions as well. One such direction worth exploring is the fluctuation in STR prices in a temporal (e.g. time of the year) as well as a spatial context. The aforementioned analysis, could be further enhanced through the inclusion of more parameters (like house size, facilities, etc) that would most likely lead to the discovery of very interesting underlying knowledge.

Fig. 1 .

 1 Fig. 1. List of Athens' neighborhoods (numbering is according to Tbl. 1)

Fig. 3 .

 3 Fig. 3. Density (number of listings per km 2 ) change across Athens' neighborhoods between 2015 and 2018

Fig. 4 .

 4 Fig. 4. Percentage change in the mean price (in e) per month and m 2 for LTRs across Athens' neighborhoods between 2016 and 2018

Table 1 .

 1 Change in the number of Athens neighbourhoods' listings on Airbnb and the respective location quotients between July 17 th , 2015 and July 16 th , 2018

		Number of listings	Location Quotient
	id Neighbourhood	2015 July 17 th July 16 th 2018 Change	2015 July 17 th July 16 th 2018
	1 1o Nekrotafeio	15	46	207%	0.98	0.71
	2 Agios Eleftherios	10	32	220%	0.31	0.24
	3 Agios Konstantinos-Plateia Vathis	64	484	656%	1.31	2.34
	4 Agios Nikolaos	11	54	391%	0.64	0.74
	5 Akadimia Platonos	13	71	446%	0.15	0.20
	6 Akropoli	69	331	380%	0.96	1.09
	7 Ambelokipi	96	377	293%	0.76	0.71
	8 Ano Kypseli	31	78	152%	0.66	0.39
	9 Ano Patisia	23	77	235%	0.33	0.26
	10 Ellinoroson	6	52	767%	0.17	0.35
	11 Emporiko Trigono-Plaka	308	1,179	283%	3.51	3.17
	12 Gazi	27	84	211%	1.80	1.32
	13 Goudi	48	116	142%	0.35	0.20
	14 Gouva	23	67	191%	0.78	0.54
	15 Gyzi	27	96	256%	0.92	0.77
	16 Ilisia	61	201	230%	1.78	1.38
	17 Keramikos	62	217	250%	2.63	2.17
	18 Kolokynthou	3	12	300%	0.13	0.12
	19 Kolonaki	93	318	242%	2.16	1.74
	20 Kolonos	10	84	740%	0.22	0.44
	21 Koukaki-Makrygianni	117	723	518%	4.51	6.57
	22 Kypseli	54	229	324%	1.45	1.45
	23 Lykavittos	42	127	202%	1.04	0.75
	24 Mouseio-Exarcheia-Neapoli	164	790	382%	2.41	2.74
	25 Nea Kypseli	17	69	306%	0.70	0.67
	26 Neos Kosmos	146	635	335%	1.29	1.32
	27 Nirvana	16	96	500%	0.27	0.39
	28 Pangrati	132	476	261%	2.46	2.10
	29 Patisia	33	107	224%	0.61	0.47
	30 Pedio Areos	20	87	335%	0.49	0.50
	31 Pentagono	3	6	100%	0.17	0.08
	32 Petralona	83	285	243%	1.25	1.01
	33 Plateia Amerikis	30	114	280%	1.12	1.00
	34 Plateia Attikis	66	424	542%	1.18	1.79
	35 Polygono	11	30	173%	0.16	0.11
	36 Prombona	4	13	225%	0.15	0.11
	37 Rigillis	2	12	500%	0.53	0.75
	38 Rizoupoli	5	19	280%	0.14	0.12
	39 Rouf	-	-	-	-	-
	40 Sepolia	5	21	320%	0.13	0.12
	41 Stadio	46	223	385%	1.83	2.09
	42 Stathmos Larisis	8	58	625%	0.42	0.72
	43 Thiseio	60	266	343%	3.06	3.20
	44 Votanikos	19	77	305%	0.15	0.14
	45 Zappeio	33	105	218%	0.96	0.72
	Total	2,116	8,968	324%	-	-

https://airbnb.com/

http://insideairbnb.com


Oluwole Ajala
email: oluwole.ajala@kcl.ac.uk

Miznah Alshammary
email: miznah.alshammary@kcl.ac.uk

Mai Alzamel
email: mai.alzamel@kcl.ac.uk

Jia Gao
email: jia.gao@kcl.ac.uk

Costas Iliopoulos
email: c.ilioupoulos@kcl.ac.uk

Jakub Radoszewski

Wojciech Rytter
email: rytter@mimuw.edu.pl

Bruce Watson
email: bwwatson@sun.ac.za

On the cyclic regularities of strings

Keywords: Cyclic regularities, Periods, Covers

Regularities in strings are often related to periods and covers, which have extensively been studied, and algorithms for their efficient computation have broad application. In this paper we concentrate on computing cyclic regularities of strings, in particular, we propose several efficient algorithms for computing: (i) cyclic periodicity; (ii) all cyclic periodicity; (iii) maximal local cyclic periodicity; (iv) cyclic covers.

Introduction and Related Work

A fundamental concept of repeating patterns or regularities is that of periods (also known as powers). A period of order k is defined by a concatenation of k identical blocks of symbols. The study of periods can be traced to as far back as the early 1900s with the work of [START_REF] Thue | Uber unendliche zeichenreihen[END_REF], who researched a set of strings that do not contain any substrings that are periods. Periods in diverse forms gained prominence, when they became key structures in computational biology, where they are associated with various regulatory mechanisms and play an important role in genomic fingerprinting [START_REF] Kolpakov | mreps: efficient and flexible detection of tandem repeats in dna[END_REF].

In regularities in strings, one of the most general notions is related to period or power, for instance, given a string x of length n, a period k of a string x is a sub string of x, if it can be decomposed into equal-length blocks of symbols, such that x= u k u , where u is a prefix of u. However, for simplicity we will discard u and only consider u k . So far, regularities in strings related with periods and powers, which have been extensively studied, [3] [4] [5] [START_REF] Narayanan | Functions on antipower prefix lengths of the thue-morse word[END_REF] and algorithms for their efficient computation have broad applications. In this paper, we study cyclic factors of strings. The motivation of cyclic factors comes from viruses. The viruses are circular strings, for example Escherichia coli (E.coli) has 154 bases and it is circular [START_REF] Wurpel | Chaperoneusher fimbriae of escherichia coli[END_REF](Fig. 1).

Formally, the viruses break up at any point of the circle, for example, that can appear in the DNA sequence as x δ . . . x n x 1 . . . x δ-1 breaking up at position δ (Fig. 2). Now, we propose several efficient algorithms for computing: (i) cyclic periodicity; (ii) all cyclic periodicity; (iii) maximal local cyclic periodicity; (iv) cyclic covers.

Preliminaries

A string x of length |x| = n over an alphabet Σ of size σ can be denoted as

x[1 . . n] = x[1]x[2] . . . x[i] . . . x[n]
, where 1 ≤ i ≤ n and the i-th letter of x is denoted by x[i] ∈ Σ. The empty string is the string of length 0. The string x R is the reverse of string x. And x[i . . j], 1 ≤ i ≤ j ≤ n, denotes the contiguous substring (or factor) of letters, such as

x[i]x[i + 1]x[i + 2] . . . x[j]. A substring x[i . . j] is a suffix of x, if j = n and a substring x[i . . j] is a prefix of x, if i = 1.
Given a cyclic factor u of length k, 1 ≤ k ≤ n, we denote by c(u), for instance, u = ababc, c(u) is one of the following rotations: ababc, babca, abcab, bcaba, cabab. Moreover, we say u = u 1 u 2 . . . u n , c δ (u) = u δ . . . u n u 1 . . . u δ-1 .

In this paper, suffix trees are used extensively as computation tools. For a general introduction to suffix trees, see [START_REF] Crochemore | Algorithms on Strings[END_REF], [START_REF] Mccreight | A space-economical suffix tree construction algorithm[END_REF], [START_REF] Ukkonen | Constructing suffix trees on-line in linear time[END_REF], [START_REF] Weiner | Linear pattern matching algorithms[END_REF].

K-Cyclic Period

Input: Given a string x of length n, and an integer k < n, compute k-cyclicperiod of x, where Example 2. Consider a string x = aababa of length 6, a cyclic periodic array A as follows:

x = u 1 u 2 . . . u , u i = c(u j ), |u i | = |u j | = k, ∀ i, j, 1 ≤ i ≤ , 1 ≤ j ≤ ,
x[1] = a =⇒ A[1] := 1 x[1 . . 4] = aaba =⇒ A[4] := 1 x[1 . . 2] = a a =⇒ A[2] := 2 x[1 . . 5] = aabab =⇒ A[5] := 1 x[1 . . 3] = aab =⇒ A[3] := 1 x[1 . . 6] = aab aba =⇒ A[6] := 2
Definition 2. We define maximal local k-cyclic periodicity of a string x ,if a substring y is cyclic periodic and y is not a substring of another cyclic periodic strings.

Example 3. Consider a string x = aaaababaaab, Σ = {a, b}, and a substring y = aabababaa is 3-cyclic periodic and substring yα = aabababaaa, α ∈ Σ, is not cyclic periodic, and substring βy = aaabababaa, β ∈ Σ is not cyclic periodic.

Therefore, the substring y = aabababaa is maximal local 3-cyclic periodic in string x = aaaabababaaa. Definition 3. We say that a string x of length n is cyclic-coverable by a string u of length k , if and only if, for every position i of x, the following condition Proof. We construct the suffix tree of x (see [START_REF] Mccreight | A space-economical suffix tree construction algorithm[END_REF], [START_REF] Ukkonen | Constructing suffix trees on-line in linear time[END_REF], [START_REF] Weiner | Linear pattern matching algorithms[END_REF]). We let u

holds x[β . . γ] = c(u), 1 ≤ β ≤ i ≤ γ ≤ n.
= x[1 . . . k],
then let m denote the depth of the lowest common ancestor of x[1 .

. n] (see [START_REF] Bender | The LCA problem revisited[END_REF]), .

Proof. The smallest cyclic-period of x is the cyclic-period of x.

Fig. 1 .Fig. 2 .

 12 Fig.1. The E. coli K-12 MG1655 chromosome (outer black ring) was used as a reference map to visualise the locus position of 30 chromosome-borne CU fimbrial types. Types highlighted in blue are present in E. coli K-12 MG1655, types in red are absent in this strain. Fimbrial types associated with PAIs are indicated by an asterisk. A number of PAI associated fimbrial gene clusters occupy different locus positions relative to the MG1655 genome. tRNA sites that flank CU-containing PAIs are indicated on the inner blue ring.[START_REF] Wurpel | Chaperoneusher fimbriae of escherichia coli[END_REF]

Example 1 .

 1 and k × = n. Output: k-cyclic-period of x Consider a string x = aaabaabaabaabaaa =: u 1 u 2 u 3 u 4 , where u 1 = aaab, u 2 = aaba, u 3 = abaa, u 4 = baaa and k = 4, = 4. Therefore x has a period of length . Definition 1. A cyclic periodic array A of a string x of length n is defined to be as follows: A[i] := , 1 ≤ i ≤ n, if and only if x[1 . . i] has cyclic periodicity by a string u and there no u , with |u | ≤ |u| that is a cyclic period of x[1 . . i].

Example 4 .Definition 4 .Example 5 .3 Computing k-cyclic periodicity Theorem 1 .

 4451 Consider a string x = aababaa = u 1 u 2 , u 1 = aaba, u 2 = abaa, k = 4, γ = 2, is cyclic coverable by a string u, for every position i of x, x[1 . . 4] = x[4 . . 7] = c(u). Compute all cyclic covers of a given string x, that is for all possible length cyclic covers. Consider a string x = ababbaba, then ab, abab, ababb, ababbab are cyclic covers of x. Given a string x of length n and an integer k, 1 ≤ k ≤ n, test whether it is k-cyclic periodic; this can be determined in O(n/k) time and O(n) space.

4 Computing all cyclic periodicities Theorem 2 ..Lemma 1 .

 21 and x[i m . . n]. We compute the LCA m of x[1 . . n] and x[i m . . n] for i m = 2k, 3k, . . . , and k = n -k, if m = 1 for some m, then x is not k-cyclic periodic string. Now consider C rignt m = (u m +1 . . . u k ) R , compute the m the LCA of u R and C right m . If m ≥ m for all m, then x is k-cyclic periodic. Given a string x of length n, test whether it is k-cyclic periodicity for all 1 ≤ k ≤ n, this can be determined in O(n log n) time and O(n) space. Proof. We apply the algorithm of Theorem 1 for k = 1, 2, . . . , n and we test all cyclic periods of length k. The construction of the suffix tree of string x and x R is done once costing O(n). The total cost is O(n) + O( n k=1 n/k) = O(n log n) Compute the cyclic period of x.

Computing maximal local k-cyclic periodicity

Theorem 3. We can compute all k-cyclic periodicity of x in O(n log n) time.

Proof. We apply the algorithm for k = 1, 2, . . . , n and in this case, extend it to cyclic periods of length k + 1, where |y| = m is cyclic periodic and yα = m + 1 is not cyclic periodic. Next, we perform this algorithm on string x R as T (x R ), where |y| = m, again is cyclic periodic and βy = m + 1 is not cyclic periodic.

The construction of the suffix tree of string x is done once. The total cost is

. Proof. We compute and merge the arrays for yα and βy of x. That is the maximal local k-cyclic periodicity of x. Proof. We compute the suffix tree of string x as T (x), and also we compute the suffix tree of string x R as T (x R ).

Computing k -cyclic coverability

Then we check

together with the reverse pairs in T (x R ). This way we build a collection of cyclic covers if there is one.

The construction of the suffix tree costs O(n); checking of equality costs O [START_REF] Bender | The LCA problem revisited[END_REF] and there are n factors. The total time is O(n).

Computing all cyclic coverability

Theorem 5. Given a string x of length n, test whether it is k -cyclic coverable for 1 ≤ k ≤ n, this can be determined in O(n 2 ) time and O(n) space.

Proof. We apply the algorithm for k = 1, 2, . . . , n and we compare all cyclic coverable of length k . The construction of the suffix tree of string x is done once. The total cost is

. Lemma 3. Compute the cyclic coverability of x.

. Proof. The smallest cyclic coverable of x is the all the cyclic coveralbe of x.

Conclusions and open problems

In this paper, we defined k-cyclic periodicity, we presented several efficient algorithms for computing: (i) cyclic periodicity; (ii) all cyclic periodicity; (iii) maximal local cyclic periodicity; (iv) cyclic covers. Future work will be focused on computing the cyclic-periodic array, that is the cyclic periodicity of every prefix of string x and computing the cycliccoverability array, that is testing each prefix of x, for cyclic-coverability. Finally, we will extend the cyclic periodicity to cover the case u 1 u 2 u 2 . . . u k u 1 , where u i =c(u j ) ∀ i, j and u 1 is a substring of some u i .