Karim Benouaret
email: karim.benouaret@inria.fr

Raman Valliyur-Ramalingam
email: raman.valliyur-ramalingam@loria.fr

Franc ¸ois Charoy

Answering Complex Location-Based Queries with Crowdsourcing

Keywords: Crowdsourcing, Location-Based Queries, Query Transformation, Process Management

Crowdsourcing platforms provide powerful means to execute queries that require some human knowledge, intelligence and experience instead of just automated machine computation, such as image recognition, data filtering and labeling. With the development of mobile devices and the rapid prevalence of smartphones that boosted mobile Internet access, location-based crowdsourcing is quickly becoming ubiquitous, enabling location-based queries assigned to and performed by humans. In sharp contrast of existing location-based crowdsourcing approaches that focus on simple queries, in this paper, we describe a crowdsourcing process model that supports queries including several crowd activities, and can be applied in a variety of location-based crowdsourcing scenarios. We also propose different strategies for managing this crowdsourcing process. Finally, we describe the architecture of our system, and present an experimental study conducted on pseudo-real dataset that evaluates the process outcomes depending on these execution strategies.

I. INTRODUCTION

Over time the World Wide Web has evolved beyond just being a platform for retrieving information. It has become an essential mean for sharing user-generated information and a communication platform for many people.

Furthermore, crowdsourcing, also known as human computation or social computation, is an emerging computation paradigm. People use increasingly crowdsourcing platforms such as Amazon Mechanical Turk1 , oDesk 2 and Crowd-Flower 3 to solve problems that require human intelligence, experience and assistance.

With the development of mobile devices, and the prevalence of smartphones that boosted mobile internet-access, people can provide various types of data such as photos, location, etc. any time and any where. Therefore, it appears interesting to request contribution from people utilizing facilities of their device together with their intelligence and knowledge for answering location-based queries.

Substantial research work has addressed the problem of answering queries with crowdsourcing from different perspectives and within various communities, including database [START_REF] Doan | Crowdsourcing applications and platforms: A data management perspective[END_REF], [START_REF] Franklin | Crowddb: answering queries with crowdsourcing[END_REF], [START_REF] Liu | Cdas: A crowdsourcing data analytics system[END_REF], information retrieval [START_REF] Alonso | Crowdsourcing for information retrieval: principles, methods, and applications[END_REF], [START_REF]Crowdsourcing for information retrieval: principles, methods, and applications[END_REF], [START_REF] Lease | Crowdsourcing for information retrieval[END_REF], image processing [START_REF] Chen | A crowdsourceable qoe evaluation framework for multimedia content[END_REF], [START_REF] Lee | Surfing in the crowd: feasibility study of experience sharing in a taiwanese night market[END_REF], [START_REF] Yan | Crowdsearch: exploiting crowds for accurate real-time image search on mobile phones[END_REF] as well as geographic information systems [START_REF] Alt | Location-based crowdsourcing: extending crowdsourcing to the real world[END_REF], [START_REF] Bulut | Crowdsourcing location-based queries[END_REF], [START_REF] Kazemi | Geocrowd: enabling query answering with spatial crowdsourcing[END_REF]. These works are important and useful, but we claim that they cannot support the kind of queries we are considering. Especially, these approaches focus on answering simple queries such as "take a photo of a given suspect" and "check the opening hours of a given store". Instead, we propose a crowdsourcing approach to answer complex location-based queries, i.e., queries that require the combination of several atomic tasks.

To illustrate the problem of answering location-based queries with crowdsourcing, imagine that the mayor of Nancy -a middle sized city from the North-East of France -wants to get a view on the state of the roads of the city to schedule repairs. He asks for citizens' contribution and collaboration to help him to achieve that goal. Two main reasons motivate the need of citizens' participation. First, in this kind of scenarios, information provided by humans (citizens) is more relevant than that provided by sensors and computers. Second, it can be done on a lower budget since citizens' participation is not directly rewarded.

The mayor may ask the following query: "what roads need a repair in Nancy". This query is simple when you ask experts to do it with a precise specification. It is more tricky when you want ordinary citizens to help you. Specifically, if hundreds of roads are reported as damaged, are all these roads really need a repair? And more importantly, how to find those that need an immediate repair?

Fortunately, smartphones are becoming increasingly sophisticated with cameras and wireless connectivity. In addition, according to digitalbuzz 4 , mobile Internet usage should take over desktop Internet usage by 2014. Thus, the query can be changed to: "provide photos of roads that need a repair in Nancy along with an assessment {not damaged, damaged, very damaged}". This query can be answered in a straightforward way, i.e., each participant send one or more photos of damaged roads along with their assessment. However, with this procedure, we may receive a lot of photos with different assessment for the same locations: some people may make mistakes, while some others may lie so that the roads in their vicinity will be repaired first.

A natural option is to use CrowdForge [START_REF] Kittur | Crowdforge: crowdsourcing complex work[END_REF], [START_REF] Kittur | Crowdforge: crowdsourcing complex work[END_REF], which gives the user the possibility to manually translate her/his main query into different tasks, and then the results of these tasks are combined to form the final results. However, the user may not know enough how to translate her/his query into different tasks. Thus, she/he needs to go through several trial-run processes to satisfy her/his needs. Another option is to use Turkomatik [START_REF] Kulkarni | Turkomatic: automatic recursive task and workflow design for mechanical turk[END_REF], [START_REF]Collaboratively crowdsourcing workflows with turkomatic[END_REF], which leverages the crowd to propose a transformation of the query into simple tasks. However, from a crowdsourcing vision, this system presents a complex set of tradeoffs involving delay and accuracy.

In this work, we propose to overcome this problem with a more sophisticated process: (i) ask some citizens to provide photos of roads that need a repair. We refer to this step as data collection; (ii) ask some other participants to select the most representative photo of the problem for each location since a lot of photos of the same location may be provided. We refer to this step as data selection; it ensures that for the following step the crowd will have the same view on the problem at hand and it allows removing irrelevant photos; and (iii) ask some people to assess each selected photo with the different assessments defined by the user. We refer to this step as data assessment.

Unfortunately, designing and managing this process execution would be very painful or costly for the mayor (or any other user), and most probably not easy to repeat. First, he has to transform his query into small tasks realizable by humans and post them to the crowd. Then, he needs to decide how and when to move from one step to another one, i.e., from data collection to data selection, or from data selection to data assessment. This has an impact on the accuracy of the results and on the execution time of the process. It is important to set up an effective locationbased crowdsourcing framework that would (i) automatically transform queries into simple tasks realizable by humans; and (ii) collect, aggregate and cleanse the data and answers provided by humans, and then return the results to the user.

In this paper, we argue that the process of data collection, data selection and data assessment can support a lot of scenarios, and we propose a location-based crowdsourcing framework to cope with the above-mentioned challenges. Our main contributions are summarized as follows:

• We propose a crowdsourcing process model, which aims at transforming a complex location-based crowdsourced query into an executable process; • We present different execution strategies to manage the process leading into different kind of outcomes;

• We describe the design and the architecture of our implemented location-based crowdsourcing system; • We experimentally evaluate the process outcomes depending on the proposed execution strategies, using pseudo-real dataset. The remainder of this paper is organized as follows: Section II reviews related work. In Section III, we present our location-based crowdsourcing process model, while in Section IV we describe different processing strategies to manage the process. Section V gives an overview on our implemented system. Then, Section VI presents our experimental evaluation. Finally, Section VII concludes the paper.

II. RELATED WORK

The work related to our falls in three crowdsourcing categories: optimizing crowdsourcing, location-based crowdsourcing and executing crowdsourcing processes. Hereafter, we provide some salient related work.

A. Optimizing Crowdsourcing

For quality assurance, current approaches; e.g., [START_REF] Franklin | Crowddb: answering queries with crowdsourcing[END_REF], [START_REF] Kazemi | Geocrowd: enabling query answering with spatial crowdsourcing[END_REF], [START_REF] Yan | Crowdsearch: exploiting crowds for accurate real-time image search on mobile phones[END_REF], propose to assign each task to multiple humans. It is typical to have k assignments per task, and then aggregate the results using majority voting. In our work, the data selection and data collection steps also rely on this kind of aggregation.

On the other hand, there has been some recent work that focus on designing fundamental strategies for optimizing the quality of the results. In [START_REF] Guo | So who won?: dynamic max discovery with the crowd[END_REF], the authors focus on finding the maximum, i.e., the highest ranked item in a set, using the crowd. The authors first introduce the judgement problem: given a set of comparison results, which element has the maximum likelihood of being the maximum element, and the next vote problem: given a set of results, which future comparisons will be most effective. Then, they prove that the optimal solution to both problems is NP-hard, and provide efficient heuristics that work well in practice. Finding the maximum in a crowdsourcing environment has also been considered in [START_REF] Venetis | Max algorithms in crowdsourcing environments[END_REF]. The authors first present several families of parametrized max algorithms that take as input a set of items and as output an item from the set that is considered as the maximum. Then, they we propose strategies that select appropriate max algorithm parameters. Parameswaran et al. consider in [START_REF] Parameswaran | Crowdscreen: algorithms for filtering data with humans[END_REF] the problem of filtering data with humans, and develop deterministic and probabilistic strategies to optimize the expected cost and quality. The work presented in [START_REF] Liu | Cdas: A crowdsourcing data analytics system[END_REF] provides an estimated accuracy for results based on workers' historical performances. The main objective is to minimize the cost by predicting how many questions must be asked in order to achieve a given quality. In [START_REF] Cao | Whom to ask? jury selection for decision making tasks on micro-blog services[END_REF], the authors study the problem of jury selection by utilizing crowdsourcing for decision-making tasks on micro-blog services. More specifically, the problem is to enrol a subset of a crowd under a limited budget, whose aggregated wisdom via majority voting has the lowest probability of drawing a wrong answer. To solve this problem, the authors propose efficient algorithms and effective bounding techniques. However, these approaches assume that the probability that each human provides the right answer is available, but in our case this information is not known.

B. Location-Based Crowdsourcing

With the rapid increase in smartphone technology, location-based crowdsourcing is becoming more popular. In [START_REF] Alt | Location-based crowdsourcing: extending crowdsourcing to the real world[END_REF], the authors propose a prototype for location-based mobile crowdsourcing consisting of a Web and a mobile client. Through these clients, people of the crowd can search for tasks and submit solutions. Similarly, in [START_REF] Bulut | Crowdsourcing location-based queries[END_REF], the authors design a framework for crowdsourcing locationbased queries on the top of Twitter. The Framework employs Foursquare to find the appropriate people to answer the query. In [START_REF] Kazemi | Geocrowd: enabling query answering with spatial crowdsourcing[END_REF] Kazemi and Shahabi introduce a taxonomy of spatial crowdsourcing and then propose three various techniques for assigning the maximum number of tasks to the crowd. They also introduce a taxonomy for spatial data. Unfortunately, these frameworks cannot support complex queries.

Given a query photo, taken from a given location l, and a set of photos of the same location l retrieved by a search engine, Yan et al. propose in [START_REF] Yan | Crowdsearch: exploiting crowds for accurate real-time image search on mobile phones[END_REF] a system that asks humans to vote for each photo to check whether it represents the query photo or not. The authors then propose some realtime techniques to find the appropriate photo. This process may be useful from location-based crowdsourcing vision, but cannot support collecting and handling masses of data.

C. Executing Crowdsourcing Processes

Despite all the studies on crowdsourcing, only a few studies have focus on executing crowdsourcing processes. The work presented in [START_REF] Kittur | Crowdforge: crowdsourcing complex work[END_REF], [START_REF] Kittur | Crowdforge: crowdsourcing complex work[END_REF] gives the user the possibility to translate manually her/his main query into different small tasks, and then the results of these tasks are combined to form the final results using a MapReduce-based approach. Similarly, in [START_REF] Minder | Crowdlang: A programming language for the systematic exploration of human computation systems[END_REF], the authors propose a crowdsourcing language allowing the user to transform her/his main query into a set of activities and to define the order in which these activities will be executed. However, the user may not know enough how to translate her/his query into different tasks. Thus, these approaches require a lot of efforts from the user. In [START_REF] Kulkarni | Turkomatic: automatic recursive task and workflow design for mechanical turk[END_REF], [START_REF]Collaboratively crowdsourcing workflows with turkomatic[END_REF], the authors propose to leverage the crowd to transform the query into a crowdsourcing process. The crowd first propose a set of simple tasks realizable by humans. Then, the crowd select a set of interesting task. Finally, the crowd replace the query with a set of simple tasks. However, from a crowdsourcing vision, this approach presents a complex set of tradeoffs involving delay and accuracy. While these approaches are manual, demanding a high number of crowd dependency for every execution step, in our approach we use the declarative query model, which aims to maximize automation, based on the data collection, data selection and data assessment process.

Bernstein et al. present in [START_REF] Bernstein | Soylent: a word processor with a crowd inside[END_REF], Soylent, a word processing interface that enables to short, proofread of documents. The authors introduce the Find-Fix-Verify pattern, which splits tasks into a series of generation and review stages. However, this pattern is designated for word processing and cannot support collecting data.

On the other hand, some approaches; e.g., [START_REF] Khazankin | Optimized execution of business processes on crowdsourcing platforms[END_REF], [START_REF] Kucherbaev | Business processes for the crowd computer[END_REF], propose to incorporate crowdsourcing activities into business processes. The main idea is to combine business processes and crowdsourcing. But these approaches remain very sequential compared to the execution strategies we propose.

III. LOCATION-BASED CROWDSOURCING PROCESS MODEL

The first challenge is to transform a complex locationbased query into an executable process. In this section, we first define the input model of our framework. Then we describe how to extract the data collection, data selection and data assessment tasks from this input. Finally, we propose an output model. For reference, Table I summarizes the frequently used notations.

A. Input Model

We consider a simplified formalization of query to give users the flexibility to pose their queries on one hand, and to ease achieving our contextualized goal on the other hand.

The input for our framework is a query Q, which follows the format of < O, C, R, A, T s , T e , S >, where O describes the set of objects the user is looking for, C describes the context of O that the crowd has to consider in answering Q, R stands for the region, e.g., a city, A = {a 1 , a 2 , . . . , a m } comprises the domain of the assessments that can be attributed to O in the context of C, T s and T e are respectively the start and end time of the query execution, and S is a parameter to select an execution strategy (we present different execution strategies in Section IV, namely, Buffer, Deadline and FIFO). The query in our example can be represented as: <roads, need repair, Nancy, {not damaged, damaged, very damaged}, 07/01/2013 -8:00, 07/03/2013 -20:00, Deadline>. In our example, a data collection task is represented as <roads, need repair, Nancy>. It asks citizens to take photos of road that need repair in Nancy.

B. Tasks Model

As a lot of photos of the same objects in a given location l i ∈ R, e.g., photos of the same roads, are expected, we need to filter these similar photos to select the most representative photo of location l i , in the context C. This step, i.e., data selection, ensures that for the next step, i.e., data assessment, all participants will have the same view on the problem and it allows removing irrelevant photos. We use the term jury to denote a set of humans that can make decision either on data selection or on data assessment. Formally, a jury J i = {h 1 , h 2 , . . . , h k } is a set of k humans. Each human h j ∈ J i is called a juror. Data selection task: given a set P i = {p i1 , p i2 , . . . , p ini } of photos, within context C, and taken from the same location l i , we define a data selection task DST as a triple < P i , C, l i >. It requires a jury J i to vote "yes" for photos that represent location l i within context C, and "no" for the remaining ones.

The answer to a data selection task DST :-< P i , C, l i > is called selection voting. Formally a selection voting SV i = {(p i1 , sv 1 ), (p i2 , sv 2 ), . . . , (p ini , sv ni )} is a set of tuples, where sv j is the selection score the photo p ij ; it represents the number of "yes" votes for the photo p ij . The photos p ij with the highest selection score sv j , with sv j ≥ k 2 , i.e., he majority of jurors have agreed that p ij represents location l i in the context C, is called the most representative photo of location l i within context C, and it is denoted by p * i . Note that if P i comprises only one photo p ij , i.e., P i = {p ij }, then p ij is the most representative photo of location l i within context C if and only if sv j ≥ k 2 , i.e., the majority of jurors vote "yes" for the photo p ij . Thus, it is typical to have k odd, allowing majority voting. It is also worth to note that, if several photos have the best score, a random one, among them, will be selected as the most representative photo.

Once the most representative photo p * i of location l i within context C is selected, we need to assess it in order to return the observation in location l i to the user. i with an assessment a j ∈ A in the context C. The answer to a data assessment task DAT :-< p * i , C, A > is called assessment voting. Formally an assessment voting AV i = {(a 1 , av 1 ), (a 2 , av 2 ), . . . , (a m , av m )} is a set of tuples, where av j is the assessment score the assessment a j ; it represents the number of jurors who assessed p * i with a j . The assessment a j with the highest assessment score av j is called the assessment of the photo p * i , and it is denoted by a * i . Similar to the case of data selection, if several assessment have the best score, a random one, among them, will be selected as the assessment of the photo p * i . It is also worth to note that we can compute a mean instead of the mode. However, it is not applicable in all scenarios since the labels can change with scenario and the mean would not be meaningful. For example if the assessment is {uneven pavement, road pothole, road crack}, we cannot compute the mean.

C. Output Model

The output of our framework, which comprises the result of the query Q, is a set of triples < l i , p * i , a * i >, i.e., a set of photos of O along with their locations and assessments. For easy and better viewing the output, one can then invoke a map-based result visualisation service. Fig. 1 shows a screenshot of the output model of of our system.

IV. QUERY PROCESSING STRATEGIES

The second challenge in building our framework is managing and executing the different tasks, and detecting citizen errors or misbehaviour -recall that the probability that each human provides the right answer is not available in our case. The natural option to handle the errors is to distribute each task to k participants and to aggregate the answers. Our framework follows this direction for data selection and data assessment tasks (|J i | = k; see Section III-B) since we assume that we will always find participants to provide such answers. However, a data collection task is more critical since (i) it requires citizens to be on-site to take photos; and (ii) it has an influence on the data selection and data assessment tasks. Of course, we can wait for k photos in each location l i , but, this may take a very long time for some critical scenario like crisis management, where results are required insistently. On the other hand, in some other scenarios, where a high quality is required, k photos may not be sufficient to get the right result. Therefore, the number of photo that we need for each location depends on the scenario as well as the duration of the query, i.e., T s and T e . Given a query Q:-< O, C, R, A, T s , T e , S >, we present in this section three different strategies, namely Buffer, Deadline and FIFO, to handle with these issues.

A. Buffer Strategy

Algorithm 1 shows the idea of the Buffer strategy. The process starts at T s (loop in line 2) with crowdsourcing the data collection task (line 4). Then the following process (loop in line 5) is repeated until T e . Waits for k photos of O in each location l i then distribute the selection task regarding location l i (lines 6-10). When k jurors complete their voting, the wining photo p * i is selected as the most representative photo of O for location l i in context C, then the assessment task regarding location l i is asked (lines 11-18), and wait for k votes. Once the assessment voting is done, the winning assessment a * i is considered as the appropriate assessment for the photo p * i and then the triple < l i , p * i , a * i > is returned to the user (lines [START_REF] Parameswaran | Crowdscreen: algorithms for filtering data with humans[END_REF][START_REF] Cao | Whom to ask? jury selection for decision making tasks on micro-blog services[END_REF][START_REF] Minder | Crowdlang: A programming language for the systematic exploration of human computation systems[END_REF][START_REF] Bernstein | Soylent: a word processor with a crowd inside[END_REF][START_REF] Khazankin | Optimized execution of business processes on crowdsourcing platforms[END_REF][START_REF] Kucherbaev | Business processes for the crowd computer[END_REF][25][26]. The process proceeds in the same manner for each location until T e (loop in line 5).

B. Deadline Strategy

The buffer strategy starts data selection only when it gets k photos for a given location l i . If citizens do not provide k photos of some locations at T e , we lose those results. This situation is expected in practice since some locations are more visited than others. To overcome this limitation, we propose the Deadline strategy. Algorithm 2 outlines the online processing of this strategy. The process starts at T s (loop in line 2) with crowdsourcing the data collection task (line 4). Then the idea is to collect photos of O starting from T s until a deadline d (loop in line 5) and to built buckets of photos -each bucket regroups photos of the same location l i . At time d, a data collection task is requested for each location l i (loop in line 9). The next steps are similar to the Buffer strategy. After the selection voting, the wining photo p * i is selected as the most representative photo of O for location l i in context C, and the assessment task regarding location l i is asked (lines [START_REF] Kazemi | Geocrowd: enabling query answering with spatial crowdsourcing[END_REF][START_REF] Kittur | Crowdforge: crowdsourcing complex work[END_REF][START_REF] Kittur | Crowdforge: crowdsourcing complex work[END_REF][START_REF] Kulkarni | Turkomatic: automatic recursive task and workflow design for mechanical turk[END_REF][START_REF]Collaboratively crowdsourcing workflows with turkomatic[END_REF][START_REF] Guo | So who won?: dynamic max discovery with the crowd[END_REF][START_REF] Venetis | Max algorithms in crowdsourcing environments[END_REF][START_REF] Parameswaran | Crowdscreen: algorithms for filtering data with humans[END_REF]. Once the assessment voting is completed, the winning assessment a * i is considered as the relevant assessment for the photo p * i and then the triple < l i , p * i , a * i > is returned to the user (lines 20-27). This two steps proceeds in the same manner until T e (loop in line 11).

C. FIFO Strategy

To move from the data collection phase to the data selection phase for a given location l i , the buffer and deadline strategies wait for k photos of l i or for the deadline d, respectively. It might be interesting to consider an execution that would generate results more instantly and where the result size would increase gradually. We present in Algorithm 3 the FIFO strategy, which proceeds as follows. The process starts at T s (loop in line 2) with crowdsourcing the data collection task (line 4). When receiving a photo p ij of O from a given location l i and there is not a voting regarding location l i , FIFO immediately asks participants to vote for this photo to see if it really represents location l i in the context C (lines 6-10), and wait for k answers. Once the selection voting is done, if the majority of votes are "yes", i.e., the selection score sv j of the photo p ij is at least k 2 , we select p ij as a representative photo p * i for location l i and thus a data assessment task is requested for p * i ; otherwise, another selection voting is asked for the next photo p ij of location l i (lines 11-24), and the same procedure is repeated. When the assessment voting is completed, the winning assessment a * i is considered as the relevant assessment for the photo p * i and then the user is provided with the triple < l i , p * i , a * i > (lines 25-32). This strategy proceeds in the same manner for each location until T e (loop in line 5).

V. SYSTEM OVERVIEW

In this section we outline the basic components of our system, their roles and how they interact with each other. Our system is implemented using Bonita Open Solution5 , BPM system. The architecture of the system is illustrated in Fig. 2.

The system consists of the following main components: Process Generator, the Process Engine, the Task Manager and the Result Visualizer. The Storage Engine is external, and is accessed by our system at query time. The Process Generator receives the query from the user and transforms it into a processing plan, i. e., it generates the data collection, data selection and data assessment process. The Process Engine takes the processing plan from the Process Generator and generates a sets of tasks for the The Task Manager receives progressively the tasks from the Process Engine and communicates with the crowd via a crowd platform to post tasks and retrieve the answers, then send them to the Process Engine.

The role of the Result Visualizer is to receive the results from the Process Engine and to return them to the user as a map for easy and better viewing (see Fig. 1).

VI. EXPERIMENTAL EVALUATION

The last challenge with our framework is to evaluate the quality of the results. Since we have not yet used it in a large scale setting, we propose to evaluate in this section the respective qualities of the proposed strategies, i.e., Buffer, Deadline and FIFO, focusing on: (i) the number of results returned; (ii) the quality of the results; for which, we use precision, recall and F-measure, i.e., 2 precision.recall precision+recall ; and (iii) the progressivity, i.e., how the results accumulate over time.

Due to the limited availability of large real datasets, most approaches focus on synthetic datasets. In our experimental study, we follow the direction of [START_REF] Kazemi | Geocrowd: enabling query answering with spatial crowdsourcing[END_REF] and use the Gowalla dataset 6 . This dataset contains a set of users along with their check-in time and location on Gowalla, a locationbased social networking website where users share their locations by checking-in. For our experiments, we assume that each user is a participant citizen. To generate the ground truth document, we make one random assignment of three possibilities for each location. We use a period of 5 days, and divide the data into three parts so that we have data collectors, data selectors and data assessors. We consider each check-in time in a given location as a response from that location for the current processing query. To be more realistic, for each collected data (photo), we introduce a parameter in [0.5, 1] that controls whether the data selectors and data assessors provide a correct answer or not. That is, we assume that citizens have a high probability to provide correct answers than a wrong one.

For the deadline strategy, the deadline is set to the half of the duration of the process, i.e., d = Te-Ts

2

. For all strategies, the default values for the duration of the process, i.e., T e -T s and the k value are 3 days and 7, respectively. Each experiment is run 100 times and the average it taken.

A. Number of Results

We measured the number of results, varying the duration of the process from 1 day to 5 days (Fig. 3). As expected, when the duration increases, the number of results increases since more citizens can participate. The number of results returned by Buffer is much less than that returned by Deadline and FIFO as Buffer needs to wait for k photos for each location, and some location are not popular. FIFO returns more results than Deadline since the latter strategy starts the data selection and assessment after the deadline, while the former, can do it whenever there is a photo received. We also measured the number of results, varying k from 3 up to 11. Fig. 4 shows the results of this experiment. FIFO returns more results than the other strategies and remains unaffected since it does not wait for k photos or the deadline to start the data selection step. Deadline remains unaffected for k ≤ 7. But for k > 7, the number of results decreases as the remaining time after the deadline d is insufficient to select and assess the retrieved data. Moreover, the number of results returned by Buffer decreases significantly with the increase of k since it requires k photos for each location. To summarize, from Fig. 3 and Fig. 4, we obtain the following result: FIFO returns more results than Deadline, which in turn returns more results than Buffer.

B. Quality

Fig. 5 shows the quality of the results varying the duration. FIFO has the lowest quality, and is not affected by duration. In almost all cases, the first photo of each location is selected; since it is probably not the best photo of that location it affects the assessment step. The quality of Deadline and Buffer increases with the duration. Notice that Deadline is better than Buffer since it collects the maximum number of photos until the deadline d, and can move to data selection and assessment without having k photos for a location, while buffer, misses some location because some photos are missing to reach the threshold. Fig. 6 depicts the quality of the results varying k. From this experiment, we can see that the quality of all strategies increases with the increase of k. When using more citizens or jurors, the probability to get a correct answer increases. Similarly to the last experiment, Deadline is better than Buffer, which in turn is better than FIFO for the same reasons.

Summarizing, from Fig. 5 and Fig. 6, we obtain the following result: Deadline has better quality than Buffer, which in turn has better quality than FIFO.

C. Progressivity

As shown in Fig. 7, FIFO and Buffer return some results the first day and progressively return the remaining ones. However, FIFO is around 3 times better since Buffer has to wait for k photos for each location. Moreover, the first results of Deadline can only appear after the deadline d, i.e., after 1.5 days, then increases significantly From Fig. 7, we obtain the following result:

FIFO is more progressive than Buffer, which in turn is more progressive than Deadline.

From our experimental study, we can observe that there is a very good tradeoff between the number, the quality and the velocity of occurrences of the results depending on the strategy we use: FIFO returns more results and is more timely, but less trustworthy than Deadline. Buffer is in between regarding quality and progressivity, but the worst regarding number of results.

VII. CONCLUSION

Our crowdsourcing framework leverages citizen participation to answer complex location-based queries in a given context. It is possible to follow different strategies based on data collection, data selection and data assessment process to answer these complex queries. Through our experimental evaluation, we see that each strategy has its merits. The choice of the strategy depends on the user needs. Hence, the proposed strategies are complementary. For example, if high accuracy is required, the Deadline strategy appears to be better but in a crisis situation where results are required urgently to take actions, the FIFO strategy is very well suited.

In the future, we plan to find the minimal set of strategies that cover all possible execution strategies and to conduct an experimentation on a large scale with the Lorraine Smart City Living Lab.

  Given a query Q:-< O, C, R, A, T s , T e , S >, we formally define the data collection, data selection and data assessment tasks as follows: Data Collection Task: We use photos as a means to retrieve the set of objects O and define a data collection task DCT as triple < O, C, R >. It asks the crowd to take photos of O within context C, in region R.

Figure 1 :

 1 Figure 1: Output Model

Figure 2 :

 2 Figure 2: System Architecture

Figure 3 :

 3 Figure 3: Number of Results vs Duration (k = 7)

Figure 4 :

 4 Figure 4: Number of Results vs k (Duration = 3 days)

Figure 7 :

 7 Figure 7: Progressivity (Duration = 3 days, k = 7)

Table I :

 I Summary of Notations

	Symbol	Description
	O	objects name
	C	context
	R, l i	region, location
	A, a j	domain of the assessments, assessment
	Ts, Te	start time, end time
	J i , h j	jury, human
	k	number of jurors
	P i , p ij	set of photos of location l i , photo of location l i
	SV i , AV i	selection voting, assessment voting
	sv j , av j	selection score, assessment score
	p * i , a * i	the most representative photo of location l i in context C, the assessment of the photo p * i within context C

Algorithm 2 :

 2 DeadlineInput: a query Q; an integer k; a deadline d; Output: a set of triples < l i , p * ij in the corresponding set P i ;

		i , a * i >;
	1 begin
	2	while currentTime < T s do
	3	wait();
	4	crowdsourceDCT(O, C, R);
	5	while currentTime < d do
	6	case providing(h j , p ij , l i )
	8	stop photos from all locations;
	9	foreach location l i do
	10	crowdsourceDST(P i , C, l i );
	11	while currentTime < T e do
	12	case selectionVoting(h j , P i )

7 put p 13 put h j in J i ; 14 update SV i ; 15 if |J i | = k then 16 stop selection voting in P i ; 17 select winning photo p * i ; 18 remove all jurors from J i ; 19 crowdsourceDAT(p * i , C, A); 20 case assessmentVoting(h j , p * i ) 21 put h j in J i ; 22 update AV i ; 23 if |J i | = k then 24 stop assessment voting for photo p * i ; 25 select the winning assessment a * i ; 26 remove all jurors from J i ; 27 return < l i , p * i , a * i >;

https://www.mturk.com/mturk/welcome

https://www.odesk.com

http://crowdflower.com

http://www.digitalbuzzblog.com/2011-mobile-statistics-stats-factsmarketing-infographic

http://fr.bonitasoft.com/

http://snap.stanford.edu/data/loc-gowalla.html


Alexia Bontempi

Laurent Thiery

Damien Teyssieux

Danick Briand

P Vairac

Quantitative thermal microscopy using thermoelectric probe in passive mode

I. INTRODUCTION

Surface temperature measurement with high spatial resolution remains a major issue since none of the current techniques are mature enough to provide quantitative results. They can be classified in two groups: conventional and near-field. In any case, two uncertainties origin can be pointed out: the first is related to the physics principle of the technique and the second stems from the physics of heat transfer that relate the sample to the thermal detector.

Non-contact techniques are typical conventional techniques which are not subjected to the aforementioned uncertainties but are limited in terms of spatial resolution, temperature range and their dependence on the surface optical nature. These encompass optical techniques such as infrared or near-infrared thermography, 1,2 thermoreflectance, 3,4,5 photoluminescence 6 or Raman spectroscopy. 7,8 Contact techniques overcome part of these drawbacks but thermal diffusion between the sample and the sensor becomes the main error source that needs to be carefully addressed. Among available techniques, liquid crystal thermography, 9,[START_REF] Lau | AIP Conf. Proc[END_REF] fluorescence thermography [START_REF] Saidi | [END_REF]12 or near-field optical thermography (NFOT) 13,14 are also based on an optical measurement. However, the use of a probe tip ensures to increase the spatial resolution as it was demonstrated for all the near-field techniques.

Thermal near-field microscopes are generally called Scanning Thermal Microscopes following the original idea of Williams and Wickramasinghe 15 in 1986 that derived the use of a Scanning Tunnelling Microscope (STM) to operate on non-conducting samples. Progress in manufacturing thermal probes at the very tip of tapered materials have led to a family of near-field thermal 2 techniques very closed to Atomic Force Microscope (AFM) for which a thermal sensitive area provides an additional information related to heat transfer between this area and the sample. The sensitive part can be quasi-punctual or distributed. Thermocouple or thermodiode allow a quasipunctual measurement while thermoresistive elements provide an integrated temperature value. These sensors are used to measure temperature distribution on hot samples (passive mode) or sample thermal properties when an additional heat source causes a heat transfer between the probe and the sample. The probe can be self-heated, typically by Joule effect (active mode) or an external heat source such as laser illumination. 16 In any case, quantitative measurements remain hard to derive.

Moreover, spatial resolution in thermal imaging is still an open issue since diffusion thermal process is depending on the probe dimension, but also the sample nature and the heated volume including the external condition (medium or vacuum) and the dynamics of the phenomenon (DC, AC or pulsed).

Besides, temperature range of operation is fixed by the probe itself. Thermoresistive wire element such as Wollaston 5 micrometers in diameter platinum-rhodium wire probe is probably the most robust. [START_REF] Dinwiddie | Thermal Conductivity[END_REF] Otherwise, thin-film microfabricated probes cannot exceed a hundred degrees typically except micro-pipette thermocouple for which the temperature limit is about 500°C. [START_REF] Fish | [END_REF]19 For years, many attempts to develop micrometric size thermocouple or thermodiode sensors have been proposed by authors from the welding of K type wires, 20 S types, 21,22 thin-film deposition on a micropipette, 23 to an AFM 24,25 or cantilever structured 25,26 or optical fiber tip. [START_REF] Thiery | OPTO 2002 International Conference Proceedings[END_REF] However, most of these developments remain inaccurate for quantitative measurements in ambient environment due to major contribution of probe-to-sample disturbing heat transfers. In this article, we focus on the passive mode of operation using a thermocouple probe which is fabricated with Wollaston wires of platinum and platinum-rhodium of 1.3 micron diameter welded together by means of a sparking technique. [START_REF] Voisin | [END_REF] The chosen diameter represents a compromise between a maximum robustness and the minimum invasive effect of its contact. After a brief recall of the probe characteristics and the problematic of its use through the analysis of the thermal interaction with a sample, results of temperature scans on a microhotplate are presented as an actual alternative to available high resolution thermography.

II. THERMOCOUPLE PROBE

Accurate measurement in a large temperature range requires the use of standard bulk wires.

However, available diameters are rather large, typically above 12 micrometers. The thinnest K type thermocouple wires are 7.6 µm (3×10 -4 inch). Wollaston wires remain the thinnest standard S type commercially available, whose fabrication process ensures to reduce a platinum or a 10% rhodiumplatinum core down to 0.5 µm (2×10 -5 inch) inside a silver cladding. Among the different available diameters, 1.27 µm (5×10 -5 inch) represents the best compromise between size and robustness. The silver cladding is removed by a chemical or electro-chemical etching process so that a thermocouple junction can be obtained by welding platinum with rhodium-platinum wires. [START_REF] Voisin | [END_REF] Sparking technique from a capacitor discharge is used. The next figure shows results of junction depending on the 2 provided energy. Figure 1a shows the complete thermocouple for which the removed cladding length is about one hundred of micrometers. In figure 1b, wires temperature have reached their melting points due to an amount of energy of about 10 µJ, leading to large balls on both wire extremities whereas in figure 1b, this phenomenon has been avoided by reducing the spark energy to about 4 µJ. Wollaston wires are commonly used as thermal resistors for hot-wire anemometry and commercial scanning thermal microscope (SThM®Topometrix), techniques for which the relation between the measured signal and the surface or contact temperature is hard to derive. Conversely, such a thermoelectric micro-junction provides punctual temperature signal that results from S type conversion law. Seebeck coefficient is known as a function of temperature, whose value is 5.88 µV K - 1 at 20°C, 9.13 µV K -1 at 300°C or 10.87 µV K -1 at 800°C as shown in figure 2.

FIG. 2. S type thermocouple

Seebeck voltage (dashed line) when reference temperature (cold junction) is 0°C and sensitivity as a function of temperature.

2

The main reason that such probes are not widely used in laboratories is due to the difficulty to fabricate them reproducibly. However, by controlling the spark energy, the junction area remains close to the aspect of figure 1c. In addition, each thermocouple is tested according to a contact procedure previously described. 29 Consequently, this probe remains a reliable tool for temperature mapping of microsystems especially for temperature ranging from ambient to 800°C typically and conditions for which optical techniques are not suitable.

III. TIP TO SAMPLE THERMAL CONTACT

The advantage of a microthermocouple regarding thermoresistive elements is the presence of a junction from which a Seebeck voltage relies to its temperature. Such a local temperature however never represents a true surface temperature since it results from a new thermal equilibrium. The main difference between contact and non-contact (optical) techniques results from the surface temperature disturbance. A suitable parameter to quantify the difference between actual and measured temperature is the probe thermal response τ. It results from the expression of the thermal power that dissipates between sample surface and medium through the probe. Figure 3 depicts the thermal effect of such a heat dissipation Q.

FIG. 3. Principle of thermal interaction between a probe tip and a hot surface.

Following figure 3 description, thermal power dissipation is expressed as: τ is deduced from the ratio between the probe temperature and the actual surface temperature relatively to ambient. Assuming constant values of thermal resistances in a large temperature range τ can be written as: Such a definition takes into account the probe-to-surface thermal interaction as described in figure 3 in which the coupled effects of thermal transfers can be simply depicted as a series of thermal resistances. This suggests that depending on the sample nature and the ambient medium, one single probe thermal response may significantly vary. 30,31 Different authors have used a more restrictive definition of a probe response assuming that the modification of internal thermal equilibrium of the sample could be negligible. 32 This is realistic only when the sample is massive enough. In such a case, R m → 0 and T m → T s so that the mentioned parameter called φ is reduced to: It could be considered as an intrinsic characteristic of the thermal probe whose ideal value would reach 1 in case of a perfect contact (R c → 0). More generally, if R e >> R c any probe could be considered as efficient. We have measured these parameters in a previous paper for this temperature probe between ambient temperature up to 600°C, leading to a mean value φ = 0.934. 29 In the same paper, it has been shown that thermal contact on thin samples such as micro-hotplate membranes could lead to noticeable effects of cooling down the point contact and changing slightly the thermal balance of the device. By measuring both the cooling down and the power of heat dissipated by the probe, the micro-hotplate thermal resistance R m has been estimated to 2.45×10 -4 K W -1 . Then, the global thermal response of the probe was calculated as τ = 0.925. Such estimation is absolutely necessary for quantifying temperature measurements. However, another sample would imply another value of τ so that the following results have been obtained with a strictly identical sample device structure (see section 4). Among publications related to the mentioned contact techniques of temperature measurements, a very few have investigated this aspect of measurement quantification. In the very few data, one can mention Shi and Majumdar indications about their well-known batchfabricated thermocouple probe. 30 A supposed asymptotic value φ = 0.64 has been obtained when measuring temperature on a 5.8 µm width aluminum film. Reducing the film width demonstrated a decrease of this value down to 0.05 on a 0.35 µm width. This clearly indicates an effect of cooling down due to the existence of non-negligible thermal resistance R m of the sample and that the mentioned value corresponds to the definition of τ. This demonstrates that the use of φ ratio should be restricted to massive samples in order to compare different probes. Thermal response τ takes account of the sample nature and should be used to justify quantitative measurements. Furthermore, this also affects the lateral resolution ∆x as proposed by the same authors. According to their definition, and our thermal response τ, a corrected expression should give:

1 < = + + = - - =
1 < = - - = + =
AB A8 8 AB A8 8 B 6 C 3 C τ ∆ = ∆ = ∆ (4) 2
where ∆T n is the noise of the measurement chain and dT p /dx is the measured lateral temperature gradient. According to this definition, lateral resolution is inversely proportional to the thermal response of the probe. As a result, only a perfect probe (τ→1) may exhibit the best lateral resolution. This also indicates that thermal lateral resolution does not depend on the probe only but also on the sample nature.

IV. EXPERIMENTAL SETUP

A scanning thermal microscope is similar to near-field imaging system since the probe is a local tip that needs to be scanned over a sample. However, the contact is necessary to ensure an efficient thermal transfer between the surface and the tip. The contact force value depends on the tip geometry and its ability to support it without damage. Thin-wire thermocouples are flexible enough to undergo several tens of nano-Newton. Figure 4 depicts a distribution of measured DC temperature above the membrane center when approaching the probe from 1.8 mm to contact while the microhotplate is supplied with 13 mW DC power. DC thermocouple voltage is converted according to the Seebeck response of the S type standard law, corrected from ambient temperature (cold junction) and taking into account the effect of the probe thermal response given by expression (2) and quantified in reference 29, such: The secondary graph of figure 4 represents the last 10 micrometers and the effect of the contact force increase between the thermocouple probe and the sample surface. Series of experiments are superimposed on this graph. Contact occurs at 0 abscissa and contact force increases for negative positions. Observed elastic deformation of the probe has allowed us to estimate that the maximum contact is in the range 50 to 100 nN. In this range, the measured temperature is stabilized showing that the surface to junction heat transfer is saturated. As a consequence, a precise control of the contact force is not necessary for this passive measurement mode. This is not the case in active mode of operation. 33 It follows that our set-up remains quite simple without any contact control loop that would slow down the acquisition time. 2 Besides, extracting absolute temperature of the thermoelectric junction requires knowing the reference temperature which corresponds to the separating area between the silver cladding and the platinum or platinum-rhodium wires. [START_REF] Voisin | [END_REF] A large diameter silver wire acts as a perfect heat sink connected to ambient medium. This particular point is also depicted in the figure 4 with the geometry of the thermocouple probe in front of the sample surface and the temperature gradient. The length of the thermocouple wires is typically between 250 and 300 µm and the silver cladding is 75 µm of diameter. It has been verified that thermal conduction in silver is sufficient for ensuring a homogeneous ambient temperature. This value is measured by means of a thin-film platinum resistor (Pt1000) which is fixed in the vicinity of the silver wires.

Figure 5 presents a general view of the setup. Three piezo-actuators axis are used for the sample displacement whereas a long-range vertical axis is used to rough approach of the probe near sample surface. Since the contact force is not a controlled parameter and as long as surface sample is flat, a reference plan is acquired by contacting a few reference points before starting a complete automated scan. The thermocouple voltage is connected to a low-pass filtering voltmeter and a lock-in amplifier for simultaneous DC and AC measurements. AC current source is used to supply the tested sample and a computer both records the data while point-to-point displacement is managed. Measurements can be made in static or harmonic mode since the thermal bandwidth of the probe is larger than the 2 micro-hotplate one (see Fig. 7). However, the main difference between thermal and other near-field microscope such as STM or AFM systems is related to a larger time constant that require point by point measurements during which a tip-sample thermal equilibrium is necessary. This time is typically on the order of one second even if the time constant of the probe itself is much lower. This is mainly depending on the sample and the overall conditions of heat dissipations.

FIG. 5. Experimental set-up.

To demonstrate the performance of our system, micromachined silicon micro-hotplates represent pertinent electro-thermal devices to be studied since their active part is thermally insulated and can be heated up efficiently by Joule effect. The DC and/or AC current supplied to the metallic conductor generate DC and/or AC heating in the central active area. As shown in figure 6, the chosen device is similar to those which were described in previous papers and with which our probe has been calibrated 2,29 . A 200 nm-thick platinum film is embedded in a LPCVD silicon nitride suspended membrane whose thickness is 1 µm. The design of the platinum heater and the membrane thickness

V. RESULTS

Depending on the excitation mode of the active sample, several thermal signals can be extracted from the thermoelectric probe voltage. A static current generates a DC heating and AC current at a frequency f generates both a DC and a doubled frequency 2f heating of the heater due to Joule effect. A comparison between the thermal pass band of the sensor and micro-hotplate is however required before any measurement. Figure 7 presents the normalized magnitude of both the probe and the tested device while subjected to AC current at frequency f. Joule effect generates a double frequency 2f temperature elevation and a subsequent resistance variation that can be detected at the triple frequency 3f by means of a lock-in. Indeed, the measured voltage represents the product between the electrical resistance which varies at 2f and the supplied current at f frequency. This reveals thermal cut-off frequencies near 20 Hz for the micro-hotplate and 300 Hz concerning the thermocouple probe wires. FIG. 7. Thermal pass band comparison between the thermocouple probe and the micro-hotplate. Series of measurements have been performed while supplying an alternative current at a frequency f. As a result, three thermal signals are provided by the thermocouple using a DC voltmeter and a lockin (magnitude and phase) at the double frequency 2f. The thermocouple probe has been scanned over the micro-hotplate and each measurement point has been stored after one second of contact. AC RMS voltage is converted in AC RMS temperature according to the sensitivity (derivative) of the S type thermocouple shown in figure 2 which is taken for each point at the probe DC temperature value (T p ).

The whole membrane is 1 mm square. Figure 8 presents a result of a complete scan while the heater is supplied with an AC RMS current of 10 mA. DC temperature component points out the thermal homogeneity of the central area whereas AC 2f components reveal interesting thermal contrasts both in magnitude and phase. Despite the frequency range which exceeds the probe and the sample bandwidths, signal to noise ratio remain sufficient for extracting the following images. However, if DC images are quantitative, AC contrast provides only qualitative data. Let us recall that the platinum heater is only visible on the optical view due to the transparency of the silicon nitride membrane in which it is embedded. The phase signal clearly reveals its presence whereas magnitude points out the heat source intensity. The center of the coil being less resistant, the magnitude is consequently lower than for the perimeter area. The influence of the current frequency helps to reveal these details as presented in figure 9 where scans have been reduced to the central area (560 µm square). AC RMS supplied current is 12 mA and frequency varies between 10 and 850 Hz. 2 Result on DC temperature distribution remains identical at any frequency. Besides, only the central part of the coil is slightly visible and comparable to 10 Hz frequency magnitude image. The heater geometry appears in both magnitude and phase images when increasing frequency. However, due to both micro-hotplate and the thermocouple pass band, magnitude decreases whereas phase contrast increases. Magnitude strongly depends on the dissipated power but phase only depends on the physics of heat transfers. Indeed, phase results from a competition between Joule heat source areas which exhibit phase values close to heat source and heat diffusion into materials. This is why the complete metallic coil is clearly visible at higher frequencies regarding to magnitude images. Conversely the silicon nitride membrane acts as a passive material which undergoes strong temperature gradients and strong phase variations. Thermal imaging remains strongly different to other near-field imaging system in the fact that the measured surface contrast derives from a volumetric contribution of heat 132 2 diffusion's law. As a result, thermal contrast of these images is often considered as subsurface contrast.

VI. CONCLUSION

We have shown that a standard micro-thermocouple can be used as a local temperature probe in a scanning quantitative thermal imager. In spite of a scanning operation that requires one second typically per acquisition point, this represents a real alternative to conventional techniques which are unable to operate from ambient to 800°C while remaining insensitive to surface optical nature.

Besides, the quantitative aspect of these contact measurement represent a major point which has not been correctly addressed by authors yet whereas it represents the main limiting factor of local thermal probing. In spite of recent attempts to correct the effect of a probe contact 34,35 , quantitative measurements still remain generally inaccurate due to the dependence on the sample nature itself which is rarely considered. This is mainly due to the confusion between the actual surface temperature underneath the tip in contact and the actual temperature far beyond contact. The latter is the only relevant value whereas most of techniques do not mention any difference since the sample nature introduced with R m thermal resistance (see Fig. 3) is neglected. According to our analysis and without taking account of artifacts due to topography, temperature quantification at micro and nano-scales is only possible if:

-The sample is already thermally characterized such as in the present paper (R m ), leading to a correction of temperature measurements using τ, 29 -A relevant method for correcting the effect of contact by canceling the heat flux is applied (null point method). 34 In such a case however, operating under vacuum is helpful because attempts to reduce only heat transfer at contact jump as proposed by Chung 34 may not be sufficient to take account of the heat which is transferred during far approach of the probe. Indeed, as shown in figure 4, DC heat diffusion through air by means of conduction and convection affects measurements in a millimeter range from the sample surface. Moreover, this also affects the resolution limit which is not studied in this paper. This will be the subject of further articles as well as the extension of the present system to active mode of operation. 33 To date, the very few tested nano-thermocouples which were fabricated on a silicon nitride tip similarly to AFM cantilevers and probably most of resistive thermal nano-probes are supposed to exhibit a response τ on the order of 0.05 when scanning nanostructured heated elements. 30 Improving thermal characteristics of these probes would benefit to both resolution and a better evaluation of the quantification errors in surface temperature measurement. A common approach in scanning thermal microscopy would help to define measurable thermal quantities, including a standard definition of lateral resolution. Otherwise, no progress in thermal measurements at micro and nano-scales may be

FIG. 1 .

 1 FIG. 1. Scanning electron micrograph of the thermocouple junction. General aspect (a), high energy sparking (b) and lower energy sparking (c).

FIG. 4 .

 4 FIG. 4. Temperature gradient above the center point of the micro-hotplate up to 1.8 mm and schematic view of the probe at this scale. Influence of the contact force on the DC measured temperature value.

  FIG.6. Top view image and schematic of the cross-section of the micro hotplate.

1B2 2 FIG. 8 .

 28 FIG. 8. Complete membrane scan (106 × 106 points / 1 mm 2 ) at a supply current frequency of 270 Hz.

FIG. 9 .

 9 FIG. 9. Active part scan (141 x 141 points / 560 x 560 µm) at different supply current frequencies.

2

expected as long as micro-thermal probes will not be tested and compared in standard benchmark conditions.