Konstantin Avrachenkov
email: k.avrachenkov@inria.fr

Kishor Patil
email: kishor.patil@inria.fr

Gugan Thoppe
email: gugan.thoppe@gmail.com

Change Rate Estimation and Optimal Freshness in Web Page Crawling

come

Introduction

The world wide web is gigantic: it has a lot of interconnected information and both the information and the connections keep changing. However, irrespective of the challenges arising out of this, a user always expects a search engine to instantaneously provide accurate and up-to-date results. A search engine deals with this by maintaining a local cache of all the useful web pages and their links. As the freshness of this cache determines the quality of the search results, the search engine regularly updates it by employing a crawler (also referred to as a web spider or a web robot). The job of a crawler is (a) to access various web pages at certain frequencies so as to determine if any changes have happened to the content since the last crawled instance and (b) to update the local cache whenever there is a change. To understand the detailed working of crawlers, see [START_REF] Heydon | Mercator: A scalable, extensible web crawler[END_REF][START_REF] Castillo | Effective web crawling[END_REF][START_REF] Kumar | A survey of web crawling algorithms[END_REF][START_REF] Olston | Web crawling[END_REF][START_REF] Edwards | An adaptive model for optimizing performance of an incremental web crawler[END_REF].

In general, a crawler has two constraints on how often it can access a page. The first one is due to limitations on the available bandwidth. The second one-also known as the politiness constraint-arises when a server imposes limits on the crawl frequency. The latter implies that the crawler can not access pages on that server too often in a short amount of time. Such constraints cannot be ignored, since otherwise the server may forbid the crawler from all future accesses.

In summary, to identify the ideal rates for crawling different web pages, a search engine needs to solve the following optimisation problem: Maximise the freshness of the local database subject to constraints on the crawling frequency.

In the early variants of this problem, the freshness of each page was assumed to be equally important [START_REF] Cho | a database to improve freshness[END_REF][START_REF] Edwards | An adaptive model for optimizing performance of an incremental web crawler[END_REF]. In such cases, experimental evidence surprisingly shows that the uniform policy-crawl all pages at the same frequency irrespective of their change rates-is more or less the optimal crawling strategy.

Starting from the pioneering work in [9], however, the freshness definition was modified to include different weights for different pages depending on their importance, e.g., represented as the frequency of requests for the pages. The motivation for this change was the fact that only a finite number of pages can be crawled in any given time frame. Hence, to improve the utility of the local database, important pages should be kept as fresh as possible. Not surprisingly, under this new definition, the optimal crawling policy does indeed depend on the page change rates. This was numerically demonstrated first in [9] for a setup with a small number of pages. A more rigorous derivation of this fact was recently given in the path breaking paper [START_REF] Azar | Tractable near-optimal policies for crawling[END_REF] by Azar et al. In fact, this work also provides a near-linear time algorithm to find a near-optimal solution.

A separate study [START_REF] Avrachenkov | Whittle index policy for crawling ephemeral content[END_REF][START_REF] Niño-Mora | A dynamic page-refresh index policy for web crawlers[END_REF] provides a Whittle index based dynamic programming approach to optimise the schedule of a web crawler. In that context, the page/catalogue freshness estimate also influences the optimal crawling policy and its good estimation is needed.

Our work is mainly motivated by the work from Azar et al. [START_REF] Azar | Tractable near-optimal policies for crawling[END_REF]. In particular, input to their algorithm is the actual page change rates. However, in practice, these values are not known in advance and, instead, have to be estimated. This is the issue that we address in this paper.

Our main contributions can be summarised as follows. First, we propose two novel approaches for online estimation of the actual page change rates. The first is based on the Law of Large Numbers (LLN), while the second is derived using the Stochastic Approximation (SA) principles. Second, we theoretically show that both these estimators almost surely (a.s.) converge to the actual change rate values, i.e., both our estimators are asymptotically consistent. Furthermore, we also derive their convergence rates in the expected error sense. Finally, we provide some simulation results to compare the performance of our online schemes to each other and also to that of the (offline) MLE estimator. Alongside, we also show how our estimates can be combined with the algorithm in [START_REF] Azar | Tractable near-optimal policies for crawling[END_REF] to obtain near-optimal crawling rates.

The rest of this paper is organised as follows. The next section provides a formal summary of this work in terms of the setup, goals, and key contributions. It also gives the explicit update rules for our two online schemes. In Section 3, we discuss their convergence and converge rates and also provide the formal analysis for the same. The numerical experiments discussed above are given in Section 4. We conclude in Section 5 with some future directions.

Setup, Goal, and Key Contributions

The three topics are individually described below.

Setup: We assume the following. The local cache consists of copies of N pages and w i denotes the importance of the i-th page. Further, each page changes independently and the actual times at which page i changes is a homogeneous Poisson point process in [0, ∞) with a constant but unknown rate ∆ i . Independent of everything else, page i is crawled (accessed) at the random instances {t k } k≥0 ⊂ [0, ∞), where t 0 = 0 and the inter-arrival times, i.e., {t k -t k-1 } k≥1 , are iid exponential random variables with a known rate p i . Thus, the times at which page i is crawled is also a Poisson point process but with rate p i . At time instance t k , we get to know if page i got modified or not in the interval (t k-1 , t k ], i.e., we can access the value of the indicator

I k := 1, if page i got modified in (t k-1 , t k ],
0, otherwise.

We emphasise that each page is crawled independently. In other words, the notations {t k } and {I k } defined above do depend on i. However, we hide this dependence for the sake of notational simplicity. We shall follow this practice for the other notations as well; the dependence on i should be clear from the context.

Although the above assumptions are standard in the crawling literature, nevertheless, we now provide a quick justification for the same. Our assumption that the page change process is a Poisson point process is based on the experiments reported in [START_REF] Brewington | How dynamic is the web?[END_REF][START_REF] Brewington | Keeping up with the changing web[END_REF][START_REF] Cho | The evolution of the web and implications for an incremental crawler[END_REF]. Some generalised models for the page change process have also been considered in the literature [START_REF] Matloff | Estimation of internet file-access/modification rates from indirect data[END_REF][START_REF] Singh | Estimating the rate of web page updates[END_REF]; however, we do not pursue these ideas here. Separately, our assumption on {I k } is based on the fact that a crawler can only access incomplete knowledge about the page change process. In particular, a crawler does not know when and how many times a page has changed between two crawling instances. Instead, all it can track is the status of a page at each crawling instance and know if it has changed or not with respect to the previous access. Sometimes, it is possible to also know the time at which the page was last modified [START_REF] Castillo | Effective web crawling[END_REF][START_REF] Cho | Estimating frequency of change[END_REF], but we do not consider this case here.

Goal: Develop online algorithms for estimating ∆ i in the above setup. Subsequently, find optimal crawling rates {p * i } so that the overall freshness of the local cache defined by

E 1 T T 0 N i=1 w i 1{Fresh(i, t)} dt (1)
is maximised subject to

N i=1 p i ≤ B.
Here, T > 0 is some finite horizon, B ≥ 0 is a bound on the overall crawling frequency, 1{} is the indicator, and Fresh(i, t) is the event that page i is fresh at time t, i.e., the local copy matches the actual page.

Key Contributions:

We present two online methods for estimating ∆ i , the first based on the LLN and the second based on SA. If {x k } and {y k } denote the iterates of these two methods, then their update rules are as shown below.

• LLN Estimator : For k ≥ 1,

x k = p i Îk /(k + α k -Îk ). (2)
Here, Îk = k j=1 I j ; hence, Îk = Îk-1 + I k . And, {α k } is any positive sequence satisfying the conditions in Theorem 1; e.g., {α k } could be {1}, {log k}, or { √ k}.

• SA Estimator : For k ≥ 0 and some initial value y 0 ,

y k+1 = y k + η k [I k+1 (y k + p i ) -y k ]. (3)
Here, {η k } is any stepsize sequence that satisfies the conditions in Theorem 2. For example, {η k } could be {1/(k + 1) γ } for some γ ∈ (0, 1].

We call these methods online because the estimates can be updated on the fly as and when a new observation I k becomes available. This contrasts the MLE estimator in which one needs to start the calculation from scratch each time a new data point arrives. Also, unlike MLE, our estimators are never unstable. See Section 3.3 for the complete details on this.

Our main results include the following. We show that both {x k } and {y k } converge to ∆ i a.s. Further, we show that

1. E x k -∆ i = O max k -1/2 , α k /k , and 2. E y k -∆ i = O(k -γ/2 ) if η k = (k + 1) γ with γ ∈ (0, 1).
Finally, we provide three numerical experiments for judging the strength of our two estimators. In the first one, we compare the performance of our estimators to each other and also to that of the Naive estimator and the MLE estimator described in [START_REF] Cho | Estimating frequency of change[END_REF]. In the second one, we combine our estimates with the algorithm in [START_REF] Azar | Tractable near-optimal policies for crawling[END_REF] and compute the optimal crawling rates. Subsequently, we use this to measure the overall freshness of the local cache. In the last and final experiment, we look at the behaviour of our estimators for different choices of the sequences {α k } and {η k }.

Change rate estimation

Here, we provide a formal convergence and convergence rate analysis for our two estimators. Thereafter, we compare their behaviours to that of the estimators that already exist in the literature-the Naive estimator, the MLE estimator, and the Moment Matching (MM) estimator.

LLN Estimator

Our first aim here is to obtain a formula for E[I 1 ]. We shall use this later to motivate the form of our LLN estimator.

Let

τ 1 = t 1 -t 0 = t 1 .
Then, as per our assumptions in Section 2, τ 1 is an exponential random variable with rate p i . Also, E[I 1 |τ 1 = τ ] = 1 -exp (-∆ i τ ). These two facts put together show that

E I 1 = ∆ i /(∆ i + p i ). ( 4
)
This gives the desired formula for

E[I 1 ].
From this last calculation, we have

∆ i = p i E[I 1 ]/(1 -E[I 1 ]) (5)
Separately, because {I k } is an iid sequence and E|I 1 | ≤ 1 , it follows from the strong law of large numbers that E I 1 = lim k→∞ k j=1 I j /k a.s. Thus,

∆ i = p i lim k→∞ k j=1 I j /k 1 -lim k→∞ k j=1 I j /k a.s.
Consequently, a natural estimator for ∆ i is

x k = p i k j=1 I j /k 1 - k j=1 I j /k = p i Îk k -Îk , ( 6
)
where Îk is as defined below (2). Unfortunately, the above estimator faces an instability issue, i.e., x k = ∞ when I 1 , . . . , I k are all 1. To fix this, one can add a non-zero term in the denominator. The different choices then gives rise to the LLN estimator defined in [START_REF] Azar | Tractable near-optimal policies for crawling[END_REF].

The following result discusses the convergence and convergence rate of this estimator.

Theorem 1. Consider the estimator given in (2) for some positive sequence {α k }.

1. If lim k→∞ α k /k = 0, then lim k→∞ x k = ∆ i a.s. 2. Additionally, if lim k→∞ log(k/α k )/k = 0, then E|x k -∆ i | = O max k -1/2 , α k /k . Proof. Let µ = E[I 1 ], I k = Îk /k, and α k = α k /k.
Then, observe that (2) can be rewritten as

x k = p i I k /(1+α k -I k )
. Now, lim k→∞ I k = µ a.s. and lim k→∞ α k = 0. The first claim holds due to the strong law of large numbers, while the second one is true due to our assumption. Statement ( 1) is now easy to see. We now derive Statement (2). From (5), we have

|x k -∆ i | = x k -p i µ 1 -µ ≤ p i (|A k | + |B k |) ,
where

A k = I k α k + 1 -I k - µ α k + 1 -µ and B k = µ α k + 1 -µ - µ 1 -µ .
Since α k > 0 and, hence, α k > 0,

|B k | = α k µ (1 -µ)(α k + (1 -µ)) ≤ α k µ (1 -µ) 2 .
Similarly,

|A k | ≤ 1 + α k 1 -µ |I k -µ| α k + 1 -I k .
Because we have assumed α k → 0, we get lim k→∞ E[B k ] = 0. It remains to show lim k→∞ E[A k ] = 0. Towards that, let {δ k } be a positive sequence that we will pick later.

Then,

E |I k -µ| α k + 1 -I k ≤ E[C k ] + E[D k ]
where

C k = |I k -µ| α k + 1 -I k 1 I k -µ ≤ δ k µ and D k = |I k -µ| α k + 1 -I k 1 I k -µ ≥ δ k µ .
On the one hand,

E[C k ] ≤ E|I k -µ| α k + 1 -(1 + δ k )µ ≤ Var[I 1 ] √ k(α k + 1 -(1 + δ k )µ) .
On the other hand, since |I k -µ| ≤ 2 and 1 -I k ≥ 0, it follows by applying the Chernoff bound that

E[D k ] ≤ 2 α k Pr{I k ≥ (1 + δ k )µ} ≤ 2 α k exp -kδ 2 k µ/3 .
We now pick {δ k } so that δ 2 k = 6 log(1/ α k )/(kµ) for all k ≥ 1. Then, E[D k ] ≤ 2α k . Now, due to our assumptions on {α k }, lim k→∞ E[D k ] = 0. Similarly, lim k→∞ δ k = 0, whence it follows that lim k→∞ E[C k ] = 0. These relations together then show that lim k→∞ E[A k ] = 0.

The desired result now follows.

SA Estimator

Here, we use the theory of stochastic approximation to study the behaviour of our SA estimator.

Theorem 2. Consider the estimator given in (3) for some positive stepsize sequence {η k }.

Suppose that

∞ k=0 η k = ∞ and ∞ k=0 η 2 k < ∞. Then, lim k→∞ y k = ∆ i a.s. 2. Suppose that η k = 1/(k + 1) γ with γ ∈ (0, 1). Then, E y k -∆ i = O k -γ/2 .
Proof. For k ≥ 0, let F k := σ(∆ 0 , I 1 , . . . , I k ). Then, from (4) and the fact that {I k } is an iid sequence, we get

E[I k+1 (y k + p i ) -y k |F k ] = ∆ i ∆ i + p i (y k + p i ) -y k = h(y k ),
where h(y) = (∆ i -y)p i /(∆ i + p i ). Hence, one can rewrite (3) as

y k+1 = y k + η k [h(y k ) + M k+1 ], (7)
where

M k+1 = [I k+1 (y k + p i ) -y k ] -h(y k ) = I k+1 - ∆ i ∆ i + p i (y k + p i ).
Since E[M k+1 |F k ] = 0 for all k ≥ 0, {M k } is a martingale difference sequence. Consequently, ( 7) is a classical SA algorithm whose limiting ODE is

ẏ(t) = h(y). (8)
Now, Statement (1) follows from Corollary 4 and Theorem 7 in Chapters 2 and 3, respectively, of [START_REF] Borkar | Stochastic approximation: a dynamical systems viewpoint[END_REF], provided we show that: i.) h is a globally Lipschitz continuous function.

ii.) ∆ i is an unique globally asymptotically stable equilibrium of (8).

iii.)

∞ k=0 η k = ∞ and ∞ k=0 η 2 k < ∞. iv.) {M k } is a martingale difference sequence with respect to the filtration {F k }. Further, there is a constant C ≥ 0 such that E[M 2 k+1 |F k ] ≤ C(1 + y 2 k ) a.
s. for all k ≥ 0. v.) There exists a continuous function h ∞ such that the functions h c (x) := h(cx)/c, c ≥ 1, satisfy h c (x) → h ∞ (x) uniformly on compact sets as c → ∞.

vi.) The ODE ẏ(t) = h ∞ (y) has origin as its unique globally asymptotically stable equilibrium.

Since h is linear, the Lipschitz continuity condition trivially holds. Separately, observe that h(∆ i ) = 0; this shows that ∆ i is an equilibrium point of [START_REF] Cho | a database to improve freshness[END_REF]. Now, L(y) = (y -∆ i ) 2 /2 is a Lyapunov function for [START_REF] Cho | a database to improve freshness[END_REF] with respect to ∆ i . This is because L(y) ≥ 0, while ∇L(y)h(y) = -p(y -∆ i ) 2 /(p i + ∆ i ) ≤ 0; the equality holds in both these relations if and only if y = ∆ i . This shows that ∆ i is a unique globally asymptotically stable equilibrium of (8), which establishes Condition ii.).

Condition iii.) trivially holds due to our assumption about {η k }. Regarding the next condition, observe that {M k } is indeed a martingale difference sequence. Further, |M k+1 | ≤ |y k | + p i , whence it follows that Condition iv.) also holds.

Next, let h ∞ (y) := -yp i /(∆ i + p i ). Then, it is easy to see that Condition v.) trivially holds. Similarly, it is easy to see that Condition vi.) holds as well.

Statement (1) now follows, as desired. We now sketch a proof for Statement [START_REF] Azar | Tractable near-optimal policies for crawling[END_REF]. First, note that

y k+1 -∆ i = (1 -λη k )(y k -∆ i ) + η k M k+1 , where λ = p i /(∆ i + p i ). Now, since E[M k+1 |F k ] = 0, E[(y k+1 -∆ i ) 2 |F k ] = (1 -λη k ) 2 (y k -∆ i ) 2 + η 2 k E[M 2 k+1 |F k ]. Recall that E[M 2 k+1 |F k ] ≤ C(1 + y 2 k )
for some constant C ≥ 0. Using this above and then repeating all the steps from the proof of [START_REF] Dalal | Finite sample analyses for td (0) with function approximation[END_REF]Theorem 3.1] gives Statement (2), as desired.

Comparison with Existing Estimators

As far as we know, there are three other approaches in the literature for estimating page change rates-the Naive estimator, the MLE estimator, and the MM estimator. The details about the first two estimators can be found in [START_REF] Cho | Estimating frequency of change[END_REF] while, for the third one, one can look at [START_REF] Upadhyay | Learning to crawl[END_REF]. We now do a comparison, within the context of our setup, between these estimators and the ones that we have proposed.

The Naive estimator simply uses the average number of changes detected to approximate the rate at which a page changes. That is, if {z k } denote the values of the Naive estimator then, in our setup, z k = p i Îk /k, where Îk is as defined below in [START_REF] Azar | Tractable near-optimal policies for crawling[END_REF]. The intuition behind this is the following. If τ 1 is as defined at the beginning of Section 3.1, then observe that E[N (τ 1 )] = ∆ i /p i . Hence, the Naive estimator tries to approximate E[N (τ 1 )] with Îk /k so that the previous relation can then be used for guessing the change rate.

Clearly, E[z k ] = p i ∆ i /(∆ i + p i ) = ∆ i . Also, from the strong law of large numbers, z k a.s.

→ p i ∆ i /(∆ i + p i ) = ∆ i .
Thus, this estimator is not consistent and is also biased. This is to be expected since this estimator does not account for all the changes that occur between two consecutive accesses.

Next, we look at the MLE estimator. Informally, this estimator identifies the parameter value that has the highest probability of producing the observed set of observations.In our setup, the value of the MLE estimator is obtained by solving the following equation for ∆ i :

k j=1 I j τ j /(exp (∆ i τ j ) -1) = k j=1 (1 -I j ) τ j , (9)
where τ k = t k -t k-1 and {t k } is as defined in Section 2. The derivation of this relation is given in [10, Appendix C]. As mentioned in [10, Section 4], the above estimator is consistent. Note that the MLE estimator makes actual use of the inter-arrival crawl times {τ k } unlike our two estimators and also the Naive estimator. In this sense, it fully accounts for the randomness in crawling intervals. And, as we shall see in the numerical section, the quality of the estimate obtained via MLE improves rapidly in comparison to the Naive estimator as the sample size increases.

However, MLE suffers in two aspects-computational tractability and mathematical instability. Specifically, note that the MLE estimator lacks a closed form expression. Therefore, one has to solve (9) by using numerical methods such as the Newton-Raphson method, Fisher's Scoring Method, etc. Unfortunately, using these ideas to solve (9) takes more and more time as the number of samples grow. Also note that, under the above solution ideas, the MLE estimator works in an offline fashion. In that, each time we get a new observation, (9) needs to be solved afresh. This is because there is no easy way to efficiently reuse the calculations from one iteration into the next. One reasonable alternative is to perform MLE estimation in a batch mode, i.e., wait until we gather a large number of samples and then apply one of the above-mentioned methods. However, even then the computation time will be long when k is large.

Besides the complexity, the MLE estimator is also unstable in two situations. One, when no changes have been detected (I j = 0, ∀k ∈ {1, . . . , k}), and the other, when all the accesses detect a change (I j = 1, ∀k ∈ {1, . . . , k}). In the first setting, no solution exists; in the second setting, the solution is ∞. One simple strategy to avoid these instability issues is to clip the estimate to some pre-defined range whenever one of bad observation instances occur.

Finally, we talk about the MM estimator. Here, one looks at the fraction of times no changes were detected during page accesses and, then, using a moment matching method tries to approximate the actual page change rate. In our context, the value of this estimator is obtained by solving k j=1 (1 -I j ) = k j=1 e -∆iτj for ∆ i . The details of this equation are given in [START_REF] Upadhyay | Learning to crawl[END_REF]Section 4]. While the MM idea is indeed simpler than MLE, the associated estimation process continues to suffer from similar instability and computational issues like the ones discussed above.

We emphasise that none of our estimators suffer from any of the issues mentioned above. In particular, both our estimators are online and have a significantly simple update rule; thus, improving the estimate whenever a new data point arrives is extremely easy. Also, both our estimators are stable, i.e., the estimated values will almost surely be finite. More importantly, the performance of our estimators is comparable to that of MLE. This can be seen from the numerical experiments in Section 4.

Numerical Results

In this section, we provide three simulations to help evaluate the strength of our estimators.

In the first experiment, we look at how well our estimation ideas perform in comparison to the Naive and the MLE estimator. In the second experiment, we substitute the change rate estimates obtained via the above approaches into the algorithm given in [START_REF] Azar | Tractable near-optimal policies for crawling[END_REF] and compute the optimal crawling rates. To judge the quality of the crawling policy so obtained, we also look at the associated average freshness as defined in [START_REF] Avrachenkov | Whittle index policy for crawling ephemeral content[END_REF]. Finally, in the third experiment, we compare the performance of our two estimators for different choices of {α k } and {η k }, respectively.

Expt. 1: Comparison of Estimation Quality

Here, we compare four different page rate estimators: LLN, SA, Naive, and MLE. Their performances can be seen in Fig 1 . We now describe what is happening in the two figures there. Unless specified, the notations are as in Section 2. In Fig. 1(a), we work with exactly one page. We suppose that the times at which this page changes is a homogeneous Poisson point process with rate ∆ 1 = 5. Separately, we set the crawling frequency arbitrarily to be p 1 = 3. This implies that the times at which we crawl this page is another Poisson point process with rate p 1 = 3.

Using the above parameters, we now generate the random time instances at which this page changes. Alongside, we also sample the time instances at which this page is crawled. We then check if the page has changed or not between two successive page accesses. This generates the values of indicator sequence {I k }.

We now give {I k }, {τ k }, and p i as input to the four different estimators mentioned above and analyse their performances. The trajectory shown in Fig. 1(a) corresponds to exactly one run of each estimator. Note that the trajectory of the estimates obtained by the SA estimator is labelled ∆ SA 1 , etc. For the SA estimator, we had set η k = (k + 1) -γ with γ = 0.75. On the other hand, for our LLN estimator, we had set α k ≡ 1.

In Fig. 1(b), the parameter values are exactly in Fig. 1(a). However, we now run the simulation 1000 times; the page change times and the page access times are generated afresh in each run. We then look at the 95% confidence interval of the obtained estimates.

We now summarise our findings. Clearly, in each case, we can observe that performances of the MLE, LLN, and the SA estimators are comparable to each other and all of them outperform the Naive estimator. This last observation is not surprising since the Naive estimator completely ignores the missing changes between two crawling instances. However, the fact that the estimates from our approaches are close to that of the MLE estimator-both in terms of mean and variance-was indeed surprising to us. This is because, unlike MLE, our estimators completely ignore the actual lengths of the intervals between two accesses. Instead, they use p i , which only accounts for the mean interval length. While the plots do not show this, we once again draw attention to the fact that the time taken by each iteration in MLE rapidly grows as k increases. However, our estimators take roughly the same amount of time for each iteration.

Expt. 2: Optimal Crawling rates and Freshness

In this experiment, we consider N = 100 pages together. The {∆ i } sequence-the mean rates pages-is obtained sampling from the uniform distribution on [0, 1], i.e., ∆ i ∼ U [0, 1]. We further assume that the bound on the overall bandwidth is B = 80. The initial crawling frequencies for different pages are set by breaking up B evenly across all pages, i.e., p i = B/N = 0.8 for all i. Because the p i values are arbitrarily chosen, these are not the optimal crawling rates. We then independently generate the change and access times for each page as in Expt. 1. Subsequently, we estimate the unknown change rate for each page individually.

For each k, we then substitute the change rate estimates given by the different estimators into [2, Algorithm 2] and obtain the associated optimal crawling rates. In the same way, we substitute the actual ∆ i values there and obtain the true optimal crawling rates. Fig. 2(a) provides a comparison between these values for a single page. We can see that the estimate of the optimal crawling rate obtained from our approaches is much better than that of the Naive estimator.

To check how good our estimate of the true optimal crawling policy is, we look at the associated average freshness given by1 F (p) = N i=0 w i p i p i + ∆ i [START_REF] Cho | Estimating frequency of change[END_REF] and compare the same to that of the true optimal crawling policy. This comparison is given in Fig. 2(b). Somewhat surprisingly, the average freshness does not vary much for all the three estimators. However, eventually, the average freshness captured by our estimators becomes much closer to the true optimal average freshness.

Figure 1 :

 1 Figure 1: Comparison between Different Estimators.

Figure 2 :

 2 Figure 2: Optimal Crawling Rates and Freshness

In[START_REF] Azar | Tractable near-optimal policies for crawling[END_REF], it was shown that maximising (1) under a bandwidth constraint for large enough T corresponds to maximising[START_REF] Cho | Estimating frequency of change[END_REF] under the same bandwidth constraint.

Acknowledgement

This work is partly supported by ANSWER project PIA FSN2 (P15 9564-266178 \DOS0060094) and DST-Inria project "Machine Learning for Network Analytics" IFC/DST-Inria-2016-01/448.

The details are as follows. Here, again, we restrict our attention to one single page. For Fig. 3(a), we chose ∆ = 1000 and p = 200. Notice that the page change rate is very high, whereas the crawling frequency is relatively a low value. We then used the LLN estimator with three different choices of {α k }; these choices are shown in the figure itself. The LLN estimator with α k = k 0.75 has the worst performance. This behaviour matches the prediction made by Theorem 1.

In Fig. 3(b), we again consider the same setup as above. However, this time we run the SA estimator with three different choices of {η k }; the choices are given in the figure itself. We see that the performance for γ = 0.75 is better than the γ = 0.5 case. This is as predicted in Theorem 2. However, it worsens for the γ = 1 case. Notice that the latter case is not covered by Theorem 2.

Conclusion and Future work

We proposed two new online approaches for estimating the rate of change of web pages. Both these estimators are computationally efficient in comparison to the MLE estimator. We first provide theoretical analysis on the convergence of our estimators and then provide numerical simulations to compare their performance with the existing estimators in the literature. From numerical experiments, we have verified that the proposed estimators perform significantly better than the Naive estimator and have extremely simple update rules which make them computationally attractive.

The performance of both our estimators currently depend on the choice of {α k } and {η k }, respectively. One aspect to analyse in the future would be to ask what would be the ideal choice for these sequences that would help attain the fastest convergence rate. Another interesting research direction is to combine the online estimation with dynamic optimisation.


Markus Suta

Flavie Lavoie-Cardinal

Jacob Olchowka

Claudia Wickleder
email: wickleder@chemie.uni-siegen.de

Nature of localized excitons in CsMgX 3 (X = Cl, Br, I) and their interactions with Eu 2+ ions †

Supplementary Information available: X-ray powder diffraction patterns of the undoped halides CsMgX3 (X = Cl, Br, I). ‡ These authors contributed equally.

In this paper, the luminescence properties of self-trapped excitons (STEs) of undoped and Eu 2+ doped perovskite-type materials CsMgX3 (X = Cl, Br, I) are presented. The three compounds crystallize isostructurally in a hexagonal crystal system that exhibits an intrinsic pseudo one-dimensionality. This feature has a highly stabilizing effect upon the localization of excitons. Similarities to the properties of STEs in alkali halides are drawn that are justified by band structure and density of states (DOS) calculations.The luminescence spectra of all three halides are characterized and interpreted despite of their high complexity with many emissive transitions. It is illustrated that both self-trapped excitons (STEs) and impurity-localized self-trapped excitons (IL-STEs) are responsible for the features in the spectra . The impurity localization of the STEs is proven by doping the hosts with Sr 2+ ions instead of Eu 2+ ions. The decay times in the µs range indicate that emission predominantly occurs from a triplet state of the STEs with a prominent afterglow component for the IL-STEs that ideally suits a trapping model along the one-dimensional chains of the halides. Moreover, by thermal activation, the excitons tend to annihilate at the Eu 2+ traps thereby inducing an energy transfer to the Eu 2+ ions. Due to this action, an extreme increase of the intensity of the Eu 2+ -based 4f 6 5d-4f 7 emission at room temperature could be observed, which might be a general explanation for unusual temperature-dependent emission intensities of Eu 2+ ions. In general, an understanding of the basic optical properties of the STEs may give some new insights into the mechanism of currently used X-ray storage phosphors as well as scintillators.

Introduction

Many phosphors gain their luminescence properties by the intentional addition or even total composition of activators such as lanthanides, transition metals or s 2 ions. Their applications range from light-emitting diode (LED) phosphors over lasing materials to X-ray storage phosphors and scintillators [START_REF] Yen | Phosphor Handbook[END_REF]. Particularly for the last two applications, however, the optical properties of intrinsic defects that arise upon formation of excitons by incident ionizing radiation plays a major role in the mechanistic details of the luminescence process [START_REF] Rodnyi | Physical Processes in Inorganic Scintillators[END_REF], [START_REF] Lecoq | Inorganic Scintillators for Detector Systems[END_REF]. Moreover, defects are generally created by doping if the size and/or the charge of the dopants and the substituted ion of the host does not coincide. In these cases, the defects influence the optical properties of the compounds usually remarkably due to quenching of the emissions of the activators or even due to intrinsic emission of defects stabilized by lattice distortions [START_REF] Rodnyi | Physical Processes in Inorganic Scintillators[END_REF], [START_REF] Lecoq | Inorganic Scintillators for Detector Systems[END_REF]. One prominent example is the X-ray storage phosphor BaFBr:Eu 2+ , in which it was shown that point defects such as color centers are correlated to the local Eu 2+ impurities thereby influencing its photostimulable luminescence (PSL) properties [START_REF] Rüter | [END_REF], [5]. Therefore, defects and excitons are of key importance concerning the luminescence properties and the efficiency of materials and are, thus, worth to be investigated in detail.

In ionic insulators such as alkali halides, a created hole shows a high tendency for self-localization due to the high strength of the coupling to longitudinal optical (LO) phonons in these compounds that supports the formation of a polaronic quasiparticle [6], [7], [8], [9]. Upon attraction of the electron, these self-trapped excitons (STEs) have a rich electronic structure that gives rise to complicated luminescence [10], [11], [12], [13], [14], [15] and electron paramagnetic resonance (EPR) spectra [16], [17], [18], [19]. The literature on the optical and magnetic properties of STEs in binary alkali halides is very exhaustive and a very broad overview over the different properties is given in a review and a book by Song and Williams in the 1990s [20], [START_REF] Song | Self-trapped excitons[END_REF]. Since then, however, no comparably detailed literature on the optical properties of self-trapped excitons in more complex halides has been published so far.

In binary halides it is now established that STEs can be well described by a "molecule in a lattice" configuration, in which the self-trapped hole forms a dimer anion X 2 -(X = Cl, Br, I) and attracts the additional loosely bound electron without strong perturbation by the surrounding crystal field [16], [START_REF] Gilbert | [END_REF], [23]. This (V K + e) or on-centre configuration is highly unstable against adiabatic relaxation in the lighter halides, in which the electron first occupies an adjacent anion vacancy thus pushing the hole to the other anion vacancy [24], [25], [26]. A theoretical explanation for this phenomenon was first convincingly given by Toyozawa upon inclusion of a pseudo Jahn-Teller mixing between the excited -and -like states of the electron [27]. From this off-centre configuration, further separation of the electron and the hole gives rise to a separated F-H defect pair [25], [26], [28], [29], which has also been proven experimentally [30]. It has been moreover shown in detailed investigations that this configuration is basically determined by the geometry of the crystal lattice that is parametrized according to Rabin and Klick (see also section 3.2) [28], [31], [32]. Besides binary alkali halides, there are only few examples of more complex halides that were investigated regarding their intrinsic luminescence such as BaFX (X = Cl, Br, I) [33], [34], [35], [36], NH 4 X (X = Cl, Br, I) [37], [38] or the fluoride-based perovskites AMgF 3 (A = K, Rb, Cs) [39], [40], [41], [42]. One special class of halides that are interesting in this context are representatives of the CsNiCl 3 crystal structure such as CsMnBr 3 and CsCdBr 3 [43], [44], [45]. It is well-known from these compounds that they show intrinsic luminescence ascribed to self-trapped excitons [46], [47], [48], [49], [50], [51], [52], [53]. Compounds of this structure type exhibit an | 2 intrinsic pseudo one-dimensionality due to linear chains of face-sharing coordination octahedra that allows a spontaneous self-trapping of excitons by electron-phonon coupling without a potential barrier [54]. This phenomenon is already well investigated in the , in which the exciton forms as a result of an intervalence charge transfer (IVCT) and becomes self-trapped along a Peierls-distorted one-dimensional chain [START_REF] Song | Self-trapped excitons[END_REF], [55], [56]. The one-dimensionality also allows for a movement of the excitation energy through the lattice along the linear chains thus also enabling energy transfer processes [52], [53]. Thus, such systems are ideally suited for the investigation of the intrinsic electronic properties of STEs and their interaction with activators such as Eu 2+ , which plays a tremendous role for the performance of novel scintillators or X-ray storage phosphors.

Out of the previous reasons, the intrinsic photoluminescence properties of STEs in the distorted perovskites CsMgX 3 (X = Cl, Br, I) are presented in this paper, which also exhibit linear chains in their structure (see Figure 1). In CsMgCl 3 , an intrinsic luminescence has already been reported and also proven [57]. Moreover, this compound is known to show core-valence luminescence upon X-ray radiation [58], [59]. However, to the best of our knowledge, for CsMgBr 3 and CsMgI 3 no such studies have been reported yet. We therefore desire to present a systematic study about the varying optical properties of STEs as well as a comparison to binary alkali halides for these ternary compounds. Their chemical nature will be demonstrated with aid of band structure calculations. An efficient energy transfer to doped Eu 2+ ions is illustrated, which makes these materials interesting for applications in the field of scintillators. All mixtures were sealed in evacuated silica ampoules, respectively, and melted at temperatures higher than the corresponding melting points according to the binary phase diagrams for 36 h [68], [69], [70]. Afterwards, the mixtures were slowly (2 °C/h) cooled down to 100 °C below the melting point and finally to room temperature with a rate of 10 °C/h. The purity of all samples was verified by X-ray powder diffraction (Stoe Stadi P, Cu K α radiation, see supplementary material).

Optical measurements

Clear and transparent pieces (~ 1 mm 3 ) of the products were sealed in evacuated thin silica ampoules for photoluminescence investigations. Emission and excitation spectra were detected with a Fluorolog3 (FL3-22) spectrofluorometer (Horiba Jobin Yvon) equipped with a 450 W Xe lamp and double Czerny-Turner monochromators that allow a resolution down to 0.05 nm. The signal was detected with a photomultiplier tube R928P (Hamamatsu) coupled with a photon counting system. Emission spectra were corrected for the photomultiplier sensitivity and excitation spectra for the lamp intensity. A He closed-cycle cryostat (Janis) allowed measurements between 10 K and room temperature. Decay times down to 5 µs were measured at 10 K using a 75 W Xe flash lamp that is attached to the same spectrometer. Diffuse reflectance measurements were performed with a Cary 5000 UV-VIS spectrometer (Agilent) that detects reflectance between 200 nm and 2500 nm. The reflectance spectra were corrected for the background with a Spectralon reference sample.

| 3

Band structure and density of states (DOS) calculations

Calculations of the band structures and the density of states (DOS) of the host compounds were performed with the Vienna ab initio simulation package (VASP) [START_REF] Kresse | Vienna ab initio simulation package[END_REF], [72], [73], [74], [75]. All calculations were carried out within the generalized gradient approximation (GGA) by a Perdew-Wang functional (PW91) to account for the exchange and correlation functionals [76], [77], [78]. The interaction between core and valence electrons was approximated in terms of the projected augmented wave (PAW) method [79], [80]. Full geometry optimizations were performed with a cutoff energy of 550 eV and 10 k points in the Brillouin zone. The atomic positions were allowed to relax until the residual Hellmann-Feynman forces were smaller than 0.03 eV/Å. The band structure and density of states calculations were conducted with the relaxed structures and a plane-wave cutoff energy of 400 eV and 20 k points in each direction. Convergence was achieved for smaller energy variations than 10 -6 eV.

Results and Discussion

Band structure and electronic density of states (DOS) calculations

Figure 2 depicts the reflectance spectra of the undoped halides CsMgCl 3 , CsMgBr 3 and CsMgI 3 . In the cases of CsMgBr 3 and CsMgI 3 , strong absorption bands are detected at high energies, which are readily recognized as transition from the valence to the conduction band and allow a determination of the optical band gaps as given in Table 1. In particular, our experimentally determined value for the band gap of CsMgI 3 (4.57 eV) is in very good agreement with an earlier measurement by McPherson and Talluto (4.84 eV) [81]. In the case of CsMgCl 3 , the band-band transition is energetically above the measurable range of the reflectance spectrometer. Additionally, several small absorption bands are present at lower energies than the actual band-band transition, which can therefore be assigned to transitions into the different excitonic hydrogen-like states . Since all of the compounds crystallize in the same hexagonal crystal system with space group P6 3 /mmc (no. 194) [45], [82], the band structures and DOS look accordingly similar (see Figure 2). All halides show a direct band gap at both the Γ and K point, which decreases for the heavier halides in agreement to expectations. Moreover, the calculated value for CsMgCl 3 of 5.24 eV agrees well with the recently reported value of 5.31 eV [83]. However, the theoretical values are lower than the experimentally determined band gaps (see Figure 2 and Table 1). This is a wellknown fact from GGA-DFT calculations due to the approximation in the electron exchange correlation functional [84], [85] and the energy derivative discontinuities that arise from the integer number of electrons [86], [87].

The low curvature of the valence band close to the Γ point in all three compounds indicates a high effective hole mass, whereas the effective electron mass is much lower according to the curvature of the lowest conduction band. This is a confirming aspect for the formation of STEs in the manner that is known from the binary alkali halides [16]. In particular, the direct band gap of all three compounds CsMgX 3 (X = Cl, Br, I) also suggests that the formation of excitons should be very efficient.

In general, several main groups of bands can be distinguished in all three compounds according to the DOS calculations (see Figure 3). The narrow core bands in the range between -15 to -10 eV have dominant s orbital contribution from the halide anions with very small mixing of Mg 2s and 2p character in all compounds. Additionally, at around -8 to -6 eV dominant 5p core bands from the Cs atoms are present in all cases, which shift to lower energies and become narrower for the heavier halides. This is reasonable since valence orbitals of the halides increase in energy with higher atomic number and lower electronegativity and therefore make the Cs core bands more non-bonding and hence, dispersionless. Since the gap between the upper edge of the valence bands and the core band, E vc , increases for the heavier halides, only CsMgCl 3 is expected to show core-valence luminescence (E vc < E g ), which agrees with reported observations [58], [59].

The calculations additionally show that the lowest valence bands are most dominantly composed of Mg 2s orbitals. For the uppermost valence bands, the p orbitals of the halide anions show by far the highest contribution, whereas also slight mixing of the Mg 2p and Cs 5p orbitals is obvious. Just below the Fermi level, however, only p bands from the halides are present. The lowest conduction bands are mainly composed of Mg 3s orbitals. At higher energies (5 eV -10 eV), conduction bands with mainly 5d contribution of the Cs ions and little mixing of Mg 2p orbitals as well as halogen s, p and d orbitals (for Br and I) are present (note the scales in Figure 3). Especially the projected DOS calculations indicate a striking similarity of the electronic properties of the compounds CsMgX 3 (X = Cl, Br, I) to the simple binary alkali halides [START_REF] Song | Self-trapped excitons[END_REF], which is mainly related to the high ionicity in this compound. In fact, the sole contribution of the halogen p orbitals at the Fermi level and the Mg 3s orbitals at the bottom of the conduction bands confirms the previously stated argument that STEs in the presented compounds form in a similar way as known for the alkali halides. Moreover, the strong participation of Mg on the lowest conduction band allows the conclusion that the STEs are strongly confined along the linear chain of face-sharing [MgX 6 ] 4-octahedra in direction of the hexagonal c axis. This is in agreement to the reported luminescence properties of STEs in isostructural compounds such as CsMnBr 3 or CsCdBr 3 [47],

[51], [52], [53]. Due to the intrinsic one-dimensionality that is also exhibited in the compounds CsMgX 3 (X = Cl, Br, I), STE formation should be highly favoured [54]. configuration according to the classification of Kan'no et al. [28], [29]. The low Rabin-Klick parameters imply that a singlet or σ emission should also be observed, which is characterized by low Stokes shifts [20], [START_REF] Song | Self-trapped excitons[END_REF]. In fact, a UV emission band is observed at 340 nm (29410 cm -1

) in CsMgBr 3 (see Figure 4b) with a Stokes shift of 2680 cm -1

. Another lower energetic emission in at 406 nm (24610 cm -1

) is correspondingly assigned to a triplet or π emission. The respective excitation spectra are characterized by broad featureless bands in proximity to the conduction band, which additionally justifies the assignment. For the other two halides, only one emission could be observed with similarly broad and featureless excitation bands (see Figure 4a &c). In CsMgCl 3 , it is located at 25700 cm -1 (389 nm), whereas in CsMgI 3 , the emission is peaking at 25520 cm -1

(392 nm) in perfect agreement to the reported value for the intrinsic emission in this iodide [81]. According to the decay times (see section 3.3), they are also assigned to π transitions. All three π emissions are characterized by very large Stokes , 11600 cm -1 and 13660 cm -1 for CsMgCl 3 , CsMgBr 3 and CsMgI 3 , respectively) similar to the alkali halides [20], [START_REF] Song | Self-trapped excitons[END_REF], which additionally justifies the assignment. Interestingly, the positions of all three π emission bands are very similar to each other. This may be assigned to a compensating effect between the expected redshift due to the higher degree of polarizability of the heavier halides and the stronger constraint of the surrounding lattice in formation of the STEs as indicated by the Rabin-Klick parameters S/D.

Decay times of self-trapped excitons in CsMgX 3 (X = Cl, Br, I)

The decay curves obtained upon detection of the emissions from the STEs and ITEs in CsMgCl 3 , CsMgBr 3 and CsMgI 3 show a multi-exponential behaviour with decay times in the µs range and an afterglow component in the range of tens of ms at 10 K (see supplementary material). This clearly identifies the transitions as triplet-like or π emissions in analogy to alkali halides [15], [20], [START_REF] Song | Self-trapped excitons[END_REF]. Only the shortest components were interpreted due to the arbitrariness of the multi-exponential fitting function in order to crudely model the afterglow. In general, the decay time of the π emissions decreases with heavier halide due to the increasing impact of spin-orbit coupling that mixes singlet character into the excited state of the STE hence allowing the π emission at all. The decay time of the triplet state is given by [15], [29] (

where C is a constant, E π is the π emission energy and b is the mixing coefficient indicating the amount of singlet-triplet mixing that is proportional to the spin-orbit coupling constant ζ of the free halogen atom. The radial integral accounts for the transition dipole moment between the excited and ground singlet state of the STE. Since the emission energies for the STEs do not vary significantly in the regarded isostructural compounds CsMgX 3 (X = Cl, Br, I), the main impact on the decay time arises from the mixing parameter b and hence, the spin-orbit coupling and the exchange splitting ΔE ex between the singlet and triplet state. In the weak perturbation limit, it is [15], [29] (2)

In the case of the presented halides, the shortest decay time components were assigned to the π emission and read 35 µs in CsMgCl 3 , 57 µs in CsMgBr 3 and 11 µs in CsMgI 3 at 10 K. Since the spin-orbit coupling constant ζ increases from the chloride to the iodide, the initial increase in decay time from the chloride to the bromide may be related to a compensating effect from the decrease in the π emission energy. The relatively low decay times in the µs range compared to values from some alkali halides in the ms range [15], [20], [START_REF] Song | Self-trapped excitons[END_REF], [28], [29] is ascribed to the difference in Rabin-Klick parameters S/D and the corresponding amount of relaxation of the STEs. In CsMgX 3 , the S/D values are comparably low thereby leading to type I STEs with considerable singlet character of the excited states. In alkali halides, the more open structure allows for a higher degree of structural relaxation of the STEs also reflected in the larger S/D values [START_REF] Song | Self-trapped excitons[END_REF]. This typically leads to the sole observation of a π emission and therefore larger decay times due to the larger triplet character.

A corresponding decay time for the singlet or σ emission was below the detectable limit of the employed flash lamp (< 10 µs) thereby justifying the assignment. Unfortunately, a corresponding measurement with a pulsed laser was not possible at the necessary cryogenic temperature.

Photoluminescence spectra of impurity-localized excitons in CsMgX 3 :Eu

2+

The 4f 6 5d-4f 7 luminescence of Eu 2+ located at the Mg 2+ sites in CsMgX 3 (X = Cl, Br, I) has already been discussed in detail in literature [66], [67], [90]. Only one redshifted emission band due to the 4f 6 5d → 4f 7 transition of Eu 2+ ions is observed in each case. The occupation of the small Mg 2+ sites has so far been proven by structure-luminescence relationships and theoretical considerations [66], [67], [91]. However, a second dominant emission is visible in the blue range in each of the halides (see Figure 5). Their maxima are located at 23360 cm -1 (428 nm), 22990 cm -1 (435 nm) and ) and CsI (E em = 22370 cm -1

) [92], [93], [94]. However, the mismatch both in charge and the Shannon ionic radii of Cs + (r(Cs + ) = 1.88 Å) and Eu 2+ (r(Eu 2+ ) = 1.43 Å) might imply that this situation is not highly probable [95]. Moreover, as indicated above, preliminary studies already excluded this interpretation for low concentrations (< 3 mol%) [66], [67], [91].

In order to elucidate the nature of the blue luminescence in the Eu 2+ -doped halides CsMgX 3 , a concentration series with Eu 2+ and Sr 2+ was investigated (see Figure 5). With increasing concentration, the Eu 2+ -based 4f 6 5d → 4f 7 emission band decreases in intensity in agreement to expectation, whereas the blue emission band retains its intensity. This indicates that the distortion caused by the ionic mismatch between Eu 2+ or Sr 2+ , respectively, and Mg 2+ is crucial for the origin of the blue luminescence bands [95].

The appearance of the photoluminescence excitation spectra (cf. Figure 6) upon detection of the corresponding blue emission bands additionally show a striking similarity to the excitation spectra from CsSrX 3 :Eu 2+ (X = Cl, Br, I) both in energies and fine structure (see Figure 6, lower panels). The position of the higher energetic blue emission band agrees very well with the emission bands of Eu 2+ in the previously mentioned Sr-based halides [66], [67]. Thus, the intense emission bands peaking at 23360 cm -1 (428 nm), 22990 cm -1 (435 nm) and 22320 cm should be noted at this stage that this term is not to be confused with the also currently prominent impurity-trapped excitons (ITEs) in, e.g. Yb 2+ -doped fluorides that contrarily stem from photoionization of the Yb 2+ ions upon excitation of the electron into the conduction band [96], [97], [98], [99], [100], [101], [102], [103]. The IL-STEs regarded in this paper refer to mobile polaronic STEs along the linear chains in CsMgX 3 (X = Cl, Br, I), which become occasionally localized at impurities. A reasonable explanation for the assignment to IL-STEs is possible upon referring to the works on excitons in compounds with face-sharing octahedra such as CdX 2 = Cl, Br, I) or especially CsCdBr 3 [START_REF] Nakagawa | Proc. SPIE[END_REF], [START_REF] Heber | [END_REF], [106]. Upon doping the halides CsMgX 3 (X = Cl, Br, I) with Eu 2+ , their 5d orbitals are located in the band gap and can therefore interact with the np orbitals of the halide anions to form covalent bonds. Accordingly, the localized excitons in close proximity to the Eu 2+ sites may be rather described in terms of a whole [EuX 6 ] 4-octahedron (X = Cl, Br, I) within the linear chains along the hexagonal c axis instead of simple perturbed STEs. The similarity of the excitation spectra of the ITEs to the excitation spectra of isolated Eu 2+ centres in CsSrX 3 [66], [67], [65] is a strong hint on this idea and arises from the fact that Eu (r(Eu 2+ ) = 1.17 Å, r(Sr 2+ ) = 1.18 Å) and therefore characterize perfectly isolated [EuX 6 ] 4-octahedra [95]. Therefore, the actual excited states of the IL-STEs are strongly localized on the Eu 2+ ions, which may be interpreted in a decoupled scheme that treats the 4f 6 core separately from the 5d orbital and has been discussed in detail by us earlier [66], [67]. The observation that | 10 two blue emissions are observed in Eu 2+ -activated CsMgCl 3 and CsMgBr 3 is explained by a perturbation from the local crystal field due to the ionic mismatch between Eu 2+ and Mg 2+ ions. In the iodide, the metal-ligand distances are, however, longer such that the local perturbation is assumed to be negligibly weak.

Alternatively, the incorporation of Eu 2+ ions might also lead to stacking faults in the sense that the [EuBr 6 ] 4-are tilted instead of face-sharing in the original structure of CsMgX 3 . Calculations or EPR measurements, which give further insight about the local structure of the IL-STEs, are planned.

Analysis of the afterglow of the luminescence of impuritylocalized excitons

In the photoluminescence decay curves of the IL-STEs an additional afterglow component in the decay curve becomes more dominant (see Figure 7, lower panels), thus excluding a pure 4f 6 5d → 4f 7 emission of interstitial Eu 2+ ions and justifying the attempted assignment. Contrarily, the decay times of the proposed 4f 6 5d → 4f 7 emission of Eu 2+ at the Mg 2+ sites are below 1 µs at room temperature and do not increase above 10 µs even at 10 K [66], [67]. The shortest components of the decay curves characteristic to the IL-STEs are very similar to the decay times obtained for the STEs (see Table 2), which indicates that they indeed are formed by localization of the excitons at the Eu 2+ impurities. It was shown that trapping of excitons at local impurities in an ideal one-dimensional chain should follow a t -0.5 dependence in the decay curve, which was also experimentally confirmed [89], [107]. The afterglow components of the decay curves related to the IL-STEs in CsMgX 3 : 0.1% Eu 2+ (X = Cl, Br, I) can be well fitted to a t -0.4 to t -0.7 decay instead. The deviation from the ideal case is interpreted to arise due to the possibility of interchain diffusion as the Cs + ions are not bulky enough to confine the exciton formation exclusively to the linear chains in the structure [89]. The decay kinetics therefore also justifies the picture of exciton trapping at present Eu 2+ impurities.

Thermal annihilation of excitons at Eu

2+ ions in CsMgX 3 (X = Cl,

Br, I)

Both the π emissions of the STEs as well as the most intense IL-STE transition in all three halides (see Figure 4 and Figure 6) overlap with the excitation bands of Eu 2+ thus fulfilling the resonance condition of an energy transfer from excitons to Eu 2+ . Since the decay times of the excitonic transitions (see may be excluded [108], [109]. Upon excitation in the UV range, the intensity of the Eu 2+ -based luminescence in the samples CsMgX 3 : 1% Eu 2+ increases with increasing temperatures (see Figure 8). This is especially pronounced for CsMgBr 3 : Eu 2+ , where the highest intensity of the Eu 2+ emission is detected at room temperature. This is an unusual observation if classical thermal quenching is taken into account and so far, only rarely reported [110]. Here, a thermally assisted energy transfer to the Eu 2+ ions by the localized excitons must be indicated, most probably by thermal annihilation. A possible energy transfer mechanism that was thoroughly investigated in the class of quasi one-dimensional compounds relies on the possibility of exciton hopping within the linear chains along the hexagonal c axis [52], [53]. The hopping diffusion of the excitons is based on a "zig-zag"-like movement, in which the bonds of the V K center X 2 -fold along the c axis. Hence, the activation energy for the hopping mechanism should correlate with the binding energy of the V K center X 2 -(X = Cl, Br, I) [111]. This perfectly agrees with the decreasing activating temperature from CsMgCl 3 to CsMgI 3 required for an increase in luminescence intensity of the Eu 2+ -based 4f 6 5d → 4f 7 emission. The presented results are particularly useful in the sense of applications as high-energy detecting materials, which strongly rely on an interaction of excitons or defects with an embedded activator. In that sense, these materials may provide a useful insight into the mechanistic details of exciton-activator interaction of halides.

Conclusions

In this paper, the optical properties of Eu 2+ -localized and selftrapped excitons in the quasi one-dimensional linear chain salts CsMgX 3 (X = Cl, Br, I) were investigated. The calculated DOS of the halides highly suggest that the excitons that form in these compounds are very similar to the well-investigated STEs in simple binary alkali halides and can hence be described as excitons of the form X 2 -+ e respectively. Their intrinsic nature has also been proven by doping with Sr 2+ ions instead of Eu 2+ ions. From the afterglow components of the decay curves of the IL-STE-based emissions, a t -0.4 to t -0.7 dependence was found that additionally indicates a trapping of the excitons at the Eu 2+ impurities.

Finally, the interaction of the excitons with local Eu 2+ impurities was investigated by means of temperaturedependent luminescence studies. An energy transfer from the excitons to the local Eu 2+ impurities is evident that can be interpreted in terms of thermal annihilation of the excitons. In this context, it is very remarkable that the luminescence intensity of the Eu 2+ -based 4f 6 5d → 4f 7 emission in CsMgBr 3 :Eu 2+ is much higher at room temperature than at low temperatures, which may be generally valid for an understanding of such observations. The activation energy for the energy transfer decreases from CsMgCl 3 to CsMgI 3 , which is related to the decreasing bond strength of the self-trapped hole (X 2 -) for heavier halides. This study gives valuable insights into the mechanistic details of the non-radiative interaction between excitons and activators that may have relevance for the optimization of high energy detecting materials such as scintillators or storage phosphors.

Notes and references

Figure 1 .

 1 Figure 1. (Color online) Schematic view on the crystal structure of the quasi onedimensional halides CsMgX3 (X = Cl, Br, I). The Cs + ions are twelve-fold coordinated and the Mg 2+ ions are six-fold coordinated by the X -ions.

Figure 2 .

 2 Figure 2. (Color online) Diffuse reflectance spectra of the undoped halides CsMgCl3, CsMgBr3 and CsMgI3 at room temperature.

Figure 3 .

 3 Figure 3. (Color online) Calculated band structures and electronic total as well as projected density of states (DOS) of CsMgCl3 ((a), (b)), CsMgBr3 ((c), (d)) and CsMgI3 ((e), (f)).

Figure 4 .Figure 4

 44 Figure 4. (Color online) Photoluminescence emission (solid) and excitation spectra (dashed or dotted) of STEs in undoped (a) CsMgCl3, (b) CsMgBr3 and (c) CsMgI3 at 10 K. The π and σ emissions are indicated in each case.

7 CsMgBr 3 1 )

 731 22320 cm-1 (448 nm) for CsMgCl 3 , CsMgBr 3 and CsMgI 3 , respectively. Additionally, redshifted emission bands peaking at 21740 cm -1 (460 nm) in CsMgCl 3 and 21050 cm -1 (475 nm) in| are detected upon excitation with UV light (see Figure6(a) & (c), upper spectra). The presence of these bands is not trivially understood since the crystal structure of the presented halides would intuitively only allow one additional emission band besides the one due to Eu 2+ located on the Mg 2+ sites that could formally be assigned to another 5d-4f emission of Eu 2+ on the respective 12-fold coordinated Cs + sites. Also the energetic positions of the blue emission bands would be reasonable for that assumption if compared to the emission energies of Eu 2+ in CsCl (E em = 22730 cm -

Sr2+Figure 5 .

 5 Figure 5. (Color online) Emission spectra at 10 K of (a) CsMgCl3: x% Eu 2+ , y% Sr 2+ , (b) CsMgBr3: x% Eu 2+ , y% Sr 2+ and (c) CsMgI3: x% Eu 2+ , y% Sr 2+ . The total doping concentration was always (x + y)% = 1%.

- 1 (

 1 448 nm) for CsMgCl 3 , CsMgBr 3 and CsMgI 3 , respectively, are assigned to impurity-localized STEs (IL-STEs) at the Eu 2+ ions. It | 8

9 Figure 6 .

 96 Figure 6. (Color online) Photoluminescence emission spectra recorded at 10 K for (a) CsMgCl3:Eu 2+ , (c) CsMgBr3:Eu 2+ and (e) CsMgI3:Eu 2+ . Solid lines denote a doping concentration of 0.1 mol%, dashed lines a doping concentration of 1 mol% Eu 2+ . The assignments of the emissions arising from 4f 6 5d →4f 7 emissions of Eu 2+ on Mg 2+ sites are indicated. The spectra depict the 4f 6 5d-4f 7 emissions of Eu 2+ in CsSrX3 (X = Cl, Br, I), respectively (cf. also refs. [65], [66], [67]). The corresponding photoluminescence excitation spectra upon detection of the IL-STE transitions are also given for (b) CsMgCl3: 1% Eu 2+ , (d) CsMgBr3: 1% Eu 2+ and (f) CsMgI3: 1% Eu 2+ at 10 K. The dashed curves relate to the 4f 6 5d → 4f 7 emission of Eu 2+ on the Mg 2+ sites. The corresponding excitation spectra.

Figure 7 .

 7 Figure 7. (Color online) Upper panels: Photoluminescence decay curves of (a) CsMgCl3: 0.1% Eu 2+ (λex = 248 nm), (b) CsMgBr3: 0.1% Eu 2+ (λex = 275 nm) and (c) CsMgI3: 0.1% Eu 2+ (λex = 255 nm) for the π emissions of the STEs as well as the emissions of the IL-STEs. Lower panels: Double-logarithmic plots of the decay curves of the IL-STE transitions indicating the t -n dependence of the afterglow components. Fitting curves are indicated as solid lines.

Figure 8 .

 8 Figure 8. (Color online) Temperature-dependent emission spectra of (a) CsMgCl3: 1% Eu 2+ , (b) CsMgBr3: 1% Eu 2+ and (c) CsMgI3: 1% Eu 2+ . In all three cases, a UV excitation wavelength was used for the purpose of an efficient excitation into STE states.

-.→ 4f 6 5d

 6 photoluminescence in the blue range at 10 K and can be readily identified by their excitation spectra, which are strikingly similar to the excitation spectra based on the 4f 7 → 4f 6 5d transitions of the Eu 2+ -doped halides CsSrX 3 ,

2 Experimental 2.1 Preparation

  CsMgCl 3 and CsMgBr 3 , the corresponding anhydrous starting materials were fused together in stoichiometric amounts with small molar amounts of EuX 2 and/or SrX 2 (X = Cl, Br). Doped samples of CsMgI 3 were obtained by fusing CsI 3 (Alfa Aesar, 98%) with Mg metal (smart-elements, 99.8%) in stoichiometric amounts and doping the product with EuI 2 and/or SrI 2 .

	sublimation under vacuum at 600 °C. All subsequent
	preparative steps were performed under dry Ar atmosphere in
	a glove box (Braun).
	EuCl 2 was synthesized in liquefied NH 3 using Eu metal (smart-
	elements, 99.99%) and vacuum-dried NH 4 Cl (Th. Geyer, 99.8%)
	[60], whereas EuBr 2 and EuI 2 were directly obtained upon
	thermal decomposition under vacuum of the ternary halides
	(NH 4 ) 3 EuX 6 (X = Br, I) [61], [62], [63], [64]. The ternary halides
	were synthesized from a solution of Eu 2 O 3 (smart-elements,
	99.99%) and the desired ammonium halide NH 4 Br (Acros
	Organics, 99%) or NH 4 I (Riedel-de Haën, 99%) in the half-
	concentrated acids HBr (Alfa Aesar) and HI (Merck),
	respectively, upon evaporation of the solvent. The halides SrX 2
	(X = Cl, Br, I) were also obtained upon drying of the respective
	hydrates SrCl 2 • 6 H 2 O (Riedel-de Haën, 99%), SrBr 2 • 6 H 2 O
	(Alfa Aesar, 99%) and SrI 2 • x H 2 O (Heraeus, 99.5%) at 200 °C
	under vacuum. Strontium iodide was pre-treated with diluted
	HI in order to remove traces of SrCO 3 that form upon standing
	on air.
	The synthesis of the halides CsSrX 3 (X = Cl, Br, I) doped with 0.1 mol% Eu 2+ has already been described in literature in detail
	[65], [66], [67]. For the preparation of the Eu	2+ and Sr 2+ -co-
	doped compounds
	CsCl (Merck, 99.5%) and CsBr (Chempur, 99.9%) were pre-
	dried at 200 °C in a dynamic vacuum overnight. The starting
	materials MgCl 2 • 6 H 2 O (Riedel-de Haën, 99%) and MgBr 2 • 6
	H 2 O (Sigma Aldrich, 99%) were carefully dehydrated by

Table 1 .

 1 Calculated and experimental band gaps of CsMgX3 (X = Cl, Br, I). For details on the calculations, see text.

	Compound	Eg(theoretical) / eV	Eg(experimental) / eV
	CsMgCl3	5.24	> 6 (8.50)*
	CsMgBr3	4.16	5.95
	CsMgI3	3.13	4.57

* References

[58]

,

[59]

.

Table 2 .

 2 Characteristic values of optical properties of the STEs in CsMgX3 (X = Cl, Br, I). All measured values were acquired at 10 K. For details, see text.

	Compound	Rabin-Klick parameter S/D	Eem / cm -1	FWHM / cm .1	Stokes cm -1 shift ΔS /	τ / µs
	CsMgCl3	0.1624	25700 (π)	2110	11860 (π)	35 (π)
	CsMgBr3	0.1038	24610 (π) 29410 (σ)	2470 2240	11600 (π) 2680 (σ)	57 (π) < 10 (σ)
	CsMgI3	0.0286	25520 (π)	3240	13660 (π)	11 (π)
	shifts (11860 cm -1

Table 2 and

 2 Figure 7) do not vary significantly with varying Eu

2+ concentration within the range between 0.1 -1 mol%, a classical resonance-type energy transfer according to Förster or Dexter | 11