=Paper=
{{Paper
|id=Vol-1810/BIGQP_paper_06
|storemode=property
|title=Privacy Preservation of Semantic Trajectory Databases using Query Auditing Techniques
|pdfUrl=https://ceur-ws.org/Vol-1810/BIGQP_paper_06.pdf
|volume=Vol-1810
|authors=Despina Kopanaki,Nikos Pelekis
|dblpUrl=https://dblp.org/rec/conf/edbt/KopanakiP17
}}
==Privacy Preservation of Semantic Trajectory Databases using Query Auditing Techniques==
<pdf width="1500px">https://ceur-ws.org/Vol-1810/BIGQP_paper_06.pdf</pdf>
<pre>
    Privacy Preservation of Semantic Trajectory Databases
              using Query Auditing Techniques
                      Despina Kopanaki                                                            Nikos Pelekis
                      Dept. of Informatics                                         Dept. of Statistics and Insurance Science
                  University of Piraeus, Greece                                          University of Piraeus, Greece
                     dkopanak@unipi.gr                                                         npelekis@unipi.gr

ABSTRACT                                                                   increasing need of analyzing mobility data has led to the
Existing approaches that publish anonymized spatiotemporal                 representation of trajectories with contextual data from external
traces of mobile humans deal with the preservation of privacy              data sources, thus transforming raw trajectories to the so-called
operating under the assumption that most of the information in the         semantic trajectories. A semantically-annotated trajectory, in short
original dataset can be disclosed without causing any privacy              semantic trajectory, is considered as a sequence of stops (i.e.
violation. However, an alternative strategy considers that data            places where the object remains “static”) and moves (i.e. parts of
stays in-house to the hosting organization and privacy-preserving          the object’s trajectory in between two stops) [12]. This alternative
mobility data management systems are in charge of privacy-aware            representation of trajectories may pose even greater privacy
sharing of the mobility data. Furthermore, human trajectories are          violation threats. Consider for example a malevolent user who is
nowadays enriched with semantic information by using                       able to detect places of interest (POIs) where a moving object has
background geographic information and/or by user-provided data             stopped (e.g. home, hospital, betting office, etc.). This additional
via location-based social media. This new type of representation           knowledge allows the inference of personal sensitive information
of personal movements as sequences of places visited by a person           of this specific individual. On the one hand, analyzing
during his/her movement poses even greater privacy violation               semantically-enriched movement traces of users can aid decision
threats. To facilitate privacy-aware sharing of mobility data, we          making in a wide spectrum of applications, on the other hand, the
design a semantic-aware MOD engine were all potential privacy              disclosure of such data to untrusted parties may expose the
breaches that may occur when answering a query, are prevented              privacy of the users whose movement is recorded. Sharing user
through an auditing mechanism. Moreover, in order to improve               mobility data for analysis purposes should be done only after the
user friendliness and system functionality of the aforementioned           data has been protected against potential privacy breaches.
engine, we propose Zoom-Out algorithm as a distinct component,             Most of the methodologies that have been proposed in the
whose objective is to modify the initial query that cannot be              literature, aim at protecting users’ privacy by releasing an
answered at first due to privacy violation, to the ‘nearest’ query         anonymized version of the original dataset ([1][2][6][7][8][9][11]
that can be possibly answered with ‘safety’.                               [16]). These approaches assume that in the anonymized dataset a
                                                                           malevolent user will not be able to link a specific user with a
Keywords                                                                   movement. In this paper, we employ a more conservative
Privacy-aware query engine; mobility data; anonymity; semantic             approach to privacy by assuming that data stays in-house to the
trajectories.                                                              hosting organization in order to prevent any privacy breach. An
                                                                           auditing mechanism is responsible to control the information that
1. INTRODUCTION                                                            is released to third parties and ensure privacy-aware data sharing.
Nowadays, the ease of collecting and storing data from an
increasing variety of devices where positioning technologies               Gkoulalas-Divanis et al. [5] first proposed an envisioned query
(GPS) are embedded along with their enhanced processing                    engine where subscribed users have gained restricted access to the
capabilities, led inevitably to the desire of revealing useful             database to accomplish various analysis tasks. Pelekis et al. [13]
information from them. Alongside this progress, potential                  then proposed HERMES++, a privacy-aware query engine that
breaches of individuals’ privacy came to the light. Space-time             can protect the trajectory database from potential attacks, while
‘fingerprints’ of each recording moving entity (i.e. trajectories)         supporting popular queries for mobility data analysis. Both
may prove to be a dangerous tool in the hands of a malicious user.         approaches deal with spatiotemporal trajectory databases.
The scientific community has proposed various approaches to
protect individual’s privacy ([1][2][6][7][8][9][11][16]).                 Inspired by the work previously described and considering the
                                                                           richer representation of semantic trajectories, we design a query-
Most of the aforementioned studies, define raw trajectories as             based auditing mechanism that can effectively identify and block
sequences of points on a geometric space, focusing on their                a range of potential attacks that could lead to user identification or
spatiotemporal nature without complementing raw data with                  tracking, for privacy-aware sharing of in-house semantic mobility
additional information from the application context. However, the          data. The proposed mechanism provides an answer if k-anonymity
                                                                           principle is not violated w.r.t the user’s current history. Moreover,
                                                                           we propose an algorithm, called Zoum-Out, which modifies the
 2017, Copyright is with the authors. Published in the Workshop            original query that cannot be answered at first due to privacy
 Proceedings of the EDBT/ICDT 2017 Joint Conference (March 21,             restrictions, to the most similar query that can be safely answered.
 2017, Venice, Italy) on CEUR-WS.org (ISSN 1613-0073).
                                                                           The algorithm generalizes space, time and/or semantic dimension
 Distribution of this paper is permitted under the terms of the Creative   of one or more sub-queries w.r.t. to a distortion threshold.
 Commons license CC-by-nc-nd 4.0
                                                                           Summarizing, in this paper we make the following contributions:
     •    We identify various types of attacks and thus privacy          indistinguishable from. Kopanaki et al. [7] introduced the problem
          violations that malevolent users may try to pursue when        of Personalized (K,∆)-anonymity where user-specific privacy
          querying the original semantic trajectory database.            requirements are used to avoid over-anonymization and decrease
                                                                         information distortion. They proposed efficient modifications to
     •    We design a query-based auditing mechanism that can            state-of-the-art (k,δ)-anonymization algorithms by introducing
          effectively identify and block a range of potential            techniques built upon users’ personalized privacy settings and
          attacks that could lead to user identification or tracking.    trajectory segmentation.
     •    We propose Zoom-Out algorithm aiming at increasing             Recently, in [10] authors faced the problem of anonymizing
          user friendliness of the proposed mechanism by                 semantic trajectories. To release a safe version of a semantic
          modifying the (original) query posed that cannot be            trajectory dataset, they propose a method that generalizes
          answered due to privacy violation, to the ‘nearest’            sequences of visited places based on a privacy place taxonomy.
          possible ‘safe’ query.
                                                                         On the other hand, in several sharing scenarios data should stay
The rest of the paper is structured as follows: Section 2 presents       in-house to the hosting organization and the information must
related work. Section 3 introduces different types of attacks of a       remain private. This is the case when a data holder is not willing
malevolent user. Section 4 provides the auditing mechanism that          or is not able due to regulations to publish the entire dataset.
handles the previously described attacks as well as the Zoom-Out         Assuming that at least part of the data has to become available to
algorithm. Finally, Section 5 concludes the paper.                       possibly untrusted third parties for analysis purposes, a
                                                                         mechanism is needed in order to ensure that no sensitive
2. Related Work                                                          information will be released during this process. Along this
Methods that have been proposed so far to tackle the issue of            direction, methodologies have been proposed for disclosure
privacy-preserving mobility data publication mostly adopt the            control in statistical databases [3]. These approaches support only
principle of k-anonymity, which was originally proposed for              count and/or sum queries, since no other information can be made
relational databases [15]. k-anonymity principle is the most             available to the inquirer.
common approach that has been adopted for the anonymization of
both relational and mobility data. For mobility data, it states that a   Gkoulalas-Divanis and Verykios [5] first described the design
dataset must be anonymized so that every trajectory is                   principles of a query engine that protects user privacy by
indistinguishable from at least k-1 other trajectories.                  generating fake trajectories. The idea behind [5] is that malevolent
                                                                         users who query the trajectory database should not be able to
Hoh and Gruteser [6] presented a data perturbation algorithm that        discover (with high confidence) any real trajectory that is returned
is based on path crossing. When two non-intersecting trajectories        as part of the answer set of their query, while they can use the
are close enough, it generates a fake crossing in the sanitized          returned data to support their analytic tasks.
dataset to prevent adversaries from tracking a complete user's
trajectory. Terrovitis and Mamoulis [16] consider datasets as            In [13] and [14] authors extend and developed a privacy-aware
sequences of places visited by users. Based on the assumption that       query engine along with a benchmark framework. The proposed
a malevolent user holds partial information of users’ trajectories, a    engine audits queries for trajectory data to block potential attacks
suppression technique is proposed that eradicates the least number       to user privacy, supports range, distance, and k-nearest neighbor
of places from a user’s trajectory so that the remaining trajectory      spatial and spatiotemporal queries, and preserves user anonymity
is k-anonymous.                                                          in answers to queries by returning realistic fakes trajectories,
                                                                         while protecting user-specific sensitive locations.
Abul et al. [1] proposed a k-anonymity approach that relies on the
inherent uncertainty of moving objects whereabouts where a               Finally, in [17] authors proposed a data stream management
trajectory is considered as a cylinder. The anonymity algorithm          system aiming at preserving users’ privacy by enforcing
identifies trajectories that lie close to each other in time, employs    Hippocratic principles. Limited collection, limited use and limited
space translation and generates clusters of at least k trajectories.     disclosure of data are the main privacy requirements that the
Each cluster of k trajectories forms an anonymity region and the         system implements.
co-clustered trajectories can be released. To achieve space-time         To the best of our knowledge, this is the first work that proposes a
translation, the authors proposed W4M [2], which uses a different        query auditing mechanism for semantically-enriched mobility
distance measure that allows time-warping.                               data, able to provide answers while ensuring that no personal
Nergiz et al. [11] proposed a coarsening strategy to generate a          information will be disclosed to untrusted third parties.
sanitized dataset that consists of k-anonymous sequences. The
algorithm first generalizes a set of trajectories into a set of
                                                                         3. Privacy Attacks
sequences of k-anonymized regions, reconstructs, consolidates the        The main purpose of every attack of a malevolent is to broaden
trajectories of the original dataset into clusters of k and              her knowledge about an individual or a situation that interests her.
anonymizes the trajectories in each cluster. Monreale et al. [9]         This occurs when the attacker raises her confidence about an
proposed another anonymization approach that is based on the             event that may be related to an individual who is the ‘target’ or a
combination of spatial generalization and k-anonymity principle.         situation for which she wishes to acquire more specific
The geographical area covered by the trajectories belonging to the       knowledge. Usually, a malevolent has prior knowledge, i.e. time,
dataset is partitioned into sub-areas. The original trajectories are     place, type of event and/or semantics (or any possible
then generalized and transformed so as to satisfy k-anonymity            combination) about an individual.
principle.                                                               In our setting, each query may contain one or more sub-queries
Mahdavifar et al. [8] introduced the idea of non-uniform privacy         (i.e. standalone spatiotemporal range queries with key words
requirements, whereby each trajectory is associated with its own         constrains within another query) . Moreover, overlapping queries
privacy level indicating the number of trajectories it should be         is a sequence of at least two queries posed by a user, having as a
characteristic that the criteria of these successive questions are      Q1 with a sub-query that for sure contains the target (how many
overlapping. We assume that the queries differ only in one              people stayed during the night in area A and during the day were
dimension (space / time / semantics) or in the number of the sub-       working in area B). The number of trajectories that fulfil Q1 is 6.
queries that each one contains.                                         Q2 contains the same sub-queries with Q1 along with a new sub-
                                                                        query that asks for those that returned after work back to area A
User Identification Attack. In this attack the identity of a user can
                                                                        during the night. If the answer of Q2 returns 5 trajectories, then the
be revealed by posing overlapping queries in spatial and/or             malevolent may assume that the target did not spend the night at
temporal dimension. The attacker poses a query and if the number        home. If the result again was 6, then she would be certain that the
of trajectories is at least k, proceeds with one or more queries        target returned to her home. However, by posing two queries her
modifying each time only the same dimension such that every             confidence was increased.
time the new query contains the previous one.
Let’s assume that a user poses query Q1 that contains n                 4. Attack Prevention
trajectories where n³k and then Q2 which returns as an answer           To prevent the previously described attacks, an auditing
n+m trajectories, where m<k. The malevolent may conclude that           mechanism is required:
the area corresponding to the difference between Q1 and Q2                • to ensure that k-anonymity principle is not violated before
contains m trajectories which is less than threshold k, thus privacy        answering each query;
violation is occurred.                                                    • to protect sensitive episodes that include sensitive
Consider the example depicted in Figure 1. A user poses a query             information about entities and should not be disclosed to the
Q1: Find people starting from area A between [8.00-8.30am] and,             attackers;
then, stop at area B between [9.15-11.30pm]. This query contains          • to properly modify the original query if k-anonymity
two different sub-queries, each one able to provide an answer if            principle is violated, so as to make it acceptable;
posed independently from the other. The same user poses query             • to allow the data owner to have knowledge about the extent
Q2: Find people starting from area A’ between [8.00-8.30am]                 of the data leakage by examining the history of user queries
and, then, stop at area B between [9.15-11.30pm]. The answer of             to the database.
Q1 contains 7 trajectories while the answer of Q2 contains 8
trajectories. Thus, the malevolent can easily infer that only person    4.1 Sensitive Episodes
appears in the area A’-A. By combining this knowledge with              Sensitive episodes correspond to known locations that contain
additional information, the malevolent can identify this person.        particularly sensitive information and can expose the identity of a
                                                                        user. We call such locations sensitive for a user as no information
                                                                        should be disclosed to the attackers. In order to deal with user-
                                                                        defined sensitive episodes, the auditing mechanism initially does
                                                                        not include the sensitive episodes as part of the answer set of the
                                                                        query. If the number of non-sensitive episodes exceeds threshold k
                                                                        then sensitive episodes are incorporated in the answer set.

                                                                        4.2 Zoum-Out Algorithm
                                                                        When a user poses a query to the database, she is willing to gain
                                                                        knowledge about whether there are semantic trajectories that are
                                                                        answering the query w.r.t. some criteria. If the number of the
         Figure 1: An example of two Overlapping Queries
                                                                        semantic trajectories composing the result set are less than the
In the same line, assume the following example that takes into          anonymity threshold k, the query is not safe to be answered. This
account the semantic dimension. The user poses query Q1 and the         ensures a first level of privacy protection.
answer corresponds to a specific spatiotemporal area that includes
7 stop episodes. During Q2 the malevolent maintains the criteria of     The main idea of the proposed approach is that instead of not
Q1 but also adds tag=‘work’. The output of Q2 contains 6                providing an answer when k-anonymity principle is violated, an
trajectories. The malevolent can conclude that one entity was not       auditing mechanism should try to answer the query posed by a
working.                                                                user in any case. In other words, the mechanism will provide an
                                                                        answer of the most ‘similar’ query to the original that fulfills k-
Sequential Tracking Attack. In this attack the user is tracked          anonymity principle by relaxing conditions via generalization.
down through her trajectory by a set of focused queries. A              Query relaxation enlarges the search range to include additional
malevolent poses a sequence of queries, which differ only in the        information. The output of this process is like a generalized query
number of the sub-queries that each one contains. Between two           in one or more possible dimensions. Put differently, a user seeks
consecutive queries, assume that Q1 contains n sub-queries and Q2       to query an area but the mechanism resolves it for a zoomed-out
contains n+m, where m³1. To achieve an attack the malevolent            area that is generalized up to a permissible degree of analysis.
should know that her target participates in n sub-queries. Then the
                                                                        The main goal of implementing such an approach is to increase
malevolent may compare the number of the trajectories that
                                                                        user friendliness and improve database functionality. A user can
answer the query consisting of n sub-queries in relation to n+m. If
                                                                        gain information without posing consecutive queries expanding
the difference of the number of trajectories that are participating
                                                                        the criteria set until an answer is provided. To achieve this the
in the answer of the two queries is less than k, the malevolent may
                                                                        mechanism allows the generalization of one or more criteria, of
conclude sensitive information about the target.
                                                                        the sub-queries that constitute the original query. The
Consider the following example. The malevolent is aware of a            generalization may occur in the spatial, the temporal or even the
target home and working address and the goal is to learn if the         semantic dimension.
target slept at her home. Assume that k=4. The user poses query
Let’s assume that the answer of query Q consists of less than k         Algorithm 1. Zoom-Out
trajectories. The output of the algorithm is a modified query Q’. If
the modification process is successful, then the execution of query     Input: (1) anonymity threshold k, (2) initial query with sub-queries Q
                                                                        = <SQ1, SQ2,…, SQn>, (3) a semantic trajectory database D, (4)
Q’ will result at least k trajectories. The sets of subqueries in Q
                                                                        distortion limit dist, (5) array H[tr_id, freq, SQ1, SQ2, …, SQn]
and Q’ are of the same size. Each sub-query of Q’ is either the         Output: Q’= <SQ’1, SQ’2,…, SQ’n>
same or generalized w.r.t. the corresponding sub-query contained        1.   Q’ ¬ Q; H ¬ Æ;
in Q.                                                                   2.   Ntr ¬ Count(Q’)
                                                                        3.   repeat
An obvious approach would be to apply the aforementioned
                                                                        4.         Something_Changed ¬ False;
method only in case where a query cannot be answered marginally         5.         for i=1 to n do
w.r.t. to k-anonymity threshold. A threshold should then be             6.             Execute_Query(in SQ’i out tr_ids)
required based on which the mechanism would be activated every          7.             Fill_Help_Table(in H, tr_ids out H)
time that the query could not be answered. In such a case where         8.         end for
the mechanism is activated only if few trajectories are missing         9.         Find_Freq_Position(in H, n out i)
from the answer set, privacy breach may occur. A malevolent user        10.        episode_found ¬ False
can easily assume that the modified query does contain certain          11.        repeat
number of additional trajectories within the returned extra area.       12.            Compute_Distortion_Units(in out episode_found, H, i)
An obvious solution is to apply Zoom-Out algorithm regardless of        13.            Select_best_candidate_episode(in H, dist, i out tr_id,
the number of trajectories that are needed to reach k-anonymity              ep_id)
                                                                        14.            i ¬ i+1
principle.
                                                                        15.        until episode_found or EOF
The goal of the algorithm is to modify one or more sub-queries to       16.        if episode_found then
provide an answer to the user. To enable the algorithm to decide        17.            Embed_New_Episode(in H, tr_id, ep_id, in out SQ’i,
                                                                             Something_Changed)
which episode is preferable to be included in the answer of the
                                                                        18.            Νtr ¬ Count(Q’)
modified query, the algorithm should be able to compare the
                                                                        19. until (not Something_Changed) or (Ntr=k)
distortion (the specific definition of a distortion metric is           20. Compute_Random_Number(in Rmin, Rmax out R)
orthogonal to our approach) that is caused on each sub-query            21. Compute_New_Episodes(in Q’, R out Q’)
when trying to include two or more candidate episodes. A unit           22. return Q’
that calculates the distortion caused due to the generalization of
one or more dimensions on one or more sub-queries is required.
The distortion should be as low as possible to maintain the             sub-query in order to be modified so as include an episode from
information that the user required when posing the original query.      the trajectory. In case we have a distortion unit greater than a
                                                                        distortion limit (user-defined), the episode takes the tag INF and
Zoom-Out algorithm takes as input a semantic trajectory database,       the algorithm proceeds with the next trajectory. Under these
the original query posed by a user that cannot be answered,             conditions the algorithm selects as preferable the episode that has
anonymity threshold k and a matrix H. The output of the                 the lowest distortion unit value (line 13).
algorithm is the modified query along with the corresponding sub-
queries.                                                                As a next step, the sub-query is modified in one or more
                                                                        dimensions to contain the episode that minimizes the distortion
The algorithm after the initialization process (lines 1-2) continues    (line 17). The repetition ends (line 19) either if k trajectories have
with a loop phase where each sub-query of the original query is         frequency equal to the number of sub-queries or if no episodes
executed individually and the trajectories that comprise each one       were integrated.
are retrieved (line 6). Each trajectory id of these trajectories is
inserted into a matrix (H) along with the frequency indicating its      During the generalization process of the sub-queries, a privacy
appearance (freq) in all sub-queries (line 7). Thus, H is a tuple       breach may occur. Let’s assume that the spatial dimension of the
containing trajectory id (traj_id), frequency (freq) and the sub-       area that the query covers is enlarged so as to contain exactly k
queries (SQi). The maximum value that the counter (freq) can take       episodes. The spatial generalization should be the minimum
in each record is equal to the number of the sub-queries. Consider      possible in order to keep the distortion caused from this process as
as an example a query with three sub-queries, the counter for each      low as possible. To achieve this, most of the episodes that are
trajectory in matrix H will receive a value ranging from 1 up to 3.     added will appear in the borders of the modified area. The
If the counter receives the maximum value, the episodes of this         malevolent user thus will be more confident that between the
trajectory are identified in all sub-queries, thus this trajectory is   query posed and the modified query will be at least one episode.
returned as an answer to the overall query.                             In order to avoid such a violation, the modified query is expanded
                                                                        on each side by a randomly generated percentage R (line 21).
Based on matrix H, the algorithm detects the trajectory or              Finally, we get as output the final modified query along with its
trajectories with frequency (i.e., number of sub-queries) less than     sub-queries (line 22).
the maximum possible frequency but at the same time with the
highest value among the other trajectories in the matrix (line 9).      4.3 Query Auditing
Subsequently, a loop starts that ensures that if no episode is found,   The main goal of the Query-Auditing algorithm is to prevent any
the algorithm will search the trajectory that has the subsequent        privacy violation that may occur. The input of the algorithm is the
smaller frequency. This loop ends either when permissible               anonymity threshold k, the initial query posed by the user along
episodes can be integrated, or if all the remaining trajectories from   with the corresponding sub-queries, a semantic trajectory database
the matrix have been investigated and no episode is found (line         D and the id of the user posing the query. The algorithm first
15). To define the most appropriate candidate episodes, the             executes query Q and gets the number of trajectories that belong
algorithm employs a process called Compute_Distortion_Units. A          to the answer set (line 1). Then, the episodes that are considered
metric function is used that calculates the distortion caused in a      as sensitive are defined and removed from the answer set (line 2).
Algorithm 2. Query Auditing Algorithm                                      5. CONCLUSIONS
Input: (1) anonymity threshold k, (2) initial query with sub-queries, Q    In this paper, we proposed an envisioned query engine able to
= <SQ1, SQ2,…, SQn>, (3) a semantic trajectory database, D, (4) user id,   provide safe answers to queries posed by users in semantic
uid                                                                        trajectory databases. Different types of privacy attacks have been
Output: FQ                                                                 addressed and an effective auditing mechanism able to prevent
1.   FQ ¬ Execute Q                                                        privacy braches have been proposed. Finally, Zoom-Out algorithm
2.   Find all sensitive episodes, remove them from FQ                      is able to modify an initially not acceptable query to the closest
3.   if ||FQ||<k then                                                      one that can be safely answered, thus increasing the user
4.      Q ¬ Zoom-Out (k, Q, D, dist, H[tr_id, freq, SQ1, SQ2, …, SQn])
                                                                           friendliness of the engine. As a future work, we plan to finalize
5.      if Q = Q then return false
                                                                           the implementation of the proposed query engine and testbed its
6.   else
7.      for each SQi 
 Q do                                                utility.
8.         for each Qj 
 D where user_id=uid do
9.           for each SQjm 
 Qj do
                                                                           6. ACKNOWLEDGMENTS
10.            if SQi overlaps SQjm then
                                                                           The publication of this paper has been partly supported by the
11.               if SQ # − SQ %& ≥ k then                                 University of Piraeus Research Center.
12.                 QD = QD U Create_dummy_query (SQi - SQjm)
13.              else
                                                                           7. REFERENCES
14.                 return false                                           [1] Abul, O., Bonchi, F., Nanni, M. (2008). Never walk alone:
15.          end for                                                           Uncertainty for anonymity in moving objects databases. In
16.        end for                                                             Proc. of International Conference on Data Engineering,
17.     end for                                                                ICDE, pp. 376-385.
18. Add sensitive episodes to FQ
                                                                           [2] Abul, O., Bonchi, F., Nanni, M. (2010). Anonymization of
19. QD ¬ QD U Q
20. return FQ
                                                                               moving objects databases by clustering and perturbation.
                                                                               Information Systems, 35(8), pp. 884-910.
                                                                           [3] Adam, N.R. and Worthmann, J. C., (1989). Security-control
If the number of episodes is less than k, Zoom-Out algorithm,                  methods for statistical databases: A comparative study. ACM
previously described, is called to modify the original query and               Computing Surveys, 21(4):515-556.
try to provide an answer (line 4). If Zoom-Out algorithm is not
able to modify the query w.r.t. a distortion threshold, no answer is       [4] Chow, C. Y., Mokbel, M. F. (2011). Trajectory privacy in
provided to the user and the algorithm ends (lines 5). Contrary, if            location-based services and data publication. ACM SIGKDD
the original query Q or the modified query F_Q have equal or                   Explorations Newsletter, 13(1), pp. 19-29.
more than k episodes, the auditing mechanism continues to further          [5] Gkoulalas-Divanis, A. and Verykios, V. S., (2008) A
investigate the query based on user’s history. Note that in this               privacy–aware trajectory tracking query engine. SIGKDD
approach, we assume that sub-queries are totally overlapping.                  Explorations, 10(1):40-49.
Approaches that have been proposed so far, do not provide any              [6] Hoh, B., Gruteser, M. (2005). Protecting location privacy
answer when two queries posed by the same user are overlapping                 through path confusion. In Proc. of SecureComm, pp. 194-
to prevent any privacy violation. To increase user friendliness and            205.
system functionality, we argue that the previous approach is very          [7] Kopanaki, D., Theodossopoulos, V., Pelekis, N., Kopanakis,
conservative and the algorithm should proceed to further                       I., Theodoridis, Y., (2016). Who Cares about Others’
examination before denying an answer. Let’s assume that k=3, a                 Privacy: Personalized Anonymization of Moving Object
user poses query Q1: A®B®C®D which is satisfied by 7                           Trajectories. In Proc. of the 19th International Conference
semantic trajectories. The same user poses Q2: A®B and the                     on Extending Database Technology, 425-436.
answer contains 4 trajectories. Since the difference of these two
                                                                           [8] Mahdavifar, S., Abadi, M., Kahani, M., Mahdikhani, H.
queries that corresponds to query C®D is equal to k, no privacy
                                                                               (2012). A clustering-based approach for personalized privacy
violation can be caused. However, the auditor even though has not
                                                                               preserving publication of moving object trajectory data. In
directly reply to the query C®D, the information has been                      Proc. of Network and System Security, pp. 149-165.
inferred. To prevent future violation, the algorithm generates a
fake query that is stored in the database and corresponds to the           [9] Monreale, A., Andrienko, G. L., Andrienko, N. V., Giannotti,
difference of the two queries Q1-Q2.                                           F., Pedreschi, D., Rinzivillo, S., Wrobel, S. (2010).
                                                                               Movement data anonymity through generalization.
The auditor proceeds by comparing every sub-query of Q with all                Transactions on Data Privacy, 3(2), pp. 91-121.
the sub-queries that belong to queries posed from the user in the
past. Every time two sub-queries are overlapping, the auditor              [10] Monreale, A., Trasarti, R., Pedreschi, D., Renso, C.,
checks if the number of trajectories belonging to the difference of             Bogorny, V., (2011). C-safety: a framework for the
the corresponding sub-queries is equal or greater than k (lines 7-              anonymization of semantic trajectories. Transactions on
11). If so, a dummy query corresponding to the difference is                    Data Privacy, 4(2), pp.73-101.
created (line 12). Otherwise, the algorithm ends and no answer is          [11] Nergiz, M. E., Atzori, M., Saygin, Y. (2008). Towards
provided to the user (line 14). Finally, if the query is executed, the          trajectory anonymization: a generalization-based approach.
sensitive episodes are added to the answer, the query is stored in              In Proc. of the ACM International Workshop on Security and
the database and the answer is returned to the user (lines 18-20).              Privacy in GIS and LBS, SIGSPATIAL pp. 52-61.
                                                                           [12] Parent, C., Spaccapietra, S., Renso, C., Andrienko, G.,
                                                                                Andrienko, N., Bogorny, V., Damiani, M.L., Gkoulalas-
    Divanis, A., Macedo, J., Pelekis, N. and Theodoridis, Y.,       [15] Sweeney, L (2002) k-anonymity: a model for protecting
    (2013). Semantic trajectories modeling and analysis. ACM             privacy. International Journal on Uncertainty, Fuzziness and
    Computing Surveys (CSUR), 45(4), p.42.                               Knowledge Based Systems, 10(5), pp. 557-570.
[13] Pelekis, N., Gkoulalas-Divanis, A., Vodas, M., Kopanaki, D.,   [16] Terrovitis, M., Mamoulis, N. (2008). Privacy preservation in
     Theodoridis, Y., (2011). Privacy-aware querying over                the publication of trajectories. In Proc. of International
     sensitive trajectory data. In Proc. of the 20th ACM                 Conference on Mobile Data Management MDM, pp. 65-72.
     international conference on Information and knowledge          [17] Wu, H., Xiang, S., Ng, W.S., Wu, W. and Xue, M., (2014).
     management, pp. 895-904.                                            HipStream: A Privacy-Preserving System for Managing
[14] Pelekis, N., Gkoulalas-Divanis, A., Vodas, M., Plemenos, A.,        Mobility Data Streams. In 2014 IEEE 15th International
     Kopanaki, D., Theodoridis, Y., (2012). Private-HERMES: a            Conference on Mobile Data Management, pp. 360-363.
     benchmark framework for privacy-preserving mobility data
     querying and mining methods. In Proc. of the 15th
     International Conference        on   Extending     Database
     Technology, pp. 598-601.

</pre>