Abbas Salhab

Julien Carlier

Malika Toubal

Pierre Campistron

Marc Neyens

Bertrand Nongaillard

Vincent Thomy

Analysis of Wetting Transition and Pattern Collapse During the Drying Process of Deep Trench Isolation Structures Using Ultra-high Frequency Acoustic Waves and SEM Imaging

published or not. The documents may come

L'archive ouverte

Introduction

The trend in the semiconductor industry is to make smaller structures as the size of electronic components such as transistors continues to decrease reaching sizes of some nanometers. This trend in size reduction lead to higher aspect ratio (AR) which is defined as the ratio of height to lateral dimension of the structure. Thus when making patterned (etched) silicon (Si) wafers, it is therefore crucial to establish efficient cleaning (complete wetting) and drying processes of these silicon structures. However, these high AR make it difficult to penetrate the liquid inside the structures as well as making them susceptible to deformation due to high capillary forces of the liquid during the drying process. On one hand, to remove organic impurities and metal contamination, the complete liquid penetration into the silicon structures is desired. On the other hand, after the wet cleaning process is done, efficient and uniform drying of these high AR structures is desired to prevent structural deformation known as pattern collapse.

To understand and optimize these phenomena it is essential to characterize the wettability of solid surfaces. In the case of a smooth surfaces, the wettability can be judged based on the Young's contact angle "θ" [START_REF] Young | An essay on the cohesion of fluids[END_REF], where a surface is said to be either hydrophilic "wettable" (θ < 90°) or hydrophobic "non-wettable" (θ > 90°). In case of textured surfaces, the wetting characterization is more challenging in a sense that we could have multiple wetting states. For example, studying wetting transition from Cassie-Baxter [START_REF] Cassie | Contact angles[END_REF] to Wenzel state [START_REF] Wenzel | Resistance of solid surfaces to wetting by water[END_REF] is important to see what factors control this transition and to prevent it when designing superhydrophobic textured surface for applications such as waterproof textiles [START_REF] Park | Superhydrophobic Textiles: Review of Theoretical Definitions, Fabrication and Functional Evaluation[END_REF] and drag reduction [START_REF] Chen | Flow inside Micro-Channel Bounded by Superhydrophobic Surface with Eccentric Micro-Grooves[END_REF]. Other applications, such as cleaning processes need to promote Wenzel state for liquid total impregnation inside the structuration.

The characterization of such wetting states is still challenging and numerous methods have been developed based on different physical effect. ATR-FTIR (Attenuated Total Reflectance-FTIR) [START_REF] Vrancken | In-situ ATR-FTIR for dynamic analysis of superhydrophobic breakdown on nanostructured silicon surfaces[END_REF] and EIS (Electrochemical Impedance Spectroscopy) [START_REF] Chen | Probing Pore Wetting in Membrane Distillation Using Impedance: Early Detection and Mechanism of Surfactant-Induced Wetting[END_REF] are some of the methods that could give real-time wetting characterization of micro / nanometric structured interfaces.

In our study, we will monitor the wetting transition on the Deep Trench Isolation (DTI) structures with different AR by ultra-high frequency acoustic reflectometry method. The DTI is used as pixel insulator in image sensors and the efficient cleaning of such structures is important to prevent the apparition of white pixels on images. In addition, we will use a PolyDiMethylSiloxane (PDMS) based microchannel system to inject the liquid on the surface of the DTI in order to study the wetting process using flow conditions as close as possible to those used at STMicroelectronics. Finally, the use of Scanning Electron Microscopy (SEM) images on the DTI will enable us to detect pattern collapse.

Experimental setup

DTI geometry

The DTI structures are etched inside matrices found on the frontside of 300 mm diameter silicon (Si) wafer of 785 ± 5 μm thickness made by STMicroelectronics. They are composed of 200 nm wide and 4 μm to 7 μm deep trenches (Figure 1). On the top surface of the trenches, three layers composed of 7.5 nm silicon dioxide (SiO 2 ), 55 nm silicon nitride (Si 3 N 4 ) and 80 ± 20 nm (SiO 2 ) are stacked respectively (Figure 2).

PDMS micro-channel

We create a fluidic channel whose dimensions and flow parameters allow finding the cleaning conditions applied in industry. Thus an 80 μm deep PDMS micro-channel mold is fabricated by laser lithography starting from SU-8 2075 resist (Kayaku advanced materials Inc.). The micro-channel mold 3.1 x 3.3 mm 2 lateral dimensions are chosen so that it can cover the all the surface area of the 2.1 x 2.3 mm 2 DTI matrix (Figure 3). In the industrial single wafer cleaning process, the liquid film thickness "h" can change depending on the distance from the wafer's center "r", flow rate "Q", liquid kinematic viscosity "v" and the rotational speed of the wafer "ω" (Figure 4.a). The micro-channel thickness is taken as "2h" to have the same velocity profile distribution as the single wafer system (Figure 4.b). The liquid film thickness "h" is related to the different parameters by [START_REF] Zamani | surface cleaning of small structures during spin rinsing of patterned substrates[END_REF]: ℎ = 0.782 × 𝑄 0.33 × 𝜈 0.33 ×  -0.67 × 𝑟 -0.67 [START_REF] Young | An essay on the cohesion of fluids[END_REF] The 80 μm (2h) depth of the micro-channel is calculated for the following parameters values: Q = 0.12 L.min -1 , v = 1.10 -6 m 2 .s -1 (water at 20 °C), ω = 800 r.p.m. and r = 50 mm. After preparing the mold, the next step is the preparation of the PDMS mixture. First 30 g of the PDMS base is added into a cup then 1/10 of the amount PDMS curing agent is added into the same cup (3 g). Then the cup is putted into a planetary mixer (ARV310, Thinky USA, INC) for about 1 minute under a vacuum pressure of 30 KPa and a rotational speed of 2000 r.p.m. The purpose of this operation is that, both liquids (base and curing agent) will be properly mixed and that the air bubbles in the resulting solution will be also removed under vacuum.

The PDMS solution is then poured on the mold and put in an oven at 70 °C for 3 hours to polymerize the PDMS. After the heating process, the PDMS which contain the micro-channel pattern is detached from the mold. Then using a biopsy punch with diameter equal to 2 mm, the inlet and outlet of the micro-channel is drilled into the PDMS.

Then, the surface of the PDMS micro-channel is treated with Electro-Technic Products (Chicago, IL) hand-held corona plasma discharge for 1 minute. Then the PDMS micro-channel is immediately placed over the DTI silicon wafer at the specified position in order to cover the DTI matrix. Upon contact, a bridging bond Si-O-Si is created at the interface making an irreversible seal. Note that the surface of the DTI wafer was not exposed to the plasma O 2 since it can transform the surface to hydrophilic changing its wettability. The last step includes heating the DTI wafer in an oven at 70 °C for 1 hour to strengthen the bond with PDMS micro-channel.

Acoustic reflectometry method

The acoustic reflectometry method for wetting characterization developed at the IEMN laboratory [START_REF] Virgilio | Wetting Characterization of High Aspect Ratio Nanostructures by Gigahertz Acoustic Reflectometry[END_REF], consists of using ultra-high frequency longitudinal incident waves generated by piezoelectric transducers built on the backside of a 7 x 7 cm 2 patterned silicon wafer.

The piezoelectric transducers are made up of three layers. First, a ground electrode deposited on silicon by thermal evaporation (10 nm titanium "Ti" + 50 nm platinum "Pt"). The transducers are circular in shape (100 μm in diameter) and defined in shape and size by a photolithography process. Another layer of zinc oxide (ZnO) is deposited on top of the ground electrode by magnetron sputtering.

The thickness of the ZnO will determine the central frequency of the transducer. In this work we deposited a thin film (thickness of about 330 nm) of ZnO which will give us transducers generating longitudinal waves of 4 GHz for the central frequency. This central frequency corresponds to a wavelength of 2.1 μm in the silicon, smaller than the etch depth (4 μm) to ensure the separation of echoes between the top and bottom surface of the DTI (Figure 2). A final layer of top electrode is deposited by thermal evaporation (50 nm Pt). The different thicknesses of the materials have been predicted by a simulation to achieve the maximum conversion of electrical energy into acoustic energy [START_REF] Virgilio | Caractérisation du mouillage de surfaces micro/nanostructurées par méthode acoustique haute fréquence : application aux traitements humides dans l'industrie de la microélectronique[END_REF]. The incident longitudinal waves will be reflected at the bottom and top surface of the trenches generating two different echoes A 11 and A 12 respectively (Figure 5). Depending on the medium present at the interface (air or liquid), the surface characterization is done by measuring the electrical impedance of the transducer. The measurement procedure is done by first measuring the scattering parameter S 11 (f) (ratio of complex voltage of reflected to incident waves) using a SussMicrotech probe coupled with a Rhode & Schwarz 300 kHz -8 GHz Vector Network Analyzer (VNA). Using an inverse Fourier transform to S 11 (f), the reflected echoes (A 11 and A 12 ) are obtained in the time domain S 11 (t). To obtain the acoustic reflection coefficients, the amplitude of the signal is then normalized to air in order to eliminate any intrinsic insertion losses related to the measurements. The reflection coefficients on the bottom and top surface of the DTI (r 1 and r 2 respectively) are given as:

|𝑟 1 | = 𝐴 11 𝑙𝑖𝑞𝑢𝑖𝑑 𝐴 11 𝑎𝑖𝑟 𝑎𝑛𝑑 |𝑟 2 | = 𝐴 12 𝑙𝑖𝑞𝑢𝑖𝑑 𝐴 12 𝑎𝑖𝑟 ( 2
)
Figure 5 -Schematic of acoustic reflectometry method in wetting characterization of textured interfaces.

The final system (PDMS micro-channel + piezoelectric transducer + (7 x 7) cm 2 DTI wafer) is shown in Figure 6. To control the liquid flow inside the micro-channel, a microfluidic system MFCS-FLEX (from Fluigent company) is used by varying the pressure from some mbar up to 1 bar. The liquid will fill the micro-channel at a pressure of 300 mbar through a series of microfluidic tubes (0.5 mm internal diameter with 0.8 mm wall thickness) then air will be sent at a pressure of 1 bar to dry the liquid from the micro-channel.

The VNA is connected to a MatLab program which get the S 11 (t) data and enable the direct calculation of r 1 and The automated acquisition with MatLab will enable us to monitor the wetting transition inside the DTI with a time delay of 12 s.

The measurements are done at 20 °C on four DTI samples with different etch depth (4, 5, 6 and 7 μm) and using different ethanol (EtOH) / distilled water (DW) mixtures (surface tension decreases as the ethanol concentration increases). A diluted version of the Standard Clean 1 (SC1) solution used at STMicroelectronics to eliminate organic and oxide contaminations, is also used for the measurements. The SC1 will be composed of: 80 parts H 2 O, 1 part ammonia solution (NH 4 OH (30%)) and 2 parts hydrogen peroxide solution (H 2 O 2 (30%)).

A highly diluted version of the SC1 is used in order to avoid basic pH as it can damage the PDMS micro-channel.

Results and discussion

Wetting transition

The measurements were carried out with 100 μm diameter transducers, with about a 4 GHz central frequency within the band [1 GHz; 6 GHz].

First, experimental measurements using different EtOH / DW mixtures on four different trenches depths DTI wafers (4 μm, 5 μm, 6 μm and 7 μm) were carried out. Each solution was injected into the micro-channel at a pressure of 300 mbar and air is injected at 1 bar between each solution to dry up the micro-channel.

The measurements of the acoustic reflection coefficient r 1 using water/ethanol mixtures are shown in Figure 7. The precision of the measurements is Δr 1 = 0.0025. It was obtained by calculating the standard deviation on 20 measurements points when DW is injected inside the microchannel.

We can observe, from the obtained values for the four DTI samples that the r 1 values are always superior to those obtained for silicon smooth surface. The smooth silicon surface values represent the experimental reference case where we have complete wetting (liquid completely cover the bottom surface of DTI). For example, in the case of water and pure ethanol for the DTI 4 μm, we obtain values of 0.91 and 0.93 respectively which are significantly higher than the values obtained on smooth surface (0.86 and 0.91). These superior values indicate that wetting inside the trenches is not total and could be related to air being present in the network. Thus, the amount of reflected energy is greater than that in a purely Wenzel state, implying an increase in the reflection coefficient and non-complete wetting inside the trenches. Thus, using the different mixtures of water / ethanol, a partial and non-complete wetting was observed. By observing Figure 8, at phase 1 we can state that the micro-channel is empty (r 1 = r 2 = 1), then at t = 212 sec we can see the impact of liquid filling the micro-channel. The values of the bottom and top reflection coefficients fall instantly to reach phase 2 (r 1 = 0.92 and r 2 = 0.75). The values of the reflection coefficient r 1 obtained here are similar to the ones obtained with DW (Figure 7). This result was expected since the SC1 is highly diluted (r Si/SC1 = 0.86). At t = 1000 sec, air is injected in the micro-channel to dry it. The liquid inside the micro-channel starts to be pushed to the outlet. At t = 1123 sec a transition from phase 2 to phase 3 takes place, r 2 increases gradually and r 1 decreases to reach a value of 0.87 at t = 1220 sec which is close to the theoretical value on a smooth surface for complete wetting (r Si / SC1 = 0.86). Finally, a transition to phase 4 takes place where the micro-channel is completely dry and the reflection coefficients regain their original value close to 1.

A remarkable transition from phase 2 to phase 3 occurred in the case of DTI 6 μm (Figure 8) where we saw that r 1 reached a value of 0.87 which is very close to the value obtained for complete wetting (r Si / DW = 0.86) indicating a quasi-complete wetting behavior on the bottom surface of the DTI. The transition from phase 2 to phase 3 was accompanied by the observation (using the microscope positioned above the micro-channel) of bubbles exiting the DTI network (Figure 9.b). This confirms the scenario we proposed about trapped air pockets inside the trenches which inhibited the total wetting. The origin of these bubbles is correlated to the observation of bubbles when the SC1 was injected in the micro-channel (Figure 9.a) and inside the beaker of the prepared SC1 solution. Indeed they are due to the presence of oxygen (O 2 ) generated due to the decomposition of hydrogen peroxide: It is important to note that the transition from phase 2 to phase 3 was not always systematic. It was dependent whether the trapped air is able to exit the DTI network or not. Also, it was independent of the DTI sample as we observed it also on the DTI 4 μm with the diluted SC1 solution.

2𝐻 2 𝑂 2 → 2𝐻 2 𝑂 + 𝑂 2 (3)
We formulated a hypothesis that the wetting transition is directly linked with the observation of O 2 bubbles in the injected solution. However, as we can see in Figure 10, a wetting transition to total wetting state for pure ethanol (r 1 = 0.91 = r Si/EtOH ) on the DTI 4 μm, with 80 μm microchannel, could be observed during the drying phase (phase 3) without the appearance and influence of the O 2 bubbles. This wetting transition observation with ethanol indicates that this transition can be related to the pressure changes inside the micro-channel when we inject air at 1 bar (liquid is injected at 300 mbar).

To understand the pressure change effect one explanation could be formulated. The pressure is balanced between the liquid on one side (Laplace pressure), which is acting downward on the liquid air meniscus, and the pressure generated from the trapped air pockets on the bottom of the trenches on the other side which is acting upwards on the liquid air meniscus (Figure 11). When air is injected into the micro-channel at a pressure of 1 bar, the pressure of the suspended liquid increases and pushes further on the air pockets. It reduces their volume leading to a diffusion of these pockets into the liquid and the increase in the wetted bottom surface area of the trenches (air pockets replaced by the liquid). This diffusion of the air pockets into the liquid could also explain the phenomenon observed in Figure 9.b showing tiny air bubbles exiting from the DTI network.

Pattern collapse

As we are dealing with high AR structures like the DTI, the structural deformation due to capillary forces acting on the trenches during the drying phase is highly probable. The capillary pressure is the pressure difference formed across a meniscus (Liquid-air interface). It is given as [START_REF] Peter | Pattern Collapsethe Mechanical Stability and Solid Bridging of Semiconductor Nanostructures[END_REF]:

𝛥𝑃 𝑐𝑎𝑝 = 2𝛾 cos 𝛼 𝑑 ( 4
)
With α contact angle, γ surface tension of the liquid and d width of the trench. The capillary force (F cap ) acting on the trench due to different filling height of the liquid (Figure 12) is then given as a product of capillary pressure multiplied by the surface area of the trench. It is mathematically written as:

𝐹 𝑐𝑎𝑝 = 2𝛾 cos 𝛼 𝑑 ℎ𝑙 (5)
We can see from Eq. ( 5), the impact of the AR (h/d). The higher the AR, the higher the capillary forces acting on the trenches. Since the structural deformation or pattern collapse require visualization method. We used SEM images on the four DTI samples that we used to carry out the wetting characterization measurements. The SEM images were taken at the location of the DTI matrix where we placed the micro-channel after removing the PDMS.

We can see that the pattern collapse is clearly seen on the DTI 6 μm and 7 μm (Figure 13.c and Figure 13.d respectively), and it is linked to the small rectangular pillars represented by the red arrows while the larger pillars represented by the blue arrows are intact. These pillars have dimensions of (300 x 565 nm 2 ) and the larger pillars have dimensions of (1.8 x 1.9 μm 2 ) so, we get an aspect ratio (ratio of the pillar height to its lateral dimension) of 20 and 23 for the small pillar of DTI 6 μm and 7 μm respectively while the aspect ratio for the larger pillars is 3 and 4 for DTI 6 μm and 7 μm respectively. The smaller pillars tend to bend and attach to the larger ones due to the formation of solid bridges [START_REF] Alley | The effect of release-etch processing on surface microstructure stiction[END_REF] during liquid evaporation (Figure 14.b). These bridges could form from the oxidation of silicon into silicon dioxide (SiO 2 ), and act as a bond holding the structures together. The oxidation is due to the fact that we used ambient air (O 2 present) in our drying process. In industry nitrogen (N 2 ) drying is used to minimize this oxidation effect during the drying process. Usually to break this kind of bonds and straighten the pillars, hydrofluoric (HF) vapor cleaning is used at industry.

Conclusion

In this work, we presented the kinetic wetting characterization using acoustic reflectometry method on DTI structures using flow conditions as close as possible to those used at STMicroelectronics. With an 80 μm deep PDMS micro-channel we were able to inject different ethanol / distilled water mixtures and detect partial wetting state. Using automated acquisition technique with a MatLab program, wetting transition to quasi-complete wetting with the SC1 solution on DTI 6 μm etch depth and a complete wetting were detected on the DTI 4 μm etch depth using pure ethanol. However, this transition was not systematic and was related to pressure changes during the drying process and the exit of trapped air bubbles from the DTI network. Pattern collapse was also detected through SEM images on the high AR (20 and 23) DTI pillars.

Figure 1 -

 1 Figure 1 -SEM image of the DTI geometry found inside the etched matrices.

Figure 2 -

 2 Figure 2 -Schematic of the trench structure

Figure 3 -

 3 Figure 3 -Schematic of the micro-channel covering the DTI matrix. Dimensions are given in micrometers.

Figure 4 -

 4 Figure 4 -(a) Schematic of the liquid film formed during the rotation of wafer in the industrial single wafer cleaning process (b) schematic of velocity distribution in the microchannel and the single wafer system.

Figure 6 -

 6 Figure 6 -(a) Schematic of the DTI wafer coupled with PDMS micro-channel and transducers (b) image of a DTI wafer sample with micro-channel attached to it.

r 2

 2 with an acquisition time of 12 s. The measurement procedure is done in three phases:  Phase 1 : r 1 and r 2 are measured with time before injecting liquid in the micro-channel (air present: r 1 = r 2 = 1),  Phase 2 : liquid is injected in the micro-channel and the changes of the reflections coefficients are measured with time,  Phase 3: air is injected to dry the micro-channel where r 1 and r 2 are measured until returning to phase 1 (r 1 = r 2 = 1).

Figure 7 -

 7 Figure 7 -Variations of the acoustic reflection coefficient r 1 on the bottom of the DTI 4, 5, 6 and 7 μm for different distilled water / ethanol mixtures injected inside the 80 μm micro-channel. Now we will use the diluted SC1 solution. The idea behind using the SC1 is to eliminate any organic material from inside the DTI that could prevent the complete wetting. The measurement of the acoustic reflection coefficients (r 1 and r 2 ) are plotted with time (using MatLab program) for DTI 6 μm sample with 80 μm micro-channel (Figure 8). The measurements correspond to four phases:  Phase 1 is the initial phase where the micro-channel is empty,  In phase 2, the micro-channel is injected with SC1,  Phase 3 corresponds to wetting transition after injection of air to dry the micro-channel,  Phase 4 corresponds to the complete drying of the micro-channel and the return to the initial phase (phase 1).

Figure 8 -

 8 Figure 8 -Variation of the acoustic reflection coefficients r 1 and r 2 with time for DTI 6 μm with 80 μ micro-channel injected with SC1 solution: initial phase (phase 1), injection of liquid (phase 2), wetting transition (phase 3) and complete drying (phase 4)

Figure 9 -

 9 Figure 9 -(a) Observed bubbles during the injection of the SC1 solution in the micro-channel (b) air bubbles exiting the DTI network during the drying phase.

Figure 10 -Figure 11 -

 1011 Figure 10 -Variation of the acoustic reflection coefficients r 1 and r 2 with time for DTI 4 μm with 80 μ micro-channel injected with pure ethanol: initial phase (phase 1), injection of liquid (phase 2), wetting transition to complete wetting (phase 3) and complete drying (phase 4)

Figure 12 -

 12 Figure 12 -Schematic of the capillary forces acting upon trenches with different liquid filling height

Figure 13 -

 13 Figure 13 -SEM images of the DTI matrix showing the etched trenches (black color) and the silicon pillars (grey color) for (a) 4 μm, (b) 5 μm, (c) 6 μm and (d) 7 μm etch depth The pattern collapse could be observed up closely by the bending of the small rectangular pillars (Figure 14.a). The smaller pillars tend to bend and attach to the larger

Figure 14 -

 14 Figure 14 -(a) SEM images of the DTI 7 μm matrix showing the deformation of the small pillars (b) Formation of a solid bridge on the small pillar.

Acknowledgements

This work was partially supported by the French Renatech network. This research work has been partially undertaken with the support of IEMN fabrication (CMNF).

The authors would like to thank the Program NANO 2022 supporting the joint lab IEMN -STMicroelectronics.


Manos Katsomallos
email: emmanouil.katsomallos@cyu.fr

Katerina Tzompanaki
email: aikaterini.tzompanaki@cyu.fr

Dimitris Kotzinos
email: dimitrios.kotzinos@cyu.fr

Landmark Privacy: Configurable Differential Privacy Protection for Time Series

Keywords: Security and privacy; differential privacy, privacy-preserving data publishing, time series

Several application domains, including healthcare, smart building, and traffic monitoring, require the continuous publishing of data, also known as time series. In many cases, time series are geotagged data containing sensitive personal details, and thus their processing entails privacy concerns. Several definitions have been proposed that allow for privacy preservation while processing and publishing such data, with differential privacy being the most prominent one. Most existing differential privacy schemes protect either a single timestamp (event-level), or all the data per user (user-level), or per window (𝑤-event-level) in the time series, considering however all timestamps as equally significant. In this work, we define a novel configurable privacy notion, landmark privacy, which differentiates events into significant (landmarks) and regular, achieving to provide better data utility while preserving adequately the privacy of each event. We propose three schemes that guarantee landmark privacy, and design an appropriate dummy landmark selection module to better protect the actual temporal position of the landmarks. Finally, we provide a thorough experimental study where (i) we study the behavior of our framework on real and synthetic data, with and without temporal correlation, and (ii) demonstrate that landmark privacy achieves generally better data utility in the presence of landmarks than user-level privacy.

INTRODUCTION

The plethora of sensors currently embedded in personal devices and numerous crowdsensing services (e.g., Ring [1], TousAntiCovid [START_REF]TousAntiCovid[END_REF], Waze [3], etc.) based on the collected personal, and usually geotagged and timestamped data. User-service interactions gather personal event-like data, which are tuples of an identifying attribute of an individual and the-possibly sensitive-information with a timestamp e.g., ('Quackmore', 'dining', 'Canal Saint-Martin', 17:00). When the interactions are performed in a continuous manner, we obtain time series of events. Depending on the duration, we distinguish the interaction/observation into finite, when taking place during a predefined time interval, and infinite, when taking place in an uninterrupted fashion. Example 1.1 demonstrates a user-service interaction that results in retrieving location-based information or reporting user-state at various locations.

Example 1.1. Figure 1 shows a finite sequence of spatiotemporal data, generated by Quackmore, during an interval of 8 timestamps. Events in gray correspond to significant events, which Quackmore has defined beforehand, because they are related to his home (around Élysée), his workplace (around the Louvre), and his hangout (around Canal Saint-Martin). The regulation regarding the processing of user-generated data sets [START_REF] Tankard | What the GDPR means for businesses[END_REF] requires the provision of privacy guarantees to the users. To accomplish this, various privacy techniques perturb the original data or their statistical output at the expense of the overall utility of the final output. Meanwhile, it is essential to provide data of high utility to the final consumers of the privacy-preserving process. A widely recognized method that introduces probabilistic randomness to the original data, while quantifying with a parameter 𝜀 ('privacy budget' [START_REF] Frank | Privacy integrated queries: an extensible platform for privacy-preserving data analysis[END_REF]) the privacy/utility ratio, is 𝜀-differential privacy [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF]. Event, user [START_REF] Dwork | Differential privacy under continual observation[END_REF], and 𝑤-event [START_REF] Kellaris | Differentially private event sequences over infinite streams[END_REF] comprise the possible levels of privacy protection. Event-level limits the protection to any single event, user-level protects all the events of any user, and 𝑤-event provides protection to any sequence of 𝑤 events. In every case, privacy protection boils down to allocating to events an overall privacy budget that does not exceed 𝜀.

The privacy mechanisms for the aforementioned levels assume that in a time series any single event, or any sequence of events, or the entire series of events respectively is equally privacy-significant for the users. In reality, this is an assumption that deteriorates unnecessarily the utility of the released data. The significance of an event is related to certain user-defined privacy criteria, or to its adjacent events, as well as to the entire time series. We term significant events as landmark events or simply landmarks. Identifying landmarks can be done in an automatic or manual way; this is an orthogonal problem to the one presented here and thus it is out of scope of this work. For example, in spatiotemporal data, places where an individual spent some time denote points of interest (POIs) also known as stay points [START_REF] Li | Mining user similarity based on location history[END_REF]. Such events, and more particularly their spatial attribute values, can be less privacy-sensitive, e.g., parks, theaters, etc., if the user visits them few times, but if individuals frequent them, they can reveal supplementary information, e.g., residences (home addresses), places of worship (religious beliefs) [START_REF] Primault | The Long Road to Computational Location Privacy: A Survey[END_REF], etc. Another example is the detection of user interactions by contact tracing applications. This can be helpful in epidemic control, similar to the recent outbreak of the Coronavirus disease 2019 (COVID-19) epidemic [START_REF] Ahmed | A survey of COVID-19 contact tracing apps[END_REF]; however, the user may distinguish among contacts that are more privacy-sensitive than others. Last but not least, landmarks in smart grid electricity usage patterns may not only reveal the energy consumption of a user, but also information regarding activities, e.g., 'at work', 'sleeping', etc., or types of appliances already installed or recently purchased [START_REF] Khurana | Smartgrid security issues[END_REF].

Example 1.2. Continuing Example 1.1, Quackmore cares about protecting his landmarks (𝑝 1 , 𝑝 3 , 𝑝 5 , 𝑝 8 ) along with every release that he makes, however he is not equally interested for the other regular events in his trajectory. More technically, he cares about allocating a total budget of 𝜀 on any set of timestamps containing the landmarks and one regular event. Event-level protection is not suitable for this case, since it can only protect one event at a time. So, let us assume that we apply user-level privacy1 , by distributing equal portions of 𝜀 to all the events, i.e., 𝜀 8 to each one (see Figure 2). Indeed, we have protected the landmark points plus one regular event at any release as expected; we have allocated a total of 5𝜀 8 < 𝜀 to these 5 events. However, perturbing by 𝜀 8 each one of the regular points deteriorates the data utility unnecessarily; any budget less than or equal to 4𝜀 8 would be sufficient for covering the user privacy requirements. On the other hand, our proposed privacy model, landmark privacy, directly considers only the 5 events of interest (4 landmarks +1 current event) in every release, and thus changing the scope from all the time series to a significant subset of events. Subsequently, it allocates 𝜀 5 to each one of these events. Consequently, we still achieve to protect all the significant events, while the utility of a perturbed event is greater than in the case of user-level privacy ( 𝜀 5 > 𝜀 8 ).

Motivation. We argue that protecting only landmark events along with any regular event is sufficient for the user privacy protection, while it improves data utility with respect to the conventional user-level privacy. Considering landmarks can prevent over-perturbing the data in the benefit of their final utility.

Revisiting the scenario in Figure 2, if we want to protect the landmark points, we have to allocate at most a budget of 𝜀 to the landmarks, while saving some for the release of regular events. Essentially, the more budget we allocate to an event the less we protect it, but at the same time the more we maintain its utility.

With landmark privacy we propose to distribute the budget by accounting only for the landmarks when we release an event of the time series, i.e., allocating 𝜀 5 (4 landmarks + 1 regular point) to each event (see Figure 2). This way, we still guarantee that the landmarks are adequately protected, as they receive a total budget of 4𝜀 5 < 𝜀. At the same time, we avoid over-perturbing the regular events, as we allocate to them a higher total budget ( 4𝜀 5 ) than in user-level ( 𝜀 2 ), and thus less noise. Hence, at any timestamp we achieve an overall privacy protection bounded by 𝜀 in the event set consisting of the released event and the landmarks.

Contributions.

In this work, we formally define a novel privacy notion that we call landmark privacy. We apply this privacy notion to finite time series consisting of landmarks and regular events, and we design and implement three landmark privacy schemes. We further enhance our proposal by protecting the temporal position of the landmarks in the time series. We investigate landmark privacy under temporal correlation, which is inherent in time series publishing, and discuss how landmarks can affect the propagation of temporal privacy loss. Finally, we evaluate landmark privacy with real and synthetic data sets, in settings with or without temporal correlation, showcasing the validity of our proposal.

BACKGROUND AND RELATED WORK

This section provides the background knowledge that is essential to the presentation of this paper and discusses the related work. Landmark privacy is based on 𝜀-differential privacy, and hence we revisit its definition and important properties in Section 2.1 before moving on to the main ideas of this paper. Although, its local variant [START_REF] John C Duchi | Local privacy and statistical minimax rates[END_REF] is more compatible with microdata, which is our use case, for the sake of simplicity in presentation we use its standard version. Still, all discussed notions apply for local differential privacy. Section 2.2 surveys implementations of differential privacy in scenarios of continuous data publishing, and Section 2.3 describes how it behaves under the presence of temporal correlation.

Differential privacy

Differential privacy [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF] is a property of a privacy mechanism M processing a set of privacy-sensitive personal data 𝐷, while providing quantifiable privacy and utility guarantees.

Definition 1. [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF] A privacy mechanism M, with domain D and range O, satisfies 𝜀-differential privacy, for a given privacy budget 𝜀, if for every pair of neighboring data sets 𝐷, 𝐷 ′ ∈ D and all sets 𝑂 ⊆ O

Pr[M (𝐷) ∈ 𝑂] ≤ 𝑒 𝜀 Pr[M (𝐷 ′ ) ∈ 𝑂]
The privacy budget 𝜀 is a positive real number that represents the user-defined privacy goal [START_REF] Frank | Privacy integrated queries: an extensible platform for privacy-preserving data analysis[END_REF]. M achieves stronger privacy protection for lower values of 𝜀. Indeed, for lower values of 𝜀, the neighboring data sets 𝐷 and 𝐷 ′ (i.e., they differ by one tuple) have greater chances to produce the same output. M is chosen based on the range and sensitivity of the query function 𝑓 , the results of which it perturbs. We define the sensitivity of a query function 𝑓 for all neighboring data sets 𝐷, 𝐷 ′ ∈ D as Δ𝑓 = max 𝐷,𝐷 ′ ∈ D ∥ 𝑓 (𝐷) -𝑓 (𝐷 ′ ) ∥ 1 .

Popular privacy mechanisms.

A typical example of a differential privacy mechanism, for any function with range the set of real numbers, is the Laplace mechanism [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF]. It draws randomly a value from the probability distribution of Laplace(𝜇, 𝑏), where 𝜇 stands for the location parameter and 𝑏 > 0 is the scale parameter. In our case, 𝜇 is the original output value of 𝑓 , and 𝑏 is Δ𝑓 𝜀 . A specialization of this mechanism for location data, based on a multivariate Laplace distribution, is the Planar Laplace mechanism [START_REF] Miguel E Andrés | Geo-indistinguishability: Differential privacy for locationbased systems[END_REF].

For query functions that do not return a real number, e.g., 'What is the most visited country this year?', or in cases where perturbing the value of the output will completely destroy its utility, e.g., 'How many patients in the ICU?', most works use the Exponential mechanism [START_REF] Mcsherry | Mechanism design via differential privacy[END_REF]. Initially, a utility function 𝑢, with sensitivity Δ𝑢, maps pairs of the input value 𝑥 and output value 𝑟 to utility scores. Thereafter, the mechanism M selects an output value 𝑟 from a set of possible outputs 𝑅 with probability proportional to exp( 𝜀𝑢 (𝑥,𝑟 )

2Δ𝑢 ).

Another technique for differential privacy mechanisms is the randomized response [START_REF] Stanley | Randomized response: A survey technique for eliminating evasive answer bias[END_REF]. It is a privacy-preserving survey method that introduces probabilistic noise to the statistics of a research by randomly instructing respondents to answer truthfully or 'Yes' to a sensitive, binary question. Based on this methodology, the Random response mechanism [START_REF] Wang | Privacy-preserving data publishing: A survey on recent developments[END_REF] returns the true or flipped answer value with a probability proportional to the privacy budget 𝜀.

2.1.2 Composition. Any combination of a set of independent differential privacy mechanisms satisfying a corresponding set of privacy guarantees shall satisfy differential privacy as well, i.e., provide a differentially private output. When we apply a series of independent (i.e., in the way that they inject noise) differential privacy mechanisms on independent data, we can quantify the privacy of the resulting output by summing up the privacy loss of each individual mechanism [START_REF] Frank | Privacy integrated queries: an extensible platform for privacy-preserving data analysis[END_REF]. However when the data sets are disjoint, the final output's privacy loss equals the maximum privacy loss of the independent mechanisms.

Post-processing.

Every time a data publisher interacts with (any part of) the original data set, it is mandatory to consume some of the available privacy budget according to the composition property of differential privacy (Section 2.1.2). However, the postprocessing of a perturbed data set can be done without using any additional privacy budget as outlined in Theorem 1.

Theorem 1. [START_REF] Frank | Privacy integrated queries: an extensible platform for privacy-preserving data analysis[END_REF] The post-processing of the output of a differential privacy mechanism does not change its privacy guarantee.

Differential privacy in time series

In privacy-preserving continuous data publishing [START_REF] Katsomallos | Privacy, Space and Time: a Survey on Privacy-Preserving Continuous Data Publishing[END_REF], we consider the protection level with respect to not only the users, but also to the events occurring in the data. An event is a tuple of an identifying attribute of an individual and the sensitive data (including contextual information), and we can see it as corresponding to a record in a database where each individual may participate once. Data publishers typically release events in the form of sequences of data items, usually indexed in time order (time series) and geotagged, e.g., ('Daisy', 'at home at Montmartre at 𝑡 1 '), . . . , ('Donald', 'dining at Opera at 𝑡 1 '). We use the term 'users' to refer to the individuals, also known as participants, who are referenced in the processed and published data. Therefore, they should not be confused with the consumers of the released data sets. We further define the three levels of privacy provided to users, and highlight some works implementing them.

Event-level [START_REF] Dwork | Differential privacy under continual observation[END_REF] limits the privacy protection to any single event in a time series, providing high data utility. Wang and Zu [START_REF] Wang | CTS-DP: publishing correlated time-series data via differential privacy[END_REF] defined Correlated Time Series Differential Privacy, which guarantees that the correlation between the perturbation that is introduced by a Correlated Laplace Mechanism (CLM), and the original time series is indistinguishable. Chen et al. [START_REF] Chen | PeGaSus: Data-Adaptive Differentially Private Stream Processing[END_REF] developed PeGaSus, an algorithm for event-level differentially private stream processing that supports different categories of stream queries (counts, sliding window, and event monitoring) over multiple stream resolutions. Al-Dhubhani and Cazalas [START_REF] Al | An adaptive geoindistinguishability mechanism for continuous LBS queries[END_REF] proposed an adaptive privacy-preserving technique based on geo-indistinguishability, which adjusts the amount of noise required to obfuscate an individual's location based on its correlation level with the previously published locations.

User-level [START_REF] Dwork | Differential privacy under continual observation[END_REF] protects all the events in a time series, providing high privacy protection. Fan et al. designed FAST [START_REF] Fan | An adaptive approach to real-time aggregate monitoring with differential privacy[END_REF], an adaptive system that allows the release of real-time aggregate time series by implementing sampling, perturbation, and filtering. Chen et al. [START_REF] Chen | Differentially private sequential data publication via variable-length n-grams[END_REF] and Hua et al. [START_REF] Hua | Differentially private publication of general time-serial trajectory data[END_REF] exploited a text-processing technique, the n-gram model, i.e., a contiguous sequence of 𝑛 items from a given data sample, to release sequential data without releasing the noisy statistics (counts) of all of the possible sequences. Contrary to this approach, Li et al. [START_REF] Li | Achieving differential privacy of trajectory data publishing in participatory sensing[END_REF] focus on publishing a set of trajectories, where each one is considered as a single entry in the data set. Farokhi [START_REF] Farokhi | Temporally Discounted Differential Privacy for Evolving Datasets on an Infinite Horizon[END_REF], based on the discounted utility theory in economics, proposed temporally discounted differential privacy, a relaxation of the user-level protection that assigns different weights to the privacy budgets that have been invested in previous timestamps.

𝑤-event-level [START_REF] Kellaris | Differentially private event sequences over infinite streams[END_REF] provides privacy protection to any sequence of 𝑤 events in a time series. Based on the notion of decayed privacy [START_REF] Bolot | Private decayed predicate sums on streams[END_REF], Kellaris et al. [START_REF] Kellaris | Differentially private event sequences over infinite streams[END_REF] proposed two mechanisms (Budget Distribution and Budget Absorption) following a sliding window methodology, which effectively distribute the privacy budget (exponentially fading and uniformly) to sub-mechanisms applied on the data of a window of the stream. Cao et al. [START_REF] Cao | Differentially private real-time data release over infinite trajectory streams[END_REF] developed a framework that achieves l-trajectory privacy protection by dynamically adding noise at each timestamp, which exponentially fades over time. Wang et al. [37] presented DP-PSP which segments trajectories by taking into account points of interest in road networks and publishes privacy-preserving statistics.

Contrary to event-level, which provides privacy guarantees for a single event, user-and 𝑤-event-level offer stronger privacy protection by protecting a series of events. Event-and 𝑤-event-level better fit to scenarios of infinite data observation, whereas userlevel is more appropriate when the span of data observation is finite. 𝑤-event-is narrower than user-level protection due to its sliding window processing approach. In the extreme cases where 𝑤 is equal either to 1 or to the length of the time series, 𝑤-eventmatches event-or user-level protection, respectively.

All of the aforementioned privacy protection levels consider all events as equally significant in terms of privacy, and hence cannot be applied to scenarios that require configurability. Furthermore, they cannot be easily modified to differentiate among events and adapt to the notion of landmarks. To fill this gap, we propose the novel privacy notion of landmark privacy, which guarantees differential privacy while accounting for landmarks.

Privacy loss under temporal correlation

Cao et al. [START_REF] Cao | Quantifying differential privacy in continuous data release under temporal correlations[END_REF] proposed a method for computing the temporal privacy loss (TPL) of a differential privacy mechanism in the presence of temporal correlation and background knowledge. The goal of their technique is to guarantee privacy protection and to bound the overall privacy loss at every timestamp under the assumption of independent data releases. It calculates TPL as the sum of the backward and forward temporal privacy loss, 𝛼 𝐵 𝑡 and 𝛼 𝐹 𝑡 , minus the default privacy loss 𝜀 of the mechanism (because it is counted twice in the aforementioned entities). This calculation is done for each individual included in the original data set and the overall TPL is equal to the maximum calculated value at every timestamp. 𝛼 𝐵 𝑡 (or 𝛼 𝐹 𝑡 ) at any timestamp depends on the 𝛼 𝐵 𝑡 (or 𝛼 𝐹 𝑡 ) at the previous/next timestamp, the backward/forward temporal correlation, and 𝜀 as described in Definition 2. Definition 2. [START_REF] Cao | Quantifying differential privacy in continuous data release under temporal correlations[END_REF] The potential privacy loss of a privacy mechanism at a timestamp 𝑡 ∈ 𝑇 due to a series of outputs (𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈𝑇 and temporal correlation in its input 𝐷 𝑡 with respect to any adversary, targeting an individual with potential data items 𝑥 𝑡 (or 𝑥 ′ 𝑡 ) and having knowledge

D 𝑡 equal to 𝐷 𝑡 -{𝑥 𝑡 } (or 𝐷 ′ 𝑡 -{𝑥 ′ 𝑡 }), is 𝛼 𝑡 = sup 𝑥 𝑡 ,𝑥 ′ 𝑡 ,(𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈𝑇 ln Pr[(𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈𝑇 |𝑥 𝑡 , D 𝑡 ] Pr[(𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈𝑇 |𝑥 ′ 𝑡 , D 𝑡 ] (1)
By analyzing Equation 1 we get the following

(1) = sup 𝑥 𝑡 ,𝑥 ′ 𝑡 ,(𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈ [min(𝑇 ),𝑡 ] ln Pr[(𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈ [min(𝑇 ),𝑡 ] |𝑥 𝑡 , D 𝑡 ] Pr[(𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈ [min(𝑇 ),𝑡 ] |𝑥 ′ 𝑡 , D 𝑡 ] Backward privacy loss (𝛼 𝐵 𝑡 ) + sup 𝑥 𝑡 ,𝑥 ′ 𝑡 ,(𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈ [𝑡,max(𝑇 ) ] ln Pr[(𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈ [𝑡,max(𝑇 ) ] |𝑥 𝑡 , D 𝑡 ] Pr[(𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈ [𝑡,max(𝑇 ) ] |𝑥 ′ 𝑡 , D 𝑡 ] Forward privacy loss (𝛼 𝐹 𝑡 ) -sup 𝑥 𝑡 ,𝑥 ′ 𝑡 ,𝑜 𝑜 𝑜 𝑡 ln Pr[𝑜 𝑜 𝑜 𝑡 |𝑥 𝑡 , D 𝑡 ] Pr[𝑜 𝑜 𝑜 𝑡 |𝑥 ′ 𝑡 , D 𝑡 ] Present privacy loss (𝜀 𝑡 ) (2)
The intuition behind [START_REF] Cao | Quantifying differential privacy in continuous data release under temporal correlations[END_REF] is that a stronger temporal correlation results in higher privacy loss. When the transition matrix becomes sufficiently large, then the loss decreases due to the fact that larger matrices result in more uniform distributions. The authors investigate briefly all of the possible privacy levels; however, the solutions that they propose are applied only on the event-level.

LANDMARK PRIVACY

In this section, we introduce a new privacy definition, motivate its importance, and propose the methodology for achieving it.

Problem description and definition

Users generate a finite series of sensitive data over time, which are processed in batch mode in a secure and private way locally (or by a trusted curator) and are later published in order to be consumed by potentially adversarial data analysts. Data are produced as a series of events, which we call time series.

We argue that in continuous user-generated data publishing, events are not equally significant in terms of privacy. We term a significant event-according to user-or data-related criteria-as a landmark event. The identification of landmark events can be performed manually or automatically, and is an orthogonal problem to ours. First, we consider the landmark timestamps, i.e., their position in time, non-sensitive and provided by the user as input along with the privacy budget 𝜀. For example, events 𝑝 1 , 𝑝 3 , 𝑝 5 , 𝑝 8 in Figure 1 are landmark events. In Section 3.4, we extend our privacy framework to protect landmark timestamps when they are considered privacy-sensitive.

Definition 3 extends the notion of neighboring data sets (see Section 2.1) to the context of landmarks. Intuitively, 𝑆 𝑇 , 𝑆 ′ 𝑇 are pairwise, i.e., at the same timestamps, equal or neighboring and their neighboring elements are on common landmarks and/or at most on one regular event. Definition 3 allows us to guarantee at any timestamp 𝑡 that, given a set of landmark timestamps 𝐿 in a time series, all data sets corresponding to 𝐿 ∪ {𝑡 } are protected. Thus, we proceed to define landmark privacy (Definition 4), a configurable variation of differential privacy for time series with significant events. Definition 4 (Landmark privacy). Let M be a privacy mechanism with range O and domain S 𝑇 being the set of all time series with length |𝑇 |, where 𝑇 is a sequence of timestamps, and 𝐿 ⊆ 𝑇 be a set of landmark timestamps. M satisfies (𝜀, 𝐿)-landmark privacy if for all sets 𝑂 ⊆ O, and for every pair of L-landmark neighboring time series

𝑆 𝑇 , 𝑆 ′ 𝑇 , it holds that 𝑃𝑟 [M (𝑆 𝑇 ) ∈ 𝑂] ≤ 𝑒 𝜀 𝑃𝑟 [M (𝑆 ′ 𝑇 ) ∈ 𝑂]
User-level privacy can achieve landmark privacy, but it overperturbs the final data by not distinguishing between landmark and regular events. Theorem 2 states how to achieve the desired privacy goal for the landmarks and any event, i.e., a total budget less than 𝜀, and at the same time provide better utility overall. Theorem 2. Let M be a mechanism with input a time series 𝑆 𝑇 , where 𝑇 is the set of the involved timestamps, and 𝐿 ⊆ 𝑇 be the set of landmark timestamps. M is decomposed to 𝜀-differential private sub-mechanisms M 𝑡 , for every 𝑡 ∈ 𝑇 , which apply independent randomness to the event at 𝑡. Then, given a privacy budget 𝜀, M satisfies (𝜀, 𝐿)-landmark privacy if for any 𝑡 it holds that ∑

𝑖 ∈𝐿∪{𝑡 } 𝜀 𝑖 ≤ 𝜀
Proof. All mechanisms use independent randomness, and therefore for a time series 𝑆 𝑇 = (𝐷 𝑖 ) 𝑖 ∈𝑇 and outputs

(𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈𝑇 ∈ 𝑂 ⊆ O it holds that 𝑃𝑟 [M (𝑆 𝑇 ) = (𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈𝑇 ] = 𝑖 ∈𝑇 𝑃𝑟 [M 𝑖 (𝐷 𝑖 ) = 𝑜 𝑜 𝑜 𝑖 ]
Likewise, for any landmark-neighboring time series 𝑆 ′ 𝑇 of 𝑆 𝑇 with the same outputs

(𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈𝑇 ∈ 𝑂 ⊆ O 𝑃𝑟 [M (𝑆 ′ 𝑇 ) = (𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈𝑇 ] = 𝑖 ∈𝑇 𝑃𝑟 [M 𝑖 (𝐷 ′ 𝑖 ) = 𝑜 𝑜 𝑜 𝑖 ]
According to Definition 3, there exists 𝐿 ∪ {𝑡 } ⊆ 𝑇 such that 𝐷 𝑖 = 𝐷 ′ 𝑖 for 𝑖 ∈ 𝐿 ∪ {𝑡 }. Thus, we get

𝑃𝑟 [M (𝑆 𝑇 ) = (𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈𝑇 ] 𝑃𝑟 [M (𝑆 ′ 𝑇 ) = (𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈𝑇 ] = 𝑖 ∈𝐿∪{𝑡 } 𝑃𝑟 [M 𝑖 (𝐷 𝑖 ) = 𝑜 𝑜 𝑜 𝑖 ] 𝑃𝑟 [M 𝑖 (𝐷 ′ 𝑖 ) = 𝑜 𝑜 𝑜 𝑖 ]
𝐷 𝑖 and 𝐷 ′ 𝑖 are neighboring for 𝑖 ∈ 𝐿 ∪ {𝑡 }. M 𝑖 is differential private and from Definition 1 we get that

𝑃𝑟 [ M 𝑖 (𝐷 𝑖 )=𝑜 𝑜 𝑜 𝑖 ] 𝑃𝑟 [ M 𝑖 (𝐷 ′ 𝑖 )=𝑜 𝑜 𝑜 𝑖 ] ≤ 𝑒 𝜀 𝑖 . Hence, we can write 𝑃𝑟 [M (𝑆 𝑇 ) = (𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈𝑇 ] 𝑃𝑟 [M (𝑆 ′ 𝑇 ) = (𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈𝑇 ] ≤ 𝑖 ∈𝐿∪{𝑡 } 𝑒 𝜀 𝑖 = 𝑒 𝑖 ∈𝐿∪{𝑡 } 𝜀 𝑖

Achieving landmark privacy

In this section, we present schemes to achieve landmark privacy. Uniform. Figure 3a shows the implementation of the baseline landmark privacy scheme for Example 1.2 which distributes uniformly the available privacy budget 𝜀. In this case, it is enough to distribute at each timestamp the total privacy budget divided by the number of timestamps corresponding to landmarks, plus one, i.e., 𝜀 |𝐿 |+1 . Consequently, at each timestamp we protect every landmark, while reserving a part of 𝜀 for the current timestamp.

Skip. One might argue that we could skip the landmark data releases as we demonstrate in Figure 3b, by republishing previous, regular event releases. This would result in preserving all of the available privacy budget for regular events, equivalently to eventlevel protection, i.e., 𝜀 𝑖 = 𝜀, ∀𝑖 ∈ 𝑇 \ 𝐿.

In practice, however, this approach can eventually pose arbitrary privacy risks, especially when dealing with geotagged data. Particularly, sporadic location data publishing or misapplying location cloaking could result in areas with sparse data points, indicating privacy-sensitive locations [START_REF] Gambs | Show me how you move and I will tell you who you are[END_REF][START_REF] Russell | Fitness app Strava exposes the location of military bases[END_REF]. We study this problem and investigate possible solutions in Section 3.4.

Adaptive. Next, we propose an adaptive privacy scheme (Figure 4) that accounts for changes in the sequence of sensitive data sets (𝐷 𝑖 ) 𝑖 ∈𝑇 by analyzing the respective private data releases (𝑜 𝑜 𝑜 𝑖 ) 𝑖 ∈𝑇 , and thus exploiting the post-processing property of differential privacy (Theorem 1). Initially, the budget management component reserves uniformly the available privacy budget 𝜀 for each future release o. At each timestamp, the processing component decides to either sample from the time series the current input and publish it with noise or release an approximation based on previous releases. In the case when it publishes with noise the original data, the analysis component estimates the data trends by calculating the difference between the current and the previous releases and compares the difference with the scale of the perturbation, i.e., Δ𝑓 𝜀 [START_REF] Kellaris | Differentially private event sequences over infinite streams[END_REF]. The outcome of this comparison determines the adaptation of the sampling rate of the processing component for the next events: if the difference is greater it means that the data trends are evolving, and therefore it must increase the sampling rate. When the mechanism approximates a landmark (but not a regular timestamp), the budget management component distributes the reserved privacy budget to the next timestamps. Due to Theorem 1, the analysis component does not consume any privacy budget allowing for better data utility.

Landmark privacy under temporal correlation

From the discussion so far, it is evident that for the budget distribution it is not the positions, but rather the number of the landmarks that matters. However, this is not the case under the presence of temporal correlation. The Hidden Markov Model scheme (as used in [START_REF] Cao | Quantifying differential privacy in continuous data release under temporal correlations[END_REF]) stipulates two important independence properties: (i) the future (or past) depends on the past (or future) via the present, and (ii) the current observation is independent of the rest given the current state. Hence, there is independence between an observation at a specific timestamp and previous/next data sets under the presence of the current input data set. Intuitively, knowing the data set at timestamp 𝑡 stops the propagation of the Markov chain towards the next or previous timestamps in the time series.

In Section 2.3 we showed that the temporal privacy loss 𝛼 𝑡 at a timestamp 𝑡 is calculated as the sum of the backward and forward privacy loss, 𝛼 𝐵 𝑡 and 𝛼 𝐹 𝑡 , minus the privacy budget 𝜀 𝑡 , to account for the extra privacy loss due to previous and next releases 𝑜 𝑜 𝑜 of M under temporal correlation. By Theorem 2, at every timestamp 𝑡 we consider the data at 𝑡 and at the landmark timestamps 𝐿. When sequentially composing the data releases for each timestamp 𝑖 in 𝐿∪ {𝑡 } we consider the previous releases in the whole time series until the timestamp 𝑖 -that is exactly before 𝑖 in the ordered 𝐿 ∪ {𝑡 }, and the next data releases in the whole time series until the timestamp 𝑖 + that is exactly after 𝑖 in the ordered 𝐿 ∪ {𝑡 }.

𝛼 𝐵 𝑖 + ln Pr[(𝑜 𝑜 𝑜) 𝑖 ∈ [𝑖,𝑖 + -1] |𝐷 𝑖 ] Pr[(𝑜 𝑜 𝑜) 𝑖 ∈ [𝑖,𝑖 + -1] |𝐷 ′ 𝑖 ] 𝛼 𝐹 𝑖 -ln Pr[𝑜 𝑜 𝑜 𝑖 |𝐷 𝑖 ] Pr[𝑜 𝑜 𝑜 𝑖 |𝐷 ′ 𝑖 ] 𝜀 𝑖 (3)
As presented in [START_REF] Cao | Quantifying differential privacy in continuous data release under temporal correlations[END_REF], the temporal privacy loss of a time series (without landmarks) can be bounded by a given privacy budget 𝜀. Intuitively, by Equation 3 the temporal privacy loss incurred when considering landmarks is less than the temporal loss in the case without the knowledge of the landmarks. Thus, the temporal privacy loss in landmark privacy can be also bounded by 𝜀.

Protecting landmarks

So far, we assumed that the timestamps in the landmark set 𝐿 are not privacy-sensitive, and therefore we used them in our schemes as they were. This may pose a direct or indirect privacy risk to the users. For the former, we consider the case where we desire to publish 𝐿 as complimentary information to the release of the event values. For the latter, a potentially adversarial data analyst may infer 𝐿 by observing the values of the privacy budget, which is usually an inseparable attribute of the data release as an indicator of the privacy guarantee to the users and as an estimate of the data utility to the analysts. Hence, in both cases, a user-defined 𝐿, which is supposed to facilitate the configurable privacy protection of the user, could end up posing a privacy risk to them.

In Example 3.1, we demonstrate the extreme case of the application of the Skip landmark privacy scheme from Figure 3b, where we approximate landmarks with the latest data release and invest all of the available privacy budget to regular events. Example 3.1. Figure 6 shows the privacy risk that the application of a landmark privacy scheme that nullifies or approximates outputs, similar to Skip, might cause. We point out in red the details that might cause indirect information inference. In this extreme case, the minimization of the privacy budget in combination with nullifying the output (either by not publishing or by adding a lot of noise) or approximating the current output with previously released outputs might hint to any adversary that the current event is a landmark. Apart from the privacy budget that we invested at landmarks, we can observe a pattern for the budgets at regular events as well. Therefore, an adversary who observes the values of the privacy budget can easily infer not only the number but also the exact temporal position of the landmarks.

The main idea of the privacy-preserving dummy landmark selection module is to privately select extra landmark event timestamps, i.e., dummy landmarks, from the set of timestamps 𝑇 \ 𝐿 of the time series 𝑆 𝑇 and add them to the original landmark set 𝐿. Selecting extra events, on top of the actual landmarks, as dummy landmarks, can render the actual ones indistinguishable. The goal is to create a new set 𝐿 ′ such that 𝐿 ⊂ 𝐿 ′ ⊆ 𝑇 .

First, we generate a set of dummy landmark set options by adding regular event timestamps from 𝑇 \ 𝐿 to 𝐿 (Section 3.4.1). Then, we utilize the exponential mechanism, with a utility function that calculates an indicator for each of the options in the set, based on how much it differs from the original landmark set 𝐿, and randomly select one of the options (Section 3. 4.2). This process provides an extra layer of privacy protection to landmarks, and thus allows the processing, and thereafter releasing, of landmark timestamps.

Dummy landmark selection.

Optimal. The Optimal algorithm generates every possible combination (options) of landmark sets 𝐿 ′ containing one set from every possible size, i.e, |𝐿| + 1, |𝐿| + 2, . . . , |𝑇 |. Each 𝐿 ′ contains the original landmarks along with timestamps of regular events from 𝑇 \ 𝐿 (dummy landmarks). Then, it evaluates each option by comparing each of its sets with the original landmark set 𝐿 and estimating an overall similarity score for each option. We discuss possible utility score functions later on in Section 3.4.2. The goal of this process is to select the option that contains the combination of dummy landmark sets that achieve the best score.

This procedure guarantees to return the optimal option with regard to the original set 𝐿. However, it is rather costly in terms of complexity. In more detail, given |𝑇 \ 𝐿| regular events and a combination of size 𝑟 , it requires 𝑂 (𝐶 (|𝑇 \ 𝐿|, 𝑟 ) + 2 𝐶 ( |𝑇 \𝐿 |,𝑟 ) ) time and 𝑂 (𝑟 * 𝐶 (|𝑇 \𝐿|, 𝑟 )) space. Next, we present a Heuristic solution with improved time and space requirements.

Heuristic. The Heuristic algorithm follows an incremental methodology and at each step it selects a new timestamp, corresponding to a regular event from 𝑇 \ 𝐿 ′ . In this case, the elements of 𝐿 ′ at each step differ by one from the one that the algorithm selected in the previous step. Similar to the Optimal, it selects a new set based on a predefined similarity metric until it selects a set that is equal to the size of the series of events, i.e., 𝐿 ′ = 𝑇 .

In terms of complexity, given |𝑇 \ 𝐿| regular events, the Heuristic requires 𝑂 (|𝑇 \ 𝐿| 2 ) time and space. Note that the reverse process, i.e., starting with 𝑇 landmarks and removing until |𝐿 ′ | = |𝐿| + 1, performs similarly.

Partitioned. We improve the complexity of the Heuristic algorithm by partitioning the landmark timestamp sequence 𝐿. The novelty of this algorithm lies in the fact that it deals with the event series as a histogram which allows it to take advantage of its relevant features and methodology. Particularly, it uses the Freedman-Diaconis rule, which is resilient to outliers and takes into account the data variability and data size [START_REF] Meshgi | Expanding histogram of colors with gridding to improve tracking accuracy[END_REF], and generates a histogram from the landmark set 𝐿. This way, it achieves an improved complexity, compared to the Heuristic, that is dependent on the histogram's bin size. Algorithm 1 demonstrates the overall process.

Function ). In the end, it returns opts which contains all the versions of hist that are closest to the original hist for all possible bin sizes of hist.

Privacy-preserving option selection.

The algorithms that we presented in Section 3.4.1 return a set of possible versions of the original landmark set 𝐿 by adding extra timestamps in it from the series of events at timestamps 𝑇 \ 𝐿. In the next step, we randomly select a set by utilizing the exponential mechanism (Section 2.1.1).

For this procedure, we allocate a small fraction of the available privacy budget, i.e., 1% or even less (see Section 4.3.2 for more details), which adds up to that of the publishing scheme according to the sequential composition theorem.

Utility score function. Prior to selecting a landmark timestamp set including the original along with dummy landmarks, the exponential mechanism evaluates each set using a utility score function.

We present here two ways of doing so. One way to evaluate each set is by taking into account the temporal position of the events in the sequence. Events that occur at recent timestamps are more likely to reveal sensitive information regarding the users involved [START_REF] Kellaris | Differentially private event sequences over infinite streams[END_REF]. Hence, indicating the existence of dummy landmarks nearby actual landmarks can increase the adversarial confidence regarding the location of the latter within a series of events. In other words, sets with dummy landmarks with less average temporal distance from actual landmarks achieve better utility scores.

Another approach for the utility score function is to consider the number of events in each set. Sets with more dummy landmarks may render actual landmarks more indistinguishable, and therefore provide less utility. Consequently, more dummy landmarks lead to distributing the privacy budget to more events, and therefore leading to more robust overall privacy protection.

Option release. In the last step, the privacy-preserving dummy landmark selection module releases a new landmark set (including the original landmarks along with the dummy ones) from the options that were generated in the previous step, by utilizing the exponential mechanism.

The options generated by the Optimal and Heuristic algorithms contain actual timestamps that can be utilized directly by the landmark privacy schemes that we presented in Section 3.2. However, the Partitioned algorithm returns histograms instead of timestamps. Therefore, we need to process the result of the exponential mechanism further by sampling without replacement from the set 𝑇 \ 𝐿 according to the selected histogram's probability density function.

EXPERIMENTAL EVALUATION

In this section we present the experiments that we performed in order to evaluate landmark privacy on real and synthetic data sets. Section 4.1 contains all the details regarding the data sets the we used for our experiments along with the system configurations. Section 4.2 evaluates the data utility of the landmark privacy schemes that we designed in Section 3.2 in comparison to user and event level, and investigates the behavior of the privacy loss under temporal correlation for different distributions of landmarks. Section 4.3 justifies our decisions while designing the privacy-preserving dummy landmark selection module in Section 3.4 and the data utility impact of the latter.

Configurations and data sets

We implemented our experiments 2 in Python 3.9.7 and executed them on a machine with an Intel i7-6700HQ at 3.5GHz CPU and 16GB RAM, running Manjaro Linux 21.1.5. We repeated each experiment 100 times and we report the mean over these iterations.

Data sets.

Real data sets. For consistency, we sample from each of the following data sets the first 1, 000 entries that satisfy the configuration criteria that we discuss in detail in Section 4.1.2.

Copenhagen [START_REF] Sapiezynski | Interaction data from the copenhagen networks study[END_REF] data set was collected via the smartphone devices of 851 university students over a period of 4 week as part of the Copenhagen Networks Study. Each device was configured to be discoverable by and to discover nearby Bluetooth devices every 5 minutes. Upon discovery, each device registers (i) the timestamp in seconds, (ii) the device's unique identifier, (iii) the unique identifier of the device that it discovered (-1 when no device was found or -2 for any non-participating device), and (iv) the Received Signal Strength Indicator (RSSI) in dBm. Half of the devices have registered data at at least 81% of the possible timestamps. 3 devices (449, 550, 689) satisfy our configuration criteria (Section 4.1.2) within their first 1, 000 entries. From those 3 devices, we picked the first one, i.e., device with identifier '449', and utilized its 1, 000 first entries out of 12, 167 unique valid contacts. 2 Source code available at https://gitlab.com/crabbysalmon/codaspy22 HUE [START_REF] Makonin | HUE: The hourly usage of energy dataset for buildings in British Columbia[END_REF] contains the hourly energy consumption data of 22 residential customers of BCHydro, a provincial power utility in British Columbia. The measurements for each residence are saved individually and each measurement contains (i) the date (YYYY-MM-DD), (ii) the hour, and (iii) the energy consumption in kWh.

In our experiments, we used the first residence, i.e., residence with identifier '1', that satisfies our configuration criteria (Section 4.1.2) within its first 1, 000 entries. In those entries, out of a total of 29, 231 measurements, we estimated an average energy consumption equal to 0.88kWh and a value range within [0. 28, 4.45].

T-drive [START_REF] Yuan | T-drive: driving directions based on taxi trajectories[END_REF] consists of 15 million GPS data points of the trajectories of 10, 357 taxis in Beijing, spanning a period of 1 week and a total distance of 9 million kilometers. The taxis reported their location data on average every 177 seconds and 623 meters approximately. Each vehicle registers (i) the taxi unique identifier, (ii) the timestamp (YYYY-MM-DD HH:MM:SS), (iii) longitude, and (iv) latitude. These measurements are stored individually per vehicle. We sampled the first 1000 data items of the taxi with identifier '2', which satisfied our configuration criteria (Section 4.1.2). Synthetic. We generated synthetic time series of length equal to 100 timestamps, for which we varied the number and distribution of landmarks. In this way, we have a controlled data set that we can use to study the behavior of our proposal. We take into account only the temporal order of the points and the position of regular and landmark events within the time series. In Section 4.1.2, we explain in more detail our configuration criteria.

Configurations.

In this section we discuss how we tune relevant parameters of the problem for the experiments. First, we vary the landmark percentage, i.e., the ratio of timestamps that we attribute to landmarks and regular events, in order to explore the behavior of our methodology in all possible scenarios. Second, for each data set, we implement a privacy mechanism that injects noise related to the type of its attribute values and we tune the parameters of each scheme accordingly. Third, we explain how we generate synthetic data sets with various degrees of temporal correlation so as to observe the impact on the temporal privacy loss.

Landmark percentage. In the Copenhagen data set, a landmark represents a timestamp at which a specific contact device is registered. After identifying the unique contacts within the sample, we achieve each desired landmarks to regular events ratio by considering a list that contains a part of these contact devices. In more detail, we achieve 0% landmarks by considering an empty list of contact devices, 20% by extending the list with [3, [START_REF] Miguel E Andrés | Geo-indistinguishability: Differential privacy for locationbased systems[END_REF][START_REF] Chen | PeGaSus: Data-Adaptive Differentially Private Stream Processing[END_REF][START_REF] John C Duchi | Local privacy and statistical minimax rates[END_REF][START_REF] Li | Mining user similarity based on location history[END_REF][START_REF] Meshgi | Expanding histogram of colors with gridding to improve tracking accuracy[END_REF][START_REF] Wang | Privacy-preserving data publishing: A survey on recent developments[END_REF][START_REF] Stanley | Randomized response: A survey technique for eliminating evasive answer bias[END_REF]41,46,47 [181,182,192,195,196,201,203,207,221,230,235,237,239,241, 254], 80% with [260,282,287,289,290,291,308,311,318,323,324,330,334,335,344,350,353,355,357,358,361,363], and 100% by including all of the possible contacts.

In HUE, we consider as landmarks the events that have energy consumption values below a certain threshold. More precisely, we get 0%, 20% 40%, 60%, 80%, and 100% landmarks by setting the energy consumption threshold at 0.28kWh, 1.12kWh, 0.88kWh, 0.68kWh, 0.54kWh, and 4.45kWh respectively.

In T-drive, a landmark represents a location where a vehicle stopped for some time. We achieved the desired landmark percentages by utilizing the method of Li et al. [START_REF] Li | Mining user similarity based on location history[END_REF] for detecting stay points in trajectory data. In more detail, the algorithm checks for each data item if each subsequent item is within a given distance threshold Δ𝑙 and measures the time period Δ𝑡 between the present point and the last subsequent point. After analyzing the data and experimenting with different pairs of distance and time period, we achieve 0%, 20% 40%, 60%, 80%, and 100% landmarks by setting the (Δ𝑙 in meters, Δ𝑡 in minutes) pairs input to the stay point discovery method as [(0, 1000), (2095, 30), (2790, 30), (3590, 30), (4825, 30), (10350, [START_REF] Primault | The Long Road to Computational Location Privacy: A Survey[END_REF]].

We generated synthetic data with skewed (the landmarks are distributed towards the beginning/end of the series), symmetric (in the middle), bimodal (both end and beginning), and uniform (all over the time series) landmark distributions. In order to get landmark sets with the above distribution features, we generate probability distributions with restricted domain to the beginning and end of the time series, and sample from them, without replacement, the desired number of points. For each case, we place the location, i.e., centre, of the distribution accordingly. More precisely, for symmetric we put the location in the middle of the time series and for left/right skewed to the right/left. For bimodal we combine two mirrored skewed distributions. Finally, for the uniform distribution we distribute the landmarks randomly throughout the time series. For consistency, we calculate the scale parameter of the corresponding distribution depending on the length of the time series by setting it equal to the series' length over a constant.

Privacy parameters. For all the real data sets, we implement 𝜀differential privacy by selecting a mechanism from those that we described in Section 2.1.1 that is better suited for the type of its sensitive attributes. To perturb the contact tracing data of the Copenhagen data set, we utilize the random response technique [START_REF] Wang | Locally differentially private protocols for frequency estimation[END_REF], and at each timestamp we report truthfully, with probability 𝑝 = 𝑒 𝜀 𝑒 𝜀 +1 , whether the current contact is a landmark or not. We randomize the energy consumption in HUE with the Laplace mechanism [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF]. For T-drive, we perturb the location data with noise that we sample from the Planar Laplace mechanism [START_REF] Miguel E Andrés | Geo-indistinguishability: Differential privacy for locationbased systems[END_REF].

We set the privacy budget 𝜀 = 1 for all of our experiments and, for simplicity, we assume that for every query sensitivity it holds that Δ𝑓 = 1. Note that changing the value of 𝜀 would not affect the conclusions we drive from the experiments (even though the range of the results would change). For the experiments that we performed on the synthetic data sets, the original values to be released are not relevant to what we want to observe, and thus we ignore them.

Temporal correlation. Despite the inherent presence of temporal correlation in time series, it is challenging to correctly discover and quantify it. For this reason, and in order to create a more controlled environment for our experiments, we chose to conduct tests relevant to temporal correlation using synthetic data sets. We model the temporal correlation in the synthetic data as a stochastic matrix 𝑃, using a Markov Chain [START_REF] Paul | Markov Chains: From Theory to Implementation and Experimentation[END_REF]. 𝑃 is an 𝑛 ×𝑛 matrix, where the element 𝑃 𝑖 𝑗 represents the transition probability from a state 𝑖 to another state 𝑗, ∀𝑖, 𝑗 ≤ 𝑛. It holds that the elements of every row 𝑗 of 𝑃 sum up to 1. We follow the Laplacian smoothing technique [START_REF] Sorkine | Laplacian surface editing[END_REF], as utilized in [START_REF] Cao | Quantifying differential privacy in continuous data release under temporal correlations[END_REF], to generate the matrix 𝑃 with a degree of temporal correlation 𝑠 > 0 equal to (𝐼 𝑛 ) 𝑖 𝑗 + 𝑠 𝑛 𝑘=1 ((𝐼 𝑛 ) 𝑗𝑘 + 𝑠) where 𝐼 𝑛 is an identity matrix of size 𝑛. The value of 𝑠 is comparable only for stochastic matrices of the same size and dictates the strength of the correlation; the lower its value, the stronger the correlation degree. In our experiments, for simplicity, we set 𝑛 = 2 and we investigate the effect of weak (𝑠 = 1), moderate (𝑠 = 0.1), and strong (𝑠 = 0.01) temporal correlation degree on the temporal privacy loss.

Landmark events

In this section, we present the experiments that we performed, to test the methodology that we presented in Section 3.2, on real and synthetic data sets.

With the experiments on the real data sets (Section 4.2.1), we show the performance in terms of data utility of our three landmark privacy schemes: Skip, Uniform and Adaptive. We define data utility as the mean absolute error introduced by the privacy mechanism. We compare with the event-and user-level differential privacy protection levels, and show that, in the general case, landmark privacy allows for better data utility than user-level differential privacy while balancing between the two protection levels.

With the experiments on the synthetic data sets (Section 4.2.2) we show how the temporal privacy loss, i.e., the privacy budget 𝜀 with the extra privacy loss because of the temporal correlation, changes when tuning the size and statistical characteristics of the input landmark set 𝐿. We observe that a greater average landmark-regular event distance in a time series can result into greater temporal privacy loss under moderate and strong temporal correlation. 4.2.1 Landmark privacy schemes. Figure 7 exhibits the performance (bars) of the three schemes, Skip, Uniform, and Adaptive applied on the three data sets that we study. Notice that, in the cases when we have 0% and 100% of the events being landmarks, we get the same behavior as in event-and user-level privacy respectively. This happens due the fact that at each timestamp we take into account only the data items at the current timestamp and ignore the rest of the time series (event-level) when there are no landmarks. Whereas, when each timestamp corresponds to a landmark we consider and protect all the events throughout the entire series (user-level).

For the Copenhagen data set (Figure 7a), Adaptive has an overall consistent performance and works best for 60% and 80% landmarks. We notice that for 0% landmarks, it achieves better utility than the event-level protection due to the combination of more available privacy budget per timestamp (due to the absence of landmarks) and its adaptive sampling methodology. Skip excels, compared to the others, at cases where it needs to approximate 20%, 40%, or 100% of the times. In general, we notice that, for this data set and due to the application of the random response technique, it is more beneficial to either invest more privacy budget per event or prefer approximation over introducing randomization.

The combination of the small range of measurements ([0.28, 4.45] with an average of 0.88kWh) in HUE (Figure 7b) and the large scale in the Laplace mechanism, allows for schemes that favor approximation over noise injection to achieve a better performance in terms of data utility. Hence, Skip achieves a constant low mean absolute error. Regardless, the Adaptive scheme performs by far better than Uniform and balances between event-and user-level protection for all landmark percentages.

In T-drive (Figure 7c), Adaptive outperforms Uniform by 10%-20% for all landmark percentages greater than 40% and Skip by more than 20%. The lower density (average distance of 623m) of the T-drive data set has a negative impact on the performance of Skip because republishing a previous perturbed value is now less accurate than perturbing the current location.

Principally, we can claim that the Adaptive is the most reliable and best performing scheme, if we consider the drawbacks of Skip, particularly in spatiotemporal data, e.g., sporadic location data publishing or misapplying location cloaking, that could lead to the indication of privacy-sensitive attribute values [START_REF] Gambs | Show me how you move and I will tell you who you are[END_REF][START_REF] Russell | Fitness app Strava exposes the location of military bases[END_REF]. Moreover, implementing a more data-dependent sampling method that accounts for changes in the trends of the input data and adapts its rate accordingly, would result in a more effective budget allocation that would improve the performance of Adaptive in terms of data utility. We defer this study for the future.

Temporal distance and correlation.

Figure 8 shows a comparison of the average temporal distance of the events from the previous/next landmark or the start/end of the time series for various distributions in our synthetic data. More specifically, we model the distance of an event as the count of the total number of events between itself and the nearest landmark or the time series edge.

We observe that the uniform and bimodal distributions tend to limit the regular event-landmark distance. This is due to the fact that the former scatters the landmarks, while the latter distributes them on both edges, leaving a shorter space uninterrupted by landmarks. On the contrary, distributing the landmarks at one part of the sequence, as in skewed or symmetric, creates a wider space without landmarks. This study provides us with different distance settings, to be used in the subsequent temporal privacy loss study. Figure 9 illustrates a comparison among the aforementioned distributions regarding the temporal privacy loss under (a) moderate, and (b) strong temporal correlation degrees. The line shows the overall privacy loss-for all cases of landmark distribution-without temporal correlation. The privacy loss under a weak correlation degree converges with all possible distributions for all landmark percentages, and thus we omit its presentation. In combination with Figure 8, we conclude that a greater average landmark-regular event distance in a distribution can result into greater temporal privacy loss under moderate and strong temporal correlation. This is due to the fact that the backward/forward privacy loss accumulates more over time in wider spaces without landmarks (see Section 2.3). Furthermore, the behavior of the privacy loss is as expected regarding the temporal correlation degree: a stronger correlation degree generates higher privacy loss while widening the gap between the different distribution cases. On the contrary, a weaker correlation degree makes it harder to differentiate among the landmark distributions.

Selection of dummy landmarks

In this section, we present the experiments on the methodology for the dummy landmark selection presented in Section 3.4, on the real and synthetic data sets. Due to the high complexity of the Optimal and Heuristic algorithms, we choose to evaluate only the Partitioned, which is the optimized solution that we designed. With the experiments on the synthetic data sets (Section 4.3.1) we show the normalized Euclidean and Wasserstein distance metrics (not to be confused with the temporal distances in Figure 8) of the time series histograms for various distributions and landmark percentages. This allows us to justify our design decisions for our concept that we showcased in Section 3.4. With the experiments on the real data sets (Section 4.3.3), we show the performance in terms of utility of our three landmark schemes in combination with the privacy-preserving dummy landmark selection module, which enhances the privacy protection that our concept provides. Comparing the results of the Euclidean distance in Figure 10a with those of the Wasserstein in Figure 10b we conclude that the Euclidean distance provides more consistent results for all possible distributions. The maximum difference per landmark percentage is approximately 0.2 for the former and 0.15 for the latter between the bimodal and skewed landmark distributions. Overall, the Euclidean distance achieves a mean normalized distance of 0.3, while the Wasserstein distance a mean normalized distance that is equal to 0.2. Therefore, and by observing Figure 10, Wasserstein demonstrates a less consistent performance and less linear behavior among all possible landmark distributions. Thus, we choose to utilize the Euclidean distance metric for the implementation of the privacypreserving dummy landmark selection module in Section 3.4.

Privacy budget tuning.

In Figure 11, we test the Uniform mechanism in real data by investing different ratios (1%, 10%, 25%, and 50%) of the available privacy budget 𝜀 in the dummy landmark selection module and the remaining to perturbing the original data values, in order to figure out the optimal ratio value. Uniform is our baseline implementation, and hence allows us to derive more accurate conclusions in this case. In general, we are expecting to observe that greater ratios will result in more accurate, i.e., smaller, landmark sets and less accurate values in the released data. The randomized response mechanism is tolerant to the fluctuations of the privacy budget, and hence its application to the Copenhagen data set (Figure 11a) results in a constant performance in terms of data utility. For HUE (Figure 11b) and T-drive (Figure 11c), we observe that our implementation performs better for lower ratios, e.g., 0.01, where we end up allocating the majority of the available privacy budget to the data release process instead of the dummy landmark selection module. The results of this experiment indicate that we can safely allocate the majority of 𝜀 to the data publishing process, and therefore achieve better data utility, while guaranteeing more robust privacy protection. In comparison with the utility performance without the dummy landmark selection module (solid bars), we notice a slight deterioration for all three schemes (markers). This is natural since we allocated part of the available privacy budget to the privacypreserving dummy landmark selection module, which in turn increased the number of landmarks, except for the case of 100% landmarks. Therefore, there is less privacy budget available for data publishing throughout the time series. Skip performs best in our experiments with HUE (Figure 7b), due to the low range in the energy consumption and the high scale of the Laplace noise that it avoids due to the employed approximation. However, for the Copenhagen data set (Figure 7a) and T-drive (Figure 7c), Skip attains high mean absolute error, which exposes no benefit with respect to userlevel protection. Overall, Adaptive has a consistent performance in terms of utility for all of the data sets that we experimented with, and almost always outperforms the user-level privacy protection. Thus, Adaptive is selected as the best scheme to use in general.

CONCLUSION

We presented landmark privacy for privacy-preserving time series publishing, which allows for the protection of significant events while improving the utility of the final result compared to userlevel differential privacy. We proposed three schemes for landmark privacy, and quantified the privacy loss under temporal correlation. Furthermore, we designed a module to enhance our privacy notion by protecting the actual timestamps of the landmarks. The contribution of the landmark privacy, and its best performing scheme, Adaptive, is experimentally demonstrated on real and synthetic data sets. The experiments showed that our dummy landmark selection module introduces a reasonable data utility decline to all of our schemes, which is minimal for the Adaptive. In terms of temporal correlation, we observe that under moderate and strong correlation, greater average regular-landmark event distance causes greater overall privacy loss. In the future, we aim to work on automatically learning the initial landmark set by analyzing the input data sets, semantics, and user preferences. We also plan to introduce learning for the tuning of our Adaptive scheme parameters.

Figure 1 :

 1 Figure 1: A time series with landmarks (highlighted in gray).

Figure 2 :

 2 Figure 2: User-level and landmark 𝜀-differential privacy protection for the time series of Figure 1.

Definition 3 .

 3 Two time series 𝑆 𝑇 , 𝑆 ′ 𝑇 of the same length |𝑇 |, with common starting and ending timestamps, are L-landmark neighboring with respect to a set of timestamps 𝐿 ⊆ 𝑇 when (i) for each 𝑆 𝑇 [𝑖], 𝑆 ′ 𝑇 [𝑖] with 𝑖 ∈ 𝑇 and 𝑆 𝑇 [𝑖] ≠ 𝑆 ′ 𝑇 [𝑖], it holds that 𝑆 𝑇 [𝑖], 𝑆 ′ 𝑇 [𝑖] are neighboring, and (ii) for each 𝑖 ∈ 𝐿 ∪ {𝑡 } such that 𝑡 ∈ 𝑇 , we have that 𝑆 𝑇 [𝑖], 𝑆 ′ 𝑇 [𝑖] are neighboring.

For

  any 𝑂 ∈ O we get 𝑃𝑟 [ M (𝑆 𝑇 ) ∈𝑂 ] 𝑃𝑟 [ M (𝑆 ′ 𝑇 ) ∈𝑂 ] ≤ 𝑒 𝑖 ∈𝐿∪{𝑡 } 𝜀 𝑖 . If the formula of Theorem 2 holds, then we get 𝑃𝑟 [ M (𝑆 𝑇 ) ∈𝑂 ] 𝑃𝑟 [ M (𝑆 ′ 𝑇 ) ∈𝑂 ] ≤ 𝑒 𝜀 . Due to Definition 4 this concludes our proof. □

Figure 3 :

 3 Figure 3: Application scenario of the (a) Uniform and (b) Skip landmark privacy schemes on a time series.

Figure 4 :

 4 Figure 4: Concept of Adaptive privacy.

Figure 5

 5 illustrates 𝑖 - and 𝑖 + in Example 1.1, while we formalize the landmark temporal privacy loss in Definition 5.

Figure 5 :Definition 5 .

 55 Figure5: The timestamps exactly before (-) and after (+) every timestamp, where that is applicable, for the calculation of the temporal privacy loss.

Figure 6 :

 6 Figure 6: The privacy risk (highlighted in red) that the application of the landmark privacy Skip scheme might pose.

Figure 7 :

 7 Figure 7: The mean absolute error (a) as a percentage, (b) in kWh, and (c) in meters of the released data, for different landmark percentages. The markers indicate the corresponding measurements with the incorporation of the privacypreserving dummy landmark selection module.

Figure 8 :

 8 Figure 8: Average temporal distance of regular events from the landmarks for different landmarks percentages within a time series in various landmark distributions.

Figure 9 :

 9 Figure 9: The temporal privacy loss for different landmark percentages and distributions under (a) moderate, and (b) strong degrees of temporal correlation. The line shows the overall privacy loss without temporal correlation.

  4.3.1 Dummy landmark selection utility metrics. Figure10demonstrates the normalized distance that we obtain when we utilize either (a) the Euclidean or (b) the Wasserstein distance metric to obtain a set of landmarks including regular events.

Figure 10 :

 10 Figure 10: The normalized (a) Euclidean, and (b) Wasserstein distance of the generated landmark sets for different landmark percentages.

Figure 11 :

 11 Figure 11: The mean absolute error (a) as a percentage, (b) in kWh, and (c) in meters of the released data for different landmark percentages. We apply the Uniform landmark privacy mechanism and vary the ratio of the privacy budget 𝜀 that we allocate to the dummy landmark selection module.

4.3. 3

 3 Privacy schemes and dummy landmark selection.

  Figure 7 exhibits the performance of Skip, Uniform, and Adaptive schemes (presented in detail in Section 3.2) in combination with the dummy landmark selection module (Section 3.4).

  getHist generates a histogram with bins of size h for a given time series timestamps 𝑇 and landmark set 𝐿. For every new histogram version, the getDiff function (Line 11) finds the difference from the original histogram; for this operation it utilizes Algorithm 1: Partitioned landmark set options generation Data: the time series timestamps 𝑇 , the landmark set 𝐿 Output: the selected landmark set options opts

	1 hist, h ← getHist(𝑇 , 𝐿)
	2 histCur ← hist
	3 opts ← []
	4 while sum(histCur) ≠ len(𝑇 ) do
	5	diffMin ← ∞
	6	opt ← histCur
	7	foreach h 𝑖 in histCur do
	8	if h 𝑖 + 1 ≤ h then
	9	histTmp ← histCur
	10	histTmp[𝑖] ← histTmp[𝑖] + 1
	11	diffCur ← getDiff(hist, histTmp)

12 if diffCur < diffMin then 13 diffMin ← diffCur 14 opt ← histTmp 15 histCur ← opt 16 opts ← opt 17 return opts the Euclidean distance (see Section 4.3.1 for more details). In Lines 7-14, the algorithm checks every histogram version by incrementing each bin by 1 and comparing it to the original (Line 12

In this scenario, in order to protect all the landmarks from timestamp 1 to 8, 𝑤 must be set to 8, which makes 𝑤-event privacy equivalent to user-level.