PWS Cup 2019

Team 004 (またぼっち, Botch Again) / Makoto IGUCHI (Kii Corporation)

Data Anonymization
Basic strategy: Shift regions by N

Additional strategy: Protect “weak” regions by shifting

Evaluation/implementation:

Example: Shift a region by 2

Definition of “weak” regions:- “Hospital” regions (for TRP)
- “Rare” regions in each time slot (IDP and TRP)

AS-ShiftRareRegions (𝑛, 𝑑1 , 𝑑2 )- 𝑛 : threshold for “rare” region determination- 𝑑1 : # of maximum shift for hospital regions- 𝑑2 : # of maximum shift for rare regionsOriginal trace set…

…

User #0002

User #2000

Randomly shift the region (at most 2 blocks)
both vertically and horizontally

Regions
recordedon Time 1

…

……

…

……

…

……

AS (94, 0, 3) for ID disclosure challenge- Shift as many rare regions as possible by 3
- 𝑆𝑈 = 0.70270 (275598 regions untouched)…

User #0001

Consider theregion as “rare”
if the # of its
occurrence isless than thethreshold value…

…

2000 * 20 = 40000 regions

AS (89, 4, 3) for trace inference challenge- Shift all hospital regions by 4
- Shift as many rare regions as possible by 3
- 𝑆𝑈 = 0.70211 (283,175 regions untouched)

ID Disclosure
Basic strategy: Feature vector comparison
Feature vectors

Reference trace set

…

Count

…

…

00011…1…

…

User #2

00021…0…

User #1

When generating the feature vectors, count thetarget region and its surrounding regions“fuzzily.”1-NN
search00000

Pub. Anon. trace set…

Pseudo #2

…

…

…

Count

IF-FuzzyVisitVector (𝑛0 , 𝜆)- 𝑛0 : initial quantity- 𝜆 : exponential decay constantExperiments with sample data sets revealed
that IF (0.33,1) with Scheme 2 (TF weight:𝑙𝑜𝑔(1 + 𝑓𝑟,𝑢 ), IDF weight: 1) yields to the
optimal ID disclosure result 𝑆𝐼 .

Example:Find the nearest
feature vector (user)
for each pseudo user

20304…011000…30
00
0.099 0.121 0.099
0.121 0.20 0.121
0.099 1.121 0.099
00000000000000000000
10000
00000000ID disclosure evaluation: AS (94,0,3,0)𝑛0 = 0.5
𝑛0 = 0.33
𝑛0 = 0.2

1.0

Raw counting(equiv. to 𝑛0 = 1, 𝜆 = ∞)Fuzzy counting(𝑛0 = 0.2, 𝜆 = 0.5)…

Pseudo #1

Evaluation/implementation:

Additional strategy #2:“Fuzzy” feature vector generation

𝑛0 = 0.15
𝑛0 = 0.1
𝑛0 = 0.05

0.8

𝑆𝐼0.6

Additional strategy #1:“TF-IDF” style feature vector generation
When generating the feature vectors, weight“uncommon” regions more than “common”
regions
TF weight
𝑓𝑟,𝑢

IDF weightlog 𝑈Τ𝑢𝑟

Scheme 2 log(1 + 𝑓𝑟,𝑢 )𝑓𝑟,𝑢Scheme 31log 𝑈Τ𝑢𝑟

Scheme 4 log(1 + 𝑓𝑟,𝑢 )1Scheme 1The optimal
scheme is to befound throughevaluation withsample data.

“Fuzzy” counting is realized by an exponential
decay function: 𝒄 = 𝒏𝟎 ⅇ−𝝀𝒅(𝑛0 : initial quantity, λ: exponential decay constant,𝑑: distance from the target region)
𝑐0.4
0.5

1.0

1.5

𝜆 = 0.25
𝜆 = 0.33

𝜆 = 0.5

𝑓𝑟,𝑢 : raw count of Region 𝑟 in User 𝑢′s traces
𝑈: total # of users (2000)
𝑢𝑟 : # of users whose traces contain Region 𝑟

The optimal curve(i.e., 𝑛0 and λ) is tobe found throughevaluations withsample data𝑛0 = 0.5
𝑛0 = 0.33
𝑛0 = 0.2

𝑆𝐼
0.6
0.4
0.2
0.5

3 𝑑2

1

𝑛0 = 0.15
𝑛0 = 0.1
𝑛0 = 0.05

0.8

𝜆=1

𝜆=2

3.0

ID disclosure evaluation: A4-PL (3.5,1)
1.0

𝑛02

2.5

𝑟

𝑛0

𝜆 = 0.20

2.0

1.0

1.5

2.0

2.5

3.0𝑟

Trace Inference

20 regions(User #3 pub. anon. trace)

Pseudo #3…

(User #69 pub. anon. trace)

…

…

…

Pseudo #3

Trace inference result…

Pseudo #2(User #21 pub. anon. trace)

…

…
…
…

Consider the region
as “frequent” if the #of its occurrences ismore than thethreshold value…

…

Swap iffrequent

Evaluation/implementation:
TS-SwapFrequentRegions (𝑛)- 𝑛 : threshold for “frequent” region
determination
Experiments with sample data sets
indicated that TS(5) yields to the
optimal trace inference score 𝑆𝑇 .
Trace inf. evaluation: AB(89,4,3,0)+IF(0.33,1)
Team022_data01_IDP
Team023_data01_IDP
Team022_data02_TRP
Team023_data02_TRP
𝑆𝑇

Trace inference result…

…

Regions recorded
on Time 1 inuser 3’s ref. trace

Trace inference result
Pseudo #1

……
……

…

Use the ID disclosure
result to map a publicanonymized trace foreach pseudo user…
…

Pseudo #3…

…

…

Pseudo #2 → User #69……

…

User #0003…

…

User #0002

Pseudo #1 → User #21…

Reference trace set
User #0001

ID disclosure result

Pseudo #3 → User #3

Additional strategy: Use the reference trace sets toreplace “frequent” regions…

Basic strategy:
List-up public anonymized traces on thebasis of the ID disclosure result…
𝑛