A crowdsourced stream processing system (CSP) is a system that incorporates crowdsourced tasks in the processing of a data stream. % This can be seen as enabling crowdsourcing work to be applied on a sample of large-scale data at high speed, or equivalently, enabling stream processing to employ human intelligence. It also leads to a substantial expansion of the capabilities of data processing systems. % Engineering a CSP system requires the combination of human and machine computation elements. From a general systems theory perspective, this means taking into account inherited as well as emerging properties from both these elements. % In this paper, we position CSP systems within a broader taxonomy, outline a series of design principles and evaluation metrics, present an extensible framework for their design, and describe several design patterns. % We showcase the capabilities of CSP systems by performing a case study that applies our proposed framework to the design and analysis of a real system (AIDR) that classifies social media messages during time-critical crisis events. Results show that compared to a pure stream processing system, AIDR can achieve a higher data classification accuracy, while compared to a pure crowdsourcing solution, the system makes better use of human workers by requiring much less manual work effort.
conclusion.tex
% !TEX root = paper.tex

\section{Conclusions}\label{sec:conclusions}

Crowdsourced stream processing is a new computational frontier that combines high-speed processing with human intelligence.
%
Its progress hinges upon the development of efficient algorithms, as well as on the design of software architectures that implement those algorithms into applications having impact on the real world.
This paper introduces a generic framework that covers system-level properties and behavior, design principles, structural elements, compositions and patterns, to enable better designs for future CSP applications and to serve as a basis for the evaluation and re-engineering of existing ones.

Much remains to be done between the design of specific CSP applications solving concrete problems, and the development of general frameworks and best practices that can serve as a basis for those designs. 
%Examples of future extensions therefore include
%
This includes extending specialized taxonomies of CSPs, creating new metrics for their evaluation, expanding a catalog of design patterns, among many other tasks that remain open for future work.

\nonumsection{Acknowledgements}
The authors would like to thank Jakob Rogstadius and Ji Kim Lucas for their contributions in the development of AIDR.

evaluation-aidr.tex
% !TEX root = paper.tex
%\newpage

\section{Case Study: Classification of Social Media Messages during a Crisis}\label{sec:evaluation-aidr}

%\note[Ioanna]{For section 6 in particular, my basic comment is that we need to add some explanations and comparisons of AIDR with the pure stream processing and pure crowdsourcing. For this comparison we do not necessarily need any extra figure, but it would be good to have a few sentences in the text. I have marked down the places where this should go.}

In this section, we study a concrete stream data processing problem, showing that neither pure crowdsourcing nor pure stream processing are satisfactory alternatives. Next, we show how the framework we have described can guide the CSP system design and serve as an analytical tool for its evaluation. Naturally, this real-world example does not use each and every one of the elements we have introduced, but it touches several aspects that are common to a variety of cases.

\subsection{Problem Statement}

In times of crises caused by natural hazards (such as floods and earthquakes), or by human intervention (such as civil unrest or war), people are increasingly turning to social media platforms such as Twitter.\footnote{\url{http://twitter.com/}} In these platforms, users share information related to what they experience, what they need, what they witness, and/or what they consider important to repeat from other sources such as radio or television~\cite{hughes2009twitter}. Social media usage ``rises during disasters as people seek immediate and in-depth information''~\cite{fraustino_2012_start}. 

Several types of user are interested in this information~\cite{hughes_2014_smem}, and their needs are varied. Members of affected communities need to take decisions about how to best protect their lives and property. Government and non-governmental response agencies need as much information as they can get in order to increase the effectiveness of their efforts. Different emergency response agencies are interested in different types of messages during different phases of an emergency~\cite{roy2013tweet4act}. For instance, reports of damage to infrastructures should be directed to some agencies, while reports about shortages of water and/or food should be directed to others.\footnote{The United Nations organizes its agencies into clusters: \url{http://business.un.org/en/documents/6852}.}

In this case study, we use Twitter platform to perform real-time acquisition and classification of users generated content posted online during crisis situations.

\subsection{Crowdsourcing solution} \label{crowdSolution}

Manual classification of messages is not possible given the scale of information that flows on Twitter, even under very generous assumptions.

% https://crowdflower.com/jobs/352916/stats/times: 8s
% https://crowdflower.com/jobs/353742/stats/times: 11s
% https://crowdflower.com/jobs/351546/stats/times: 7s
% https://crowdflower.com/jobs/351495/stats/times: 13s
% https://crowdflower.com/jobs/353693/stats/times: 8s
% https://crowdflower.com/jobs/351570/stats/times: 7s
To estimate the speed with which volunteers can solve these tasks, we use data obtained by Olteanu et al.~\cite{olteanu2014crisislex} during the labeling of six crisis situations using paid crowdsourcing workers.
%
The simplest task was ``Indicate if tweets are informative for decision makers and emergency responders,'' with several classification options including ``negative consequences,'' ``donations or volunteering,'' ``advice, warnings and/or preparation,'' among others (6 options in total). The crowdsourcing workers are divided into two groups: \emph{trusted} and \emph{untrusted}, depending on whether their judgments agree with that of the authors in a set of test questions (known as golden data). The average time per label for trusted workers was between 7 and 13 seconds, with an average of 9 seconds. Trusted workers were not allowed to label more than 250 items.

This means that one worker can produce 400 labels per hour, assuming s/he can keep that efficiency for such a long period. If we require 3 labels per item in order to have at least some degree of worker redundancy (recommended in a crowdsourcing setting to ensure quality), 
%a crowd of 3 volunteers will be needed to label 400 items per hour. 
then a crowd of 3,000 volunteers will be needed to label 400,000 items per hour.

In a recent experience with digital volunteers during a large Typhoon in the Philippines in November 2013, the peak number of volunteers was 500, recruited through a number of channels including a large digital humanitarian network.\footnote{\url{http://irevolution.net/2013/11/13/early-results-micromappers-yolanda/}} The peak throughput we can expect from such a crowd is in the order of 67,000 items per hour, or 1,100 tweets per minute.
%
However, the largest documented peak of tweets per minute during a natural hazard that we are aware of is 16,000 tweets per minute.\footnote{During Hurricane Sandy in 2012: \url{http://www.cbsnews.com/8301-205_162-57542474/social-media-a-news-source-and-tool-during-superstorm-sandy/}} \emph{With pure crowdsourcing, we may be a factor of 10 slower than needed}.

%\note[ChaTo]{Change ``behind what is needed'' to ``slower than needed''}

\subsection{Streaming solution}
\label{subsect:streaming}

The automatic approaches to process data streams are indispensable yet challenging to adapt. The infinite length and evolving nature of data streams 
%in the context of stream classification
 introduces concept-drift and concept-evolution issues, also known as the \emph{domain adaptation problem} (an automatic machine-learned classifier trained with data from one situation does not perform well in another situation, as also discussed in Section~\ref{sec:intro}). In order to incorporate the underlying changes which have occurred in the streams, incremental updating of the classification model is required by labeling new items, incorporating them as new training data, and learning a fresh model.

In particular for the crisis domain, although crises have some elements in common, they also comprise distinct elements which make domain adaptation difficult, and thus the automatic classification using pre-existing training data is not a satisfactory solution. For example, in~\cite{imran2014coordinating}, authors performed experiments on different crisis datasets, namely the Joplin tornado, the Sandy hurricane, and the Oklahoma tornado, which all struck different areas of the US in 2011, 2012 and 2013 respectively. The performance (AUC)\footnote{AUC: area under the receiver operator characteristic (ROC) curve, a metric used for binary classification. AUC is measured in the [0,1] scale. The AUC score of a perfect classifier is equal to 1.} of different transfer scenarios was 0.52 (train on Joplin, test on Sandy), 0.56 (train on Joplin, test on Oklahoma) and 0.53 (train on Sandy, test on Oklahoma). Similar problems have been identified in another work~\cite{imran_2013_practical}. This findings suggest that crisis-specific training data are needed since they lead to higher accuracy compared to training data from past disasters. 
%\note[Ioanna]{I added a footnote to explain AUC, please check.}
\emph{With pure automated stream processing, the quality achieved may be significantly low due to the domain adaptation problem.}



%\todo[ChaTo]{I think some number is needed here, e.g. AUC goes from 0.8 to 0.6 or something when training on a crisis and testing on another, some result from our previous work.}

\subsection{A Crowdsourced Stream Application: AIDR}

%\todo[ChaTo]{@Imran: this section needs to be made more realistic, in the sense of incorporating the fact that crowdsourcing workers can provide at most 1,100 labels per minute.}

The purpose of AIDR (Artificial Intelligence for Disaster Response),\footnote{\url{http://aidr.qcri.org/}} is to filter and classify in real time messages posted in social media during humanitarian crises, such as natural or man-made disasters~\cite{imran2014aidr}.
%
Specifically, AIDR collects crisis-related messages from Twitter\footnote{\url{http://twitter.com/}} (``tweets''), asks a crowd to label a sub-set of those messages, and learns an automatic classifier based on those labels. It also improves the classifier as more labels become available.

AIDR users begin by creating a collection process by entering a set of keywords that will be used to filter the Twitter stream. Next, they define the ontologies to be used to classify messages, selecting them from a set of pre-existing ones, or creating them from scratch. AIDR then instantiates an ongoing crowdsourcing task to collect training labels, which are used to train an automatic classifier that runs over the input data. Finally, an output of messages sorted into categories is generated, which can be collected and used to create crisis maps and other types of reports or in real-time decision-making.

\subsubsection{Design overview}\label{aidr-design}

The design of AIDR follows the meta-model described in Section~\ref{sec:framework}.
%
At a high-level, the application uses the design pattern ``Human processing'', optional per item (Section~\ref{subsec:guaranteed-throughput}), according to which items (Twitter messages) are able to traverse the application independently of the availability of crowdsourcing workers.
%Human intelligence is used in a {\em supervised learning} pattern (Section~\ref{subsec:supervised-learning}).

The processing elements of the application are composed following the diagram in Figure~\ref{fig:aidr-classify}.
%
The automatic processing elements include a Twitter collector, feature extractor, task generator, learner and classifier. A crowdsourcing processing element, the annotator, gathers human-provided labels. 
The {\em collector} is an information source automatic processing element that performs edge adaptation~\cite{turaga2010design} to consume tweets using the Twitter streaming API.
%
The {\em feature extractor} is an information process automatic processing element that prepares the messages by converting them to a set of textual features using standard text operations (extraction of unigrams, bigrams, part of speech classes, etc.).

The classifier, task generator, annotator and learner processing elements {\em interact} following the ``supervised learning'' design pattern (Section~\ref{subsec:supervised-learning}).
%
The task generator samples the input stream, optionally performing de-duplication (to diversify the elements to label) and active learning (selecting elements for which the classification confidence with the current model is low). 
%
Both operations are implemented in a stream-aware way, in which the search for near-duplicates and low-confidence elements is done on a bounded-size buffer containing only the latest tweets consumed by the system.
%
The learner keeps 20\% of the labels it receives as a test set, and uses the remaining 80\% for training, allowing it to report to the user the quality of the current classifier. The learner creates a new classification model (random forest in this case) every 50 training labels and transfers it to the classifier processing element using control signals.

The composition of the processing elements is done through publish/subscribe channels and queues following the hybrid composition model. The channels are able to broadcast and distribute data items, as well as to perform {\em load shedding} - discard elements in order to maintain throughput. The queues are capable of buffering data items, when necessary.

\begin{figure}[t]
 \centering
    \includegraphics[width=\columnwidth]{figs/aidr-flow-2}
  \fcaption{AIDR general architecture. {\tt P/S} indicates a publish/subscribe channel, while {\tt Q} indicates a communication queue.}
  \label{fig:aidr-classify}
\end{figure}

\spara{Implementation.} The design of AIDR follows the {\em Service-Oriented Architecture} software architecture design pattern. All modules depicted in Figure \ref{fig:aidr-classify} provide necessary RESTFul services enabling user interactions for the management purposes such as configurations, providing input, meta-data exchange. Moreover, the communication (in terms of real data) between modules happens using publish/subscribe channels and queues. \mbox{REDIS}\footnote{\url{http://redis.io/}} is used as an underlying communication infrastructure that supports pub/sub channels and queues.

The Java programming language and the Springs 3.0 framework is used for the main application logic, and ExtJS framework~\footnote{\url{http://www.sencha.com/products/extjs/}} for the application user-interfaces. PyBossa~\footnote{\url{http://pybossa.com/}} is used as the crowdsourcing platform. The task generator modules passes newly selected items to be labeled to the PyBossa in order to employ crowdsourcing workers to label items.

\subsubsection{Evaluation}

We apply the evaluation metrics described in Section~\ref{sec:principles}. We remark that there are application-specific evaluation criteria that are outside the scope of our generic framework, e.g., user satisfaction in the case of interactive applications. Here we are interested in the performance (e.g. in high throughput and low latency) and quality (e.g. high classification accuracy of tweets) of using the AIDR CSP system. %\note[Ioanna]{To check this sentence above.}
%\note[Imran]{Added more explanation. Please check now.}

We simulate the operation of AIDR with a fixed input stream under a varying set of streaming conditions. We note that we use real data in our simulation and mimic different streaming conditions to test the system's performance. 
%\inote[Ioanna]{I added the sentence above, please check.}
%\note[Ioanna]{Why did we chose to simulate? (In case a reviewer asks). We did not have real data?}
%\note[Imran]{We used real data in our simulation. However, we mimic streaming behavior to test system's performance.}
%
For the purposes of this simulation, the application is instrumented to provide detailed information about data passing through it. {\em Mock objects} are also created to simulate data input (from Twitter's API) and data labeling (from a crowd).

We use a dataset of 206,764 tweets containing the hashtag {\tt \#Joplin} and posted during the tornado that struck Joplin, Missouri in 2011~\cite{imran_2013_practical}. We also use 4,000 human-provided labels obtained via CrowdFlower. The specific crowdsourcing task was to indicate if a message is {\em informative} with respect to the disaster and of interest to a broad audience, or if it is either entirely of a personal nature or irrelevant for the disaster (the two latter classes are merged into a single class {\em not informative}).

\begin{figure}
\subfigure[Throughputs: features extractor, classifier, system.\label{fig:throughputs}]{\includegraphics[width=\columnwidth]{figs/throughputs-FE-CLS-all}}
\subfigure[Latencies: features extractor, classifier, system.\label{fig:latencies}]{\includegraphics[width=\columnwidth]{figs/latencies-fe-cls-all}}
\fcaption{Response of AIDR to varying input loads, in terms of throughput and latency. The vertical line corresponds to the highest peak rate documented for a natural disaster to date: 270 items/second during Hurricane Sandy in late 2012.}
\label{fig:eval-stream}
\end{figure}

\spara{Throughput, latency and load adaptability.}
We first measure the attributes that AIDR inherits from being a stream processing application. 
%
To evaluate these variables, its classifier is trained using all the available labeled data, and then varying input loads are applied.
%

Figure~\ref{fig:eval-stream} shows the results. In addition to end-to-end throughput and latency, we include a breakdown for each of the two main automatic processing elements of the system: the feature extractor and the classifier.

The system is designed following the principles of {\em keep data moving}, {\em high performance}, {\em task automation}, and {\em load shedding}, outlined in Section~\ref{sec:principles}. The results indicate that the system is able to maintain a high throughput (500 items/second or more) above the observed peak rates in real disasters ($\approx$270 items/second).
%
Because some of the items are dropped, the latency is kept in the order of tens of milliseconds, even when the input load exceeds the maximum output throughput. For the purposes of this application, this is acceptable given the large amount of redundancy in Twitter messages---about 1/3 are {\em re-tweets} in this dataset, and about half of the remainder are near-duplicates of another message.

\begin{figure}
\centering
\subfigure[Quality vs. number of labels, using passive learning.\label{fig:qua-w-dd}]{\includegraphics[width=0.85\columnwidth]{figs/online-with-without-dd}}
\subfigure[Quality vs. number of labels, using active learning.\label{fig:qua-wo-dd}]{\includegraphics[width=0.85\columnwidth]{figs/online-with-without-dd-with-pp}}
%\subfigure[Quality with priority task labeling and de-duplication \label{fig:qua-wo-dd}]{\includegraphics[width=\columnwidth]{figs/Joplin-quality-with-dd-priority-2}}
%\subfigure[Quality with priority task labeling and without de-duplication \label{fig:qua-wo-dd}]{\includegraphics[width=\columnwidth]{figs/Joplin-quality-without-dd-priority-1}}
\fcaption{Area under the ROC curve (AUC) shows classification quality vs. number of training labels shows cost (i.e. monetary in case of paid-workers, time in case of volunteers). The plots on the left side are obtained without de-duplication, while the plots on the right include it.}
\label{fig:eval-crowd}
\end{figure}
%\note[Ioanna]{For the figure 8 I suggest the following: i) mention that AUC represents quality (a.k.a. Tweeter message recognition accuracy) and \# Training examples represents cost (a.k.a. human-labeled Tweeter messages that one has to pay workers to recognize or human effort in case of volunteers). ii) Give a summary of the results, i.e. ``We observe that the AIDR CSP system ...'', iii) why the right column has lower quality than the left?}

%\note[Imran]{I incorporated your suggestions in the caption of Fig 5, however, I want ChaTo to have a final look at it. Regarding your (iii) comment, the quality of right is actually not lower than the left when you  for example compare the number of training examples consumed by the left charts to reach that AUC. Right charts reach around 0.70 in 800 examples, whereas left charts reach there in 3000 examples. }

\spara{Quality and cost.}
We next measure the attributes that AIDR inherits from being a crowdsourcing application, specifically, the relationship between quality and cost. Quality is measured using the area under the ROC curve (AUC); higher values are best and 0.5 indicates a random classifier. Cost is directly mapped to the number of human labels used.

%\note[Imran]{Next paragraph is added to describe two variants of AIDR that we tested in our experiments.}

Twitter data contains a significant amount of duplicates (i.e. re-tweets). Removing duplicates could decrease the crowdsourcing efforts (i.e. cost) needed to achieve an acceptable level of accuracy. To check this, we are interested in testing two variants of the AIDR system: i) how much cost (i.e. in terms of labeling effort) AIDR requires to achieve an acceptable quality using the passing learning approach and ii) the same using active learning approach, both with and without employing the de-duplication process (i.e. to discard duplicate tweets). In total, we examine four configurations of the task generator: (1) passive learning, equivalent to uniform random sampling in this case, (2) passive learning removing near-duplicate elements, (3) active learning, and (4) active learning removing near-duplicate elements.
%
Results are shown in Figure~\ref{fig:eval-crowd} where we plot output quality vs. number of labels used by the classifier for training.

The system is designed following the principles of {\em simple tasks} and {\em task prioritization}. The test shows that even under conditions of {\em task frugality} the output quality is acceptable.
%
After enough training data has been collected ($\approx$1,000 labels), the AUC fluctuations stabilize and the system performs at an AUC of above 0.70. This point is reached with about half the labels if de-duplication is done and it collectively requires 1 minute of 500 workers, if they work simultaneously (as reported in Section \ref{crowdSolution}). Further labels continue to increase the quality of the classifier, with diminishing returns.
%
Active learning as implemented in this setting (over a bounded-size buffer) does not seem to yield significant improvements.

We remark that in Figure~\ref{fig:eval-crowd} every point represents a different (growing) testing set, a consequence of the online nature of the process.
%
An offline analysis, where the testing set is fixed to 1/3 of the labeled elements, is in general consistent with the evaluation in the online setting. In the best case and using de-duplication, we obtain a maximum AUC of 0.64 for passive learning (after $\approx$270 labels) and an AUC of 0.66 (after $\approx$200 labels) for active learning.
%
The offline analysis also shows that more labeled items further improve the results: after using 2,600 labels we reach an AUC of 0.76, which is approximately equal to 3 minutes effort of 500 workers (as reported in Section~\ref{crowdSolution}).

%\note[Ioanna]{It would be very good to have here a comparison of the above values with pure crowdsourcing. For example regarding \emph{cost} we say above that for the value of AUC 0.76 AIDR is  equal to pure crowdsourcing that uses 500 top-level workers for 3 minutes. How many workers does AIDR use (even simulated ones?). If this number is significantly lower this is great, because it would mean that AIDR achieves the same quality with fewer workers, thus it has lower cost. For \emph{quality} we can say that the 0.76 is significantly higher than the values around 0.54 that pure crowdsourcing achieves.}

Thus, \emph{compared to a pure stream processing system, the AIDR CSP can be expected to achieve much higher quality} (AUC of 0.76, higher than pure SPs as explained in Section~\ref{subsect:streaming}.)

On the other hand, using a pure crowdsourcing solution, one can achieve AUC 1.00 (by definition, because we are measuring quality against their labels) using a certain level of agreement among workers; however, to achieve such a high accuracy in a pure-stream processing system, we would need 500 workers continuously working for the duration of the event (which may span several hours or days). This is not feasible due to worker burn-out (performance deterioration, lower quality over time) and drop-out (less people over time).
Instead, in a CSP system, to maintain high accuracy, we would only need these 500 workers for 3 minutes and then to re-use them for the same period every  few hours--just to update the system (i.e. the supervised classification model in this case) with new training examples. Thus, \emph{compared to a pure crowdsourcing system, the AIDR CSP achieves a high quality demanding much less effort by the crowd workers, thus using the available worker population more efficiently}.

%Instead in a CSP system, to maintain high accuracy, we only need the 500 workers--for example 3 minutes after every 6 hours--just to update the system (e.g. model in a supervised classification setting) with new training examples. 

%\note[ChaTo]{We could say that in comparison with a pure-crowdsourcing solution:

%- In a pure-crowdsourcing solution we would have AUC 1.00 but we would need the 500 workers continuously for the duration of the event, which is not feasible because of burn-out (lower quality over time) and drop-out (less people over time).
%
%- Instead in a CSP we only need the 500 workers for, say, 3 minutes every 6 hours, just to update the model with new labels.}
%
%\note[Imran]{Incorporated this discussion in the above paragraph. }
%\note[Ioanna]{I also made a pass on the above, please check. For me it now says what we want to say, clearly.}

\mpara{In summary,} this design enables human intelligence to be applied on a data intensive application. As a stream processing system, the presented CSP is able to keep up with the input loads of even large-scale disasters; and as a crowdsourcing application, it is able to use crowdsourcing work in an effective manner.

framework.tex
% !TEX root = paper.tex

\section{General CSP Framework} \label{sec:framework}

%\todo[ChaTo]{As per our phone meeting of 2014-07-21, after the subsection ``CSP at system-level,'' subsections should follow the scheme of Figure~\ref{fig:dsp-mm}. In particular, information sources, providers, and consumers are not explained in the current version.}

Taking into account the characteristics of CSP systems and the design principles presented above, in this section and the following one, we describe a framework for their design.
%\note[Yannick]{For me, the framework consists in both the structural aspects (meta-model) and the design patterns. Thus section 4 and section 5 should me merged to make only one section for the whole framework. I made my changes so that it fits with the current structure, and I let you decide if you want to merge or not and then to adapt the text accordingly.} 
%We follow a model-driven design approach, where a model represents an abstract view of a system. This model is meant to be extended to incorporate new requirements as needed.
%\note[Yannick]{Not sure it is useful to say that a model-driven design approach is followed...I removed the 2 last sentences above.} 
%\note[Imran]{OK.}
%
In accordance with the CSP system model provided in section~\ref{sec:taxonomy}, this framework allows specifying the elements of a CSP system and communication flows among them, in a standardized way that allows to easily create various kinds of topologies, and to modify them when required. In the following we detail the proposed CSP design framework from a {\em system-level} (Section~\ref{subsec:framework-applications}), {\em processing elements} (Section~\ref{subsec:framework-pe}) and {\em communication flows} perspective. (Section~\ref{subsec:framework-com}).

%\subsection{CSP at system-level}\label{subsec:framework-applications}
\subsection{System-level technical CSP meta-model}\label{subsec:framework-applications}

\begin{figure}[t]
 \centering
    \includegraphics[width=0.95\columnwidth]{figs/dsp-abstract-mm-v2}
  \fcaption{Meta-model of a CSP system. The diagram depicts the model of processing elements, connections and communication flows between PEs and composition types.}
	%\note[Yannick]{Change boxes so that they look the same as in fig.2: CSP system, PE, APE, CSPE; ensure also that relationships are the same.}
	%\note[Imran]{Changed.}
	%\note[Yannick]{The subclass link between Information boxes and APE / CSPE is not clear to me. In particular I do not see how an Information source can be an APE, as by definition it provides information and does not process it. Same thing for Information consumer: if it is a CSPE, then it does not consume information but processes it... Another thing that I do not understand is the Composition concept. By reading the meta model, I have CSP system is composed of 1..N Compositions, but of what? The link between Connection and Composition is not labeled, so it is hard to understand how it works from the figure.}
	%\note[Imran]{APE as information source: e.g. Data accumulator component in a system that collects data from different sources. APE as Information consumer: e.g. a visualization component that ingest data from other sources and shows charts. Composition concept represents an application instance of CSPs. For example, AIDR system is one particular composition of various APEs and CSPEs}
  \label{fig:dsp-mm}
\end{figure} 

%\note[Yannick]{I am not convinced both system and application terms should be kept. Maybe simply do not use "application", or find what would be the difference between the two concepts.}
%\note[Imran]{OK. Only using ``system".}
While the systemic model provided in section~\ref{sec:taxonomy} offers a high-level view, Figure~\ref{fig:dsp-mm} of this section provides a technical meta-model for CSP systems. This figure follows the classical application-level description of software systems, with focus on stream processing systems (e.g.~\cite{neumeyer2010s4,gedik2008spade}). According to this, the basic building blocks of stream processing systems are well-defined software components, which perform various kinds of jobs, and can be connected/composed together.
%Classically, at application level, the basic building blocks of stream processing systems are well-defined software components (e.g.~\cite{neumeyer2010s4,gedik2008spade}), which perform various kinds of jobs, and can be connected/composed together. 
Similarly, in the CSP meta-model we find the core elements of a CSP system: one or more processing elements~\emph{(PE)}, which can be computer-driven or human-driven (resp. \emph{APE} or \emph{CSPE}).
%
Each PE performs dedicated tasks, and it may depend on other processing elements in terms of data requirements. The PEs are connected through communication flows for data or control, which are modeled using the \emph{Data flow} and \emph{Control flow} concepts.
%
The data flow connections tie {\em input ports} and {\em output ports}. Data items are emitted from their source through a (usually single) output port and they are ingested by the target through (possibly multiple) input ports.  
% where the source emits data items through its (usually single) output port, and the target ingests the data items through (possibly multiple) input ports. 
Section~\ref{subsec:framework-com} explains this asymmetry. 
%
Control connections can also be established to coordinate the behavior between pairs of PEs using (possibly multiple) configuration ports.

%Processing elements can also coordinate their behavior by establishing {\em control connections} among pairs of them using (possibly multiple) configuration ports.

\subsection{Processing elements}\label{subsec:framework-pe}

A processing element consumes data items and control flow signals through input ports, implements an application-specific requirement, and emits the processed data items through an output port. There are two types of processing elements as explained below.

%As we suggested while describing the examples of Section~\ref{sec:examples}, the main classes of processing elements are computer-driven and human-driven, and we refer to them respectively as {\em automatic processing elements} and {\em crowdsourced processing elements}.

\subsubsection{Automatic Processing Elements}

An automatic processing element (APE) is a standard component of stream processing systems, e.g. in~ \cite{neumeyer2010s4,gedik2008spade}. It executes a set of operations in a fully-automated manner on its input stream. Following the streaming computation model~\cite{muthukrishnan2005data}, we assume APEs do not have enough memory to hold all the items that go through them.

\subsubsection{Crowdsourced Processing Elements} \label{sec:managed-crowds}

A crowdsourced processing element (CSPE) employs a large group of people (i.e. a crowd) to process data.
%
The processing of one item in CSPEs is assumed to be more expensive and slow than in APEs.
%
There are two ways in which this cost can be incorporated in the design of a system. A first option is to assume that the system can process at most $k$ data items through CSPEs, i.e. there is a fixed \emph{budget} for the crowdsourcing tasks that the system can do. A second option is to consider that there is a certain \emph{cost per task} to be paid, and the system should be designed to minimize that cost.
A CSPE may be implemented through the API of a local crowdsourcing platform (e.g. PyBossa)\footnote{\url{http://dev.pybossa.com/}} or through the API of a remote crowdsourcing application (e.g. Amazon's Mechanical Turk\footnote{\url{https://www.mturk.com/}}, CrowdFlower\footnote{\url{https://www.crowdflower.com/}}, or others).

A processing element (PE) can act as information source, processor, or consumer as explained below.

\spara{Information source.} Processing elements with no input ports are called {\em information source} elements, and perform {\em edge adaptation}~\cite{turaga2010design}, i.e. they convert external stimuli into data to be consumed by the CSP system. Information source PEs are responsible for emitting data continuously. An example of an automatic PE (APE) as information source is a sensor (e.g. seismometer that detects earthquakes) which gathers and provides continuous access to data. An example of a crowdsourced PE (CSPE) as an information source is the data generated through web-clicks of humans on the web.

\spara{Information processor.} Processing elements with both input and output ports are called {\em information processors}.\footnote{In the Storm system~\cite{marz_2013_storm} input sources are named ``spouts'', and information processors and consumers, ``bolts''.}
An example of an APE as information processor, is an example of a computer program that performs some computation over data (e.g. a sort program). An example of a CSPE as information processor is the case of human-processed information (e.g. classification of a twitter message into positive or negative sentiments).

\spara{Information consumer.} Processing elements with no output ports are called {\em information consumers}. Processing elements that only consume information---for example to preserve or visualize it---are known as information consumer elements. An example of an APE as information consumer, is a visualization component that ingests data only to visualize it. An example of a CSPE of type information consumer is a decision-maker (a human) that ingest data from computer program to make a decision during a crisis situation.


\subsection{Connections and Communication flows}\label{subsec:framework-com}

In this section, first, we describe the general communication behavior using channels and ports, second the communication modalities (i.e. {\em point-to-point}, {\em distributed} and {\em broadcasted}) and third the flows among PEs (i.e. {\em control flow} and {\em data flow}).

%We aim for generality in this framework so we include three communication modalities among the processing elements ({\em point-to-point}, {\em distributed} and {\em broadcasted}), and two types of flows ({\em data flows} and {\em control flows}).
%
%In this section we describe these types conceptually, but first we specify their general behavior through channels and ports.
%\inote{I am not sure if it is to our benefit to say at this point that we aim for generality. I suggest to cut it and simply say that: First, we describe the general communication behavior, second the communication modalities and third the flows among PEs.}

\subsubsection{Channels and ports}

Communication between processing elements is done through generic channels (sometimes referred to as {\em streams}). The concrete implementations of these channels may vary. In case buffering is required, the communication channels may be implemented using bounded-memory queues. If buffering is not required, other message-passing patterns can be used.

The processing elements have input, configuration, and output ports. The input ports are used to ingest data from different data sources. The configuration ports provide a way to configure a PE or to set default values for some of its parameters. The output port is used to emit the output data of the PE. Each port can have multiple parameters and the data types of those parameters can be set using either built-in types (primitive data types) or domain-specific types.
%

%\note[Yannick]{This means the subclass relations between information boxes should be at the PE level, and not at the APE and CSPE as it is now. Another way to model this would be to add a "Role" concept, as a superclass of Information consumer, processor and source; and to link it to PE with a "hasRole" property.}
%\note[Imran]{To me both ways are OK.}
%
%Elements with no input ports are called {\em information source} elements, and perform {\em edge adaptation}~\cite{turaga2010design}: converting external stimuli into data to be consumed by the CSP system.
%
%Elements with no output ports are called {\em information consumers}, and elements with both input and output ports are called {\em information processors}.\footnote{In the Storm system~\cite{marz_2013_storm} input sources are named ``spouts'', and information processors and consumers, ``bolts''.}

\subsubsection{Communication modalities}

A single output port is all that is needed for most applications to emit output data. However, in addition to the one-to-one communication between two PEs, it is possible that output data has to be distributed from one source to many target PEs in parallel. To this end, the complexity of determining the destination PEs for each output item can be controlled by one of the following {\em communication modalities}:

\spara{Point-to-point.}
Point-to-point communications are the simplest case and have a single processing element as producer and a single processing element as consumer. Essentially, both source and target components in a point-to-point communication modality comprise one port each (i.e. source with the output port and target with the input port).

\spara{Distributed.}
The distribution communication modality supports cases where the output data of a processing element (e.g. data source PE) has to be ingested by multiple PEs. In such cases, multiple processing elements are subscribed to the same channel using the {\em distributed} communication model, possibly filtering data according to certain criteria or keys (as for example in ~\cite{neumeyer2010s4}). The data items are distributed to multiple consumers.
%\note[Yannick]{The subscription mechanism should be explained or at least introduced, as this is the first time here you refer to such a precess. As you say the framework is made to provide a standard way to formalize CSP systems, then it should be made clear what are the standard elements that us suggest to use systematically and what is only optional.} 
%\note[Imran]{re-phrased.}

\spara{Broadcasted.}
This communication modality is used when multiple processing elements need to process the same data items at the same time. The {\em broadcasting} communication model duplicates data items to all consumers that are subscribed to a channel.

%\note[Yannick]{The explanations here do not explain the meta-model: we do not know why Point-to-Point is the only specific flow that is both a Control flow and a Data flow...}
%\note{This point is explained below.}

\subsubsection{Data and control flows}

\spara{Data flows} pass data items across processing elements. 
%
Data flows should use high-bandwidth channels with some amount of buffering, to provide better load adaptability.

\spara{Control flows} allow a processing element to query or control the behavior of another processing element~\cite{bockermann2012processing}. This can be used, for instance, to modify a parameter or a set of parameters in the operation of a processing element.
%
Control flows should use low-latency channels with little or no buffering for faster response. Additionally, control flows should typically be used in point-to-point modality since the control signals may depend on the target processing element being addressed.


%\note[Yannick]{At this point, there are elements from the meta-model that are still not described. Since again your purpose is to provide a reference framework, all the elements that you propose in the meta-model have to be clearly explained so that people can implement the model. Missing elements at this point are: Data type and the specific types of Data type, Composition and Connexion (see my related comment at the beginning of the section)}
%\note[Imran]{Data types are explained in channels and ports block above. Compositions etc. are explained below.}

\subsection{Composition types}
A composition represents a specific topology used to connect various PEs in order to solve a specific problem. CSP systems can be composed using mainly three composition types, as follows.

\spara{Serial composition}. A serial composition represents two or more PEs connected in a serial way, according to which the target PE always depends on the source PE in terms of data or control signal(s).

\spara{Parallel composition}. Parallel composition represents the case where the connected PEs work in parallel and are independent of each other in terms of data or control signals. 
 
\spara{Hybrid composition}. Finally, the hybrid composition represents a mix of serial and parallel types and often a more complex composition of PEs.

introduction.tex
% !TEX root = paper.tex
\section{Introduction}
\label{sec:intro}

Stream processing refers to computations performed on an unbounded, high-speed, continuous, and time-varying sequence (stream) of events [49], which typically cannot be stored off-line and needs to be processed on-line. If performed timely and effectively, stream processing can play a vital role in supporting real-time decision making. Many practical applications have been developed based on the stream processing paradigm, including real-time road condition monitoring, event-based business processing and profile-based query processing, implemented through various stream processing frameworks, such as the Aurora, TelegraphCQ, S4 and Storm project system among others ~\cite{neumeyer2010s4,marz_2013_storm,carney2002monitoring,chandrasekaran2003telegraphcq}.

A significant drawback of traditional stream processing systems is that they rely entirely on automated algorithms of data processing, and as such they are limited by the processing capabilities of these algorithms. Indeed, it is often the case that data stream to be processed is imprecise, highly variable and previously unseen, yet the decision based on this data needs to be made in real-time. In this case, automated processing on its own may produce undesirable results, harming the decision-making process it needs to support.
%
For example, suppose we are interested in monitoring social media to identify messages related to a major crisis event (e.g. an epidemic spreading such as the H1N1 flu pandemic in 2009). The moment this data is issued it needs to be correctly categorized and classified, in order to inform health and policy decisions accurately and on time. Unfortunately, relying only on automated data processing algorithms may not be adequate, firstly because user-generated data in Twitter may partially be erroneous, due to human mistake or intentionally, and secondly because new data may have different characteristics than existing data used to create the algorithms used by the system.
%
In machine learning, this is referred to as the \emph{domain adaptation problem}, where due to concept drift and other issues, a model trained on one event does not perform well on another. Back to our previous example of epidemic spread detection, a fully automatic  stream processing algorithm trained on data from the H1N1 epidemic, may not function correctly on a new epidemic (e.g. the MERS-coronavirus outbreak in 2014), for instance due to the presence of unique vectors (e.g. spread through camels instead of birds) which have not been seen in previous situations.
%
Nevertheless, failing to correctly filter the stream data of the new situation may lead to incorrect conclusions.
%
It therefore becomes apparent that \emph{in cases where critical---in terms of cost, time or other valuable resource---decision-making needs to take place in real-time, based on data streams that are potentially noisy and unseen, fully automated stream processing systems do not suffice}. Similar scenarios to the above include detecting intrusion or fraud based on anomalous or unusual activities.

Crowdsourcing is a recent computing paradigm that has been used to address the above problems~\cite{geiger_2011_crowdsourcing}. It refers to utilizing a large number of users (a crowd) to perform a task, by splitting it into several sub-tasks and allocating them to individual workers. Crowdsourcing presents the significant advantage of involving human intelligence; and with it, the ability of humans to categorize, filter and evaluate, often better than automated methods.
%
In fact, crowdsourcing has proven to be better than current computer algorithms in numerous cases, ranging from image recognition and audio transcription to real-time document syntax checking. In our example above, crowdsourcing could make use of the ability of humans to make better sense of a textual message than any algorithm, and in this sense help categorize and disambiguate the information included in a crisis data stream much more effectively.
%
Given that typical crowdsourcing relies entirely on human effort, which inevitably entails the risk for low recognition quality, %in case the human workers are mistaken. In fact, the inability to guarantee quality is one of the reasons why crowdsourcing is not entirely trusted by today’s stakeholders, despite its potential to create better value than automated means. To ensure quality,
typical crowdsourcing approaches apply redundancy, i.e. they allocate the same task to multiple workers. This redundancy decreases the throughput and increases the cost of crowdsourced processing.
%
Adding to this problem is the fact that stream processing tasks, unlike other types of input to crowdsourcing, necessitate a very high response rate (throughput) from the crowd. For example, during the Hurricane Sandy a peak rate of 16,000 tweets/minute was observed, and in such case, pure crowdsourcing may easily fail due to human limitations. \emph{Summarizing, while fully automated processing may not be appropriate because of errors or quality issues, fully crowdsourced processing may not be appropriate because of processing time (throughput) and cost.} 

The above problem leads to the nascent class of crowdsourced stream processing systems (CSPs), which combine automatic and human processing elements applied on time-sensitive, often critical information in the form of data streams. Certain instances of such systems have recently appeared, requiring different amounts of automated and human involvement, and involving different architectural and design patterns, of which we provide an overview in the next sections.
%
Despite their appeal and necessity, however, no concrete framework exists currently to organize the characteristics, functionalities, architectural patterns and problem cases that CSP systems apply on. As a result, the design of CSPs today is ad-hoc and, at best, intuition-based. A systematic formalization and synthesis of these systems could significantly improve the design and engineering of CSP applications, leading to better designs and to performance improvements of current systems, and guiding the development of new ones. Given the added value and criticality of accurate, fast stream processing, and the abundance of applications that need it, one may easily understand why such systematization is essential. To the best of our knowledge, \emph{this is the first work attempting to systematize the description and analysis of CSPs through a concrete functional, architectural and evaluation framework.}

\spara{Contribution and organization of this paper.}
First, we propose a generic framework for the design and analysis of crowdsourced stream processing systems. Our contribution begins in Section~\ref{sec:taxonomy} by positioning CSPs into a broader taxonomy of systems. 
%
Then we describe design objectives, principles and quantifiable evaluation criteria (Section~\ref{sec:principles}). 
%
In Section~\ref{sec:framework} we introduce a generic application design framework in terms of composable elements and communication channels. 
%
In Section~\ref{sec:patterns} we present a series of design patterns to solve specific design problems.
%
Section~\ref{sec:evaluation-aidr} shows a case study in which we design and analyze a CSP system using our framework. 
Finally, Section~\ref{sec:related-work} outlines related work and Section~\ref{sec:conclusions} summarizes our main conclusions.

paper.tex
% a sample file for Journal of Web Engineering (JWE) in 
% LaTex2e by inputing macro file "qic.sty" with command \usepackage{jwe}, 
% all the macros have been defined in the style file, so it is no need to 
% put many macros at the beginning of the text file  

\documentclass[twoside]{article}
\usepackage{jwe,epsfig}

\textwidth=5.6truein
\textheight=8.0truein

\renewcommand{\thefootnote}{\fnsymbol{footnote}}  %use symbolic footnote

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% WATERMARK
%\usepackage{draftwatermark}
%\SetWatermarkText{DRAFT - UNDER REVIEW}
%\SetWatermarkScale{0.4}
%\SetWatermarkLightness{0.95}
%\def\firstfoot{Please do not redistribute. For inquiries contact mimran@qf.org.qa.}
%\def\firstfoot{For inquiries contact mimran@qf.org.qa.}
%\runningfoot{}
%COMMENT {bottomstuff} below to supress ACM info

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\usepackage[show]{chato-notes}
% Extra packages
\usepackage{graphics, graphicx}
\usepackage[square, comma, sort&compress, numbers]{natbib}
\usepackage{subfigure}
\usepackage{booktabs}
\usepackage{multirow}
\usepackage{paralist}
\usepackage[all]{xy}

% URL packages
\usepackage[hyphens]{url}
\usepackage{hyperref}
\hypersetup{
    colorlinks,
    citecolor=black,
    filecolor=black,
    linkcolor=black,
    urlcolor=black
}

%highlighting
\usepackage[ulem=normalem]{changes}
\usepackage{changes}

% Paragraphs
\newcommand{\spara}[1]{\smallskip\noindent{\bf #1}}
\newcommand{\mpara}[1]{\medskip\noindent{\bf #1}}
\newcommand{\para}[1]{\noindent{\bf #1}}

% Tables
\usepackage{array}
\newcolumntype{L}[1]{>{\raggedright\let\newline\\\arraybackslash\hspace{0pt}}p{#1}}
\newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}p{#1}}
\newcolumntype{R}[1]{>{\raggedleft\let\newline\\\arraybackslash\hspace{0pt}}p{#1}}

% Typesetting
\clubpenalty=10000 \widowpenalty=10000
\renewcommand{\topfraction}{1.0}
\renewcommand{\bottomfraction}{1.0}
\renewcommand{\textfraction}{0.0001}
\renewcommand{\floatpagefraction}{1.0}
\renewcommand{\dbltopfraction}{1.0}
\renewcommand{\dblfloatpagefraction}{1.0}

% Other aliases
\newcommand{\emphbf}[1]{\textbf{\emph{#1}}}

%Comments
\usepackage{verbatim}

\begin{document}
\setlength{\textheight}{8.0truein}

\runninghead{Engineering Crowdsourced Stream Processing Systems}
            {Imran et al.}
      
\normalsize\textlineskip
\thispagestyle{empty}
\setcounter{page}{1}

%\copyrightheading{V}{N}{2014}{PP--PP}

%\vspace*{0.88truein}
\alphfootnote
\fpage{1}

\centerline{\bf
ENGINEERING CROWDSOURCED STREAM PROCESSING SYSTEMS}
\vspace*{0.035truein}
\vspace*{0.37truein}
\centerline{\footnotesize
MUHAMMAD~IMRAN$^1$, IOANNA~LYKOURENTZOU$^2$, YANNICK~NAUDET$^2$, CARLOS~CASTILLO$^1$}
\vspace*{0.15truein}
\centerline{\footnotesize\it $^1$Qatar Computing Research Institute,}
\baselineskip=10pt
\centerline{\footnotesize\it Doha,
Qatar}
\baselineskip=10pt
\centerline{\footnotesize\it 
mimran@qf.org.qa, chato@acm.org}
\vspace*{0.1truein}
\centerline{\footnotesize\it $^2$CRP Henri Tudor}
\baselineskip=10pt
\centerline{\footnotesize\it Luxembourg}
\baselineskip=10pt
\centerline{\footnotesize\it ioanna.lykourentzou@tudor.lu, yannick.naudet@tudor.lu}
\vspace*{0.1truein}
%\centerline{\footnotesize\it $^3$INRIA}
%\baselineskip=10pt
%\centerline{\footnotesize\it Nancy, France}
%\baselineskip=10pt
%\centerline{\footnotesize\it ioanna.lykourentzou@inria.fr}
%\vspace*{0.225truein}
%\vspace*{0.21truein}

\abstracts{
A crowdsourced stream processing system (CSP) is a system that incorporates crowdsourced tasks in the processing of a data stream.
%
This can be seen as enabling crowdsourcing work to be applied on a sample of large-scale data at high speed, or equivalently, enabling stream processing to employ human intelligence. It also leads to a substantial expansion of the capabilities of data processing systems.
%
Engineering a CSP system requires the combination of human and machine computation elements. From a general systems theory perspective, this means taking into account inherited as well as emerging properties from both these elements.
%
In this paper, we position CSP systems within a broader taxonomy,
outline a series of design principles and evaluation metrics,
present an extensible framework for their design,
and describe several design patterns.
%
We showcase the capabilities of CSP systems by performing a case study that applies our proposed framework to the design and analysis of a real system (AIDR) that classifies social media messages during time-critical crisis events. Results show that compared to a pure stream processing system, AIDR can achieve a higher data classification accuracy, while compared to a pure crowdsourcing solution, the system makes better use of human workers by requiring much less manual work effort.  
}{}{}

\vspace*{10pt}

\keywords{Crowdsourcing, Stream Processing}
\vspace*{3pt}
%\communicate{(To be filled by the editor)}

\vspace*{1pt}\textlineskip 

\input{introduction}
\input{taxonomy}
\input{principles}
\input{framework}
\input{patterns}
\input{evaluation-aidr}
\input{related-work}
\input{conclusion}

\bibliographystyle{nourlabbrvnat}
\bibliography{paper}

% In case an appendix is needed
%\appendix

%\note{Journal of Web Engineering: limit 40 pages.
%Human Computation Journal: limit 9,000 words (see with ``\texttt{make wordcount}'')}

\end{document}

patterns.tex
% !TEX root = paper.tex
\section{Design Patterns}\label{sec:patterns}

The preceding section describes the generic technical components to implement when designing a CSP system. In this section we introduce specific design patterns for the connection of automated and crowdsourced processing elements.
%
The idea of design patterns %in software design
has been pivotal to software engineering since the work of \citet{gamma_1994_design}.
%
The design patterns presented in the section provide solutions to common problems with the CSPs context. \emph{By its nature a list of design patterns is always open}, as new problems and new solutions to existing problems can be discovered and incorporated.
%


In the remainder of this paper, we make use of the following notation: rectangles represent automatic processing elements, rounded rectangles are crowdsourced processing elements, solid lines are data flows, and dashed lines are control flows.

\subsection{Quality assurance loop}\label{subsec:qa-loop}

\noindent{\bf Schematic structure:}
\begin{figure}[ht]
\centering\vskip-1em
\includegraphics[width=0.40\columnwidth]{figs/quality-assurance-loop}
\vskip-1.5em
\end{figure}

%\medskip
%\centerline{\xymatrix{
% \ar[r] & *+[F-:<6pt>]{Work} \ar[r] &  *+[F]{Evaluate} \ar@/_1pc/[l] \ar[r] & \\
%}}
%\medskip

\spara{Problem.}
Given that the quality of work varies across workers, crowdsourcing is almost invariably used with some degree of redundancy. A fixed level of redundancy (e.g. ``each task has to be done by 3 crowdsourced workers'') may not be an optimal solution, given that some tasks may induce larger inter-worker agreement, thus requiring less redundancy, while other tasks may create larger disagreement and require more redundancy.

We would thus like to have per-task guarantees. In some cases, we would like to adaptively ask more workers to perform a task, until a certain criterion is satisfied. In other cases, we may want to ask for more expensive (but more accurate) workers to perform a certain task when we detect that regular workers are not agreeing enough. Some current crowdsourcing platforms offer this feature, by allowing to define the accuracy or expertise level of the involved workers.% (as an example CrowdFlower.com offers access to ``editorial crowd", ``level 3", ``level 2", ``level 1" workers).

\spara{Solution.}
Use an automatic quality assurance loop to aggregate and evaluate crowdsourcing work. The evaluation component may compute cost/quality trade-offs and stop when marginal accuracy increases are smaller than the cost of getting an extra label (as in~\cite{gao_2013_online}). The evaluation component may also keep a model of the trustworthiness of each individual worker, based on his/her past level of agreement (as in ~\cite{ipeirotis_2010_get_another_label}).

\spara{Applicability.}
This pattern is applicable when the quality of the crowdsourcing work can be evaluated automatically by cross-checking labels from different workers. This pattern also applies when there is a global constraint that the output should honor, for example, if we are trying to obtain a total order on items that are being compared pairwise by workers. In this scenario, the evaluation component has to detect violations on the output (a violation of the transitivity property in this example), and ask for more crowdsourcing work to be done on the problematic subsets of the data.

\subsection{User-specific task assignment}\label{subsec:task-assignment}

\noindent{\bf Schematic structure:} 
\begin{figure}[ht]
\centering\vskip-1em
    \includegraphics[width=0.40\columnwidth]{figs/task-assignment}
\vskip-1.5em
\end{figure}

%\medskip
%\centerline{\xymatrix{
% \ar[r] & *+[F]{Assign} \ar[rr]^{worker~ids}_{+ tasks} & & *+[F-:<6pt>]{Work} \ar[r] &  \\
%}}
%\medskip

\spara{Problem.} The crowd members are heterogeneous in their capacity to perform tasks. Assigning the ``right'' task to a worker leads to a reliable output, but failing to do so leads to an unreliable one.

\spara{Solution.}
An automatic processing element maintains a model of the skill of workers for different tasks. When feeding a task to a crowd, it indicates what is the specific worker-id that must perform each task.
%
This design pattern should be combined with a quality assurance loop.

\spara{Applicability.}
This pattern is applicable when there is a variety of different skills needed for a given crowdsourcing job (comprising multiple tasks) and it is possible to automatically compute an estimation of the quality of the per-skill output of a worker performing a certain task (see for example \cite{Goel:2014:ATW:2567948.2577311} where workers of different sets of skills are matched to heterogeneous tasks through a mechanism design-based automatic element). 

%\inote{We need a reference example here. I will also search but feel free to add it if you have one in mind.}
%\inote[Ioanna]{I found these two related papers (check Latex code of comment):} %http://www.ics.uci.edu/~qliu1/nips13_workshop/Papers/ActivePaper1.pdf      and         http://www.ifis.cs.tu-bs.de/sites/default/files/DASFAA14_UnCrowd_2.pdf         . They talk about matching workers with tasks based on worker expertise on various skills that the task may require.}


\subsection{Process automatically, verify manually}\label{subsec:process-verify}

\noindent{\bf Schematic structure:} 
\begin{figure}[ht]
 \centering\vskip-1em
    \includegraphics[width=0.40\columnwidth]{figs/auto-verify}
\vskip-1.5em
\end{figure}

\spara{Problem.}
The input throughput exceeds the budget of crowdsourcing calls, so the data needs to be reduced before being crowdsourced.

\spara{Solution.}
An automatic processing element operating as a ``detector'' can act as a filter, and passes only the elements that are over a certain criterion towards a ``verifier'' crowdsourced processing element.
%
For instance, crowdsourced content moderation (for profanity or hate speech or inappropriate content as in \cite{myhuemcgowran2012}) could pass only suspicious messages, containing certain keywords or image features, to a crowd of workers. 
%\inote{Example reference needed here.}

\spara{Applicability.}
In the context of binary classification tasks (other cases can be dealt with in a similar manner), this pattern is useful when there are methods to filter-out true negatives deterministically or with high precision. In this case, the number of crowdsourcing calls can be reduced by passing to the crowd only the examples that have a sufficient probability of being positive.

\subsection{Supervised learning}\label{subsec:supervised-learning}

\noindent{\bf Schematic structure:} 

\begin{figure}[ht]
 \centering\vskip-1em
    \includegraphics[width=0.40\columnwidth]{figs/supervised-learning}
\vskip-1.5em
\end{figure}
%\medskip
%\centerline{\xymatrix{
%  \ar[r] & *+[F]{Process} \ar[rr]^{(distributed~com.)} & \ar[d] & \\
% *+[F]{Learn} \ar@{-->}[ur]_{~~~model~parameters} & *+[F-:<6pt>]{Label} \ar[l] & *+[F]{Sample} \ar[l] \\
%}}
%\medskip

\spara{Problem.}
The input throughput vastly exceeds the budget of crowdsourcing calls, so an automatic system needs to learn to mimic the work process performed by crowdsourced workers.

\spara{Solution.}
An automatic processing element runs a parametrized machine-learned model. Its output is sampled according to a certain criterion, and sent to a crowdsourced processing element to provide {\em training labels}. These labels are used to learn a new model, which is sent through a control signal to the main automatic processing element.
%
The sampling can be done uniformly at random, or following the idea of {\em active learning} to maximize the gains in accuracy for every extra label.
%
An example of this solution is \citet{kamar_2012_galaxyzoo}, who use machine vision to identify galaxies based on models learned from human labels.
%\note[Yannick]{Once again, why is it about labels? Is the supervised learning pattern valid only for classification tasks?}

\spara{Applicability.} 
This pattern can be applied when it is possible to learn an automatic model of the process the crowd performs.

\subsection{Crowdwork sub-task chaining}\label{subsec:subtask-chaining}

\noindent{\bf Schematic structure:} 
\begin{figure}[h!]
 \centering\vskip-1em
    \includegraphics[width=0.70\columnwidth]{figs/sub-task-chaining}
\vskip-1.5em
\end{figure}

%\medskip
%\centerline{\xymatrix{
%\ar[r] & *+[F-:<6pt>]{Subtask~1} \ar[r] & *+[F]{Post-process} \ar[r] & *+[F-:<6pt>]{Subtask~2} \ar[r] &  \\
%}}
%\medskip

\spara{Problem.}
A complex task generates high latency and low quality output, and needs to be divided into separate parts.

\spara{Solution.}
Two or more crowdsourced processing elements can be composed on a serial, parallel, or hybrid circuit. The output from one CSPE is post-processed and sent to another CSPE (that can also be post-processed automatically). This is related to the now-centenarian paradigm of scientific management/Taylorism/Fordism.
%
One example can be the decomposition of the task of counting calories in pictures of meals described in~\cite{noronha_2011_platemate}, where a large task (identifying nutrients in a certain food plate) is decomposed to several smaller sub-tasks (drawing boxes to identify the distinct food parts in a plate's image, tag and describe the identified parts, and measure their size in terms of portions). These sub-tasks are handled in a complex workflow within the original crowdsourced task, by different CSPEs, while additional PEs exist to help the process (for example calculating the level of agreement among workers). Similar examples where a large crowdsourcing task is divided into smaller sub-tasks and handled by separate CSPEs include the detect-fix-verify paradigm in~\cite{bernstein2010soylent}, or a secondary grading task to control the quality of a primary task~\cite{sorokin_2008_utility}. 

%\inote{Explain a bit more what all these applications have in common, i.e. how exactly they decompose their task to multiple CSPEs that work in chains and how these chains are connected.}

\spara{Applicability.}
This pattern can be applied when the task can be divided in advance into discrete sub-units. If not, this pattern can be extended by following an approach similar to \cite{kulkami_2012_turkomatic}, where workers are involved not only in solving the sub-tasks, but actually designing the workflow process to be followed, by suggesting decompositions of the original task. In this case, control flows need to connect the different crowdsourced processing elements, indicating changes in the tasks (e.g. decomposition) performed by them.  %\inote{Explain this reference, with the specific task examples and CSPE example functionalities that the reference uses.}

\subsection{Human processing optional per item}\label{subsec:guaranteed-throughput}

\spara{Problem.}
A minimum throughput or maximum latency needs to be guaranteed, but crowdsourced stream processing elements can not guarantee that same throughput. Humans may become a bottleneck.

\spara{Solution.}
There should be a path of data flows between the application's input and its output that does not pass through any crowdsourced stream processing element. This means patterns such as {\em supervised learning} or other types of parallel connections need to be part of the design.

\spara{Applicability.}
This pattern can be applied when the minimum number of crowdsourcing calls needed in steady state for the application to function is zero. It can be applied after pattern presented in~\ref{subsec:supervised-learning} when an adequate amount of training data has been gathered. 

\subsection{Human processing mandatory per item}\label{subsec:guaranteed-quality}

\spara{Problem.}
A guaranteed level of quality, which can only be attained through human oversight, needs to be attained. 

\spara{Solution.}
Every path of data flows between the application's input and output needs to pass through a crowdsourced stream processing element. One example is the case of a system to deal with reports of disruptive behavior (e.g. in a massive multi-player online game or similar system), where account suspension or other penalties can only be authorized by humans~\cite{hodson_2013_juries}. Additionally, a minimum level of redundancy can be applied in all such elements if multiple paths exist.

\spara{Applicability.}
This pattern can be applied when low latency does not need to be guaranteed. Enforcing that every data element that will be written in the output needs to pass through a crowdsourced component may introduce latency in the system.


principles.tex
% !TEX root = AIDR-www2014.tex

\begin{table*}
\tcaption{Design objectives and principles}\label{tab:principles}
\small\begin{tabular}{p{1.0in}L{1.4in}L{1.4in}L{1.4in}}\toprule
                 &        & \multicolumn{2}{c}{Design principles}\\
Design objective & Example metric & Automatic  components & Crowdsourced components \\ \midrule
Low Latency      & End-to-end time            & Keep-items-moving              & Simple tasks \\
High Throughput  & Output items per unit of time & High-performance processing & Task automation \\ 
Load Adaptability& Rate response function     & Load shedding, load queueing  & Task prioritization   \\
Cost Effectiveness& Cost vs. quality/throughput/etc. & --- & Task frugality \\
High Quality     & Application-dependent & \multicolumn{2}{l}{~~~~~~Redundancy/aggregation and quality control} \\
\bottomrule
\end{tabular}
\end{table*}

\section{Design objectives, principles and metrics}\label{sec:principles}

In the previous section we presented a characterization of crowdsourced stream processing systems. In this section we give design principles that help building efficient systems. This efficiency can be achieved through optimising the important properties of CSPs inherited from its parents: stream processing and crowdsourced systems (see section~\ref{sec:CSP-System}). Each resulting design objective is quantifiable through a certain metric, and trade-offs among different objectives may occur, as summarized on Table~\ref{tab:principles}.

The first three objectives (low latency, high throughput and load adaptability) are common in the stream processing literature~(e.g. \cite{turaga2010design,mendes_2009_performance}); while they are not crowdsourcing-specific, we adapt them to the crowdsourced stream processing setting. We do so by indicating how to address each objective in the automatic and crowdsourced components of the system.
%
The last two objectives (cost effectiveness and high quality) are a consequence of the presence of humans as part of the system. %In the following, we detail design principles for each of the five objectives, for both automatic and crowdsourced processing elements, and give evaluation metrics.

\subsection{Low Latency} \label{subsec:principles-latency}

Latency is the time it takes for an item to be processed, and a low latency system takes less time to deliver results than a high latency system.
%
In the literature, low-latency crowdsourcing stream processing systems have been referred to as real-time crowdsourcing systems (e.g. \cite{kittur2013future,bernstein_2011_twoseconds}).

\spara{Measuring latency.}
A typical measure for the latency of a system is the average latency of the items traversing through it.
%
The latency of an item is trivial to compute if the mapping from input to output items is one-to-one. If that is not the case (e.g. because each output item depends on several input items that arrived at different times), then for each input item that contributed to one or more output items, its latency can be measured as the time it took for the first such output item to be produced. 

\subsubsection{Automatic components: keep data moving}

Automatic components should avoid unnecessary latencies due to network delays, storage operations, or other causes. Input items may be out-of-order, missing or delayed. Automatic processing elements should use non-blocking operations, never waiting indefinitely for some data items to arrive before continuing processing~\cite{stonebraker20058}.

\subsubsection{Crowdsourced components: simple tasks} \label{subsec:trivial-tasks}

%As described by \citet{kittur2013future} and \citet{finnertykeep} 
Task design depends on many aspects that include incentives, interface, task description, and more importantly the task itself~\cite{kittur2013future,finnertykeep}. Research and practice suggest to decompose complex tasks into simple subtasks, where each task is designed to be simple and follow specific requirements. This can not be understated, as it helps both to reduce the cost and to increase the quality of work.
%
Simpler tasks are completed earlier~\cite{horton_2010_economics}, not only because each task is completed faster, but because the pool of people with the skills required to complete a task is larger if the task is simpler. A difficult task may introduce latency, and it may also reduce output quality~\cite{kazai_2010_influence}.

Task decomposition helps reduce individual task complexity.
%For instance, a task such as ``shorten a paragraph'' may be decomposed into ``find sentences that can be shortened'', ``suggest a shorter sentence to replace a longer one'' and ``determine if a rewrite of a sentence is correct'' (this is the detect-fix-verify paradigm in~\cite{bernstein2010soylent}).
%
The latency of the decomposed task may be lower if each individual task can be answered faster and/or by a potentially larger group of crowdsourcing workers.
%
We note that task decomposition may have different constraints across applications. While in general tasks should be as simple as possible, in some cases it may be efficient to bundle a few sub-tasks together, e.g. to reduce context switching and reduce latency.

\subsection{High Throughput}

Throughput is the speed at which items are processed: a high-throughput system can process more items per unit of time than a low-throughput one. The throughput of a system is a function of its design and of the throughput of its components. 

\spara{Measuring throughput.}
Throughput can be measured as output items per unit of time, e.g. items/second. 

\subsubsection{Automatic components: high performance}

A stream processing system should process and accommodate long-running analysis requirements almost in real-time~\cite{turaga2010design}. Each automatic processing element must be implemented to have high performance, and the application infrastructure including communication channels must be able to have a high throughput.

\subsubsection{Crowdsourced components: task automation}

In a crowdsourced stream processing system, in general the throughput of the crowdsourced processing components is lower than that of the crowdsourced processing components. Crowdsourced components may become a bottleneck.

Automating as much work as possible is a way of maintaining a high throughput: any aspect that can be automated should be not passed to a crowd. For instance in binary classification if we are searching for items belonging to a positive class, if an item can be automatically classified into the negative class, it does not need to be given to crowdsourcing workers.

\subsection{Load Adaptability}

The rate of input data may experience sudden changes including significant bursts. 
%
Adaptability is the capacity of the system to respond to a surge in demand.

\spara{Measuring load adaptability.}
Adaptability can be measured as the response function of throughput and latency vs input load. Ideally, these variables should not be strongly affected by increases in input load. In other words, we should not observe a significant reduction in throughput, or a significant increase in latency.

\subsubsection{Automatic components: load shedding/queuing}

Surges in input rate may require to use {\em load shedding}, this is, completely ignoring data items that are beyond the processing capabilities of a processing element at a given time~\cite{tatbul2003load}. Buffering may prevent shedding by allowing {\em load queuing}, using a bounded-size queue.

\subsubsection{Crowdsourced components: task prioritization}

The system should prevent crowdsourcing from becoming a bottleneck. This can be done by having a method for prioritizing tasks, in such a way that during periods of increased input rate, more tasks are taken by automatic parts of the system than normally. This may be done at the expense of output quality, if necessary.

For instance, \citet{demartini_2012_zencrowd} pass to the crowd only tasks (in their case, entity linking tasks) for which an automatic system is uncertain, i.e. it has not given with high-confidence a positive or a negative answer. The thresholds of what constitute a high-confidence answer could be tunned to be able to handle more input items per unit of time.

\subsection{Cost effectiveness}

Given that crowdsourcing work is neither unlimited in supply nor free (even when done by volunteers, their time and motivation are precious resources), a principle of {\em task frugality} needs to be applied.

Crowdsourcing is usually compensated in proportion to the time spent by workers. Cost is therefore a function of (i) the payment per unit of time, (ii) of the number of items to process, (iii) the time needed by each worker to complete one item, and (iv) the plurality of workers per item. Effort is also a parameter, eventually translatable to cost as well.
%
Increasing the payment per unit of time seems to have little effect in work quality, but can help reduce its latency~\cite{mason_2010_financial}.

The number of items to process is related to task automation---replacing crowd processing by automatic processing when possible---but also to the way processing elements are composed.
%
Similarly to query planning in traditional database systems, heuristics or optimization methods can be used to determine the order in which automatic and crowdsourcing operations need to be done~\cite{franklin2011crowddb}. Task workflow design can be optimized through automatic processing elements, as described by~\citet{dai_2013_pomdp}.

The time and effort needed by each worker to complete one item can be decreased by decreasing task subjectivity and difficulty, for instance by decomposing into smaller sub-tasks, which may also lead to lower latency (Section~\ref{subsec:trivial-tasks}). Task completion time can also be reduced by using more efficient worker-to-task allocation schemas, e.g., based on the average completion time and skills of each worker~\cite{boutsis_2013_crowdsourcing}. 

The plurality of workers per item reduces the effect of cheaters/spammers by using aggregated labels. This can be optimized by using a cost-sensitive objective, e.g., combining cost with quality as in~\cite{gao_2013_online}.

\spara{Measuring cost effectiveness.}
This can be done in comparison with other aspects, e.g. cost/latency, cost/quality, etc. For instance, in~\cite{fan2013hybrid} it is shown how larger budgets (in their case, fraction of items that are crowdsourced) yield better overall accuracy. The time to complete a task is also reduced when payment is increased~\cite{mason_2010_financial,heer_2010_graphical}.

\subsection{High quality}\label{subsec:principles-quality}

The addition of human elements makes crowdsourcing stream processing non-deterministic. Crowds vary in their composition and individual workers may provide varying levels of quality.

Output quality can be maintained by the interaction between automatic and crowdsourced components through operations such as aggregation, quality management and cheating detection (as mentioned e.g., in~\cite{yuen_2011_crowdsourcing} and others). Section~\ref{subsec:qa-loop} describes a design pattern (``quality assurance loop'') based on this type of interaction. Furthermore, the automated elements can play an important role in regards to incentives engineering, for example in diversifying task recommendations (bored workers perform worse than interested ones~\cite{kazai:an}), as well as in allocating incentives to tasks \cite{Yang:2013:IT:2510649.2511161}, with an aim to attract qualitative worker contributions and thus increase overall task quality.

\spara{Measuring quality.}
Quality should be measured in an application-dependent manner. The metric may be binary (correct item vs. incorrect item) or continuous, and it may not be a single scalar but comprise several aspects.


related-work.tex
 % !TEX root = AIDR-www2014.tex
\section{Related Work}
\label{sec:related-work}

Stream processing and crowdsourcing are vast research areas, so we focus on connecting our research to previous works covering topics closely related to ours.
%
This includes engineering principles, frameworks, and taxonomies for the predecessors of CSPs, as well as example systems describing key design choices and best practices.

\subsection{Data stream processing} 

Stream processing research covers many disparate fields (e.g., stock market data analysis \cite{demers2006towards}, fraud detection system \cite{schultz2009distributed}, intrusion detection systems \cite{debar2001aggregation}, disaster prediction systems \cite{broda2009sage}), and has passed through a number of stages.
%
Real-time stream processing systems perform data mining~\cite{sudhakar2012data}, clustering~\cite{aggarwal2003framework, zhou2008tracking}, classification, time series analysis~\cite{lin2003symbolic}, and other decision support tasks~\cite{zhu2002statstream}.
%
Furthermore, to support the development of application-specific stream processing systems, there are general-purpose platforms such as S4~\cite{neumeyer2010s4} and STORM~\cite{marz_2013_storm} supporting scalable real-time processing.
%
These systems are designed for high-speed continuous data ingestion, uninterrupted long-running processing, high-throughput, and low-latency.

We have incorporated key performance indicators from the above works into our evaluation metrics (Section \ref{sec:principles}), while our application design framework has been also inspired to some extent by the design of existing general-purpose stream platforms (Section~\ref{sec:framework}).

\subsection{Crowdsourcing}

%Crowdsourcing is a vast research area, with many application examples.
Two extensive crowdsourcing surveys can be found in \cite{yuen_2011_crowdsourcing, doan2011crowdsourcing}, which examine a variety of crowdsourcing systems -- often under different names such as collective intelligence, human computation, or social systems.
%under the lenses of the various applications that they can lead to, algorithms and performance metrics.
%In the following we describe taxonomies and design frameworks in order to position our paper in the crowdsourcing engineering literature. 

\subsubsection{Crowdsourcing system taxonomies}\label{subsec:relwork-taxonomies}

%Different taxonomies may be found, categorizing crowdsourcing systems according to their business model, their task type, and other facets.
First, a number of works categorize crowdsourcing systems from an organizational theory point of view, classifying them according to their \emph{business model functionality}.
%
\citet{geerts_2009_discovering} performs a model-driven categorization, distinguishing the models of crowdcasting, crowdstorming, crowd production and crowdfunding. 
%
\citet{yukovic_2009_enterprises} categorizes crowdsourcing systems by business-driven objectives, and further distinguish them in regards to their coordination model (marketplace or competitive-based). 
%
\citet{lykourentzou_2009_collective} distinguishes different user interaction modalities in crowdsourcing: collaborative, competitive, and hybrid.
%
\citet{saxton_2013_rules} identify nine basic types which span from social financing to citizen media production models; one of their main conclusions is the need for crowd management which as we describe can be provided by a combination of processing elements, through certain design patterns.

Regarding \emph{type-based classification}, crowdsourcing systems are classified per type of task (simple, complex, creative) in \cite{schenk_2011_practices}, while the different functions of the crowd (crowd rating, creation, processing and solving) are described in \cite{geiger_2011_crowdsourcing}. The first work covers ``what'' crowdsourcing workers do, and the second one covers ``how'' they do it, which is 
in line with the description of the role of humans in CSPs (Section~\ref{sec:taxonomy}). %Specifically \ref{subsec:taxo-crowdproc}

There are other works that do not explicitly aim at a taxonomical ordering of crowdsourcing, but contain taxonomical and design elements. \citet{quinn_2011_survey} describe 3 dimensions related to our work: quality control, aggregation, and process order.
The first is a design principle (Section~\ref{subsec:principles-quality}).
The second is an automatic element role (Section~\ref{sec:taxonomy}). %Specifically \ref{subsec:taxo-auto}
The third describes interaction models between ``computers, workers and requesters'', and as such it is related to the design patters that we propose (Section~\ref{sec:patterns}). 

%as well as by whether it needs to cover a well-defined client need, or it needs to address a more open-problem like large data gathering or information base building. 
%\citet[Table 1]{geiger_2011_managing} list of taxonomies plus own taxonomy.
%\citet{quinn_2011_survey} lists 3 dimensions that are related to our discussion on engineering of crowdsourced stream processing: {\em quality control}, {\em aggregation}, and particularly {\em process order}. The first is a design pattern we have mention. The second can be engineered by different combinations of elements in our framework. The third one describes how the requester, the worker, and the computer interact, and can be incorporated by considering that the roles of requester and worker are interchangeable in automatic processing elements.

\subsubsection{Crowdsourcing frameworks and modeling approaches}

Certain studies propose frameworks and modeling approaches to improve the design of crowdsourcing systems.
\citet{bozzon2013reactive} introduce a reactive crowdsourcing modeling approach focusing on the dynamic control of the crowd, by transforming high-level specifications (e.g. regarding task planning or worker handling) into elementary task-type executions.
%
\citet{roy2013crowds} propose SmartCrowd, a framework to interactively optimize three crowdsourcing processes: task generation, worker-to-task assignments and task evaluation, by taking into account the uncertainties introduced by the human factor.
%
A number of works provide goal-driven design principles, which focus on the optimization of crowdsourcing systems for a global-level performance target. In this line, \citet{lykourentzou_2013_guided} present a stepwise modeling approach for the design of corporate crowdsourcing systems, realized in five decision-making and application steps (define goals, characterize jobs, profile workers, identify constraints and design a crowdsourcing optimization algorithm).
%
Finally, \citet{boutsis_2013_crowdsourcing} focus on the process of task-to-worker allocation, and present a framework comprising four components (task management, dynamic assignment, profiling and scheduling), which aims at guaranteeing efficient crowdsourcing system performance under dynamic conditions of the crowdsourcing environment.

These works basically describe methodologies to optimize specific objectives of crowdsourcing system design. In contrast, our work describes a broad set of objectives and principles in a top-down manner (Section~\ref{sec:principles}), providing a framework against which specific design methodologies can be implemented by composing different elements (Section~\ref{sec:framework}). 

\subsection{Use Cases for CSPs}
%\note[Ioanna]{The subsection title probably needs to change.}
%
%\note[ChaTo]{We should remove the mentions of ``best practices'' and instead say this is a list of systems described in the literature that match our definition of CSP, and serve to exemplify the cases in which CSPs are useful.}

To the best of our knowledge, no prior work attempts to provide a general framework for engineering CSPs. However, there are works that describe CSP applications (without that specific name). We have already mentioned a number of these works in Section~\ref{sec:taxonomy}.
%
Concrete examples include web table matching \cite{fan2013hybrid}, entity resolution \cite{whang2013question}, or iterative text recognition \cite{little_2009_turkit}. A common element
in them are high-throughput and low-latency requirements, which we capture in Section~\ref{sec:principles}.
%
There are also works describing real-time crowd-involving systems (``flash crowds''~\cite{kittur2013future}), such as
the system by~\citet{mashhadi_2011_quality} on quality control for user-contributed data in ubiquitous applications,
the ones proposed by \citet{bernstein2010soylent} and \citet{bigham2010vizwiz},
or the crisis response system described by \citet{rogstadius_2011_realtime} (the latter has been recently adapted to operate with AIDR, the application we describe as a use case in Section~\ref{sec:evaluation-aidr}).

An indicative example is CDAS~\cite{liu2012cdas}, a CSP system for data analytics applied to tasks of sentiment analysis and image tagging. CDAS includes a quality assurance mechanism that takes into account the performance deviations of crowdsourced processing by monitoring historical performance data to estimate each elements' accuracy (instantiation of the quality evaluation metric of Section~\ref{subsec:principles-quality}), as well as an online strategy to reduce waiting time (latency evaluation metric in our framework).  
%
Finally, systems using a mix of crowdsourced and automatic elements to achieve more efficient treatment of homogeneous data have been described, with two key examples described in
%. Two key examples are related to answering relational database queries 
\cite{wang_2013_transitive, franklin2011crowddb}.

Certain elements of our framework borrow notions from the success and limitations showcased in the above systems. As an example, the study of performance in terms of quality, cost and speed, mentioned in the above works, have been expanded into the evaluation metrics (Section~\ref{sec:principles}).
Furthermore, several of the best practices illustrated above have been converted into design patterns (Section~\ref{sec:patterns}).
%
%Vice versa, multiple elements of our framework (such as the evaluation metric of load adaptability or alternative design patterns from the ones we propose) could be examined by the above systems, to further improve their performance. 

removed.tex

\clearpage
\section*{REMOVED MATERIAL}

\spara{DBMS examples.}
specialized Data Stream Management Systems, for example, STREAM \cite{arasu2004stream}, Aurora \cite{carney2002monitoring}, TelegraphCQ \cite{chandrasekaran2003telegraphcq}.

Considering all the above mentioned dimensions, we believe that a data stream processing system that can collect, annotate and process data streams in real-time, must hold the following characteristics:

\begin{enumerate}
\item The system must be capable of handling continuous, high-speed incoming data streams that include both structured as well as unstructured data items.

\item The system should be flexible enough to be extensible and tailorable. This introduces the extendibility to hook any type of crowdsourcing platform, or to run the system using different types of processing techniques (i.e., clustering, classification, time-series analysis etc).

\item The system should support the processing of incoming data items in batch as well as real-time fashion.

\item The system should be capable of incorporating human-annotated inputs on data items to facilitate the underlaying techniques those require training data.

\item The system should be easily operable by non-programmers. Yet, being accessible for end-users is highly important as most of the times people who use these kinds of systems are domain-experts rather than IT experts.  
\end{enumerate}

Nevertheless, as of today we observed that all the required components of a system that we can call a "Data Stream Processing System" are independently available, however, to the best of our knowledge there exists no such system which encompasses all of the above mentioned characteristics under one roof or a system that provides a way to be extended.


platform for the \emphbf{acquisition, annotation}, and \emphbf{processing} of structured as well as unstructured data streams. The platform encompasses all the characteristics mention above, and mainly divided into three conceptual modules namely,  ``information collector", ``information annotator", and ``information processor". The whole platform is designed following the \emph{Separation of Concerns} design principal, that is, each of its modules (e.g., data collector, data processor and data annotator) completely designed to operate independently. A key aspect of the platform is its extensibility to any of the modules. Each module of the platform adopts an abstract model that exhibits enough expressive power to be able to easily extensible. 

\spara{Example stream data sources.}
Examples of such sources include, typically, traffic monitoring systems, environmental sensors, financial applications, and quite recently social networking websites (e.g., Twitter, Facebook, Google+, etc.), added to the stack. Each individual data item in the data streams can be a human-generated microblogging post on Twitter or Facebook, a web page click, a sensor reading, and so on.

\spara{Human intervention.}
This human intervention may take place through a crowdsoucing platforms, such as CrowdFlower\footnote{http://www.crowdflower.com/}, Amazon Mechanical Turk (AMT)\footnote{http://www.mturk.com/}, etc., or it can be provided by in-house experts.
%
For generality, we will assume it is crowdsourced as this is the ``difficult'' case. 
%
For generality, we will also consider arbitrary workflows in which manual and automatic processing steps are intermingled.

Figure \ref{fig:dsp-interactions} shows various interactions that could happen among different processing elements....

\begin{figure}[h!]
 \centering
    \includegraphics[width=\columnwidth]{figs/dsp-interactions}
  \caption{Various interaction patterns}
  \label{fig:dsp-interactions}
\end{figure} 

\spara{Knowledge-intensive crowdsourcing.}
For example, many knowledge-intensive applications (e.g. wiki article writing) work with non-decomposable tasks and sequential task handling (users write on one anothers' contributions, gradually ``building'' the article), with or without explicit collaboration. The input data is usually heterogeneous (e.g. wiki articles on different knowledge domains) and thus workers often need to access a large knowledge base (e.g. prior expertise, external web resources). The necessity to deal with heterogeneous data and the need to consult external sources usually mean that this type of crowdsourcing systems are high-latency ones.

\subsection{Inheritance from SPs and Cs}

Because of the application of automatic processing in some steps, CSPs can process more data stream elements than crowdsourcing systems (the latency of the human factor is reduced). Last, CSPs inherit from crowdsourcing systems the property of uncertainty (induced by the human element), which necessitates more robust and preventive (``plan B'') algorithms than those needed in SPs.

Reading the above, it becomes obvious that both the automatic and the human element bring along advantages and limitations to CSP systems.
%
In some cases, crowdsourced processing can be to some extent replaced by automatic processing (at a certain loss of quality). For instance, a face-detection algorithm with a lower-than-human recall can be used instead of a crowdsourcing task. In these cases, interesting trade-offs arise in the design.
%
For example, throughput can be increased and latency decreased by directing more items towards automatic processing instead of crowdsourcing, at the cost of a decrease in quality. The opposite may happen if we choose to process most or all the elements through crowdsourcing.


\section{Basic components}


\subsubsection{Definitions} \label{subsec:framework-preliminaries}

Before going into the details, in this section we first provide necessary concepts, definitions, and related terminologies, starting from our interpretation of a stream processing system:


\smallskip


\smallskip
\spara{Definition:} A {\em stream processing} system {\em ingests} data from various data sources, {\em processes} it in a flow according to a set of pre-compiled {\em processing rules} in a {\em timely manner}.
\smallskip

And, we define a crowd stream processing system as:

\smallskip
\spara{Definition:} A {\em crowdsourced stream processing} (CSP) system is a specialized class of {\em stream processing systems} (i.e., as defined above), that continuously ingests high-speed data produced by various types of data sources, processes it in a flow, additionally, allows {\em human-interventions}, and is capable to complete tasks in a {\em timely manner}.
\smallskip

\spara{Miscellaneous concepts and terminologies:}
We refer a {\em stream} as an unordered, unbounded, and possibly, unstructured infinite tokens called {\em data items}. We use term { \em Automatic Processing Element} (APE) where computer programs act as information processor, and, {\em Manual Processing Element} (MPE) where human-participation is involved for the processing of data items.

Thus, revising our definition of CSP system introducing our own terminologies ...

\section*{Framework}

\spara{From the application-level discussion.}

However, in addition to general, primitive types, the meta-model allows to use domain-specific types. We use term {\em composition} when multiple PEs connect and forms a particular topology.
%
A composition contains information of all the connections between multiple PEs, and it is the CSP system's responsibility to manage compositions. A connection between two processing elements can be of type {\em data flow} or {\em control flow}. Moreover, to fulfill different kinds of data communication needs, especially in data stream processing systems, the meta-model allows a data flow connection to behave as {\em buffered}, {\em distributed}, or as {\em broadcast} model.


%%%%%%%%%%%%%%%%

\subsection{Basic components}

\spara{Definition:} A {\em crowdsourced stream processing} (CSP) system is a connected directed graph consisting of a set of {\em Automatic Processing Elements} (APEs) and {\em Manual Processing Elements} (MPEs) connected together fulfilling a set of particular requirements in a {\em timely manner}.
\smallskip

Given these definitions, in this paper we provide necessary concepts, design principals, and formal models for the development of CSP systems through a model-drive approach. We first start with the definition of a general-purpose CSP framework, and second, we provide details on how we leverage the framework's capabilities to specialize it for a specific application domain (i.e., social media streams classification) that we present in the section 5.


\subsection{Model of a CSP system}\label{subsec:framework-pe}

To define the type of a CSP system, and in terms of modeling formalism, that what features the system should be able to support, it is necessary to define its meta-model that will also convey what expressive power it exhibits. As also briefly defined earlier this section, typically, crowdsourced stream processing systems comprised of a set of MPEs and APEs, which connect together to complete a job. They may require data flows or control flows, may require synchronization among various processing elements, and may allow concurrent access to data. The exact features of our generic framework is described by its {\em meta-model}, which is defined as below. 

\smallskip
\spara{Definition:} A {\em CSP system's meta-model} specifies a class of data stream processing systems, and thereby, the expressive power it exhibits, that is, the concepts, and composition capabilities, the underlying platform must know in order to support the development of that class of systems.
\smallskip

And, the processing elements in the system can be of type {\em information source}, {\em information processor}, or {\em information consumer}. 


In the next subsections we elaborate more on the concepts of APE, MPE and communication models. 

%\begin{figure}[t]
%  \centering
%  \includegraphics[width=\columnwidth]{figs/dsp-topology}
%  \todo[ChaTo]{@Imran: I need to get your notation right in order to be able to graphically depict the design patterns.}
%  \caption{General Model of a CSP system}\label{fig:general-overview}
%\end{figure} 

\section*{Application: AIDR}

For the validation of our general-purpose framework, in the next section we present a hybrid data stream processing application that we implement following the design principals and meta-model described in this section.

Before presenting the details of application, we first present, in below, our motivations behind its development:

\spara{Motivation.} Twitter\footnote{http://twitter.com/} is a social media blogging platform, which has more than 500 million and growing users, that receives more than 340 million posts (i.e., tweets) daily \footnote{http://en.wikipedia.org/wiki/Twitter}.

We present AIDR (Artificial Intelligence for Disaster Response), a system designed and implemented following the design principals, specifications, and expressive power manifested by the general-purpose framework presented in the previous section. AIDR is a {\em crowdsourced stream processing system} and is comprised of a set of {\em automatic processing elements} (APE) and {\em manual processing elements} (MPE), that is, it leverages both human as well as computing powers. The core of the AIDR system

\section*{From the old introduction}

Typical cases in which human computation is required include:

\begin{itemize}
 \item As a final step, e.g. to review data that has been extracted automatically. This may be seen as a manual verification step, for instance, in systems for detecting attacks/intrusions in networks, for combating fraud in e-commerce, or for moderating user-generated content.
 \item As an initial step, e.g. to provide training examples to supervised machine learning algorithms.
 \item As an intermediate step, e.g. to provide labels that are then compared and validated automatically, and may generate new elements that require to be labeled.
\end{itemize}

\spara{Desiderata.}
A crowdsourced stream processing system should have, first, all the properties of a good stream processing system. For instance, one of the fundamental requirements of a stream processing system is to efficiently deal with high-speed data and processing workloads \cite{turaga2010design}. Moreover, to make actual processing more efficient, it is highly demanded to avoid unnecessary latencies such as network delays, persistence operations, etc. At peak times when incoming data-rate is high, an intended behavior is to drop or queue incoming data items depending on the situation. Moreover, processing strategies that cause processing elements to wait indefinitely are considered bad \cite{stonebraker20058}. 

In addition, a crowdsourced stream processing system should incorporate all the good properties of a crowdsourcing system. For instance, high-quality of crowdsourcing labels should be a priority, the acquisition of crowdsourcing labels should stay within a reasonable budget, and the crowdsourcing strategy should be re-active \cite{bozzon2013reactive}.




\begin{figure}[t]
\subfigure[Distributed model\label{fig:com-modality-distributed}]{\includegraphics[width=0.95\columnwidth]{figs/distributed-com}}
\subfigure[Broadcasted model\label{fig:com-modality-broadcasted}]{\includegraphics[width=0.95\columnwidth]{figs/broadcasting-com}}
\caption{Communication modalities}
\label{fig:communication-models}
\end{figure} 

%============

%Figure \ref{fig:dsp-collector-mm} shows the meta-model of the \emph{Information Collector} module of the system.
%\begin{figure}[tb]
% \centering
%    \includegraphics[width=\columnwidth]{figs/collector-metamodel}
%  \caption{Information Collector Meta-model}
%  \label{fig:dsp-collector-mm}
%\end{figure} 
%Specifically, we use Twitter as a streaming data source, that is, the system continuously collects and classifies tweets into multiple categories (e.g., donations, damage, causalities, etc.,) related to disasters. Moreover, the application uses crowdsourcing to fulfill the training data requirements. Before we proceed, let's consider the following scenario for better understanding.

%\spara{Scenario} Twitter\footnote{http://twitter.com/} is a social media blogging platform, which has more than 500 million and growing users, that receives more than 340 million posts (i.e., tweets) daily \footnote{http://en.wikipedia.org/wiki/Twitter}. During emergencies and disasters, Twitter plays an important role help disaster responders to quickly launch relief efforts. Let's say, we want to gather information about various kinds donations such as money, food, services, blood, etc. during a flood situation in a country. Considering the scale of information that flows on Twitter, it is challenging for disaster responders to investigate each individual tweet to look for desired information. For this purpose, we leverage different machine learning techniques (i.e., information classification, and extraction) to perform the job automatically. Moreover, we want human-workers to label a part of the incoming data to be used for the training purposes of the automatic techniques. 

%\begin{figure}[tb]
% \centering
%    \includegraphics[width=\columnwidth]{figs/scenario-model}
%  \caption{BPMN workflow modeling a tweets classification system}
%  \label{fig:scenario}
%\end{figure} 

%Figure \ref{fig:scenario} depicts a flow using BPMN notations comprised of various tasks connected together to server the required needs. The first task ``Get documents" is responsible to get tweets from Twitter against a user-defined query (i.e., tracking keywords, following specific Twitter users, etc.,) in real-time. The collected tweets are then consumed by the ``Feature extraction" and ``Prepare sample data" tasks. The ``Feature extraction" task extracts features (e.g., unigrams, bigrams) from the tweets, and the ``Prepare sample data" selects a small set of tweets to be passed to the ``Get human labeled data" task that is responsible for the human annotation of the tweets. A classifier is then trained using the annotated tweets, and gets triggered to start classifying incoming tweets in the ``Classify documents" tasks. From that point the classified tweets are consumed by consumers, and ``Prepare sample data" task again gets triggered to perform the human labelling until classifier reaches desired accuracy level.

%The requirements that we extract from the scenario are 1) we have to deal with a continuous high-speed Twitter stream that generates unstructured data, 2) the process involves both human as well as computers to complete the task, 3) in contrast to typical data stream processing flows, the specified flow additionally requires real-time human interventions to serve the need of training data. From the requirements we can clearly see that the traditional data processing systems are incapable to fulfill the demands of the specified and many other similar scenarios. To this end, in the next section, we present a conceptual framework of our proposed hybrid data processing system.


%--- role of human processing


%\subsubsection{By the number of passes over the streaming data}

%\note[ChaTo]{I think we can leave this out. The base case is one pass. We can speak about multiple passes in the conclusion or as an extension.}

%\spara{Single.} **TO ADD*


%\spara{Multiple.} **TO ADD**


%which is shown in the Figure~\ref{fig:eg-detect-verify} models human as post-processor (e.g., information verifier). This is when crowd verifies technology-generated output for validation and verification purposes. Although, in this case crowds are modeled in a serial way with technology, however, their response do not directly effect technology. The fourth interaction that we present, models human as a parallel processor, but this time technology is directly involved and effected by human responses. Figure 1.d depicts our fourth interaction showing crowds continuous involved providing labeled data on request form technology. 

%Complex architectures require a combination of parallel and serial connections.
%
%Figure~\ref{fig:eg-quality-task} presents humans act as a pre-processor (e.g., human as training data provider) in a serial way along with technology. That is, in order to enable technology to effectively start processing (e.g., supervised document classification), first crowds annotate and provide training data. In this case, as crowds and technology work in serial, so the technology waits for human-inputs to start processing. 

%In this section we look at existing crowdsourcing stream processing systems described in the literature, and try to describe some general classes.


\note[ChaTo]{Next paragraph clashes/repeats discussion already under design patterns.}

A final example is that of \emph{automatic quality assurance} CSPs, where an automatic process can ask for more labels until a certain quality criterion is satisfied (concisely summarized in the ``get another label'' notion by \citet{ipeirotis_2010_get_another_label}). The role of the automatic element here is therefore mainly that of aggregation, while, to facilitate this aggregation, the human element is mainly used in binary classification types of tasks. The composition of these systems is mainly parallel (many human elements working on the same task) and, in contrast with the examples described above, in this type of systems the passes over the same data stream part are multiple. Indicative examples of systems are those proposed by \cite{whang2013question} for entity resolution and by \citet{liu2012cdas} on data analytics (sentiment analysis and image tagging tasks).

...

when few human elements are involved (either in the number of people or in the number of times that people are requested to work on) then the CSP throughput is expected to increase and latency to reduce, as a result of the high involvement of the machine elements.
On the other hand, if no or very few automatic elements exist (e.g. used only to filter-out some very simple cases, but leaving the bulk of the work to humans) then latency may be high, but at the same time the performance in terms of quality is also expected to improve, as a result of the fact that more items are directly assessed by humans. 
Cost, as well as other elements are also expected to accordingly vary.
This trade-off between automatic and human processing elements is therefore expected to significantly affect the performance of the CSP and, as a direct result, its examination and balancing is something that the CSP designer need to carefully examine and balance. 

\spara{Context.} 
During emergencies and disasters (e.g., earthquakes, floods, hurricanes, etc.), social media can play an important role help disaster responders to quickly launch relief efforts to provide various kinds of services like food, shelter, water, money, medicine, etc. to effected people and ultimately can save hundreds of lives. Let's say, we want -- in real-time -- to gather information about various kinds humanitarian services people offer through their twitter posts such as money, food, services, blood, etc. during a flood situation in a country. 
%
Considering the scale of information that flows on Twitter, it is challenging for disaster responders to investigate each individual tweet in real-time to look for desired information. For this purpose, we want to leverage different machine learning techniques (i.e., information classification, and extraction) to perform the job automatically. Moreover, we want human-workers (i.e., volunteers and paid workers) to label a part of the incoming data to be used for the training purposes of machine learning algorithms. Above all, the whole process must be ingesting, processing and feeding consumers with credible information in {\em real-time} or with low latency.

\todo[ChaTo]{Edit the ``AIDR'' part.}

\spara{AIDR.}
The objective of AIDR is to classify messages that people post during disasters into a set of user-defined categories. For this purpose, the system continuously ingests data from Twitter, processes it (i.e., using machine learning classification techniques) and leverages human-participation (i.e., through crowdsourcing) when required, all in real-time. 

For the demonstration purposes, we designed AIDR specifically to operate on social media streams (i.e., Twitter in our case), that allowed us to showcase not all but most of the design patterns described in the section \ref{sec:desing-pattern}. Moreover, processing elements (PEs) in AIDR inherit all three classes specified by the processing elements meta-mode in the section \ref{sec:framework-pe}. That is, we have information sources, processors, and consumers. Information sources responsible of data ingestion from Twitter streaming API, processors perform data processing that is then consumed by the consumers. 

From the requirements specified in above, we can see that first of all we need  APE that continuously ingests data from Twitter streaming API against queries (i.e., set of hashtags, geographical locations, etc.) defined by disaster responders.  we intend AIDR system to be comprised of a set of information collectors, those can continuously ingest twitter posts against queries defined by disaster responders. Moreover, to effectively deal with multiple disasters at same time, we envision multiple information collectors running ingesting twitter data in real-time. This single requirement can have a huge impact on the underlying system design and consequently on overall performance. As typically during disaster tweets arrive at a very high-speed (e.g., during Sandy it was 2600 tweets/sec). So, a bad communication design between system's processing elements could cause serious performance issues. To this end, 

Moreover, the system intends to process collected data items, that is, the classification of data items to their appropriate categories. Typically a machine learning technique involves a number of pre-processing steps before effectively start its actual processing. For instance, this include data cleaning, feature extraction from the cleaned data, data sampling for annotation purposes, annotation of the data, and learning. Individual step in the process has its significance and hence required its proper adjustment in the flow following a appropriate design pattern and communication model presented in the section \ref{sec:framework-com}.


\begin{figure*}[th]
 \centering
    \includegraphics[width=\textwidth]{figs/dsp-detailed-model-v3}
  \caption{AIDR high-level architecture shows APEs and MPEs and their communications}
  \label{fig:csp-model}
\end{figure*}

\section*{Related work}

Real-time crowdsourcing, or {\em flash crowds} as named by \citet{kittur2013future}, are basically crowdsourcing stream processing systems that have low latency.

\citet{kulkami_2012_turkomatic} (Collaboratively crowdsourcing workflows with turkomatic) 

\spara{Real-time/ubiquituous crowdsourcing}

Crowd processing is a type of crowdsourcing involving the processing of a large amount of homogeneous external events/data elements~\cite{geiger_2011_crowdsourcing}.

Named entity annotation \cite{higgins2010mturk, finin2010annotating}, relevance evaluation \cite{alonso2008crowdsourcing}, seeking opinions \cite{mellebeek2010opinion}, and so on, are all examples of crowdsourcing tasks that require human-intervention when even sophisticated computer programs unable to produce good results. 

and \citet{franklin2011crowddb} describes an extension to SQL which involves crowdsourcing operations, and describes how to establish an efficient query plan, while 


\citet{mashhadi_2011_quality} (Quality Control for Real-time Ubiquitous Crowdsourcing) speaks of real-time events and dynamic crowds.

Moreover, to involve crowds for real-time work with tight completion-time requirements, such as \cite{bernstein2010soylent, bigham2010vizwiz}, poses serious challenges \cite{kittur2013future}.  

Real-time crowdsourcing, or {\em flash crowds} as named by \citet{kittur2013future}, are basically crowdsourcing stream processing systems that have low latency.

\citet{kulkami_2012_turkomatic} (Collaboratively crowdsourcing workflows with turkomatic) 

\citet{mashhadi_2011_quality} (Quality Control for Real-time Ubiquitous Crowdsourcing) speaks of real-time events and dynamic crowds.


(Towards Real-time Emergency Response using Crowd Supported Analysis of Social Media) describes a system in which there is an automatic selection of items to be annotated.

(TurKit: Tools for iterative tasks on mechanical turk) seems to be a paper about {\em pure crowdsourcing stream processing}, in which each step is crowdsourced.

\citet{fan2013hybrid} hybrid crowdsourcing system example.

\citet{whang2013question} seems to also be an example.

\citet{liu2012cdas} is another example for data cleaning.

\citet{wang_2013_transitive} (Leveraging Transitive Relations for Crowdsourced Joins) 



NOT USED LITERATURE

\spara{To check:}

\cite{dai_2013_pomdp} POMDP-based control of workflows for crowdsourcing, suggested by Ioanna.

\citet{shahabi_2013_spatial} (Towards a generic framework for trustworthy spatial crowdsourcing)

\citet{kittur_2011_crowdforge} (Crowdforge) Map-Reduce kind of architecture

\citet{bernstein_2011_twoseconds} (Crowds in two seconds: Enabling realtime crowd-powered interfaces)

\citet{kulkami_2012_turkomatic} (turkomatic) ... here the crowd can create a workflow between crowdsourced elements.

Check \url{http://scholar.google.com/scholar?q=crowdsourcing+process+data+control+flow+framework&btnG=&hl=en&as_sdt=0%2C5}

\tocite{Keep it simple: reward and task design in crowdsourcing} speaks about the effect of incentives and task complexity in accuracy (a dual task where workers must do two things yields lower accuracy than a singular task where workers are only asked to do one thing).

{\em Data stream management systems} include STREAM~\cite{arasu2004stream}, Aurora~\cite{carney2002monitoring}, NiagaraCQ~\cite{chen2000niagaracq}, and~TelegraphCQ \cite{chandrasekaran2003telegraphcq} among others. These systems are usually designed for application domains where persisting and querying the data is more important than being able to ingest and process data in real-time.
%, and often oriented to process data in batches as opposted to pure real-time stream processing systems that ingest and process continuous data streams in real-time. Moreover, the overall system performance in terms of throughput, and latency are not considered as crucial performance indicators in such systems. Most of the DSMSs allow writing and executing user-defined queries over data streams through their native query languages that are mostly of declarative nature except Aurora.


\section{Characterization of CSP}


% FOLLOW THE NOMENCLATURE OF "CROWDSOURCED PROCESSING ELEMENT" vs "AUTOMATIC PROCESSING ELEMENT"

%\note[ChaTo]{The next paragraph seems out of place.}
%\note[Yannick]{Right, but only the beginning of the paragraph, which should be put somewhere in the next paragraph describing CSPE functions. In the current paragraph, starting from "three broad classes of APE functions", this seems ok to me, because it describes the different functions that can have APE in the CSP.}
%WHAT


Human intelligence, provided by crowdsourcing workers, is used for tasks that can not be automated.
Among the tasks workers can execute we may find:  \emph{providing input} to other processing elements, \emph{correcting} an element's output, \emph{validating} that an  element performed as expected, and \emph{training} the automated processing elements so that they can learn to perform a task. 
%HOW
This leads to at least three broad classes of APE functions (see Fig.~\ref{fig:systemicCSP}): binary classification, n-ary classification, and open-ended contributions.
%
In \emph{binary classification}, workers are asked to give a ``yes/no'' answer to a given question: ``do these suspicious activities constitute an attack?'' \cite{debar2001aggregation}, ``does this entity correspond to this word in this context?''~\cite{demartini_2012_zencrowd}, ``do these two records correspond to the same person?''~\cite{whang2013question}.
%
In \emph{n-ary classification}, we can include
determining if a word in a sentence represents a person, a place, or an organization~\cite{finin2010annotating},
determining if an emergency-related tweet describes infrastructure damage, casualties, injuries, needs, etc.~\cite{imran2013extracting}, 
%determining which is the concept described by a column on a table on the web~\cite{fan2013hybrid},
determining which emotion corresponds to a tweet~\cite{liu2012cdas}, etc.
%performing relevance assessment ~\cite{alonso2008crowdsourcing},
%determining certain properties of a photo of a galaxy~\cite{kamar_2012_galaxyzoo}, etc.
%
In \emph{open-ended contributions}, workers are asked to perform an open-ended task such as:
``rewrite this sentence in a shorter way''~\cite{bernstein2010soylent},
%``describe how to sub-divide a complex task''~\cite{kulkami_2012_turkomatic},
``fill in the missing fields in this record''~\cite{franklin2011crowddb},
``make a drawing of an articulated figure''~\cite{demartini_2012_zencrowd} \inote{we should remove~\cite{demartini_2012_zencrowd}}, etc. 
This list is not comprehensive as new task types emerge as crowdsourcing systems (and CSPs) mature.

% (e.g. set ordering~\cite{mason_2010_financial}) 
end{comment}

\begin{comment}
\note[Ioanna]{We need to be careful with the following paragraph. We need to say where do these examples belong (from the above categories), or if they constitute a new category. For instance, relevance assessments or ordering of sets can be considered as n-ary classification, highlighting a sentence and tracing the boundaries of an object can be seen as binary (a region belongs or not to a person etc.) Drawing a figure is open-ended. Also, we have too many references for this sub-section perhaps.}

\note[ChaTo]{We have two options:

(a) We state that our list of "how" (binary classification, n-ary classification and open ended) is comprehensive, and hammer the other cases (sorting a list, selecting a sub-string, drawing) into the three classes.

(b) We state that our list of "how" is open-ended, and list different interaction modalities.

Personally I prefer (a), but I leave it to you Ioanna to decide.}

Other forms of interaction are possible: performing relevance assessments on a set of items~\cite{alonso2008crowdsourcing}, ordering a set of items~\cite{mason_2010_financial}, highlighting a part of a sentence~\cite{imran2013extracting}, tracing the boundaries of a person/object on an image~\cite{sorokin_2008_utility}, make a drawing of an articulated figure~\cite{demartini_2012_zencrowd}, etc.


%\todo[ChaTo]{We need a list, well-placed within the literature (i.e. with substantial overlaps with previous works), but focused on crowdsourced {\em stream processing}.}

%\spara{Confirm an automatic label.} ...

%\spara{Provide a training example for an automatic system.} ...
taxonomy.tex
% !TEX root = paper.tex

\section{Characterizing crowdsourced stream processing systems}\label{sec:taxonomy}

In this section we introduce the main characteristics of crowdsourced stream processing systems (CSPs). We start by providing a systemic view on CSPs, giving their elements, functions and properties. Then, we provide tangible examples of CSPs using a series of systems previously described in the literature.

\subsection{The CSP system}\label{sec:CSP-System}

In order to better understand what a CSP system is, we follow a relaxed systemic-modeling approach~\cite{banathy1997taste}, which borrows explanatory elements from systems science and General Systems Theory~\cite{VonBertalanffyGeneralSystemTheory}. According to this theory, {\em a system is a set of interacting elements} that has {\em emerging properties} which are richer than the sum of the properties of its parts. %A system also has attributes and boundaries that differentiate it from other systems. 

A system can be examined from two main perspectives~\cite{Dietz:2008:EOE:1363686.1363824}: (i) a \emph{behavioral} or \emph{teleological} perspective, where the system's behavior and goals are examined, and (ii) a \emph{structural} perspective, where the system's structure, architecture and operations are considered. These perspectives are supported by notions that include environment, objective, function, element, relation and interface~ \cite{Naudet2010176}, as illustrated by the system model of Figure~\ref{fig:systemMModel}, adapted from~\cite{Naudet2010176}. \emph{Environment} is anything outside the system's boundaries. It influences the system as well as the system influences it. \emph{Objective} is the system's finality at a given time, a notion that directly influences the system's structure and functionality. \emph{Function}  is the set of actions the system can execute in order to realize its objective. \emph{Element} is a component of a system, which can itself be a system. Finally, \emph{Interface} is the element through which the system establishes connections with its environment, each system's element having interfaces through which \emph{Relation}s with other elements are established.
%
Environment, objective and function provide the \emph{behavioral perspective} of the system, i.e. they denote the way the system acts and reacts. Element and interface provide the \emph{structural perspective} of the system, i.e. they materialize the internal organization and architecture of the system.

\begin{figure} [h]
\centering
%\vspace*{13pt}
\includegraphics[width=0.4\columnwidth]{figs/systemicModel_Systm.pdf}
%\centerline{\epsfig{file=fig1.eps, width=8.2cm}} %100 percent
%\vspace*{13pt}
\fcaption{\label{fig:systemMModel}Simplified meta model of a System. Diamond arrow represents the composition relation.}
\end{figure} 

A CSP is a combination of two systems: a \emph{Stream Processing system} and a \emph{Crowdsourcing system}. It keeps the objective of the first, while using the other as a tool to better reach this objective.

%\note[Reviewer 1]{Why do you have a section 'system' in \ref{subsec:taxonomy-hierarchical}? It does not seem to provide any benefit to the framework.}

%\spara{System.} 
%First in the taxonomy stands the notion of system: a finite set of elements, inter-connected so that they form a unity that functions for one or more specific objectives inside an environment, from which it can be separated and with which it communicates through interfaces \cite{banathy1997taste}. 
%

\spara{Stream processing system.} 
From a {\em behavioral perspective}, the objective of a stream processing system is to process data streams.
%(sequences of data items that are not available through random disk/memory access but rather arrive as a continuous stream),
%and which typically functions by examining this data stream in one pass (or a limited number of passes, in a model known as semi-streaming computation).
%
Example applications include data mining \cite{sudhakar2012data}, clustering \cite{aggarwal2003framework,zhou2008tracking}, classification \cite{zhang2012framework}, time series analysis \cite{lin2003symbolic,zhu2002statstream} and burst detection \cite{sun2010burst}, among many others.

From a {\em structural perspective}, a stream processing system is a composition of {\em processing elements} that read an input data stream and write an output data stream. 
%
Typically, each processing element performs a fairly simple task and is thus easy to implement, debug and maintain. The data passed between elements are data streams as well.
%
Apart from handling a particular type of data (data streams) and employing single-pass processing, another property of stream processing systems is that---at a structural level---each processing element is assumed to have limited memory/storage, i.e. the amount of data it can store is small in comparison to the total amount of data that passes through it~\cite{muthukrishnan2005data}. 
%
Stream processing systems have important properties which will be evaluated to measure the system performances: \emph{latency} (the time that it takes for a stream data item to be processed), \emph{throughput} (the number of items processed/unit time), \emph{load adaptability} (the response of the system to abrupt changes in the input load), \emph{processing quality} (processing approximation error and probability of error, in case this system functions on the basis of an approximation algorithm).

\spara{Crowdsourcing system.} 
From a {\em behavioral perspective}, the objective of a crowdsourcing system is to perform some tasks by using the intelligence of a large group of persons, called the crowd. Typically, the goal is to apply human intelligence to  tasks that cannot be performed effectively by fully automated means. This is done by involving large numbers of workers who perform small portions of a larger task, improving the efficiency of more traditional ways of work organization by reducing completion time and cost. 

%crowdsourcing systems function by involving large numbers of workers, who perform small portions of a larger %task, which has been requested by a third party (requester)\citemissing. Their objective is to 
%(e.g. distributing the load of recognition of a set of 10,000 images to 1,000 people, instead of appointing the same set to 50 workers, can drastically reduce processing time), but also cost (in certain cases the aggregated cost paid per micro-task to crowd workers is less than the respective amount that would be otherwise paid to hired experts). 

From a {\em structural perspective}, a crowdsourcing system is composed of two subsystems interacting one with the other: an information system and the crowd. While the crowd brings along the power of its numbers and a large diversity of knowledge backgrounds, it still remains a human system that can have unpredictable behavior. Thus the crowd's influence on the crowdsourcing system is usually limited to the expected input of the former to the latter, an input that is moderated or filtered when necessary. When the crowd is given more freedom that can influence the functionality of the whole crowd system, more complex regulation mechanisms are put in place~\cite{naudet2014_smap_submitted}.
%\note[Ioanna]{Is the previous sentence clear enough?}
%\note[ChaTo]{Not entirely}

%\note[ChaTo]{I suggest editing the next paragraph: it should go perhaps from general to specific, ending in ``crowd processing'' which is the type of crowdsourcing that can be used in a CSP.}

At a more detailed level, crowdsourcing systems vary significantly in their structure (for comprehensive surveys see ~\cite{yuen_2011_crowdsourcing,doan2011crowdsourcing}). These variations depend on the application (knowledge or creativity-intensive or more mechanistic), type of input data (homogeneous or heterogeneous) and coordination mode (independent workers, collaboration, competition, mixed). Also, the type of task handled varies greatly from one crowdsourcing system to the other. Among the tasks that workers can execute, we may find:  \emph{providing input}, \emph{correcting}, \emph{validating} a given information, \emph{comparing}, \emph{categorizing}, but also \emph{searching} for information, \emph{synthesizing} knowledge and \emph{providing judgments}, among others. This leads to prototypical classes of crowdsourcing tasks: binary classification, n-ary classification, and data entry contributions. 
%
In \emph{binary classification}, workers are asked to give a ``yes/no'' answer to a given question, such as ``do these suspicious activities constitute an attack?'' \cite{debar2001aggregation}, ``does this entity correspond to this word in this context?''~\cite{demartini_2012_zencrowd}, ``do these two records correspond to the same person?''~\cite{whang2013question}.
%
Examples of \emph{n-ary classification}, include
determining if a word in a sentence represents a person, a place, or an organization~\cite{finin2010annotating},
determining if an emergency-related tweet describes infrastructure damage, casualties, injuries, needs, etc.~\cite{imran2013extracting}, 
%determining which is the concept described by a column on a table on the web~\cite{fan2013hybrid},
determining which emotion corresponds to a tweet~\cite{liu2012cdas}, performing relevance assessments ~\cite{alonso2008crowdsourcing}, determining certain properties of a photo of a galaxy~\cite{kamar_2012_galaxyzoo}, etc.
%
In \emph{data-entry contributions}, workers are asked to perform a data-entry task such as:
``rewrite this sentence in a shorter way''~\cite{bernstein2010soylent},
``fill in the missing fields in this record''~\cite{franklin2011crowddb},
``make a drawing of an articulated figure''~\cite{demartini_2012_zencrowd}, or
provide free-text labels for an image~\cite{von2004labeling}.
%
Binary and n-ary classification tasks are usually more restricted, self-contained and can be more easily split to micro-task level, compared to data-entry ones. 
 
%For example, many knowledge-intensive applications (e.g. Wiki article writing) work with non-decomposable tasks and sequential task handling (users write on one anothers' contributions, gradually ``building'' the article), with or without explicit collaboration. The input data is usually heterogeneous (e.g. Wiki articles on different knowledge domains) and thus workers often need to access a large knowledge base (e.g. prior expertise, external web resources). The necessity to deal with heterogeneous data and the need to consult external sources usually mean that this type of crowdsourcing systems are high-latency ones.
%On the other hand, 
Many real-time crowdsourcing applications (e.g. \cite{franklin2011crowddb, geiger_2011_crowdsourcing}), are designed to have low latency, and to rely on homogeneous input data, highly decomposable and self-contained tasks, parallelizable task handling and centralized work coordination. This kind of crowdsourcing is referred to as {\em crowd processing}~\cite{geiger_2011_crowdsourcing}, and is the one that can be most easily integrated with stream processing systems to create CSPs.

%Because of the need to respond with low latency (within seconds), workers in these crowdsourcing  applications are typically given tasks that are self-contained (workers do not need to access external sources).
%knowledge-intensive (Wikipedia, people suggesting restaurants). users may need to consult many sources of data. (this is not stream processing) + creative (http://99designs.fr/ )
%\note[Ioanna]{For previous sentence: Careful here: in the Introduction we currently say that a problem of crowdsourcing in regards to pure SPs is that crowdsourcing has \emph{high latency}. We need to be consistent and/or clarify. Also see next sentence-the two sentences do not seem to fully agree..}

%collaborative (in http://99designs.fr/  members have to look at one anothers logos, designs etc.)
%real-time  
%building a dictionary 
%\begin{figure}[t]
%\centering 
%\includegraphics[width=\columnwidth]{figs/taxonomy-2.pdf}
%\caption{A taxonomy of crowdsourced stream processing systems. Top: hierarchical taxonomy (Section~\ref{subsec:taxonomy-hierarchical}). Bottom: faceted taxonomy (Section~\ref{subsec:taxonomy-faceted}).}
%\end{figure}

As crowdsourcing is part of a CSP, key challenges of it are inherited by CSPs including dealing with the innate uncertainty of human work (e.g. workers might leave unexpectedly and their skills might vary~\cite{roy2013crowds}), and the fact that crowdsourcing is in general slower and more costly per item than fully automatic processing. Then, the crowdsourcing properties that will be usually of concern in the design of a CSP are the crowdsourcing \emph{cost} (the cost of the work of the people providing the human intelligence) and the \emph{quality} of the crowd input.
%Important evaluation metrics, also passed on, include: quality, cost and their trade-off.


%\begin{figure} [h]
%\centering
%%\vspace*{13pt}
%\includegraphics[width=0.8\columnwidth]{figs/CSP_system_abstract_model.pdf}
%%\centerline{\epsfig{file=fig1.eps, width=8.2cm}} %100 percent
%\vspace*{13pt}
%\todo[ChaTo]{To be replaced by a table containing the types of functions APEs can execute, and the types of function CSPEs can execute.}
%\fcaption{CSP as a system, with its specific elements, relations and functions. Empty triangle, plain triangle and diamond arrow represent respectively the subclass, instantiation and composition relation.}
%\label{fig:systemicCSP}
%\end{figure}

%\note[Ioanna]{I think we should delete the "open-ended" option, of Table 1, according to what we say in section 2.1: The most suitable tasks for crowdsourced processing elements are those that involve \emph{crowd processing} (such as binary and n-ary classification), \emph{while open-ended tasks are harder to integrate in a CSP because they may not be self-contained and are often non-decomposable.}}
%\note[Imran]{OK. Removed.}


\spara{Crowdsourced stream processing system (CSP).}
CSPs lie in the junction between automated stream processing systems and crowd processing systems. They inherit behaviors and structural elements from both, while demonstrating its own emerging properties.
%
What CSPs inherit from stream processing systems is their general objective: to process input streams efficiently. What differentiates them is the \emph{class of problems} that CSPs can handle.
%
From crowdsourcing systems, CSPs inherit the capability of executing data processing tasks that require human intelligence, in contrast to the tasks traditional stream processing systems execute, which can be done by computer algorithms alone. In addition, CSP inherits the uncertainty/variability introduced by human work, and its costs, which necessitates methods and design choices to mitigate it.

From a \emph{structural perspective} a CSP is composed of processing elements (PE), which involve either human or machine elements: crowdsourced PE (CSPE) and automatic PE (APE). These elements can be combined in different ways. We may distinguish two prototypical connection topologies, which generate three possible kind of relations:
\begin{compactitem}
	\item \emph{Parallel.} In parallel connections, both automatic and crowdsourced processing elements function on the same type of task and layer of data stream processing, therefore such tasks have no dependencies. 
	\item \emph{Serial.} In serial connections, tasks have dependencies among them, requiring a certain degree of serialization in their processing. 
	\item \emph{Hybrid.} We remark that in general for solving real-world problems, hybrid topologies are used, involving a combination of parallel and serial connections.
\end{compactitem}

In general, in a CSP the combination of automatic and crowdsourced processing elements is such that it \emph{avoids having crowdsourced processing elements in high-volume critical paths}, employing them only in non-critical paths or in low-volume areas of a critical path. The volume of data to be processed by crowdsourced processing elements is often reduced by automatic processing elements performing filtering or aggregation operations.
  
From a \emph{behavioral perspective} the objective of CSPs is to process data streams. 
%
This is supported by different functions given to the APE or CSPE elements, which we detail in the following.
%¹
Some tasks that workers can execute within a CSP include \emph{providing input} to other processing elements, \emph{correcting} an element's output, \emph{validating} that an  element performed as expected, and \emph{training} the automated processing elements so that they can learn to perform a task.
%
%This leads to two classes of CSPE functions (see Figure~\ref{fig:systemicCSP}), inherited by the crowdsourcing system:  binary classification (``yes/no'' answers) and n-ary classification (categorization answers), as explained above, in the description of the crowdsourcing system from a structural perspective. 
The most suitable tasks for crowdsourced processing elements are those that involve \emph{crowd processing} (such as binary and n-ary classification), while open-ended tasks are harder to integrate in a CSP because they may not be self-contained and are often non-decomposable. 

\begin{table}[t]
\centering
\tcaption{Types of processing elements CSP systems contain, with relations and some indicative functions.}
\label{tab:systemicCSP}
\small\hskip-0.5em\begin{tabular}{p{2.5in}L{1.4in}} \toprule
Type of Processing Elements & Functions  \\\midrule
\multirow{5}{*}{Automatic Processing Element (APE)} & Computation \\
	& Filtering \\
	& Task generation \\
	& Task assignment \\
	& Task aggregation \\ \midrule
\multirow{3}{*}{Crowdsourced Processing Element (CSPE)} & Binary classification \\
	& N-ary classification \\
	& Data entry \\
\bottomrule
\end{tabular}
\end{table}

%\subsubsection{By the role of the automatic processing}\label{subsec:taxo-auto}
Whereas crowdsourced processing elements deal with higher-difficulty tasks, automatic processing elements are employed for efficiency. Indicatively, we can distinguish between five functions for the APE (see Table~\ref{tab:systemicCSP}). First, and perhaps most frequently, automatic elements can be used to perform arbitrary \emph{computations} over the data (transform, aggregate, sort, join, etc.~\cite{mendes_2009_performance}). 
%
%\emph{data manipulation}, i.e. operations over the streaming data, for example in the form of edge adaptation (importing data from external sources to the CSPs) or in the form of computations (sort, rank, join, reason over the data etc. \cite{mendes_2009_performance}).
Secondly, automatic elements can be used for task \emph{filtering}: performing sampling to reduce the number of elements that need to be processed. This may help to reduce the number of crowdsourcing calls by selectively using crowdsourcing only for difficult items (e.g. \cite{kamar_2012_galaxyzoo,demartini_2012_zencrowd}).
%classified into various difficulty levels, which are then forwarded to human or automatic elements accordingly (e.g. decisions to hire or not hire workers to solve specific items in~\cite{kamar_2012_galaxyzoo}, or crowd processing only tasks for which an automatic processing element was uncertain~\cite{demartini_2012_zencrowd}).
%
Third, automatic elements can be used for automatic \emph{task generation}, as in the case of systems that need to convert input streams into questions for humans (e.g. graph searching in~\cite{parameswaran2011human}, crowd-assisted data joins in~\cite{franklin2011crowddb}).
%
Fourth, automatic elements can be used for \emph{task assignment} purposes to ensure each crowdsourcing worker receives a task s/he is most capable of doing, e.g., with the online algorithm described in~\cite{ho_2012_task_assignment}.
%
Finally, automatic elements can be used for \emph{aggregation} of the output of other processing elements, for instance in order to ensure output quality through redundancy, as in the ``get-another-label'' system~\cite{ipeirotis_2010_get_another_label}.

%\note[Yannick]{I added the following paragraph to make the link with section 4. Feel free to enhance it...}
In section~\ref{sec:framework}, we will provide a prototypical structure of a CSP and detail more precisely APE and CSPE and the way they function together.

%\note[ChaTo]{In~\cite{mendes_2009_performance} the following types for automatic processing are listed: Windowing; Filtering (Selection/Projection); 
%Transformation; Sorting/Ranking; Aggregation/Grouping; Correlation/Enrichment (Join); Merging (Union); Pattern Detection.}

%\note[Ioanna]{We need to discuss on how to structure this sub-section. To me, sorting, correlation, merging, pattern detection, all belong to the ``what'' task is done, while filtering, transformation and aggregation belong to the ``how'' it is handled.}

%\note[ChaTo]{My suggestion would be to start with the list in \cite{mendes_2009_performance} (union with perhaps other lists) just to give a reference of the variety of automatic processing elements, and then state that in this section we focus specifically on the role of automatic processing elements {\em with respect to} the manual processing ones.}

%\todo[ChaTo]{We need a list, well-placed within the literature (i.e. with substantial overlaps with previous works), but focused on crowdsourced {\em stream processing}.}
%\spara{Sample or filter from the stream.} ...
%\spara{Generate a task.} ...
%\spara{Quality assurance.} ...
%Aggregate results from different workers.

\subsection{Examples}\label{sec:examples}

We close this section by illustrating three indicative CSPs examples, categorized according to the functions of the automatic processing and crowdsourced processing elements and the kind of relation between them (Table~\ref{tab:taxonomy_examples}).

\begin{comment}
\todo[ChaTo]{The current classes of system here clash with the design patterns of Section~\ref{sec:patterns}.
We also need more examples.}

In order to understand how current systems are designed, we first go through some examples. 
%
%Several of the examples cited here were not designed as hybrid {\em stream} processing systems, but can be trivially extended to that case.

\begin{figure}[t]
\subfigure[Split automatic-manual\label{fig:eg-split}]{\includegraphics[width=.45\columnwidth]{figs/split-autoManual-tasks}}
\subfigure[Detect-verify\label{fig:eg-detect-verify}]{\includegraphics[width=.45\columnwidth]{figs/detect-verify-tasks}}
\subfigure[Active-learning, quality-assurance loop\label{fig:eg-quality-task}]{\includegraphics[width=\columnwidth]{figs/quality-loop-tasks}}
\caption{Simple crowdsourced stream processing architectures.}
\label{fig:eg-all}
\end{figure} 

\end{comment}


\begin{table}[t]
\tcaption{Three indicative examples of CSPs.}
\label{tab:taxonomy_examples}
\small\hskip-0.5em\begin{tabular}{p{1.3in}L{1.4in}L{1.6in}L{0.7in}} \toprule
Example CSPs & Crowdsourced processing & Automatic processing & Dominant composition\\\midrule
\mbox{Network intrusion} \mbox{detection}~\cite{om2012hybrid}
& input; binary classification
& filter
& serial \\%\midrule
\mbox{Automatic online} \mbox{classification}~\cite{whang2013question}
& training; n-ary classification
& task generation
& hybrid \\%\midrule
\mbox{On-demand missing} \mbox{data completion}~\cite{franklin2011crowddb}
& input; comparison
& task generation, aggregation
& hybrid \\
\bottomrule
\end{tabular}
\end{table}

%\note[ChaTo]{Wrt CrowdDB in Table~\ref{tab:taxonomy_examples}: the crowd does text input and comparison.}

\spara{Network intrusion detection.} Automatic processing elements monitor network or system logs, to detect candidate malicious activities and generate alarm reports about possible attacks~\cite{om2012hybrid}. Human input is then needed to manually verify candidate alarms and take further action (perform remedy, re-tune the system) in response. Processing composition in this example is serial, with the automated element performing the filtering part (detect) and the human element performing binary classification (verified attack or not). 

\spara{Automatic online classification.} Crowdsourced processing elements are asked to correct n-ary classification of entities (e.g. mentions of people or places in a text) into semantic clusters, helping at the same time to train the automated element of the CSP into performing more accurate automatic classifications~\cite{whang2013question}. In this case, datasets can be static or dynamic (query-dependent). The processing composition in this system is hybrid (namely, a loop), with the automated element generating entity resolution questions, humans answering them and then these answers being sent back to the automated elements for training and decision purposes. 
% One of the datasets in~\cite{whang2013question} (hotels collection) correspond to records from a dynamic collection, and in which the specific subset of records to be analyzed is query-dependent.
%\note[Ioanna]{Example no.2 (reference ~\cite{whang2013question})  was before an example of ``parallel" instead of ``hybrid", right? If this is example is indeed hybrid, then don't we need a serial example as well? Otherwise we have two hybrid, one serial and no parallel, in Table 3 with the examples.}

%\note[Imran]{''Automan: A platform for integrating human-based and digital computation" could be an example of a parallel system, but its not 100\% true.}

%\note[ChaTo]{I think not having a ``parallel'' system is not really a problem.}

\spara{On-demand missing data completion.} Crowdsourced processing elements are orchestrated to fill in missing data with respect to a query~\cite{franklin2011crowddb}. Among other operations, in this system crowdsourcing workers complete missing data in tuples that need to be selected or compared with other tuples in response to a query. Queries are not known beforehand, and the underlying dataset can change over time.

paper.bbl
\begin{thebibliography}{86}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi

\bibitem[Aggarwal et~al.(2003)Aggarwal, Han, Wang, and
  Yu]{aggarwal2003framework}
C.~C. Aggarwal, J.~Han, J.~Wang, and P.~S. Yu.
\newblock A framework for clustering evolving data streams.
\newblock In \emph{Proc. of VLDB}, pages 81--92, 2003.

\bibitem[Alonso et~al.(2008)Alonso, Rose, and Stewart]{alonso2008crowdsourcing}
O.~Alonso, D.~E. Rose, and B.~Stewart.
\newblock Crowdsourcing for relevance evaluation.
\newblock In \emph{ACM SigIR Forum}, volume~42, pages 9--15. ACM, 2008.

\bibitem[Banathy(1997)]{banathy1997taste}
B.~H. Banathy.
\newblock A taste of systemics.
\newblock \emph{The Primer Project}, 1997.

\bibitem[Bernstein et~al.(2010)Bernstein, Little, Miller, Hartmann, Ackerman,
  Karger, Crowell, and Panovich]{bernstein2010soylent}
M.~S. Bernstein, G.~Little, R.~C. Miller, B.~Hartmann, M.~S. Ackerman, D.~R.
  Karger, D.~Crowell, and K.~Panovich.
\newblock Soylent: a word processor with a crowd inside.
\newblock In \emph{Proc. of UIST}, pages 313--322. ACM, 2010.

\bibitem[Bernstein et~al.(2011)Bernstein, Brandt, Miller, and
  Karger]{bernstein_2011_twoseconds}
M.~S. Bernstein, J.~Brandt, R.~C. Miller, and D.~R. Karger.
\newblock Crowds in two seconds: enabling realtime crowd-powered interfaces.
\newblock In \emph{Proc. of UIST}, pages 33--42. ACM, 2011.

\bibitem[Bertalanffy(1969)]{VonBertalanffyGeneralSystemTheory}
L.~V. Bertalanffy.
\newblock \emph{General System Theory: Foundations, Development, Applications}.
\newblock Geoohursdaorge Braziller, Inc, revised edition, 1969.

\bibitem[Bigham et~al.(2010)Bigham, Jayant, Ji, Little, Miller, Miller, Miller,
  Tatarowicz, White, White, et~al.]{bigham2010vizwiz}
J.~P. Bigham, C.~Jayant, H.~Ji, G.~Little, A.~Miller, R.~C. Miller, R.~Miller,
  A.~Tatarowicz, B.~White, S.~White, et~al.
\newblock Vizwiz: nearly real-time answers to visual questions.
\newblock In \emph{Proc. of UIST}, pages 333--342. ACM, 2010.

\bibitem[Bockermann and Blom(2012)]{bockermann2012processing}
C.~Bockermann and H.~Blom.
\newblock Processing data streams with the rapidminer streams-plugin.
\newblock In \emph{Proc. of the RapidMiner Community Meeting and Conference},
  2012.

\bibitem[Boutsis and Kalogeraki(2013)]{boutsis_2013_crowdsourcing}
I.~Boutsis and V.~Kalogeraki.
\newblock Crowdsourcing under {Real-Time} constraints.
\newblock In \emph{Parallel \&amp; Distributed Processing (IPDPS), 2013 IEEE
  27th International Symposium on}, pages 753--764. IEEE, May 2013.

\bibitem[Bozzon et~al.(2013)Bozzon, Brambilla, Ceri, and
  Mauri]{bozzon2013reactive}
A.~Bozzon, M.~Brambilla, S.~Ceri, and A.~Mauri.
\newblock Reactive crowdsourcing.
\newblock In \emph{Proc. of WWW}, pages 153--164, 2013.

\bibitem[Broda et~al.(2009)Broda, Clark, Miller, and Russo]{broda2009sage}
K.~Broda, K.~Clark, R.~Miller, and A.~Russo.
\newblock Sage: a logical agent-based environment monitoring and control
  system.
\newblock In \emph{Ambient Intelligence}, pages 112--117. Springer, 2009.

\bibitem[Carney et~al.(2002)Carney, {\c{C}}etintemel, Cherniack, Convey, Lee,
  Seidman, Stonebraker, Tatbul, and Zdonik]{carney2002monitoring}
D.~Carney, U.~{\c{C}}etintemel, M.~Cherniack, C.~Convey, S.~Lee, G.~Seidman,
  M.~Stonebraker, N.~Tatbul, and S.~Zdonik.
\newblock Monitoring streams: a new class of data management applications.
\newblock In \emph{Proc. of VLDB}, pages 215--226, 2002.

\bibitem[Chandrasekaran et~al.(2003)Chandrasekaran, Cooper, Deshpande,
  Franklin, Hellerstein, Hong, Krishnamurthy, Madden, Reiss, and
  Shah]{chandrasekaran2003telegraphcq}
S.~Chandrasekaran, O.~Cooper, A.~Deshpande, M.~J. Franklin, J.~M. Hellerstein,
  W.~Hong, S.~Krishnamurthy, S.~R. Madden, F.~Reiss, and M.~A. Shah.
\newblock {TelegraphCQ}: continuous dataflow processing.
\newblock In \emph{Proc. of SIGMOD}, pages 668--668. ACM, 2003.

\bibitem[Dai et~al.(2013)Dai, Lin, Mausam, and Weld]{dai_2013_pomdp}
P.~Dai, C.~H. Lin, Mausam, and D.~S. Weld.
\newblock {POMDP}-based control of workflows for crowdsourcing.
\newblock \emph{Artificial Intelligence}, 202:\penalty0 52--85, Sept. 2013.

\bibitem[Debar and Wespi(2001)]{debar2001aggregation}
H.~Debar and A.~Wespi.
\newblock Aggregation and correlation of intrusion-detection alerts.
\newblock In \emph{Recent Advances in Intrusion Detection}, pages 85--103.
  Springer, 2001.

\bibitem[Demartini et~al.(2012)Demartini, Difallah, and
  Mauroux]{demartini_2012_zencrowd}
G.~Demartini, D.~E. Difallah, and P.~C. Mauroux.
\newblock {ZenCrowd}: leveraging probabilistic reasoning and crowdsourcing
  techniques for large-scale entity linking.
\newblock In \emph{Proc. of WWW}, pages 469--478. ACM, 2012.

\bibitem[Demers et~al.(2006)Demers, Gehrke, Hong, Riedewald, and
  White]{demers2006towards}
A.~Demers, J.~Gehrke, M.~Hong, M.~Riedewald, and W.~White.
\newblock Towards expressive publish/subscribe systems.
\newblock In \emph{Advances in Database Technology-EDBT 2006}, pages 627--644.
  Springer, 2006.

\bibitem[Dietz and Hoogervorst(2008)]{Dietz:2008:EOE:1363686.1363824}
J.~L.~G. Dietz and J.~A.~P. Hoogervorst.
\newblock Enterprise ontology in enterprise engineering.
\newblock In \emph{Proc. of SAC}, pages 572--579. ACM, 2008.

\bibitem[Doan et~al.(2011)Doan, Ramakrishnan, and
  Halevy]{doan2011crowdsourcing}
A.~Doan, R.~Ramakrishnan, and A.~Y. Halevy.
\newblock Crowdsourcing systems on the world-wide web.
\newblock \emph{Communications of the ACM}, 54\penalty0 (4):\penalty0 86--96,
  2011.

\bibitem[Fan et~al.(2013)Fan, Lu, Ooi, Tan, and Zhang]{fan2013hybrid}
J.~Fan, M.~Lu, B.~C. Ooi, W.-C. Tan, and M.~Zhang.
\newblock A hybrid machine-crowdsourcing system for matching web tables.
\newblock Technical report, National University of Singapore, 2013.

\bibitem[Finin et~al.(2010)Finin, Murnane, Karandikar, Keller, Martineau, and
  Dredze]{finin2010annotating}
T.~Finin, W.~Murnane, A.~Karandikar, N.~Keller, J.~Martineau, and M.~Dredze.
\newblock Annotating named entities in twitter data with crowdsourcing.
\newblock In \emph{Proc. of the NAACL HLT 2010 Workshop on Creating Speech and
  Language Data with Amazon's Mechanical Turk}, pages 80--88. ACL, 2010.

\bibitem[Finnerty et~al.(2013)Finnerty, Kucherbaev, Tranquillini, and
  Convertino]{finnertykeep}
A.~Finnerty, P.~Kucherbaev, S.~Tranquillini, and G.~Convertino.
\newblock Keep it simple: Reward and task design in crowdsourcing.
\newblock In \emph{Proc. of Italian CHI}, 2013.

\bibitem[Franklin et~al.(2011)Franklin, Kossmann, Kraska, Ramesh, and
  Xin]{franklin2011crowddb}
M.~J. Franklin, D.~Kossmann, T.~Kraska, S.~Ramesh, and R.~Xin.
\newblock {CrowdDB}: answering queries with crowdsourcing.
\newblock In \emph{Proc. of SIGMOD}, pages 61--72. ACM, 2011.

\bibitem[Fraustino et~al.(2012)Fraustino, Liu, and Jin]{fraustino_2012_start}
J.~D. Fraustino, B.~Liu, and Y.~Jin.
\newblock Social media use during disasters: A review of the knowledge base and
  gaps (final report, start).
\newblock Technical report, Human Factors/Behavioral Sciences Division, Science
  and Technology Directorate, U.S. Department of Homeland Security, College
  Park, MD, USA, 2012.

\bibitem[Gamma et~al.(1994)Gamma, Helm, Johnson, and
  Vlissides]{gamma_1994_design}
E.~Gamma, R.~Helm, R.~Johnson, and J.~Vlissides.
\newblock \emph{Design Patterns: Elements of Reusable {Object-Oriented}
  Software}.
\newblock Addison-Wesley Professional, Nov. 1994.

\bibitem[Gao et~al.(2013)Gao, Liu, Ooi, Wang, and Chen]{gao_2013_online}
J.~Gao, X.~Liu, B.~C. Ooi, H.~Wang, and G.~Chen.
\newblock An online cost sensitive decision-making method in crowdsourcing
  systems.
\newblock In \emph{Proc. of SIGMOD}, pages 217--228. ACM, 2013.

\bibitem[Gedik et~al.(2008)Gedik, Andrade, Wu, Yu, and Doo]{gedik2008spade}
B.~Gedik, H.~Andrade, K.-L. Wu, P.~S. Yu, and M.~Doo.
\newblock {SPADE}: the system {S} declarative stream processing engine.
\newblock In \emph{Proc. of SIGMOD}, pages 1123--1134. ACM, 2008.

\bibitem[Geerts(2009)]{geerts_2009_discovering}
S.~A.~M. Geerts.
\newblock Discovering crowdsourcing theory, classification and directions for
  use.
\newblock Master's thesis, Eindhoven University of Technology, 2009.

\bibitem[Geiger et~al.(2011)Geiger, Rosemann, and
  Fielt]{geiger_2011_crowdsourcing}
D.~Geiger, M.~Rosemann, and E.~Fielt.
\newblock Crowdsourcing information systems - a systems theory perspective.
\newblock In \emph{22nd Australasian Conf. on Information Systems}, Nov. 2011.

\bibitem[Goel et~al.(2014)Goel, Nikzad, and
  Singla]{Goel:2014:ATW:2567948.2577311}
G.~Goel, A.~Nikzad, and A.~Singla.
\newblock Allocating tasks to workers with matching constraints: Truthful
  mechanisms for crowdsourcing markets.
\newblock In \emph{Proceedings of the Companion Publication of the 23rd
  International Conference on World Wide Web Companion}, WWW Companion '14,
  pages 279--280, Republic and Canton of Geneva, Switzerland, 2014.
  International World Wide Web Conferences Steering Committee.
\newblock ISBN 978-1-4503-2745-9.

\bibitem[Heer and Bostock(2010)]{heer_2010_graphical}
J.~Heer and M.~Bostock.
\newblock Crowdsourcing graphical perception: using mechanical turk to assess
  visualization design.
\newblock In \emph{Proc. of SIGCHI}, pages 203--212. ACM, 2010.

\bibitem[Ho and Vaughan(2012)]{ho_2012_task_assignment}
C.-J. Ho and J.~W. Vaughan.
\newblock Online task assignment in crowdsourcing markets.
\newblock In \emph{AAAI}, 2012.

\bibitem[Hodson(2013)]{hodson_2013_juries}
H.~Hodson.
\newblock Online juries help curb bad gamer behaviour.
\newblock \emph{New Scientist}, \penalty0 (2912), Apr. 2013.

\bibitem[Horton and Chilton(2010)]{horton_2010_economics}
J.~J. Horton and L.~B. Chilton.
\newblock The labor economics of paid crowdsourcing.
\newblock In \emph{Proc. of ACM Electronic Commerce}, pages 209--218. ACM,
  2010.

\bibitem[Hughes and Palen(2009)]{hughes2009twitter}
A.~L. Hughes and L.~Palen.
\newblock Twitter adoption and use in mass convergence and emergency events.
\newblock \emph{Int. Journal of Emergency Management}, 6\penalty0 (3):\penalty0
  248--260, 2009.

\bibitem[Hughes et~al.(2014)Hughes, Peterson, and Palen]{hughes_2014_smem}
A.~L. Hughes, S.~Peterson, and L.~Palen.
\newblock Social media in emergency management.
\newblock In J.~E. Trainor and T.~Subbio, editors, \emph{Issues in Disaster
  Science and Management: A Critical Dialogue Between Scientists and Emergency
  Managers}. {FEMA} in Higher Education Program, 2014.

\bibitem[Imran et~al.(2013{\natexlab{a}})Imran, Elbassuoni, Castillo, Diaz, and
  Meier]{imran_2013_practical}
M.~Imran, S.~Elbassuoni, C.~Castillo, F.~Diaz, and P.~Meier.
\newblock Practical extraction of disaster-relevant information from social
  media.
\newblock In \emph{Proc. of Workshop on Social Media Data for Disaster
  Management}, WWW '13 Companion, pages 1021--1024. ACM/IW3C2,
  2013{\natexlab{a}}.

\bibitem[Imran et~al.(2013{\natexlab{b}})Imran, Elbassuoni, Castillo, Diaz, and
  Meier]{imran2013extracting}
M.~Imran, S.~M. Elbassuoni, C.~Castillo, F.~Diaz, and P.~Meier.
\newblock Extracting information nuggets from disaster-related messages in
  social media.
\newblock In \emph{Proc. of ISCRAM}, Baden-Baden, Germany, 2013{\natexlab{b}}.

\bibitem[Imran et~al.(2014{\natexlab{a}})Imran, Castillo, Lucas, Meier, and
  Vieweg]{imran2014aidr}
M.~Imran, C.~Castillo, J.~Lucas, P.~Meier, and S.~Vieweg.
\newblock Aidr: Artificial intelligence for disaster response.
\newblock In \emph{Proceedings of the companion publication of the 23rd
  international conference on World wide web companion}, pages 159--162.
  International World Wide Web Conferences Steering Committee,
  2014{\natexlab{a}}.

\bibitem[Imran et~al.(2014{\natexlab{b}})Imran, Castillo, Lucas, Patrick, and
  Rogstadius]{imran2014coordinating}
M.~Imran, C.~Castillo, J.~Lucas, M.~Patrick, and J.~Rogstadius.
\newblock Coordinating human and machine intelligence to classify microblog
  communications in crises.
\newblock \emph{Proc. of ISCRAM}, 2014{\natexlab{b}}.

\bibitem[Ipeirotis et~al.(2010)Ipeirotis, Provost, and
  Wang]{ipeirotis_2010_get_another_label}
P.~G. Ipeirotis, F.~Provost, and J.~Wang.
\newblock Quality management on amazon mechanical turk.
\newblock In \emph{Proc. of Workshop on Human Computation}, pages 64--67. ACM,
  2010.

\bibitem[Kamar et~al.(2012)Kamar, Hacker, and Horvitz]{kamar_2012_galaxyzoo}
E.~Kamar, S.~Hacker, and E.~Horvitz.
\newblock Combining human and machine intelligence in large-scale
  crowdsourcing.
\newblock In \emph{Proc. of AAMAS}, pages 467--474. International Foundation
  for Autonomous Agents and Multiagent Systems, 2012.

\bibitem[Kazai(2010)]{kazai_2010_influence}
G.~Kazai.
\newblock An exploration of the influence that task parameters have on the
  performance of the crowds.
\newblock In \emph{CrowdConf}, Oct. 2010.

\bibitem[Kazai et~al.(2013)Kazai, Kamps, and Milic-Frayling]{kazai:an}
G.~Kazai, J.~Kamps, and N.~Milic-Frayling.
\newblock An analysis of human factors and label accuracy in crowdsourcing
  relevance judgments.
\newblock \emph{Information Retrieval}, pages 138--178, 2013.

\bibitem[Kittur et~al.(2013)Kittur, Nickerson, Bernstein, Gerber, Shaw,
  Zimmerman, Lease, and Horton]{kittur2013future}
A.~Kittur, J.~V. Nickerson, M.~Bernstein, E.~Gerber, A.~Shaw, J.~Zimmerman,
  M.~Lease, and J.~Horton.
\newblock The future of crowd work.
\newblock In \emph{Proc. of CSCW}, pages 1301--1318. ACM, 2013.

\bibitem[Kulkarni et~al.(2012)Kulkarni, Can, and
  Hartmann]{kulkami_2012_turkomatic}
A.~Kulkarni, M.~Can, and B.~Hartmann.
\newblock Collaboratively crowdsourcing workflows with turkomatic.
\newblock In \emph{Proc. of CSCW}, pages 1003--1012. ACM, 2012.

\bibitem[Lin et~al.(2003)Lin, Keogh, Lonardi, and Chiu]{lin2003symbolic}
J.~Lin, E.~Keogh, S.~Lonardi, and B.~Chiu.
\newblock A symbolic representation of time series, with implications for
  streaming algorithms.
\newblock In \emph{Proc. of SIGMOD}, pages 2--11. ACM, 2003.

\bibitem[Little et~al.(2009)Little, Chilton, Goldman, and
  Miller]{little_2009_turkit}
G.~Little, L.~B. Chilton, M.~Goldman, and R.~C. Miller.
\newblock {TurKit}: tools for iterative tasks on mechanical turk.
\newblock In \emph{Proc. of the ACM SIGKDD Workshop on Human Computation},
  HCOMP '09, pages 29--30. ACM, 2009.

\bibitem[Liu et~al.(2012)Liu, Lu, Ooi, Shen, Wu, and Zhang]{liu2012cdas}
X.~Liu, M.~Lu, B.~C. Ooi, Y.~Shen, S.~Wu, and M.~Zhang.
\newblock {CDAS}: a crowdsourcing data analytics system.
\newblock \emph{Proc. of VLDB}, 5\penalty0 (10):\penalty0 1040--1051, 2012.

\bibitem[Lykourentzou et~al.(2009)Lykourentzou, Vergados, and
  Loumos]{lykourentzou_2009_collective}
I.~Lykourentzou, D.~J. Vergados, and V.~Loumos.
\newblock Collective intelligence system engineering.
\newblock In \emph{Proc. of MEDES}. ACM, 2009.

\bibitem[Lykourentzou et~al.(2013)Lykourentzou, Vergados, Papadaki, and
  Naudet]{lykourentzou_2013_guided}
I.~Lykourentzou, D.~Vergados, K.~Papadaki, and Y.~Naudet.
\newblock Guided crowdsourcing for collective work coordination in corporate
  environments.
\newblock In \emph{Proc. of Computational Collective Intelligence}, volume
  8083, pages 90--99. Springer Berlin Heidelberg, 2013.

\bibitem[Marz and {contributors}(2013)]{marz_2013_storm}
N.~Marz and {contributors}.
\newblock Storm project.
\newblock \url{http://storm-project.net/}, 2013.

\bibitem[Mashhadi and Capra(2011)]{mashhadi_2011_quality}
A.~J. Mashhadi and L.~Capra.
\newblock Quality control for real-time ubiquitous crowdsourcing.
\newblock In \emph{Proc. of workshop on ubiquitous crowdsourcing}, 2011.

\bibitem[Mason and Watts(2010)]{mason_2010_financial}
W.~Mason and D.~J. Watts.
\newblock Financial incentives and the "performance of crowds".
\newblock \emph{SIGKDD Explor. Newsl.}, 11:\penalty0 100--108, May 2010.

\bibitem[Mcgowran(2012)]{myhuemcgowran2012}
M.~Mcgowran.
\newblock Facebook outsources dirty-content clean-up to offshore moderators,
  March 2012.

\bibitem[Mendes et~al.(2009)Mendes, Bizarro, and
  Marques]{mendes_2009_performance}
M.~Mendes, P.~Bizarro, and P.~Marques.
\newblock A performance study of event processing systems.
\newblock In R.~Nambiar and M.~Poess, editors, \emph{Performance Evaluation and
  Benchmarking}, volume 5895, pages 221--236. Springer Berlin Heidelberg, 2009.

\bibitem[Muthukrishnan(2005)]{muthukrishnan2005data}
S.~Muthukrishnan.
\newblock \emph{Data streams: Algorithms and applications}.
\newblock Now Publishers Inc, 2005.

\bibitem[Naudet and Lykourentzou(2014)]{naudet2014_smap_submitted}
Y.~Naudet and I.~Lykourentzou.
\newblock Personalisation in crowd systems.
\newblock In \emph{(submitted to) the 9th Int. Workshop on Semantic and Social
  Media Adaptation and Personalization (SMAP2014)}, 2014.

\bibitem[Naudet et~al.(2010)Naudet, Latour, Guedria, and Chen]{Naudet2010176}
Y.~Naudet, T.~Latour, W.~Guedria, and D.~Chen.
\newblock Towards a systemic formalisation of interoperability.
\newblock \emph{Computers in Industry}, 61\penalty0 (2):\penalty0 176 -- 185,
  2010.

\bibitem[Neumeyer et~al.(2010)Neumeyer, Robbins, Nair, and
  Kesari]{neumeyer2010s4}
L.~Neumeyer, B.~Robbins, A.~Nair, and A.~Kesari.
\newblock S4: Distributed stream computing platform.
\newblock In \emph{Proc. of ICWM Workshops}, pages 170--177. IEEE, 2010.

\bibitem[Noronha et~al.(2011)Noronha, Hysen, Zhang, and
  Gajos]{noronha_2011_platemate}
J.~Noronha, E.~Hysen, H.~Zhang, and K.~Z. Gajos.
\newblock Platemate: crowdsourcing nutritional analysis from food photographs.
\newblock In \emph{Proc. of UIST}, pages 1--12. ACM, 2011.

\bibitem[Olteanu et~al.(2014)Olteanu, Castillo, Diaz, and
  Vieweg]{olteanu2014crisislex}
A.~Olteanu, C.~Castillo, F.~Diaz, and S.~Vieweg.
\newblock {CrisisLex}: A lexicon for collecting and filtering microblogged
  communications in crises.
\newblock In \emph{Proc. of {ICWSM}}, 2014.

\bibitem[Om and Kundu(2012)]{om2012hybrid}
H.~Om and A.~Kundu.
\newblock A hybrid system for reducing the false alarm rate of anomaly
  intrusion detection system.
\newblock In \emph{Proc. of RAIT}, pages 131--136. IEEE, 2012.

\bibitem[Parameswaran et~al.(2011)Parameswaran, Sarma, Garcia-Molina,
  Polyzotis, and Widom]{parameswaran2011human}
A.~Parameswaran, A.~D. Sarma, H.~Garcia-Molina, N.~Polyzotis, and J.~Widom.
\newblock Human-assisted graph search: it's okay to ask questions.
\newblock \emph{Proc. of VLDB}, 4\penalty0 (5):\penalty0 267--278, 2011.

\bibitem[Quinn and Bederson(2011)]{quinn_2011_survey}
A.~J. Quinn and B.~B. Bederson.
\newblock Human computation: a survey and taxonomy of a growing field.
\newblock In \emph{Proc. of SIGCHI}, pages 1403--1412. ACM, 2011.

\bibitem[Rogstadius et~al.(2011)Rogstadius, Kostakos, Laredo, and
  Vukovic]{rogstadius_2011_realtime}
J.~Rogstadius, V.~Kostakos, J.~Laredo, and M.~Vukovic.
\newblock Towards real-time emergency response using {CrowdSupported} analysis
  of social media.
\newblock In \emph{CHI Workshop on Crowdsourcing and Human Computation:
  Systems, Studies and Platforms}, 2011.

\bibitem[Roy et~al.(2013)Roy, Lykourentzou, Thirumuruganathan, Amer-Yahia, and
  Das]{roy2013crowds}
S.~B. Roy, I.~Lykourentzou, S.~Thirumuruganathan, S.~Amer-Yahia, and G.~Das.
\newblock Crowds, not drones: Modeling human factors in interactive
  crowdsourcing.
\newblock \emph{DBCrowd 2013}, page~39, 2013.

\bibitem[Roy~Chowdhury et~al.(2013)Roy~Chowdhury, Imran, Asghar, Amer-Yahia,
  and Castillo]{roy2013tweet4act}
S.~Roy~Chowdhury, M.~Imran, M.~R. Asghar, S.~Amer-Yahia, and C.~Castillo.
\newblock Tweet4act: Using incident-specific profiles for classifying
  crisis-related messages.
\newblock In \emph{10th International ISCRAM Conference}, 2013.

\bibitem[Saxton et~al.(2013)Saxton, Oh, and Kishore]{saxton_2013_rules}
G.~D. Saxton, O.~Oh, and R.~Kishore.
\newblock Rules of crowdsourcing: Models, issues, and systems of control.
\newblock \emph{Information Systems Management}, 30\penalty0 (1):\penalty0
  2--20, Jan. 2013.

\bibitem[Schenk and Guittard(2011)]{schenk_2011_practices}
E.~Schenk and C.~Guittard.
\newblock Towards a characterization of crowdsourcing practices.
\newblock \emph{Journal of Innovation Economics}, 2011.

\bibitem[Schultz-M{\o}ller et~al.(2009)Schultz-M{\o}ller, Migliavacca, and
  Pietzuch]{schultz2009distributed}
N.~P. Schultz-M{\o}ller, M.~Migliavacca, and P.~Pietzuch.
\newblock Distributed complex event processing with query rewriting.
\newblock In \emph{Proc. of the Third ACM International Conf. on Distributed
  Event-Based Systems}, page~4. ACM, 2009.

\bibitem[Sorokin and Forsyth(2008)]{sorokin_2008_utility}
A.~Sorokin and D.~Forsyth.
\newblock Utility data annotation with amazon mechanical turk.
\newblock In \emph{Proc. of CVPR Workshops}, pages 1--8. IEEE, June 2008.

\bibitem[Stonebraker et~al.(2005)Stonebraker, {\c{C}}etintemel, and
  Zdonik]{stonebraker20058}
M.~Stonebraker, U.~{\c{C}}etintemel, and S.~Zdonik.
\newblock The 8 requirements of real-time stream processing.
\newblock \emph{ACM SIGMOD Record}, 34\penalty0 (4):\penalty0 42--47, 2005.

\bibitem[sudhakar Lahane(2012)]{sudhakar2012data}
P.~sudhakar Lahane.
\newblock Data stream mining.
\newblock \emph{International Journal of Advances in Computing and Information
  Researches}, 1\penalty0 (1):\penalty0 6--10, 2012.

\bibitem[Sun et~al.(2010)Sun, Zeng, and Chen]{sun2010burst}
A.~Sun, D.~D. Zeng, and H.~Chen.
\newblock Burst detection from multiple data streams: a network-based approach.
\newblock \emph{IEEE Transactions on Systems, Man, and Cybernetics, Part C:
  Applications and Reviews}, 40\penalty0 (3):\penalty0 258--267, 2010.

\bibitem[Tatbul et~al.(2003)Tatbul, {\c{C}}etintemel, Zdonik, Cherniack, and
  Stonebraker]{tatbul2003load}
N.~Tatbul, U.~{\c{C}}etintemel, S.~Zdonik, M.~Cherniack, and M.~Stonebraker.
\newblock Load shedding in a data stream manager.
\newblock In \emph{Proc. of VLDB}, pages 309--320, 2003.

\bibitem[Turaga et~al.(2010)Turaga, Andrade, Gedik, Venkatramani, Verscheure,
  Harris, Cox, Szewczyk, and Jones]{turaga2010design}
D.~Turaga, H.~Andrade, B.~Gedik, C.~Venkatramani, O.~Verscheure, J.~D. Harris,
  J.~Cox, W.~Szewczyk, and P.~Jones.
\newblock Design principles for developing stream processing applications.
\newblock \emph{Software: Practice and Experience}, 40\penalty0 (12):\penalty0
  1073--1104, 2010.

\bibitem[Von~Ahn and Dabbish(2004)]{von2004labeling}
L.~Von~Ahn and L.~Dabbish.
\newblock Labeling images with a computer game.
\newblock In \emph{Proceedings of the SIGCHI conference on Human factors in
  computing systems}, pages 319--326. ACM, 2004.

\bibitem[Vukovic(2009)]{yukovic_2009_enterprises}
M.~Vukovic.
\newblock Crowdsourcing for enterprises.
\newblock In \emph{Services - I, 2009 World Conf. on}, volume~0, pages
  686--692. IEEE, July 2009.

\bibitem[Wang et~al.(2013)Wang, Li, Kraska, Franklin, and
  Feng]{wang_2013_transitive}
J.~Wang, G.~Li, T.~Kraska, M.~J. Franklin, and J.~Feng.
\newblock Leveraging transitive relations for crowdsourced joins.
\newblock In \emph{Proc. of SIGMOD}, pages 229--240. ACM, 2013.

\bibitem[Whang et~al.(2013)Whang, Lofgren, and
  Garcia-Molina]{whang2013question}
S.~E. Whang, P.~Lofgren, and H.~Garcia-Molina.
\newblock Question selection for crowd entity resolution.
\newblock In \emph{Proc. of VLDB}, 2013.

\bibitem[Yang et~al.(2013)Yang, Cheung, Mo, Cheng, and
  Kao]{Yang:2013:IT:2510649.2511161}
X.~S. Yang, D.~W. Cheung, L.~Mo, R.~Cheng, and B.~Kao.
\newblock On incentive-based tagging.
\newblock In \emph{Proc. of ICDE}, pages 685--696. IEEE Computer Society, 2013.

\bibitem[Yuen et~al.(2011)Yuen, King, and Leung]{yuen_2011_crowdsourcing}
M.-C. Yuen, I.~King, and K.-S. Leung.
\newblock A survey of crowdsourcing systems.
\newblock In \emph{Proc. of the IEEE Third International Conf. on Social
  Computing (SocialCom)}, pages 766--773. IEEE, Oct. 2011.

\bibitem[Zhang et~al.(2012)Zhang, Gao, Liu, Shi, and Guo]{zhang2012framework}
P.~Zhang, B.~J. Gao, P.~Liu, Y.~Shi, and L.~Guo.
\newblock A framework for application-driven classification of data streams.
\newblock \emph{Neurocomputing}, 92:\penalty0 170--182, 2012.

\bibitem[Zhou et~al.(2008)Zhou, Cao, Qian, and Jin]{zhou2008tracking}
A.~Zhou, F.~Cao, W.~Qian, and C.~Jin.
\newblock Tracking clusters in evolving data streams over sliding windows.
\newblock \emph{Knowledge and Information Systems}, 15\penalty0 (2):\penalty0
  181--214, 2008.

\bibitem[Zhu and Shasha(2002)]{zhu2002statstream}
Y.~Zhu and D.~Shasha.
\newblock Statstream: Statistical monitoring of thousands of data streams in
  real time.
\newblock In \emph{Proc. of VLDB}, pages 358--369, 2002.

\end{thebibliography}
