The spread of digital signage and its instantaneous adaptability of content challenges out-of-home advertising to conduct performance evaluations in an online fashion. This implies a tremendous increase in the granularity of evaluations as well as a complete new way of data collection, storage and analysis. In this paper we propose a distributed system for the large-scale online monitoring of poster performance indicators based on the evaluation of mobility data collected by smartphones. In order to enable scalability in the order of millions of users and locations, we use a local data processing paradigm and apply exponential histograms for an e cient storage of visit statistics over sliding windows. In addition to an immediate event centralization we also explore a hierarchical architecture based on a merging technique for exponential histograms. We provide an evaluation on the basis of a real-world data set containing more than 300 million GPS points corresponding to the movement activity of nearly 3,000 persons. The experiments show the accuracy and e ciency of our system.
Advertising media are under the obligation to provide
reliable performance indicators for the pricing of advertising
campaigns. For the German out-of-home (OOH)
advertising industry, generating yearly net sales of about 760 million
Euro [
ne-grained temporal di erentiation will be required in future. While current performance indicators inform about the poster contacts of seven or ten average days (the two standard durations of poster campaigns in Germany), digital out-of-home (DOOH) advertising spots have a duration of only a few seconds. Assuming an evaluation period of 10 seconds, the granularity of the performance indicators (and consequently of the required input data) increases by four orders of magnitude. DOOH therefore has to face the challenge of collecting and analyzing big data. In addition, digital content has the advantage that it can be instantly adapted to a changing audience. This adaptation, however, requires online performance information, which forms the second challenge of DOOH performance evaluation.
In this paper we propose a distributed system for the large-scale online monitoring of poster performance indicators based on the evaluation of mobility data collected by smartphones. We hereby consider two use cases which the system shall cover. First, we want to be able to perform online queries which obtain performance measures for the recent past in a sliding window style. Second, we want to analyze historic data for various time intervals. The rst type of query allows the online monitoring of poster performance and thus the targeted placement of advertisement spots. The second type of query can be used for billing purposes or to analyze previously collected data sets (e.g. to nd interesting visit patterns that can then be monitored in the online system). Although our use cases di er with respect to their system requirements (distributed online processing vs. analysis of massive amounts of centralized data), we want to keep the maintenance e ort of the system as low as possible. Our goal is therefore to set up a scalable system architecture that allows an e cient re-use of code from the online scenario for historic data analysis.
The key component of our approach to handle massive
streams of data is to use exponential histograms for data
compression. This data structure has the advantage that
it o ers sliding window query capabilities with a
guaranteed maximum relative error. In addition, exponential
histograms can be applied in a distributed setting [
Our online system relies on an Android implementation
that we have used in previous work [
We analyze the performance of our system using a realworld GPS data set containing trajectories of 2,967 persons containing more than 300 million GPS points over a period of one week. We extract visit events from this data set using 400,988 points of interest (POI) in Germany from OpenStreetMap (OSM). Our experiments show that the usage of exponential histograms results in an average error of less than 1/10 of the maximum acceptable error while reducing the storage space to an amount as small as 9.7% of the baseline storage space.
The remainder of our paper is organized as follows. Section 2 discusses related work. Section 3 shows our system architecture and Section 4 provides the experiments. We conclude our paper in Section 5.
Exponential histograms [
To reduce the space requirements, exponential histograms maintain buckets of exponentially increasing sizes. Bucket boundaries are chosen such that the ratio of the size of each bucket b with the sum of the sizes of all buckets more recent than b is upper bounded. In particular, the following invariant is maintained for all buckets j: Cj =(2(1 + Pij=11 Ci)) " where " denotes the maximum acceptable relative error and Cj denotes the size of bucket j (number of true bits arrived in the bucket range), with bucket 1 being the most recent bucket. Queries are answered by summing the sizes of all buckets that fully overlap the query range, and half of the size of the oldest bucket, if it partially overlaps the query. The estimation error is solely contained in the oldest bucket, and is therefore bounded by this invariant, resulting in a maximum relative error of ".
Recently, Papapetrou et al. [
In previous work we have provided a set of visit quantities
that can be used to de ne performance measures in OOH
advertisement [
The basic idea of the approach is to decentralize the data
collection and evaluation process of movement data. Instead
of constantly submitting location information of a user to
some central server, the evaluation of visits (or visit
patterns) is performed locally on a mobile device (e.g.
smartphone). The device submits only aggregated and
anonymized statistics to a central coordinator. In addition, web
anonymization techniques such as onion routing [
Our architecture consists of two or alternatively three
layers (see Figure 1). The lowest layer holds the user nodes,
which collect the users' GPS data and extract visit events.
The visit events are forwarded either directly to the central
coordinator ( at setting) or to a layer of intermediate nodes
(hierarchical setting). In the at setting, the coordinator
aggregates the visit information of each POI in an
exponential histogram. I.e., for each POI an exponential histogram
is maintained that records the visit events for this POI. As
the exponential histogram stores a time aggregate with the
event, queries over time windows can be answered. In the
hierarchical setting, the exponential histograms reside already
at the intermediate nodes. In regular time intervals the
intermediate nodes submit the exponential histograms to the
coordinator, which merges them and answers user queries.
The exponential histograms cannot be applied at the user
level because the number of visit events per user is too small
to make the data structure e cient. The layer of
intermediate nodes was introduced for horizontal scalability and to
avoid an overload of the coordinator. However, it also serves
a privacy purpose given that the intermediate nodes do not
collude (see [
As motivated by our use case, our system shall be able
to perform analyses online as well as on historic data. The
above architecture describes the online use case. For
historic data analysis we have to substitute the layer of local
nodes. This substitution should still allow to process data in
parallel in order to scale to large amounts of data. In
addition, a streaming environment would be preferable in order
to re-use existing code. Both aspects can be met by using
a distributed streaming processing system as, for example,
Storm2 or S4 [
For our experiments we use a subset of a large-scale GPS
survey [
After clean-up the data set contains 304 million GPS points.
In addition, we extracted 400,988 points of interest (POI)
from OpenStreetMap4 (OSM) [
POI type shop restaurant leisure education parking public transport stop total
The extraction of visit events is performed by the local
nodes (see Section 3). A visit results from the spatial
intersection of a trajectory and a geographic location and has to
last a given minimum period of time. For a formal de
nition of a visit see [
In total we extracted 23,508 visit events to 11,809 di erent POI for all test persons. This number has been considerably below our expectations. Most likely it results from two reasons. First, the number of OSM POI are incomplete. From the online source http://www.haltestellen-suche.de we know to expect at least 217,000 stations of public transport in Germany, and also the number of shops in Germany is considerably above the extracted number of POI. Second, GPS signals are typically blocked inside of buildings. As we applied a light-weight event extraction algorithm (that can run on a mobile device), we may have lost a number of visit events.
Table 2 shows an overview of the number of visit events per POI. Most often, only a single visit occurred. This number is quite reasonable given our low number of visits and the independent movement behavior of the test persons.
In order to perform experiments also on a large-scale data set resembling more closely the real-world situation, we replicated the original visit data by a factor of 1,000. We set the time of each such visit by adding Gaussian noise to the current time with = 0 and = 10,000 seconds. 4.2
In our experiments we conducted point queries in a sliding window fashion. I.e., we queried the number of events per POI in the past t seconds. The selected query windows were of length 30, 600, 1800, 3600 or 86400 seconds. We performed those queries every 10 minutes (in the hierarchical setting this coincides with the time interval of the force action). For our observation period of one week this resulted in nt = 1,008 queries per query window for each of the np = 11,809 visited POI. In accordance with our maximum query interval, we set the sliding window parameter of the exponential histogram to 86,400 seconds in all experiments. Further, we varied the maximum acceptable relative error " to take the values 0.01, 0.02, 0.04, 0.08 and 0.16. In the hierarchical setting we used 10 intermediate nodes which submitted their data structures every 600 seconds to the coordinator.
We measured the error for each experiment using the mean absolute percentage error (MAPE), which is de ned as follows:
M AP E =
Pnp Pnt xij xbij i=1 j xij np nt where xij denotes the true number of visit events at POI i in query window j and xbij denotes the number of events returned from the exponential histogram. In the case of xij = 0 we added a relative error of zero if our estimate was correct (xbij = 0) and a relative error of 1 if xbij 6= 0. This latter case, however, did not occur. We performed all experiments for the at and hierarchical setting as well as for the original and multiplied data set. 4.3
Figure 3 shows the results for the at and hierarchical setting of the multiplied data set. The respective numbers are provided in Tables 3 and 4. Note that we display only the results for the multiplied data set because due to the few visit events in the original data set the error was nearly always zero there.
In general, the MAPE is very low, lying with one exception below 1%. For both the at and hierarchical setting two trends can be observed. First, the MAPE decreases with smaller ". Second, the MAPE decreases with decreasing size of the query window. The rst e ect is nearly linear for all query windows and can be expected from the characteristics of exponential histograms. The second is also expected because the error guarantees are given on the size of the sliding window, which was xed to 86,400 seconds. Accordingly, the error for smaller time intervals has to be lower. However, the e ect is linear to the logarithm of the query window sizes, i.e. when increasing the query window, the MAPE increases sublinearly.
When comparing the error between the at and hierarchical setting, the merge operations result in only a small increase in error.
"=0.01 "=0.02 "=0.04 "=0.08 "=0.16 mem. 14.5 MB 8.8 MB 5.5 MB 3.4 MB 2.5 MB
In order to set the MAPE in perspective to the number of visit events, Table 5 shows the average and maximum number of visits per POI and query interval. The average is hereby calculated once for all POI and time slots and once only for those containing at least one event.
The memory usage of the exponential histogram at the
end of the observation period is depicted in the last line in
Tables 3 and 4. Assuming xed 32-bit counters, it depends
only on " and the maximum possible count N in the sliding
window of each POI, requiring O( 1" log N ) space [
30 s 600 s 1,800 s 3,600 s 86,400 s avg. events max. events avg. events
> 0
Our experiments show that the resultant error is very low. For all settings of " the mean error (MAPE) is less than 1/10 of the maximum acceptable error. This is a very good result. Especially we can be sure for small total number of visits that the query results are always correct. For example, setting " = 0:01 will result in no errors if less than 100 events occur per POI. This is an important characteristic because the visit frequency of POI is right-tailed, containing only few POI with very high frequencies.
Further the experiments show that our setting scales horizontally. By introducing a layer of 10 intermediate nodes, the MAPE was on average 7.5% higher and at most 23% higher than in the at setting. Both numbers are considerably below the maximum acceptable error as well as the maximum relative error guaranteed for the join of exponential histograms.
Finally, to evaluate the memory usage, we can compare the numbers to the following baseline scenario. Whenever a visit event occurs, the POI identi er and timestamp are stored at the coordinator using two 4 Byte integers. As our sliding window covers only one day, we will assume that we have to store 1/7 of the total visit events. For the original 23,509 events this results in 0.026 MB. For the multiplied data set it results in 25.6 MB. The storage amount for the original events using exponential histograms varied between 0.54-4.7 MB. In this case we did not save on memory. However, using the more realistic multiplied data set with exponential histogram sizes between 2.5-14.5 MB, our experiments require only 9.7-56.6% of the baseline storage space depending on the selected ".
When extrapolating to the envisioned setting of monitoring 20 million persons generating each 210 events per day on about 6,500,000 distinct POIs in Germany (including the 6,000,000 distinct street segments), just storing the raw event data would result in 31.3 GB memory consumption. This is considerably above the 1.3-7.8 GB required by the exponential histograms (by just taking into account that our memory consumption increases linearly with the number of distinct POIs).
Considering our entire approach including exponential histograms and local evaluation, the storage reduction is even much higher compared to a naive centralized setting where the users submit a GPS position every second to some central coordinator.
Also note that inserting into and querying an exponential histogram almost takes constant time far below a microsecond, which is much faster than searching an event database of raw events.
In this paper we propose a distributed system for the large-scale online monitoring of poster performance indicators based on the evaluation of mobility data. Our system relies on the collection and local processing of mobility data via smartphones and uses exponential histograms for the e cient storage and querying of visit statistics in a sliding window fashion. Our experiments on a multiplied real-world data set with nearly 3,000 persons show that the usage of exponential histograms results in an average error of less than 1/10 of the maximum acceptable error while reducing the storage space to an amount as small as 9.7% of the baseline storage space.
We thank our colleague Sebastian Bothe for supporting us to run the cluster-based version of the experiments and the Arbeitsgemeinschaft Media-Analyse e.V. for granting the use of the GPS data set. The research leading to these results has received funding from the European Union's Seventh Framework Programme (FP7/2007-2013) under grant agreement no. 255951 (LIFT).