Nelly Vouzoukidou
email: nelly.vouzoukidou@lip6.fr

Bernd Amann
email: bernd.amann@lip6.fr

Vassilis Christophides
email: vassilis.christophides@inria.fr

Continuous Top-k Queries over Real-Time Web Streams

The Web has become a large-scale real-time information system forcing us to revise both how to effectively assess relevance of information for a user and how to efficiently implement information retrieval and dissemination functionality. To increase information relevance, Real-time Web applications such as Twitter and Facebook, extend content and social-graph relevance scores with "real-time" user generated events (e.g. re-tweets, replies, likes). To accommodate high arrival rates of information items and user events we explore a publish/subscribe paradigm in which we index queries and update on the fly their results each time a new item and relevant events arrive. In this setting, we need to process continuous top-k text queries combining both static and dynamic scores. To the best of our knowledge, this is the first work addressing how non-predictable, dynamic scores can be handled in a continuous top-k query setting.

Introduction

The proliferation of social media platforms and mobile technology enables people to almost instantly produce and consume information world-wide. In the real-time Web, traditional scoring functions based on content similarity or link graph centrality are no longer sufficient to assess relevance of information to user needs. For example, textual content relevance may severely be obscured by the "churn" observed in the term distribution of real-time media news or social content and those found in historical query logs [START_REF] Lin | A study of "churn" in tweets and real-time search queries[END_REF], while social relevance [START_REF] Khodaei | Social-textual search and ranking[END_REF] of short living information cannot be reliably computed on static graphs. Streams of user events like "replies" (for posting comments), "likes" (for rating content) or "retweets" (for diffusing information) represent nowdays valuable social feedback [START_REF] Kwak | What is twitter, a social network or a news media[END_REF] on web content1 that is not yet exploited online to assess contextual relevance aspects.

Real-time Web search engines are essentially confronted with a double challenge. First, "ephemeral" Web content [START_REF] Grinev | Analytics for the realtime web[END_REF] should become searchable for millions of users immediately after being published. Second, dynamic relevance of streaming information (e.g. user attention [START_REF] Wang | Automatic online news topic ranking using media focus and user attention based on aging theory[END_REF][START_REF] Liu | Personalized news recommendation based on click behavior[END_REF], post credibility [START_REF] Gupta | Credibility ranking of tweets during high impact events[END_REF], information recency [START_REF] Dong | Time is of the essence: Improving recency ranking using twitter data[END_REF]) should be continuously assessed as users provide their feedback.

To tackle both content and score dynamicity, a first solution consists in extending a content retrieval model (textual, spatial) and implementing adequate index structures and refresh strategies for low-latency and high throughput snapshot query evaluation. Best-effort refresh strategies [START_REF] Cho | Effective page refresh policies for web crawlers[END_REF][START_REF] Horincar | Online change estimation models for dynamic web resources[END_REF] could determine optimal re-evaluation of active user queries which combined with real-time content indexing [START_REF] Chen | Ti: An efficient indexing mechanism for real-time search on tweets[END_REF][START_REF] Busch | Earlybird: Real-time search at twitter[END_REF][START_REF] Wu | Lsii: An indexing structure for exact real-time search on microblogs[END_REF][START_REF] Magdy | Mercury: A memory-constrained spatio-temporal real-time search on microblogs[END_REF][START_REF] Li | Real time personalized search on social networks[END_REF] can achieve high result freshness and completeness. However, real-time content indexing systems usually accommodate high arrival rates of items at the expense of result accuracy by either (a) excluding a significant portion of the incoming items (e.g. with infrequent keywords) from the index to reduce update costs or (b) by ranking items only by arrival time to support append-only index insertion and thus ignore content relevance to queries [START_REF] Wu | Lsii: An indexing structure for exact real-time search on microblogs[END_REF]. Coupling both static (e.g. content similarity to user queries) with dynamic aspects of relevance beyond information recency [START_REF] Dong | Time is of the essence: Improving recency ranking using twitter data[END_REF] is clearly an open issue in existing real-time search engines.

An alternative solution is a publish/subscribe architecture [START_REF] Haghani | The gist of everything new: personalized top-k processing over web 2.0 streams[END_REF][START_REF] Mouratidis | Efficient evaluation of continuous text search queries[END_REF][START_REF] Vouzoukidou | Processing continuous text queries featuring non-homogeneous scoring functions[END_REF][START_REF] Shraer | Top-k publish-subscribe for social annotation of news[END_REF][START_REF] Chen | An efficient query indexing mechanism for filtering geotextual data[END_REF][START_REF] Guo | Location-aware pub/sub system: When continuous moving queries meet dynamic event streams[END_REF][START_REF] Chen | Temporal spatial-keyword top-k publish/subscribe[END_REF] in which user (continuous) queries rather than information items are indexed while their results are updated on the fly as new items arrive. In predicate-based [START_REF] Chen | An efficient query indexing mechanism for filtering geotextual data[END_REF][START_REF] Guo | Location-aware pub/sub system: When continuous moving queries meet dynamic event streams[END_REF] publish/subscribe systems, incoming items that match the filtering predicates are simply added to the result list of continuous queries, while in similarity-based top-k [START_REF] Haghani | The gist of everything new: personalized top-k processing over web 2.0 streams[END_REF][START_REF] Mouratidis | Efficient evaluation of continuous text search queries[END_REF][START_REF] Vouzoukidou | Processing continuous text queries featuring non-homogeneous scoring functions[END_REF][START_REF] Shraer | Top-k publish-subscribe for social annotation of news[END_REF][START_REF] Chen | Temporal spatial-keyword top-k publish/subscribe[END_REF] systems, matching items have also to exhibit better relevance w.r.t. the items already appearing as the top-k results of continuous queries. In publish/subscribe systems both (a) early pruning of the query index traversal for locating relevant queries to an incoming item and (b) the efficient maintenance of their results lists are challenging problems. Only recently, these problems have been studied for more dynamic settings such as decaying information relevance as time passes (e.g. for textual [START_REF] Shraer | Top-k publish-subscribe for social annotation of news[END_REF][START_REF] Vouzoukidou | Processing continuous text queries featuring non-homogeneous scoring functions[END_REF] or spatio-textual [START_REF] Chen | Temporal spatial-keyword top-k publish/subscribe[END_REF] streams). However, there is an important difference between information decay and social feedback: while information freshness is defined as a known in advance, global function applied on all item scores simultaneously, social feedback is locally defined as a stream of non-predictable, random events per item. First, such randomness introduces a new degree of freedom requiring adaptive optimization strategies to the incoming feedback events. Second, the item score dynamics significantly varies and calls for new techniques to balance processing cost (memory/CPU) between items with high and low feedback.

In this paper we are studying a new class of continuous queries featuring real-time scoring functions under the form of time decaying positive user feedback for millions of social feedback events per minute and millions of user queries. In a nutshell, the main contributions of our work are:

• We introduce continuous top-k queries over real-time web streams aggregating both static item content and dynamic real-time event scores. Then, we decompose the continuous topk query processing problem into two separate tasks matching item contents and feedback events.

• We propose new efficient in-memory data structures for indexing continuous top-k queries when matching incoming user events along with a family of adaptive algorithms for maintaining the result of top-k queries with highly dynamic scores.

• We experimentally evaluate our index structures over a real-world dataset of 23 million tweets collected during a 5-month period and compare the impact of dynamic scores in the performance of our algorithms and associated data structures.

The rest of the paper is organized as follows. Section 2 gives a formal definition of the problem. Section 3 presents our proposed solution and pruning techniques for event matching. Then, Section 4 describes a number of index implementations that apply these techniques whose experimental evaluation is detailed in Section 5. Related work is presented in Section 6 and the main conclusions drawn from our work are summarized in Section 7.

Real-time top-k queries

In this section we formally define the problem of evaluating continuous top-k queries with dynamic scores.

Data Model

The general data model builds on a set of search queries Q, a set of items I and a set of events E. Each feedback event e ∈ E (e.g., "replies", "likes", "retweets") concerns exactly one target item i denoted by target(e) (e.g., media news articles, social posts). The set of all events with target i is denoted by E(i). We also assume a time-stamping function ts : Q ∪ I ∪ E → T which annotates each query, item and event with their arrival time-stamp in the system. This function introduces a weak ordering between queries, items and events and formally transforms all sets Q, I and E into streams Q ts , I ts and E ts .

Continuous top-k queries A continuous top-k query q = (k, S qu , S dyn , α) is defined by a positive constant k, a static query score function S qu , an event score function S ev and some non negative query score weight α ≤ 1:

• The constant k defines the maximum size of the query result at each time instance.

• The query score function S qu : Q × I → [0, 1] returns a static score of query q ∈ Q and item i ∈ I. It may capture popular content similarity measures (e.g. textual like cosine, Okapi BM25 or spatial similarity), but it might also reflect other static, query independent scores like source authority [START_REF] Miao | Evaluating importance of websites on news topics[END_REF] or media focus [START_REF] Mao | A method for ranking news sources, topics and articles[END_REF].

• The event score function S ev : E → [0, 1] returns a positive score for each e ∈ E. Events can be scored according to their type and content (e.g. comment, share, click, like) [START_REF] Duan | An empirical study on learning to rank of tweets[END_REF] as well as their author (e.g. friend versus anonymous [START_REF] Alkhouli | Continuous top-k processing of social network information streams: a vision[END_REF]). Distance measures between the author of an even the user subscribing a query could be also considered [START_REF] Li | Real time personalized search on social networks[END_REF].

• The dynamic (feedback) score function S dyn : I × T → [0, ∞] aggregates the scores of all events e ∈ E(i) with target i up to time instant τ :

S dyn (i, τ ) = e∈E(i),ts(i)≤ts(e)≤τ S ev (e)
Observe that we only allow positive event scores and the aggregated event score is unbound.

• The total score of some item i w.r.t. some query q is defined a linear combination of the query score S qu (q, i):

S tot (q, i, τ ) = α • S qu (q, i) + (1 -α) • S dyn (i, τ )
Observe that feedback on items is ignored when α = 1 whereas items are only ranked with respect to their feedback (independently from the query score) when α = 0. As a matter of fact, we consider a general form of static and dynamic scoring function that abstracts several score aspects of items proposed in the literature. Decay function To take account of information freshness [START_REF] Dong | Time is of the essence: Improving recency ranking using twitter data[END_REF], we consider an order-preserving decay function decay(s, d) which can be applied to query, item or event score values s: given a time duration d such that decay(s, 0) = s and decay(s, d) ≤ decay(s, d ) for all d > d , i.e. if s > s , then decay(s, d) > decay(s , d) for any duration d. Order-preserving decay functions2 allow in particular the use of the backward decay techniques [START_REF] Cormode | Forward decay: A practical time decay model for streaming systems[END_REF] where all scores are computed, stored and compared with respect to some fixed reference time instant τ 0 used as a landmark.

It should be stressed that two possible semantics for event decay can be defined. The aggregated decay semantics consists in applying decay to the aggregated event score with respect to the target item age, whereas the event decay semantics consists in applying decay to each individual event with respect to the event age. In the first case, all events have the same decay, whereas the second case favors recent events to old ones. In the special case of linear decay both semantics lead to the same results. The aggregated decay semantics maintains the order preserving property, whereas the event decay semantics might change the item order for order preserving exponential decay. In the following and in our experiments, we assume a linear order-preserving decay function.

Formal semantics and problem statement We denote by P(q) the set of relevant items which have a strictly positive query score S qu (q, i) > 0. The top-k result of a continuous query q = (k, S qu , S dyn , α) at some time instant τ , denoted R(q, τ, k), contains the subset of maximally k relevant items i ∈ P(q) with the highest total scores S tot (q, i, τ ). In other words, for each item i ∈ R(q, τ, k) there exists no other (relevant) item i ∈ I -R(q, τ, k) with a higher total score S tot (q, i , τ ) > S tot (q, i, τ ). Using the backward decay technique described before, we suppose that all scores are computed, stored and compared with respect to some fixed reference time instant τ 0 used as a landmark.

We can now state the general real-time top-k query evaluation problem which we will address in the rest of this paper:

Problem statement 1 Given a query stream Q ts , an item stream I ts , an event stream E ts and a total score function S tot (with order-preserving decay), maintain for each query q ∈ Q ts its continuous top-k result R(q, τ, k) at any time instant τ ≥ ts(q).

Query execution model

This top-k query maintenance problem can be reformulated into a sequence of updates triggered by the arrival of new queries, items and events at different time-instants. We will consider a fixed time instant τ and denote by • Q(i) = {q|i ∈ R(q, τ, k)}, the set of active queries where item i is published at time instant τ ;

• C(q) = {i|i ∈ R(q, τ, k) ∧ S qu (q, i) > 0}, the set of all candidate items which might be inserted into the result of q on a later time instant τ > τ due to feedback score updates.

• C(i) = {q|i ∈ C(q)}, the set of all candidate queries for item i; Example 2 For the example of Figure 1, during time interval (τ 2 , τ d ] , query q appears in the active sets of items c and b. After the arrival of item d, query q is inserted into the active set of d and moves from the active set to the candidate set of b. The arrival of a new event targeting b at time instant τ 3 switches q from the active (candidate) set to the candidate (active) set of d (b).

Problem statement 1 can be decomposed into three separate matching tasks at a given time instant τ :

Query matching: Given a query q, compute the set R(q, τ, k) + of items that should be added to the top-k result of q;

Item matching: Given an item i, identify the set Q(i) + of all queries that should be updated by adding i in their result.

Event matching: Given an event e with target item i = target(e), identify the set Q(i) + of all queries that should be updated by adding i to their result.

Observe that through the definitions of Q(i) and R(q, τ, k) all three matching tasks are strongly related and some tasks could be partially solved by using others. For example, item matching can be solved by re-evaluating (refreshing the result of) all queries while event matching can be solved by re-executing the item matching task for its target item with the updated event score. We will show in Section 3 and experimentally verify in in Section 5, this solution exhibits serious performance limitations for information items with highly dynamic scores. In the rest of this article we are mainly interested in the definition and implementation of an efficient solution for the event matching task by relying on existing efficient solutions for the query and item matching task.

Query evaluation architecture and algorithm As a matter of fact, by considering distinct matching tasks, we can devise a modular architecture and experiment with different data structures and algorithms. As depicted in Figure 2 the main processing modules Query Handler (QH), Item Handler (IH) and Event Handler (EH) are independent and share data structures for indexing queries (Query Index) and items (Item Index). Events are not stored but dynamically aggregated in the corresponding item scores and updated in the Item Index. The general interaction of these models for processing incoming queries, events and items is illustrated in Algorithm 1. Function QH.processQuery() indexes each new incoming query q. Functions IH.processItem() and EH.processEvent() match new incoming items and events against the registered queries and identify the queries whose result (top-k set) have to be updated. Function QI.matchItem computes Q(i) + for a given item (contents) i with a positive constant event score. This supposes that the Item Handler supports continuous top-k queries with inhomogeneous score functions aggregating a query-dependent score (e.g. cosine similarity) and a query-independent constant value (for example item popularity). Such an index structure has been proposed for example in [START_REF] Vouzoukidou | Processing continuous text queries featuring non-homogeneous scoring functions[END_REF].

Function EH.matchEvent() matches each new incoming event and generates Q(target(e)) + . In the rest of this paper we are mainly interested in the efficient implementation of this function and our approach will be described in Section 3. Function RTS.add() publishes item i in the result of q. It also updates the publication and candidate sets for i and query q and, if necessary, for item i which has been replaced by i in the result of q (see Example 2).

Theorem 1 Algorithm 1 guarantees that the results of all queries are correct.

Proof: [sketch] We assume that function II.matchQuery, QI.matchItem and EH.matchEvent correctly compute the update sets R(q, τ, k) + and Q(i) + , respectively, as defined in Section 2. The correctness of the item matching function directly implies that all items are coherently added to the query results by function RTS.add. We then have to show that an item can only Algorithm 1: Real-time top-k query evaluation QH.processQuery(q: Query) QI.addQuery (q); II.matchQuery (q); foreach i ∈ R(q, τ, k) do RTS.add (q,i);

IH.processItem(i: Item) II.addItem (i); QI.matchItem (i); foreach q ∈ Q(i) + do RTS.add (q,i); EH.processEvent(e: Event)
EH.matchEvent (e); foreach q ∈ Q(target(e)) + do RTS.add (q,i); II.matchQuery(q: Query) compute R(q, τ, k) + ; QI.matchItem(i:

Item) compute Q(i) + ;
EH.matchEvent(e: Event) compute Q(target(e)) + ; // see Section 3 RTS.add(q: Query, i: item) remove top-k item (if it exists) from the result of q; add item i to the result of query q; be removed from the query result by being replaced by an item with a higher score (function RTS.add). This can easily be shown by the fact that we allow only positive event scores (S tot is monotonically increasing). Observe that with negative event scores, we would have to define a new function RTS.del which allows to replace some item after one or several negative scores and replace them by some other candidate item.

Event Handler algorithms

In this section we will present two algorithms for solving the (positive and negative) event matching problems described in the previous section.

The first algorithm is called All Refresh (AR). The basic idea is to increase for each new positive event e the query-independent score of its target item target(e) and to retrieve the queries whose result have to be updated, by re-evaluating the item in the Item Handler.

QI.matchItem (i); 8 for q∈ Q(i) + do 9 RTS.add (q,i);
Theorem 2 Algorithm AR is correct.

Proof: [sketch] We assume that function II.matchQuery, QI.matchItem and RTS.add are correct and condition AlgCorr(i) holds for target item i before the event. We show that for a given item i there exists no query q ∈ C(i) where S tot (q, i) > S min (q) after the execution of EH.processEvent(e) processing an event e with target item i. EH.processEvent(e) calls QI.matchItem (through function EH.matchEventSimple) and then RTS.add (i) after the update of the dynamic score. By definition, the item matching function QI.matchItem returns all queries where S tot (q, i) > S min (q) and after processing RTS.add (i), Q(i) contains all these queries.

The AR algorithm achieves an acceptable performance when events are quite rare, compared to the item's arrival rate, but becomes inefficient on a real-time web system suich as Twitter with feedback events arriving from millions of users. In a highly dynamic setting we would expect that a single event on an item, e.g. a single retweet or favorite, should have, on average, a small impact on the set of queries that would receive it. However, by re-evaluating the item through the Item Handler, we would have to re-compute a potentially long list of candidate queries that have already received i.

We propose the Real Real-Time Search (R 2 T S) algorithm, which is based on the idea of using the Item Handler for computing for each item a list of query candidates that could potentially be updated by any future event. These lists are then processed by the Event Handler for retrieving all queries whose result has to be updated with the item targeted by the incoming events. Compared to AR, R 2 T S avoids examining the same list of candidate queries for an item i each time a new event arrives targeting i. The efficiency of this algorithm relies on the following observations:

• each item i has a partial set of query candidates q which might be updated by future events;

• each event increases the score of a single item and triggers a limited number of updates

• there exists a maximal dynamic aggregated score θ(i) max for each item which depends on the scoring function and the number of events it will receive.

The total scoring function (Equation 1) linearly increases the item score for each new event. This leads to a straightforward way of choosing the candidates by setting a threshold θ(i) > 0 for each item i which controls the number of query candidates and which is bound by the maximal dynamic score i can receive by all future events. Candidates and threshold condition: Given a positive threshold value θ, the candidates

|C(i, θ(i))| ⊆ Q of an item i is the set of queries: |C(i, θ(i))| = {q ∈ Q|S min (q) ∈ (S(q, i), S(q, i)+ γ • θ]}.
We say that the threshold condition T(e,θ) holds for some event e iff the dynamic score of its target item does not exceed threshold θ: T(e, θ) = (S dyn (target(e) + S ev (e)) < θ. It is easy to see that when T(e,θ) is true, then all queries updated by e are in the candidate set |C(i, θ(i))|. Otherwise, the candidate set is no longer valid and needs to be recalculated through the Item Handler by increasing threshold θ.

The threshold-based approach of R 2 T S is detailed in Algorithm 3. Each new item i is assigned with a constant positive threshold θ(i) (line 6) and a refresh counter r(i) (line 7). θ = r(i) • θ(i) represents the aggregate threshold value after r(i) refresh steps. When a new event arrives, function EH.matchEvent first increases the dynamic score (line 12) and updates the item index. If the threshold condition does not hold, the candidate list is updated by calling procedure EH.refreshCandidates. The instructions from line 23 to line 26 increment the refresh counter and compute the query candidates by calling the item handler with the new aggregated threshold (item c is a placeholder copy of item i with a virtual aggregated event score corresponding to the threshold of i before the next refresh). Observe that for θ(i) = 0, C(i) contains exactly all queries that have to be updated by the new event. At line 16 the threshold condition holds for event e and EH.matchEvent copies all candidate queries q where the minimum score of q is strictly smaller than the global score of i to the update set U(e) (lines 16 to 19). Theorem 3 Algorithm R 2 T S is correct for positive event scores.

Proof: [sketch] We have to show that both functions, IH.processItem and EH.matchEvent, guarantee that for all items i and all queries q ∈ Q, if S tot (q, i) > S min (q), then q ∈ Q(i) (condition AlgCorr). It is easy to see that the correctness condition holds for some new item i after the execution of function IH.processItem (proof of Theorem 1).

We now show that AlgCorr also holds after the execution of function EH.matchEvent. If S ev (e) = 0 the result does not change (line 9). Otherwise, lines 11 to 13 update the event score of target item target(e). Line 14 checks if the candidate set |C(i, θ(i))| of item i has to be updated. If this is the case, lines 23 to 26 increment r(i) by one and recompute the candidate set |C(i, θ(i))|. We know at line 16 that the candidate set

|C(i, θ(i))| of i contains all queries q ∈ Q -Q(i) where S min (q) ≤ S tot (q, i) = α • S qu (i, q) + (1 -α) • r(i) • θ(i) (1)
Algorithm 3: The R 2 T Salgorithm

14 if S dyn (i, τ ) > r(i) • θ(i) then 15
EH.refreshCandidates(i);

16 for q ∈ |C(i, θ(i))| do 17 for i ∈ R(q, τ, k) do 18 if S tot (q, i)>S tot (q, i ) then 19
RTS.add (q,i); Then we can show that |C(i, θ(i))| contains all queries that have to be updated by event e (and other queries which are not updated). By definition and equation 1, for all queries q to be updated by event e the following holds

S min (q ) < S tot (q , i) = S stat (q , i) + γ • S dyn (i, τ ) ≤ S stat (q , i) + γ • r(i) • θ(i)
which means that q ∈ |C(i, θ(i))| and if S tot (q, i) > S min (q), then q ∈ Q(i) after executing lines 16 to 19 (condition AlgCorr).

The challenge arising from this algorithm is twofold. Identify optimal threshold values θ(i) for each item and index the obtained candidate queries in a way that allows efficient retrieval of updates during the event matching operation (see Section 4). Cost analysis: The choice of threshold θ(i) controls the number of candidate query refresh operations and has an important impact on the overall performance of the system.

From Algorithm 3 we can easily understand that higher values of θ(i) minimize the number of costly candidate refresh operations (by calling the Item Handler) but also might generate a large number of false positive query candidates which will never be updated by an event targeting i.

On the other hand, low values of θ(i) lead to more frequent costly candidate re-evaluations on the Item Handler.

In the following we will use the notation in Table 1. Under the assumption that each event i target item θ(i) estimated threshold value for i θ(i) max estimated maximal aggregated event score for i N i estimated total number of events for i r(θ(i))

estimated number of candidate refresh operations for i costIH(i, θ(i)) aggregated item matching cost costEH(i, θ(i)) aggregated event matching cost |C(i, θ(i))| average size of the candidate list of item i. costT cost of checking if item i updates candidate q costM (i) average item matching cost for i costC(i, θ(i)) average candidate list construction cost for i and θ(i) cost(i, θ(i))

aggregated total matching cost Table 1: Cost function parameters targets only one item and that items are processed independently, we are interested in finding an optimal value for the threshold value θ(i) that minimizes the aggregated total cost cost(i, θ(i))

for each item i. This local optimization leads to a globally optimized evaluation cost. By definition the total aggregated matching cost is defined by the sum of the aggregated item and the aggregated event matching costs:

cost(i, θ(i)) = costIH(i, θ(i)) + costEH(i, θ(i))
If we suppose that all events have the same event score S ev (e), then r(θ(i)) = θ(i) max /θ(i) . We can estimate the aggregated item and event matching costs costIH(i, θ(i)) and costEH(i, θ(i)) as follows (Algorithm 3). First, each candidate list is refreshed r(θ(i)) times where each refresh consists in matching the item and constructing the candidate list (function EH.refreshCandidates):

costIH(i, θ(i)) = r(θ(i)) • (costM (i) + costC(i, θ(i))) (2)
Second, each event is matched in the Event Handler N i times. Supposing that there is no early stopping condition when checking the candidates, the cost of every event match operation depends on the average size of the candidate list |C(i, θ(i))| and on the (constant) cost costT of checking if item i updates a given query candidate q:

costEH(i, θ(i)) = N i • |C(i, θ(i))| • costT (3)
Finding optimal θ(i): The value of |C(i, θ(i))| depends on the distribution of the query minimum scores. Our cost model relies on the assumption that the average size of all candidate lists produced by each refresh step linearly depends on threshold value θ(i):

|C(i, θ(i))| = a•θ(i),
where a is a positive constant 3 . Similarly, we assume that the candidate creation costC(i, θ(i)) depends linearly on θ(i): costC(i, θ(i)) = b•θ(i). This cost abstractions simplify the computation of the optimal θ(i)and they have been also experimentally validated. Given r(θ(i)) = θ(i) max /θ(i) (we consider here the real value instead of the integer floor value), Equations ( 2) and (3) the total cost(i, θ(i)) can be written as:

cost(i, θ(i)) = 1 θ(i) • c1 θ(i) max • costM (i) +θ(i) • N i • a • costT c 2 + θ(i) max • b c 3
We minimize the cost function using the first derivative:

d(cost(i, θ(i))) dθ(i) = - c 1 (θ(i)) 2 + c 2
Function cost is monotonically decreasing in the interval (0, c 1 /c 2 ) and increasing in ( c 1 /c 2 , θ(i) max ], thus making θ(i) = c 1 /c 2 the optimal value:

θ(i) opt = 1 a • θ(i) max N i • costM (i) costT
This equation essentially shows that θ(i) opt depends on the query distribution in the Item Handler index (first factor) and increases with the ratio costM (i)/costT between the item matching cost and the event test cost (third factor).

Candidate indexing

The Event Handler matches incoming events against a precomputed list of query candidates which has to be regularly refreshed. In the above cost model, we do not take account of the cost of maintaining the candidate list. This cost clearly depends on the size of the list, as well as, on the choice of the data structures for indexing candidates in the Event Handler. In this section we introduce three indexing schemes aiming to optimize the cost of storing and retrieving candidates. We are particularly interested in finding efficient early stopping conditions during event matching in order to avoid visiting all candidates.

The main task of the Event Handler is to retrieve result updates triggered by any arriving event. Since each event e increases the score of a single item target(e), these updates will only concern a subset of this item's candidate queries. Hence, the building block of all the indexes we propose is a dictionary from each item to its set of candidates. The proposed indexes aim at organizing the posting lists, i.e. the candidates sets in a way that decreases the number of false positives encountered during event matching and to efficiently support insertions and deletions. Although deletion in both cases in not necessary for the correctness of the algorithm, maintaining these queries as candidates would lead to an unnecessary number of false positives, deteriorating the overall event-matching performance for following event evaluations. A straightforward implementation of the Event Handler posting lists is to maintain an unordered set of candidates as illustrated in Figure 3-(a). Assuming a dynamic array implementation of this index, insertions and deletions of candidates can be performed in (amortized) constant time. On the one hand, if θ(i) is large enough, this solution has the advantage of avoiding candidate list updates for a potentially big number of arriving events (as long as the θ(i)-condition holds).

On the other hand, it is not possible to apply any early stopping condition, and all candidate queries need to be checked for updates. Following the "sort and prune" principle, we try to define an efficient ordering and appropriate data structures for matching query candidates that will allow us to define an early stopping condition (Figure 3-(b)). As defined in Section 3, a query q is a candidate of an item i if diff(q, i) = S min (q) -S(q, i) ∈ (0, θ(i)] and diff(q, i) represents the lower dynamic score bound i must receive before updating q(S min (q) is monotinically increasing). So, if candidates are ordered by value diff(q, i), on event arrival, it is sufficient to visit only candidates with negative diff(q, i). Notice that this set of visited candidates guarantees not only zero false negatives but also zero false positives. Nevertheless, maintaining this order in a dynamic environment is a non-trivial problem: from the moment a query becomes a candidate of an item i until to a new event with target i, the minimal scores of other candidates might have changed (increased) due to result updates or, more frequently, due to events received by their k-th item. In the following, we will discuss the implications of maintaining the accurate order and present two lazy re-orderinf approaches reducing update costs. Exhaustive ordering Index: This solution accurately maintains the order of query candidates by the score difference diff(q, i). To achieve this, it executes all necessary re-orderings on each S min (q) change, independently to whether it is due to an event or an item and in all postings of items that q is a candidate. We will observe in our experiments that in a real-world workload the performance gains from avoiding false positives are outperformed by the time wasted to maintain the order.

The following two solutions follow a lazy re-ordering approach, in order to achieve a reasonable trade-off between the cost of eliminating false positives and the cost of re-orderings candidates. Static-order Index: This solution sorts all candidates only at the creation of the candidate list. New queries are inserted to the beginning of the candidate lists, independently of their diff(q, i) values. All minimal score S min (q) changes are also ignored. On event arrival, the matching algorithm vists all candidate queries for which the stored (and not actual) difference score is lower than the item's dynamic score: diff(q, i) < S dyn (i, τ ). It is easy to show that this condition is safe but also converges with time to the previous simple Event Handler solution. Lazy re-ordering Index: The two previous approaches either have a very high maintenance cost due to frequent re-ordering operations (Exhaustive), or an inefficient event matching due to lack of maintenance of this order (Static-order ). The Lazy approach lies in-between by following a lazy "on false-positive" update approach. Given an item i, any order changes caused by minimal score updates are ignored until the next arrival of a new event with target i. The heuristics behind this approach is that many re-orderings of the Exhaustive approach never are exploited because candidate queries are moved several times before actually being visited on an event arrival. Therefore, the Lazy approach attempts to minimize the number of re-orderings at the expense of introducing false positives on event matching. Given that in the general case the cost of re-ordering an element in a sorted list has a logarithmic complexity, while the cost of eliminating a false positive is constant, the Lazy approach is expected to outperform the Exhaustive one. Item Partitioning Event Handler: Ordered indexes reach their limits for highly varying diff(q, i) values. The Item Partitioning approach relies on the following observation: if two queries q 1 and q 2 are both candidates of an item i and both have the same item i' as their k-th result item, both difference score values diff(q 1 , i) and diff(q 2 , i) are synchronized and the relative order of both queries in the posting list of i will remain the same. For this reason, we organize the query candidates of each item, with respect to their k-th element. The order assigned in each such group during insertion remains constant for as long as their k-th result remains the same, i.e. as long as they do not receive any updates. For example, in Figure 3, item i has 5 candidate queries, two of which (q 2 and q 5 ) have i' as their k-th element. These queries are grouped together (Figure 3-(c)) in a sorted list, (ordered according to diff). For as long as i' remains the k-th element of both these candidate queries, the ordering of the list is static. On event arrival, the matching operation checks each one of these groups if the corresponding item, until reaching true negative candidate. In case of an update, however, of a query q by an item, q has to be re-indexed in the group of its new k-th element in all items where it is a candidate. Despite the additional cost on the query update operation, as we will see later in Section 5, the minimization of both re-orderings (only on the case of updates) and false positives leads to an overall better performance than the previous approaches.

Experiments

In this section we experimentally evaluate the algorithms presented in Section 3 and the data structures proposed in Section 4, using a real dataset collected from Twitter's public streams. Through these experiments we compare the performance of the R 2 T S algorithm implementations over the simple candidates (Simple), the lazy ordering (LazyOrder) and the item partitioned (ItemPart) index with the naïve approach of the AR algorithm (Naive) over a number of parameters, like the total number of stored continuous queries, the size k of query result lists, and the weight of user feedback (γ) on the total score function. Additionally, we are interested in assessing the impact of the θ(i) tuning parameter over the overall system performance. Our experiments rely on a slightly modified version of the item matching algorithm4 (Item Handler) presented in [START_REF] Vouzoukidou | Processing continuous text queries featuring non-homogeneous scoring functions[END_REF] to additionally detect candidate queries given a value of θ(i).

Experiments were conducted using an Intel Core i7-3820 CPU@3.60. Algorithms were implemented in Java 7 and executed using an upper limit of 8GB of main memory (-Xmx8g). The configuration used only one core for the execution of the different algorithms. We present the average execution times of three identical runs after an initial warm-up execution. All queries were stored before any item or event evaluation and their insertion time is not included in the results. We collected a real-world dataset from the Twitter Stream API over a period of 5

α 0.3 (1 -γ)/2 β 0.3 (1 -γ)/2 γ 0.4 [0.05, 0.95] k 1 [1, 20] θ(i) strategy θ(i) max /2 [0, 0.2] or [0, θ(i) max ]
Table 3: Experimental parameters months (from March to August 2014). In our data model, an original tweet corresponds to an item and a retweet to a feedback signal, i.e. an event for the original item. From this set we have filtered out non-English tweets, as well as those without any retweets (events), leading to a dataset of more than 23 million tweets and retweets (DS1) (Table 2). Two additional subsets were created by considering only tweets (and the corresponding retweets) with at least 5 (DS5) or 10 retweets (DS10) per item. DS5 dataset is the default dataset for the experiments and contains 2.2 million tweets and retweets. Queries were generated by uniformly selecting the most frequent n-grams of 1, 2 or 3 terms from the tweet and retweet dataset leading to an average length of 1.5 terms per query. In each of the following experiments we change one parameter within a given range, while all system parameters remain constant. Table 3 shows the default values for each parameter, as well as the range of each parameter used for the corresponding experiments. Exact maximal threshold θ(i) max : In this experiment we use as maximal threshold θ(i) max the exact final aggregated event score S dyn (i, τ ) (Equation 2.1) of each item i. The horizontal axis of Figure 4a represents the percentage (from 0 to 100%) of the θ(i) max value assigned as θ(i) value to an incoming item while the vertical axis represents the time required to match the items and events of the dataset DS5. Naive execution time is independent of the θ(i) value and thus shown as a constant line. Note that in the special case of θ(i) = 0 all indexes converge to the Naive one. ItemPart outperforms the other three indexes, while LazyOrder has higher execution time than Simple, despite the early stopping condition defined. The relatively good We can also observe a particular pattern in this plot: execution time exhibits local minima for θ(i) values which are fractions of θ(i) max , i.e., 100%, 50%, 33%, 25% etc. To understand this form, consider for example the case of θ(i) = 0.5 • θ(i) max . On the first evaluation of any given item i, the list of candidates with a difference up to θ(i) is computed. Since θ(i) corresponds to half the maximal value of the aggregated item score, the item will be re-evaluated through the Item Handler a second time, and there will be no need for a third evaluation. When a higher value is chosen, e.g., 0.6 • θ(i) max , two evaluations in the Item Handler would also be required, with the difference that some already known candidates would be retrieved again. Hence, an additional cost incurs to a) compute the redundant candidates and b) to filter out the probably higher number of false positives on event matching in the Event Handler.

Figure 4b shows the average percentage of lists visited, until the stopping condition becomes true. The size of the candidate lists is the same for all algorithms for the same θ(i) threshold. Simple always visits 100% of the lists due to the lack of a stopping condition. We can observe that ItemPart has a 20% smaller execution time (Figure 4a) while visiting in average only 5% of the candidate lists. Global threshold θ: In this experiment we assign the same θ value to all items without using any knowledge of the maximal dynamic score per item. Figure 4c shows, for each absolute value θ assigned to all items, the time required to evaluate the whole dataset (DS5). We can observe that as the value of θ(i) increases from 0, there is a quick improvement in the performance of the indexes Simple, LazyOrder and ItemPart while after exceeding the optimal θ(i) point, it deteriorates with a smaller slope: for very small values of θ, the lists become frequently obsolete (when the θ(i)-condition no longer holds) and a large number of incoming events need to be evaluated in the Item Handler. This explains the first phase where execution time decreases. As values of θ become much bigger, the lists become longer: computing the candidates becomes more costly and more false positives are likely to appear. Unlike in the previous experiment the three indexes exhibit similar performance with no more than 5% of difference in execution time. This behavior indicates that the stopping condition for both LazyOrder and ItemPart fails to prune as much query candidates as in the previous experiment. This is attributed to the arbitrary assignment of the same θ value to all items. For some items this value can be large w.r.t. θ(i) max and the algorithms thus spend unnecessary time for finding candidate queries which will never be used. On the other hand, a small value of the θ(i) w.r.t. θ(i) max means that there will be to many costly evaluations of events in the Item Handler.

Scalability and throughput:

In this experiment, we are interested in the scalability of our indexes w.r.t. the number of continuous queries stored in the system (index creation time is excluded from our measurements). As we can see in Figure 5a all implementations scale linearly with the number of continuous queries.

ItemPart scales better: over 100, 000 queries it requires 50% of the corresponding time for Naive while over 900, 000 it only requires 36%. The low slope of ItemPart indicates the good performance of its stopping condition to prune more candidate queries over increasing list sizes. In terms of throughput, over 900, 000 continuous queries ItemPart is able to serve using a single CPU core an average of 3.2 million items (tweets) or events (retweets) per minute which is one order of magnitude more than the number of tweets Twitter actually receives. Over a total of 100, 000 stored continuous queries the throughput would go up to 10.9 million items and events per minute. Item/event score weight γ: In this experiment, we vary the weight of the dynamic score (aggregating event scores) to the total score of an item (i.e., the γ parameter in Equation 1). Recall that when γ is small, each arriving event has a minimal impact on the total item score and only a small number of queries will be updated by the corresponding target items of incoming events. As shown in Figure 5b, Naive performance improves for values of γ up to 0.2 and then exhibits a constant behavior. On the contrary, the three other indexes require a higher execution time for greater γ values. In fact, the more γ becomes important, the more the initial static score between queries and items becomes obsolete. As score changes due to any single event become more significant, the candidate lists computed on item matching are soon invalidated given that minimal score of indexed candidate queries has changed. This leads to an increasing number of false positives and explains the increase in execution time. For realistic γ values in [0.1, 0.5] the performance difference of any of these three indexes to their optimal value is of less than 10%. Result size k: Figure 5c shows the performance of the four indexes over different values of the k parameter. Higher k values result in lower values of minimal scores for the stored queries and consequently increase the number of item updates received by the queries. As we can see in Figure 5c all indexes scale linearly on the value of k and that ItemPart and Simple exhibit a better performance of about 20% than the other two indexes when the k = 20. Events per item: In this experiment we measure the overall performance of our indexes over the three datasets DS1, DS5 and DS10 (see Table 2) that feature a different average number of events each of the items receives: DS1 has an average of only 1.29 events per item while DS10 has 19.60. Figure 6 shows per dataset the average execution time for matching a single item or event along with the average number of updates (#updates) implied. We can observe that for all indexes execution time increases proportionally w.r.t. the number of updates. Additionally, the performance of the R 2 T S algorithm for the three indexes (Simple, LazyOrder and ItemPart) is better than Naive as the number of events per items increases. Over the DS1 dataset (with the smallest number of events/item), ItemPart, which is the best performing index, needs 68% of the time required by Naive, while over DS10 it only requires 29,8%. Decay: In our final experiment in Figure 7, we measure the performance of all indexes over linear decay. The horizontal axis shows the time it would take for a score of 1.0 to decay to 0, i.e., the maximum expiration time of an "idle" item (an item receiving no further events). A general observation is that as score decay becomes faster, indexes performance become worse: fast decay leads to a high number of updates (see number of updates in Figure 7), which in turn, leads to a higher delay in matching items and events. More precisely, while Simple exhibits a 20-30% overhead over Naive the performance of LazyOrder and ItemPart becomes worse than Naive even with a small decay factor. This behavior indicates that the ordering maintained by these two indexes becomes very dynamic and the stopping condition employed, is not sufficient to overcome the high maintenance cost. Simple on the other hand, does not require any order maintenance and achieves a faster item and event matching time. Conclusions on the experiments: Our experiments demonstrate that the ItemPart and Simple solutions outperform the Naive and LazyOrder ones over all settings, with ItemPart having a slight edge over Simple of about 5%. Comparing the stopping conditions, ItemPart manages to filter with the defined stopping condition a big percentage of the candidate lists and on most cases only had to visit about 10% of the candidates before having correctly identified all updates and stopping the algorithm. However, the heavy data structures maintained for each item (an unsorted set of sorted lists) only allows ItemPart to require from 50 to 35% the time used by the Naive index, which always visits all stored candidates. Our indexes perform better over highly dynamic environments with high numbers of events per published item.

Related work

Real-time search engines: Twitter Index (TI) was the first system proposed for real time search [START_REF] Chen | Ti: An efficient indexing mechanism for real-time search on tweets[END_REF]. It relies on a general form of scoring functions combining linearly textual similarity of items to queries with (static and dynamic) query-independent parameters. A "User PageRank " authority measure is employed to estimate statically the importance on an item while its dynamic score is computed by counting tweet replies. A rational decay function is applied on the result to capture the freshness of information: S tot (q, i)/∆τ , where S tot (q, i) is the initial query-item score and ∆τ is the time difference since the publication of the item. TI adopts a partial indexing approach that distinguishes frequent keyword queries from infrequent ones. For any new tweet, if it is relevant to at least one frequent query, it is inserted into an inverted index immediately; otherwise, it is inserted to an append-only log, the content of which is periodically flushed into the inverted index. However, user queries are evaluated only using the inverted index without looking at the log. The posting lists of this index are ordered on decreasing arrival time of tweets to privilege access to recent tweets even without sufficient consideration of their relevance to queries.

Deeper insights on how Twitter's Search actually works have been published in [START_REF] Busch | Earlybird: Real-time search at twitter[END_REF]. To efficiently index all incoming tweets, Earlybird uses compression techniques for tweets' contents and for long posting lists, multi-threaded algorithms and resources allocation optimizations. It relies on an append-only inverted index where each posting list stores tweets sorted by arrival time. This order enables to consider an effective stopping condition: when, during the traversal of the posting list, k items with a similarity score greater than a value s min have been found, the scanning of the posting lists can stop iff s min is greater than the maximal value of any other available tweet given that it is published exactly the same time as the one currently being checked. The estimation of this maximal value is based on the score decay function. Several works that followed [START_REF] Wu | Lsii: An indexing structure for exact real-time search on microblogs[END_REF][START_REF] Magdy | Mercury: A memory-constrained spatio-temporal real-time search on microblogs[END_REF][START_REF] Li | Real time personalized search on social networks[END_REF] proposed improved versions of the inverted index for increasing the accuracy of results returned to real-time search or for supporting various forms of analytic queries without considering continuous query evaluation issues. Top-k publish/subscribe on text streams: The Incremental Threshold (IT) algorithm [START_REF] Mouratidis | Efficient evaluation of continuous text search queries[END_REF] was the first work that introduced continuous top-k queries with sliding information expiration windows to account for information recency. It maintained two inverted indexes: one for queries and the other for items. The latter contains only the most recent items belonging to the current window and its posting lists are sorted by decreasing weight of the terms assigned to represent the items. In the former the posting lists are sorted in decreasing order of a value θ q,t , where t is the term of the posting list and q the continuous query that contains it. IT relies on the Fagin's Threshold Algorithm (TA) to evaluate queries and on an early stopping condition to maintain their result lists. It continuously updates the inverted index on item publication and expiration and thus incurs a high system overhead. This limitation is addressed by the COLfilter algorithm [START_REF] Haghani | The gist of everything new: personalized top-k processing over web 2.0 streams[END_REF] maintaining only an inverted index of queries with a sorted posting list for each query term. The sorting criteria takes account for the term weight and the minimum query score and allows to define a necessary and sufficient stopping condition for monotonic, homogeneous scoring functions such as cosine or Okapi-25. [START_REF] Haghani | The gist of everything new: personalized top-k processing over web 2.0 streams[END_REF] maintains posting lists where queries are sorted according to the minimum top-k scores and items expire after some fixed time period (window based decay). Minimum top-k scores can change frequently and induce an important resorting overhead. This body of work cannot address continuous top-k queries beyond query-dependent item scores (i.e., content similarity). Efficient stopping conditions over a two-dimensional representation of queries featuring both a query-dependent and queryindependent scores (with time decay) have been firstly proposed in [START_REF] Vouzoukidou | Processing continuous text queries featuring non-homogeneous scoring functions[END_REF]. In this paper, we leverage the item matching algorithm implementing the Item Handler for static scores with time decay and propose several alternative index structures for implementing event matching in the Event Handler (see Figure 2) that accounts for the dynamic score of items due to social feedback.

Finally, [START_REF] Shraer | Top-k publish-subscribe for social annotation of news[END_REF] considers the problem of annotating real-time news stories with social posts (tweets). The proposed solution adopts a top-k publish-subscribe approach to accommodate high rate of both pageviews (millions to billions a day) and incoming tweets (more than 100 millions a day). Compared to our setting, stories are considered as continuous queries over a stream of tweets while pageviews are used to dynamically compile the top-k annotations of a viewed page (rather than for scoring the news). The published items (e.g., tweets) do not have a fixed expiration time. Instead, time is a part of the relevance score, which decays as time passes. Older items retire from the top-k only when new items that score higher arrive. This work adapts, optimizes and compares popular families of IR algorithms without addressing dynamic scoring aspects of top-k continuous queries beyond information recency, namely TAAT (term-at-a-time) where document/tweet scores are computed concurrently one term at a time, and DAAT (document-at-a-time) where the score of each document is computed separately. Top-k publish/subscribe on spatio-textual streams: AP (Adaptive spatial-textual Partition)-Trees [START_REF] Wang | Ap-tree: Efficiently support location-aware publish / subscribe[END_REF] aim to efficiently serve spatial-keyword subscriptions in location-aware publish/subscribe applications (e.g. registered users interested in local events). They adaptively group user subscriptions using keyword and spatial partitions where the recursive partitioning is guided by a cost model. As users update their positions, subscriptions are continuously moving. Furthermore, [START_REF] Wang | Skype: Top-k spatial-keyword publish/subscribe over sliding window[END_REF] investigates the real-time top-k filtering problem over streaming information. The goal is to continuously maintain the top-k most relevant geo-textual messages (e.g. geo-tagged tweets) for a large number of spatial-keyword subscriptions simultaneously. Dynamicity in this body of work is more related to the queries rather than to the content and its relevance score. Opposite to our work, user feedback is not considered. [START_REF] Chen | Sops: A system for efficient processing of spatialkeyword publish/subscribe[END_REF] presents SOPS (Spatial-Keyword Publish/Subscribe System) for efficiently processing spatial-keyword continuous queries. SOPS supports Boolean Range Continuous (BRC) queries (Boolean keyword expressions over a spatial region) and Temporal Spatial-Keyword Top-k Continuous (TaSK) query geo-textual object streams. Finally, [START_REF] Chen | Temporal spatial-keyword top-k publish/subscribe[END_REF] proposes a temporal publish/subscribe system considering both spatial and keyword factors. However, the top-k matching semantics in these systems is different from ours (i.e., boolean filtering).

In our work, online user feedback is part of the ranking score of items, which renders existing spatial-keyword solutions inapplicable, while challenges index structures and matching algorithms for top-k continuous query evaluation.

Conclusions

To support real-time search with user feedback, we have introduced a new class of continuous top-k queries featuring complex dynamic scores. The main problem we solved in this context, is the search of queries that need to update their result lists when new information items and user events affecting their scores, arrive. To accommodate high arrival rates of both items and events, we have proposed three general categories of in-memory indexes and heuristic-based variations for storing the query candidates and retrieving the result updates triggered by events. Using an analytic model we have theoretically proven efficient early stopping conditions avoiding visiting all candidate queries for each item. Our experiments validated the good performance of our optimized matching algorithm. All three indexes for candidate maintenance (Simple, LazyOrder and ItemPart) achieve a high throughput of items and events, with ItemPart being able to handle 3.2 million events per minute over 900 thousand stored continuous queries. This performance has been achieved using a centralized single-threaded implementation of our algorithms. The usage of posting-lists as basic data structures for filtering events opens a number of opportunities for parallelization. The main challenge in this direction concerns the reordering cost of the ordered solutions (LazyOrder and ItemPart) with early stopping conditions. One direction of future work is to consider workload-oriented parallelization by identifying independent item clusters (for example, with disjoint query keywords). Another direction is to extend the unordered solution Simple, which is certainly a good candidate for a first parallel implementation Finally, we intend to study richer top-k query settings with random negative feedback scores. The efficiency of our solution is strongly based on the monotonicity of the scoring function and adding negative score might need the exploration of completely different multi-dimensional indexing approaches.

Figure 1 :Example 1

 11 Figure 1: Top-2 result evolution of query q

Figure 2 :

 2 Figure 2: Architecture

Algorithm 2 :

 2 The AR algorithm 1 EH.matchEventSimple(e : Event) 2 if S ev (e) == 0 then 3 return ∅;

4 i

 4 := target(e); 5 dynscore(i) := dynscore(i) + score(e); 6 II.updateItem(i);

7

 7

24 S

 24 20 EH.refreshCandidates(i: Item) 21 c := copy(i); 22 if θ(i) > 0 then 23 r(i) := r(i) + S dyn (i, τ )/θ(i) + 1; dyn (c, τ ) := r(i) • θ(i); 25 QI.matchItem(c); 26 C(i):=Q(c) + -Q(i);

Figure 3 :

 3 Figure 3: (a)Simple (b)Ordered (c)Partitioning indexes

  ) max /T h (b) Selectivity exact threshold θ(i) max /T h (c) Time global threshold value θ

Figure 4 :

 4 Figure 4: Exact and Global Threshold

Figure 5 :

 5 Figure 5: Scalability

Figure 6 :

 6 Figure 6: Scalability events per item

Figure 7 :

 7 Figure 7: Scalability (linear) decay

Table 2 :

 2 Number of items and events in each dataset

		#items	#events min	avg
	DS1	10 676 097 13 787 349	1	1.29
	DS5 (default)	201 581	2 013 427	5	9.99
	DS10	56 417	1 105 639	10 19.60
	parameter default value			range
	#queries	900 000	[100 000, 900 000]

This trend is expected to be amplified in the future Internet of Things (IoT) where users can provide online feedback regarding almost any digital or physical object[START_REF] Christophides | Report on the first international workshop on personal data analytics in the internet of things (pda@iot 2014)[END_REF].

Whereas any linear or exponential function is order-preserving, it is possible to define polynomial functions which are not order preserving.

A more precise cost model estimating the optimal threshold for each individual refresh would need a query/item/event distribution model which is difficult to obtain for a real-world workload.

Available as an open source library continuous-top-k: https://code.google.com/p/continuous-top-k/


Hayette Gatfaoui
email: h.gatfaoui@ieseg.fr

Isabelle Nagot
email: isabelle.nagot@univ-paris1.fr.z

Philippe De Peretti

45r

Are critical slowing down indicators useful to detect financial crises?

Keywords: Critical slowing down, Complex dynamical system, Global …nancial crisis, Phase transition. JEL codes: C1, C4

In this article, we consider …nancial markets as complex dynamical systems, and check whether the critical slowing down indicators can be used as early warning signals to detect a phase transition. Using various rolling windows, we analyze the evolution of three indicators: i) Firstorder autocorrelation, ii) Variance, and iii) Skewness. Using daily data for ten European stock exchanges plus the United States, and focusing on the Global Financial Crisis, our results are mitigated and depend both on the series used and the indicator. Using the main (log) indices, critical slowing down indicators seem weak to predict to Global Financial Crisis.

Using cumulative returns, for almost all countries an increase in variance and skewness does precede the crisis. However, …rst-order autocorrelations of both log-indices and cumulative returns do not provide any useful

Introduction

The rapid succession of …nancial crises over these recent years has created a strong incentive to build some tools able to predict crises, i.e. early warning signals. One very appealing framework, widely used with success in ecology, climatology (Dakos et al. [DAK 08]) or physics is to consider that systems are complex or self-critically organized (Sornette [SOR 09]). Under such a framework, systems can switch between multiple equilibria without external forces (Sche¤er [SCH 09], [SCH 12]). In other words, the complex dynamic interplay between each particle of the system will lead to a phase transition or a bifurcation (Kuehn [KUE 11]).

Within complex systems, the critical slowing down (CSD) concept is useful to predict critical transitions. Critical slowing down refers to the fact that a system becomes less and less able to absorb shocks and then to come back to an equilibrium state. In particular, the accumulation of shocks can alter the resilience of the system, driving it towards a critical transition, i.e. the system will switch to an other state. Before that transition, the changes will become slower and slower and as a consequence, for a particular series, the autocorrelation at lag one will increase, as well as the variance, and maybe other higher moments. Critical slowing down is therefore appealing because it allows for studying phase transitions within a theoretical framework with very simple tools, and without having to specify the particular underlying model. The goal of this paper is to empirically investigate the CSD concept, when applied to …nancial markets. For this prospect, we focus on stock exchanges for Our paper is organized as follows. Section 2 focuses on theoretical aspects while introducing CSD concept, indicators and related measurement tools.

Then, section 3 implements the empirical analysis and displays CSD indicators.

Finally, section 4 proposes concluding remarks.

Over past and recent history, …nancial markets have been subject to several sudden changes, i.e. regime shifts. Such abrupt changes depict critical transitions from a non-depressed or normal state to a depressed or crisis state and conversely. Shifts occur when the considered system, such as a given set of …nancial markets, reaches a critical threshold frequently named tipping point (Dakos et al. [DAK 08]). In particular, the system converges towards a tipping point around which it becomes more and more unable to absorb small shocks (Kuehn [KUE 11]). As a result, its ability to recover from such perturbations slows down (see for example the fold catastrophe model, Sche¤er [SCH 09]), so that its potential for recovery becomes also low, i.e. zero recovery rate and increasing recovery time are observed (van Nes and Sche¤er [NES 07]). Indeed, the dynamical system exhibits a decreasing resilience (Dai et al. [DAI 12]). Under such a low resilience regime, the system loses e¢ ciency and accumulative small perturbations1 can trigger the system's shift to a depressed state, i. ). When the system converges towards a tipping point, it becomes less able to recover from perturbations and remains therefore close to its previous state. As a result, data auto-correlation should increase in the short run, i.e. lag-1 auto-correlation. Such memory phenomenon will help trap the system in the depressed state. For example, the higher the lag-1 autocorrelation becomes, the slower the recovery of the system is (Ives ). In the vicinity of a tipping point, shocks keep the same magnitude and accumulate within the system, which increases the variance of the system's fundamentals. Alternatively, following its low recovery rate, the system shouldn't be able to ‡uctuate too much around its prevailing state so that fundamentals'variance should decrease. Under the …rst scenario, the increase in variance happens before the occurrence of a critical transition. Thirdly, an increase in ‡uctuations'asymmetry, i.e. skewness, can arise before the occurrence of a catastrophic bifurcation. Under the fold catastrophe model for example, the system can reach two alternative stable equilibrium states (solid lines) and one intermediate unstable equilibrium state (dashed line, see …gure 1). Speci…cally, unstable equilibria illustrate the border between the basins of attractions of the two previous stable states. When slowing down, the system stays more often in an unstable equilibrium than in a stable equilibrium, generating therefore asymmetry.

As a result, …rst-order auto-correlation, variance and asymmetry can indicate the vicinity of a tipping point when a dynamical system gets closer to a critical transition (Carpenter and tors can indeed anticipate critical transitions in …nancial markets such as the beginning of a major crisis.

Data and empirical application

In this section, we set the focus on the ability of critical slowing down indicators to predict the Global Financial Crisis. We consider stock market indices for the U.S. stock market and for ten European stock exchanges such as Belgium, France, Germany, Greece, Ireland, Italy, Netherlands, Portugal, Spain and U.K. Data span from October 10 th , 2002 to July 2 nd , 2007 (i.e. 10OCT02-02JUL07 period), which starts at the end of the Dot.com bubble and terminates at the beginning of the GFC (see 1). Speci…cally, we implement the analysis on To detrend series, we employ a classical moving-average process. For a given series fy t g T t=1 , the corresponding detrended series fx t g T t=1 is computed as:

x t = y t M A t (1)
where M A t is a signal, computed as:

M A t = P t 1 i=t T G(i)y t i t 1 P i=t T G(i) (2)
and G(:) is a gaussian kernel de…ned as:

G(i) = 1 p 2 e i 2 2 2
(3)

In (3), is the bandwidth parameter, which is normally assumed to range from We compute the three critical slowing down indicators of detrended logindices. We …rst report results for the log-indices and then for cumulative returns.

Log-indices

First-order auto-correlation First-order auto-correlation is considered as the major indicator of phase transitions.

2

  Documents de travail du Centre d'Economie de la Sorbonne -2016.45R (Version révisée) ten European countries plus the United States, from the post Dot.com bubble up to the beginning of the Global Financial Crisis (GFC). We focus on two kinds of data, the main indices, in log-form, as suggested by Diks et al. [DIK 15] within a similar framework, and the cumulative returns, which are considered as a re-scalling of main indices. Then, we analyze whether auto-correlations at lag one, as well as moments of orders two and three increase before the crisis, thus signaling a phase transition. Following Lenton et al. [LEN 12], our study is performed on large rolling windows of size T =2 and T =4, T being the length of the whole sample period, and on detrended data, using a Gaussian kernel with a low bandwith. Whereas CSD has turned to be very useful in other domains, our results are here quite mitigated. Compared to Diks et al. [DIK 15], we …rst show that using log-indices, basing our analysis on …rst-order autocorrelations, leads to false alarms. At best, and unexpectedly the analysis might have an informational content about the May 2006 market crash, but not about the Global Financial Crisis, i.e. not about a phase transition. There is no information in the evolution of the variances and skewness, which questions the use of log-indices in this kind of analysis. Applied to cumulative returns, indicators, do provide an important information about the GFC, but only through upward trends in variances and sudden downward trends in skewness. But still, …rst-order autocorrelations provide no useful information. Since upward trends in variances have been reported by several authors, such as Hens and Schenk-Hoppe [HEN 09] in other frameworks, and since …rst-order autocorrelations are considered as the main indicator of CSD, concluding about the validity of CSD is by far not straightforward.

  e. a critical transition (Carpenter et al. [CAR 11], Sche¤er [SCH 09]). Such phenomenon is called critical slowing down (van Nes and Sche¤er [NES 07], Sche¤er [SCH 09], Wissell [WIS 84]). Under a slowing down regime, the pattern of data ‡uctuations undergoes modi…cations, which can be characterized by a set of three indicators. Such indicators signal the closeness of the system to a tipping point. Firstly, among predicted changes, data auto-correlation should increase (Livina and Lenton [LIV 07], Ives [IVE 95]

  [IVE 95], van Nes and Sche¤er [NES 07]). Such a characteristic can be observed a long time before the critical transition (Dakos et al. [DAK 08]). Secondly, critical slowing down can also translate into an increase and sometimes a decrease in variance (Berglund and Gentz [BER 06], Carpenter and Brock [CAR 06], Dakos et al. [DAK 12]

  Brock [CAR 06], Carpenter et al. [CAR 11], Dakos et al. [DAK 08], [DAK 12], Drake and Gri¤en [DRA 10]). As such, they can be considered as critical slowing down indicators, or equivalently, early warning signals, which predict a signi…cant future transition in the dynamical system's state (van Nes et al. [SCH 12]). Hence, such indicators can help predict forthcoming downward shifts in …nancial markets, i.e. …nancial crises. For example, …nancial markets' reversals can happen after a period of either increased volatility (Hens and Schenk-Hoppe [HEN 09]) or decreased volatility (Arvedlund [ARV 02]). Moreover, variance and …rst-order autocorrelations are linked in …nancial markets (Campbell et al. [CAM 93]). In the following of the chapter, we'll study if critical slowing down indica-5 Documents de travail du Centre d'Economie de la Sorbonne -2016.45R (Version révisée)

Figure 1 :

 1 Figure 1: Fold catastrophe model and critical transition (F 1 and F 2 are bifurcation points, source: Sche¤er [SCH 09]).

  computed log-indices and on cumulative returns of indices. To extract the relevant information in view of our critical slowing down study, we follow the methodology of Dakos et al. (2008). In their paper, they propose a two-step methodology while analyzing univariate time series. First, 6 Documents de travail du Centre d'Economie de la Sorbonne -2016.45R (Version révisée)

where T = 1122 .

 1122 Over each rolling window, considering detrended time series, compute: a) First-order auto-correlations by ordinary least squares, b) The second moment, c) The third moment.

10 to 20 .8

 20 According to …gure (2), a high value of the bandwidth parameter such as setting = 20 tends to slightly oversmooth the series, possibly introducing 7 Documents de travail du Centre d'Economie de la Sorbonne -2016.45R (Version révisée) an arti…cially high auto-correlation. Hence in the sequel of the study, the lowest bandwidth value = 10 will be applied. Documents de travail du Centre d'Economie de la Sorbonne -2016.45R (Version révisée)

Figure 2 :9

 2 Figure 2: SP500 (log), trends for two di¤erent bandwidths and corresponding detrended series.

  Figure (3) summarizes the resultsfor the two rolling windows using log-indices. It provides heatmaps, which illustrate the magnitude of autocorrelations over time for each stock exchange under consideration. The darker the colour, the stronger the …rst-order autocorrelation is. Clearly, there is no empirical evidence of an increase in the …rstorder dependence of stock market indices, except maybe for Portugal, before the GFC. Heatmaps rather suggest that auto-correlations decrease for some countries, in particular France and the United-States, which invalidates the announcement of the GFC contrary to what happened later to these countries.Moreover, the result is robust, whatever the considered rolling window is. Nevertheless, it is obvious that …rst-order correlations, based on T =2 trigger a false alarm in late 2005, early 2006, where at best it might provide an informational content concerning the May 2006 market crash, for some countries such as Ireland, Belgium, Netherland, or UK. The May 2006 market crash being not a phase transition. Figure (4) clearly shows a sharp increase in the magnitude of the autocorrelations, followed by a plateau up to early May 2006. Nevertheless, on the end of the period sample, there is no information concerning the GFC.

Figure 3 :

 3 Figure 3: First-order autocorrelation of log-indices for two rolling windows: T =2 (left), T =4 (right).

Figure 4 :Figure 5 :Figure 6 :

 456 Figure 4: Smoothed autocorrelations of log-indices based on rolling windows (T =2).Vertical reference 10MAY06.

Figure 7 :Figure 8 :Figure 9 :Figure 10 :Figure 11 :

 7891011 Figure 7: First-order autocorrelation of cumulative returns for two rolling windows: T =2 (left), T =4 (right).

4

  ConclusionIn this chapter, we have tested the ability of critical slowing down indicators to predict a major future crisis such as the GFC in the present case. Our results are mitigated and deeply depend on both the series used and the indicators. Using log-indices, as in Diks et al. [DIK 15], the framework clearly fails to predict the GFC, leading to a false alarm. Indeed, based on autocorrelations, we falsely predict a phase transition, whereas we only observe the May 2006 market crash, which is not a phase transition. This result holds for some countries, as shown by related heatmaps. Also, there is no clear informational content in the second and third moments. This result deeply questions the use of log-returns in this kind of analysis. Considering cumulative returns, …rst-order autocorrelations still convey no relevant information. Conversely, the analysis of trends in variance and skewness turns out to be very useful. Especially, trends in variance as well as shifts in skewness do precede the GFC. There are several conclusions to draw from our …ndings. First, concerning 25 Documents de travail du Centre d'Economie de la Sorbonne -2016.45R (Version révisée) the series used, the study performs much better on a re-scaled index than on a log-index. Second, concerning CSD indicators, whether we can have increases in variance and/or skewness without an upward trend in …rst-order autocorrelation is unclear. As a result, drawing sound conclusions about the validity of CSD for …nancial markets is by far not straightforward. Nevertheless, within or beyond the CSD, we found that increases in variance (Carpenter et al. [CAR 11]) and skewness (Guttal et al. [GUT 08]) are two useful early warning indicators. A combination of these two moments may provide a good early warning signal for …nancial markets, i.e. the probability of an upcoming …nancial crisis.

Table 1 :

 1 Stock market indices

	Country	Index label
	Belgium	BEL20
	France	CAC40
	Germany	DAX
	Greece	ASE
	Ireland	ISEQ
	Italy	FTSEMIB
	Netherland	AEX
	Portugal	PSI
	Spain	IBEX
	U.K.	UKX
	USA	SP500

detrend daily log-indices and cumulative returns over the 10OCT02-02JUL07 period. Second, de…ne rolling windows with two di¤erent sizes, T =2 and T =4;

Table ( 2

 ( ) summarizes our …ndings for both log-indices and cumulative re-

	turns.
	Table 2: Usefulness of indicators to predict the GFC
	Country	AR(1) Variance Skewness
	Belgium	No	Yes	Yes
	France	No	Yes	Yes
	Germany	No	Unclear	No
	Greece	No	Yes	Yes
	Ireland	No	Yes	No
	Italy	No	Yes	Yes
	Netherland	No	Unclear	Yes
	Portugal	Yes	Yes	Yes
	Spain	No	Yes	No
	U.K.	No	Yes	Yes
	USA	No	No	Yes

Documents de travail du Centre d'Economie de la Sorbonne -2016.45R (Version révisée)

Such perturbations can consist of a possible combination of additive and multiplicative noises. 4 Documents de travail du Centre d'Economie de la Sorbonne -2016.45R (Version révisée)

Acknowledgement 1 This work was achieved through the Laboratory of Excellence on Financial Regulation (Labex ReFi) supported by PRES heSam under the reference ANR10LABX0095. It bene…ted from a French government support managed by the National Research Agency (ANR) within the project Investissements d'Avenir Paris Nouveaux Mondes (investments for the future Paris New Worlds) under the reference ANR11IDEX000602.


Vasilis Efthymiou

Kostas Stefanidis

Vassilis Christophides
email: vassilis.christophides@inria.fr

Minoan ER: Progressive Entity Resolution in the Web of Data

Entity resolution aims to identify descriptions of the same entity within or across knowledge bases. In this work, we present the Minoan ER platform for resolving entities described by linked data in the Web (e.g., in RDF). To reduce the required number of comparisons, Minoan ER performs blocking to place similar descriptions into blocks and executes comparisons to identify matches only between descriptions within the same block. Moreover, it explores in a pay-as-you-go fashion any intermediate results of matching to obtain similarity evidence of entity neighbors and discover new candidate description pairs for resolution.

DESCRIPTION

Over the past decade, numerous knowledge bases (KBs) have been built to power large-scale knowledge sharing, but also an entity-centric Web search, mixing both structured data and text querying. These KBs offer comprehensive, machine-readable descriptions of a large variety of real-world entities (e.g., persons, places, products, events) published on the Web as Linked Data (LD). Although KBs (e.g., DBpedia, Freebase) may be derived from the same data source (e.g., a Wikipedia entry), they may provide multiple, nonidentical descriptions of the same real-world entities. This is mainly due to the different information extraction tools and curation policies employed by KBs, resulting to complementary and sometimes conflicting entity descriptions. Entity resolution (ER) aims to identify descriptions that refer to the same real-world entity appearing either within or across KBs [START_REF] Christophides | Entity Resolution in the Web of Data[END_REF][START_REF] Dong | Big Data Integration[END_REF]. Compared to data warehouses, the new ER challenges stem from the openness of the Web of data in describing entities by an unbounded number of KBs, the semantic and structural diversity of the descriptions provided across domains even for the same real-world entities, as well as the autonomy of KBs in terms of adopted processes for creating and curating entity descriptions. In particular: The two core ER problems, namely how can we (a) effectively compute similarity of entity descriptions and (b) efficiently resolve sets of entities within or across sources, are challenged by the large scale (both in terms of the number of sources and entity descriptions), the high diversity (both in terms of number of entity types and properties) and the importance of relationships among entity descriptions (not committing to a particular schema defined in advance). In particular, in addition to highly similar descriptions that feature many common tokens in values of semantically related attributes, typically met in the center of the LOD cloud and heavily interlinked mostly using owl:sameAs predicates, we are encountering somehow similar descriptions with significantly fewer common tokens in attributes not always semantically related, that appear usually in the periphery of the LOD cloud and are sparsely interlinked with various kinds of predicates. Plainly, the coming up of highly and somehow similar semi-structured entity descriptions requires solutions that go beyond those applicable to duplicate detection. A promising area of research in this respect is cross-domain similarity search and mining [START_REF] Zhen | Cross-modal similarity learning via pairs, preferences, and active supervision[END_REF][START_REF] Shrivastava | Data-driven visual similarity for cross-domain image matching[END_REF], aiming to exploit similarity of objects described by different modalities (i.e., text,

Poster Paper

Series ISSN: 2367-2005 We present in this poster the Minoan ER platform for resolving entities described by linked data in the Web (e.g., in RDF). Figure 1 illustrates the general steps involved in our process. Blocking and Meta-blocking in Minoan ER: We use blocking as a pre-processing step for ER to reduce the number of required comparisons. Specifically, blocking places similar entity descriptions into blocks, leaving to the entity matching algorithm the comparisons only between descriptions within the same block.

Typically, token-based blocking algorithms place highly similar descriptions (having many common tokens) in many common blocks; intuitively, the more common blocks two descriptions share, the more likely it is that they match. This leads to many repeated comparisons between the same pairs of descriptions. To overcome this problem, we accompany blocking with meta-blocking, which prunes such repeated comparisons. Moreover, meta-blocking aims at discarding comparisons between descriptions that share few common blocks and are thus less likely to match. In Minoan ER, to support a Web-scale resolution of heterogeneous and loosely structured entities across domains, we use algorithms for blocking and meta-blocking that disregard strong assumptions about knowledge of the data schema and rely on a minimal number of assumptions about how entities match (e.g., when they feature a common token in their descriptions or URIs) within or across sources. For doing so, we exploit the parallel processing power of a computer cluster via Hadoop MapReduce, as presented in [START_REF] Efthymiou | Big data entity resolution: From highly to somehow similar entity descriptions in the Web[END_REF][START_REF] Efthymiou | Parallel meta-blocking: Realizing scalable entity resolution over large, heterogeneous data[END_REF]. Progressive Entity Matching in Minoan ER: Blocking approaches in the Web of data, especially when handling somehow similar descriptions appearing in the periphery of the LOD cloud, may miss highly heterogeneous matching descriptions featuring few common tokens [START_REF] Efthymiou | Big data entity resolution: From highly to somehow similar entity descriptions in the Web[END_REF]. To overcome that, we focus on exploiting the partial matching results as a similarity evidence for their neighbor (i.e., linked) descriptions. Since this inherently iterative process entails an additional overhead, we are interested in maximizing its benefit, given a computational cost budget. So, we need to estimate which part of the graph is the most promising to explore in the next iteration, in a progressive way.

In this respect, Minoan ER focuses on extending the typical ER workflow with a scheduling phase, which is responsible for selecting which pairs of descriptions, that have re-sulted from blocking, will be compared in the entity matching phase and in what order. The goal of this new phase is to favor more promising comparisons, i.e., those that are more likely to increase the targeted benefit. This way, those comparisons are executed before less promising ones and thus, higher benefit is provided early on in the process. The update phase propagates the results of matching, such that a new scheduling phase will promote the comparison of pairs that were influenced by the previous matches. This iterative process continues until the cost budget is consumed.

In contrast to existing works in progressive relational ER (e.g., [START_REF] Altowim | Progressive approach to relational entity resolution[END_REF]), which consider the quantity of entity pairs resolved, as the benefit of ER, we explore different aspects of data quality, improved through ER. In particular, we are interested in characterizing the quality of the resolved pairs, with respect to the number of descriptions resolved, corresponding to the same real-world entity (targeting attribute completeness), the number of real-world entities resolved (targeting entity coverage), and the number of real-world entity graphs resolved (targeting relationship completeness).

Figure 1 :

 1 Figure 1: The Minoan ER Framework.

Acknowledgements: This work was partially supported by the EU H2020 PARTHENOS (#654119), FP7 DIACHRON (#601043) and FP7 SemData (#612551) projects.


Clara Barbanson

Andrés Almansa

Yann Ferrec

Reconstruction du relief par images des plans épipolaires à partir d'acquisitions aériennes denses

teaching and research institutions in France or abroad, or from public or private research centers.

Reconstruction du relief par images des plans épipolaires à partir d'acquisitions aériennes denses

Clara Barbanson 1 , Andrés Almansa 2 , Yann Ferrec 1 , Pascal Monasse Dans le domaine des imageurs infrarouges hyperspectraux aéroportés, l'ONERA a développé Sieleters, un spectromètre imageur à transformée de Fourier basé sur un interféromètre statique. En raison du mode d'acquisition de ce type d'instrument, les variations d'élévation d'une scène, si elles ne sont pas connues, entraînent des diffcultés de reconstruction des spectres. L'objectif du travail présenté ici est d'estimer le relief de la scène à partir des images acquises par Sieleters elles-mêmes. L'originalité de la méthode proposée vient de la nature des images, qui contiennent des franges d'interférences, ainsi que de leur nombre, puisque l'instrument acquiert des images à très fort recouvrement, décalées chacune d'un pixel, soit 50cm.

Contexte

Sieleters est un spectromètre imageur à transformée de Fourier statique [START_REF] Sieleters | an airborne infrared dual-band spectro-imaging system for measurement of scene spectral signatures[END_REF]. Il comporte un interféromètre de Michelson, placé en amont de l'objectif d'imagerie, qui génère, au niveau de l'image, des franges d'interférences codant l'information spectrale. L'image obtenue en sortie est donc la superposition de la scène à des franges d'interférence rectilignes, comme le montre la fgure 1. Ces franges sont fxes par rapport au détecteur, et le déflement de la scène est assuré par le déplacement de l'avion. Chaque ligne de l'image a donc une même valeur de différence de marche.

L'avion suivant une trajectoire rectiligne (perpendiculaire aux franges d'interférences), tout point au sol est vu successivement sur chacune des lignes de l'image, c'est-à-dire sous différents états d'interférence. On peut alors reconstruire un interférogramme pour chaque élément de la scène, et leur spectre par transformée de Fourier. Si la scène présente du relief et qu'on n'en tient pas compte, alors les correspondances entre les différentes images associées pour la construction de l'interférogramme sont incorrectes, et le spectre est erroné. Il faut donc disposer d'un modèle numérique de surface (MNS). Dans ce travail, nous nous proposons de déterminer ce MNS à partir des images elles-mêmes.

Méthodes

Compte tenu du fait que le porteur a une trajectoire rectiligne, et afn de tenir compte des nombreuses images à disposition, la méthode des images des plans épipolaires [START_REF]Epipolar-Plane Image Analysis : An approach to determining structure from motion[END_REF][START_REF]Scene reconstruction from high spatio-angular resolution light felds[END_REF], nommées EPI par la suite, a semblé intéressante. Partant d'images recalées en géométrie épipolaire, cette méthode exploite le fait qu'en trajectoire rectiligne, les centres d'images sont colinéaires. Dans ce cas, les plans épipolaires sont identiques pour toutes les paires d'images. L'idée est alors de construire des images spatio-temporelles, les EPI, à partir des lignes épipolaires correspondantes, issues de chacune des images. On obtient ainsi une image de droites, qui représentent les « trajectoires » des éléments de la scène par rapport à la caméra. La pente de ces lignes est inversement proportionnelle à la disparité : plus un point est éloigné de la caméra, plus la pente de sa droite sur l'EPI sera élevée.

Cependant, comme nos images possèdent des franges d'interférences, un algorithme d'extraction de segments risque d'être perturbé, puisque ces franges induisent dans l'image épipolaire des variations radiométriques décorrélées du relief. Le choix a donc été fait d'effacer les franges des images.

L'effacement des franges a été dirigé par le fait que leurs fréquences spatiales, dans l'espace de Fourier, sont principalement limitées à une zone du spectre, appelée Ω. En faisant l'hypothèse d'un modèle d'image où l'image mesurée, w, est décrite comme la somme d'une image de la scène sans franges, u, et d'une image de franges, v, on cherche u, en minimisant variation totale sur u. La variation totale (TV) est un opérateur qui lisse les zones homogènes d'une image tout en conservant les discontinuités [START_REF] Rudin | Nonlinear total variation based noise removal algorithms[END_REF][START_REF]Edge direction preserving image zooming: a mathematical and numerical analysis[END_REF][START_REF]Decomposition and restoration using total variation minimization and the H 1[END_REF]

Perspectives

La hauteur de vol étant, dans notre cas, nettement supérieure aux hauteurs relatives des éléments de la scène, les orientations des lignes de l'EPI sont très proches. Il est donc d'autant plus important de déterminer précisément les pentes, ce qui sera facilité par l'absence de franges. L'algorithme d'extraction des lignes de l'EPI est en cours de traitement. Sa précision conditionnera la qualité de la carte de disparité.

3 1:

 3 Onera, Chemin de la Hunière et des Joncherettes BP 80100, 91123 Palaiseau Cedex -France 2: Télécom Paristech, 46 rue Barrault, 75634 Paris Cedex 13 -France 3 : Ecole des Ponts ParisTech, 6-8, Av Blaise Pascal -Cité Descartes, Champs-sur-Marne, 77455 Marne-la-Vallée cedex 2 -France clara.barbanson@onera.fr

Figure 1 :

 1 Figure 1 : Image mesurée par Sieleters. On observe, dans la partie basse de l'image, des franges très contrastées.

  . Le problème d'optimisation s'exprime alors de la forme suivante : minu TV(u) sous contraintes : û|Ωc = ŵ|Ωc et w = u + v Où l'accent circonfexe désigne la transformée de Fourier, et Ωc est la zone fréquentielle complémentaire de Ω. Résultats La méthode d'effacement des franges a permis d'obtenir des images où les franges ont été effacées sur les zones lisses. Sur les zones à forte discontinuité radiométrique, elles n'ont pas tout à fait disparu (insuffsance du modèle additif), mais ont néanmoins été suffsamment atténuées pour permettre de traiter le problème géométrique. Une image des plans épipolaires obtenue est montrée sur la fgure 2. Elle correspond à la scène présentée en fgure 1. La colonne encadrée dans l'image des plans épipolaires correspond à celle encadrée dans l'image 1. Chaque ligne représente donc un objet, et l'axe des abscisses montre l'évolution de son déplacement d'une image à l'autre.

Figure 2 :

 2 Figure 2 : Image des plans épipolaires (EPI). V est l'axe spatial des colonnes de l'image, le même que pour l'image originale. S est l'axe des numéros d'images (assimilé au temps).