Data Platform/Data Lake/Traffic/Pageview hourly/K Anonymity Threshold Analysis

In a plan to secure our user data, the pageview_hourly dataset needs to be sanitized in such a way that it does not allow to track user path.
See this page for a broad view on the pageview_hourly sanitization project, and this one for a detailed description of the algorithm proposal.
This page go through the various analysis we have been doing in defining K, the minimum number of distinct IPs a finger-printing group must have not to go through anonymization (see an introduction on k-anonymity).
= Dataset specification =
* One hour of pageviews (${YEAR},${MONTH},${DAY},${HOUR})
* filtered from
** IPs having more than IP_UA_THRESHOLD different user agents
**: (trying to remove mobile "many devices for a single IP" artifact)
** IPs having more than IP_REQ_THRESHOLD views
**: (trying to remove u "many devices for a single IP" artifact)
*finger-printing Dimensions we took as defining a group are:
** project (not to be anonymized)
** language_variant (not to be anonymized)
** access method (not to be anonymized)
** agent type, (not to be anonymized)
** zero carrier,
** geocoding hierarchical data (continent, country, subdivision, city)
** user_agent_map
* Data to analyze
** Distinct IPs (count and list)
** Titles of page viewed
** Number of requests	
 CREATE TABLE pv_san.idents_buckets STORED AS PARQUET AS
WITH wrong_ips AS (
 SELECT
 client_ip AS w_ip,
 COUNT(DISTINCT user_agent) AS user_agent_count,
 COUNT(1) AS request_count
 FROM wmf.webrequest
 WHERE webrequest_source IN ('mobile', 'text')
 AND year=${YEAR} AND month=${MONTH} AND day=${DAY} AND hour=${HOUR}
 AND is_pageview
 GROUP BY client_ip
 HAVING (COUNT(DISTINCT user_agent) >= ${IP_UA_THRESHOLD}
 OR COUNT(1) >= ${IP_REQ_THRESHOLD} )
)
SELECT
 pageview_info['project'] as project,
 pageview_info['language_variant'] as language,
 agent_type,
 access_method,
 agent_type,
 x_analytics_map['zero'] AS zero_carrier,
 geocoded_data['continent'] AS continent,
 geocoded_data['country'] AS country,
 geocoded_data['subdivision'] AS subdivision,
 geocoded_data['city'] AS city,
 user_agent_map,
 COUNT(DISTINCT client_ip) AS ips_count,
 COLLECT_SET(client_ip) AS unique_ips,
 COUNT(DISTINCT pageview_info['page_title']) AS pages_count,
 COLLECT_SET(pageview_info['page_title']) AS unique_pages,
 COUNT(1) AS request_count
FROM wmf.webrequest webrequest
 LEFT OUTER JOIN wrong_ips ON (webrequest.client_ip = wrong_ips.w_ip)
WHERE wrong_ips.w_ip IS NULL and
 AND webrequest_source IN ('mobile', 'text')
 AND year=${YEAR} and month=${MONTH} and day=${DAY} and hour=${HOUR}
 AND geocoded_data['continent'] not in ('Unknown', '--', '-')
 AND geocoded_data['country'] not in ('Unknown', '--', '-')
 AND geocoded_data['subdivision'] not in ('Unknown', '--', '-')
 AND geocoded_data['city'] not in ('Unknown', '--', '-')
 AND is_pageview
 AND agent_type = 'user'
GROUP BY
 pageview_info['project'],
 pageview_info['language_variant'],
 access_method,
 agent_type,
 x_analytics_map['zero'],
 geocoded_data['continent'],
 geocoded_data['country'],
 geocoded_data['subdivision'],
 geocoded_data['city'],
 user_agent_map;
= General shape of data =
;bucket_count
:The number of unique sets of bucketed values
;request_count
:The total number of requests
{| class="wikitable"	
bucket_count	request_count
2865382 	21135520
It looks like we see ~10 requests per unique bucket on average, but the distribution is highly skewed as can be seen below. 
== Finger-printing groups, distinct ips, distinct pages and requests ==
We only dig into finger-printing groups that have 10 or less distinct IPs, or 10 or less distinct pages since those are where the anonymization problem exists.
Tables below show show two results:
* Number of request per IP is stable at 2.4 and number of request per page is stable at 1.2, making number of pages per IP stable at 2. 
* Both for distinct ips and distinct pages, number of buckets and number of requests follow power laws (more or less steep).
=== Distinct IPs ===
{| class="wikitable"		 	 	 		 	 	 		 	
ips_count		bucket_count	% 	%_cumul		request_count	% 	%_cumul		request_per_ip	%_difference_to_average
1 		2127846 	74.26%	74.26% 		4617515 	21.85%	21.85% 		2.17 	4.74%
2 		315539 	11.01%	85.27% 		1416920 	6.70% 	28.55% 		2.25 	1.43%
3 		125822 	4.39% 	89.66% 		868266 	4.11% 	32.66% 		2.30 	-0.98%
4 		68535 	2.39% 	92.06% 		623021 	2.95% 	35.61% 		2.27 	0.23%
5 		42663 	1.49% 	93.54% 		488106 	2.31% 	37.92% 		2.29 	-0.45%
6 		29511 	1.03% 	94.57% 		402144 	1.90% 	39.82% 		2.27 	0.30%
7 		21460 	0.75% 	95.32% 		343318 	1.62% 	41.44% 		2.29 	-0.33%
8 		16422 	0.57% 	95.90% 		299057 	1.41% 	42.86% 		2.28 	0.07%
9 		12803 	0.45% 	96.34% 		267363 	1.26% 	44.12% 		2.32 	-1.86%
10 		10465 	0.37% 	96.71% 		245865 	1.16% 	45.29% 		2.35 	-3.14%
=== Distinct pages ===
{| class="wikitable"		 	 	 		 	 	 		 	
pages_count		bucket_count	% 	%_cumul		request_count	% 	%_cumul		request_per_page	%_difference_to_average
1 		1551522 	54.15%	54.15% 		2065809 	9.77%	9.77% 		1.33 	-7.42%
2 		463215 	16.17%	70.31% 		1164015 	5.51%	15.28% 		1.26 	-1.37%
3 		223403 	7.80% 	78.11% 		822750 	3.89%	19.17% 		1.23 	0.96%
4 		131879 	4.60% 	82.71% 		650671 	3.08%	22.25% 		1.23 	0.49%
5 		87189 	3.04% 	85.75% 		533933 	2.53%	24.78% 		1.22 	1.19%
6 		61462 	2.14% 	87.90% 		451024 	2.13%	26.91% 		1.22 	1.33%
7 		45987 	1.60% 	89.50% 		389742 	1.84%	28.76% 		1.21 	2.32%
8 		35842 	1.25% 	90.76% 		353985 	1.67%	30.43% 		1.23 	0.40%
9 		28092 	0.98% 	91.74% 		313424 	1.48%	31.91% 		1.24 	-0.01%
10 		23060 	0.80% 	92.54% 		279851 	1.32%	33.24% 		1.21 	2.09%
= Example of pages viewed together =
== By number of distinct IPs ==
=== 2 distinct IPs ===
* English_words_without_vowels, Davido
* Main_Page, Jay_Chou
* Flunitrazepam, Photograph, Main_Page
* Derivative, Leibniz_integral_rule, Fundamental_theorem_of_calculus,
*: Sir_John_Mandeville, Crocodile
* Main_Page, Hamster_wheel
* List_of_countries_by_GDP_(PPP), Luxembourg, List_of_countries_by_GDP_(nominal),
*: List_of_countries_by_GDP_(nominal)_per_capita, List_of_countries_by_GDP_(PPP)_per_capita,
*: The_Curious_Case_of_Benjamin_Button_(film), The_Social_Network
* Substance_over_form, SsangYong_Rexton
* Barkha_Dutt, Arnab_Goswami, Sagarika_Ghose, Rajdeep_Sardesai, Rosacea
* Bigg_Boss_9, Debtor, Sovereign_debt_crisis, Great_Recession, Sovereign_default,
*: European_sovereign-debt_crisis, Credit_worthiness, Greek_government-debt_crisis,
*: Secondary_market, Loan_covenant, Credit_rating, Default_(finance), Main_Page,
*: Tom_Enders, Airbus_Group, Financial_crisis_of_2007–08, Economic_bubble,
*: Credit_rating_agency, * Intrinsic_value_(finance), Bailout
* Trilateration, Ilya_Ilyin	
 SELECT
 unique_pages
FROM pv_san.idents_buckets
WHERE ips_count = 2
 AND project = 'en.wikipedia'
LIMIT 10;
=== 3 distinct IPs ===
* Sharman_Joshi, Amendment_of_the_Constitution_of_India,
*: List_of_amendments_of_the_Constitution_of_India,
*: Ninety-third_Amendment_of_the_Constitution_of_India, Abu_Bakr_al-Baghdadi,
*: Abu_Ahmed_al-Kuwaiti, Alfreda_Frances_Bikowsky, Ayman_al-Zawahiri, Main_Page,
*: Kelly_Hu, Battlefield_Hardline
* Pahlaj_Nihalani, Main_Page, Okariki_Okaru, Johnson_&_Johnson
* GDP, List_of_countries_by_GDP_(PPP), Gross_domestic_product, GDP_per_capita,
*: List_of_countries_by_GDP_(nominal)_per_capita, List_of_countries_by_GDP_(nominal),
*: Purchasing_power_parity, Nauru, Turkey, NATO, Main_Page, BATE_Borisov, FC_BATE_Borisov
* Main_Page, The_Revenant_(2015_film), Brandade, Bruschetta
* Jon_Hamm, Minions_(film), Romulan, Vitruvian_Man
* The_Late_Show_with_Stephen_Colbert, Smart_casual, Alice_in_Chains, Main_Page
* Howard_Schultz, Starbucks, Influenza, Rhinorrhea, 1918_flu_pandemic, Peet's_Coffee_&_Tea
* Triple_H, Triple_X_(professional_wrestling), Stephanie_McMahon, Nauru, Tuvalu,
*: Funafuti, Palau, President_of_the_United_States, Rolex
* Sargassum_fish, Kim_Richards, Kyle_Richards, Jamiroquai, Jay_Kay
* Jamie_Vardy, Mad_Season_(band), Greg_Graffin, General_Dynamics_F-16_Fighting_Falcon_variants,
*: Sukhoi_Su-24, Academy_Award_for_Best_Picture, The_Departed, Eurofighter_Typhoon	
 SELECT
 unique_pages
FROM pv_san.idents_buckets
WHERE ips_count = 3
LIMIT 100;
== By number of distinct pages (with more than only 1 IP) ==
Showing 20 random samples having X distinct pages and more than one IP, we can see that even when only 2 distinct pages are seen, they are from different topics, preventing having a (single) section reconstructed.
=== 2 distinct pages ===
* :en:Muzzle, :en:86_(term)
:: 
* :en:Groundhog_Day, :en:History_of_Earth
* :en:Pollution_of_the_Ganges, :en:Atlantis
* :en:Wikipedia:About, :en:ECL
* :en:An_Education, :en:Madeira_cake
* :en:The_Flash_(2014_TV_series), :en:Cyclone_Hudhud
* :en:Category:Flowers, :en:Main_Page
* :en:Substance_over_form, :en:SsangYong_Rexton
* :en:Google_Guava, :en:Mastani
* :en:Islamic_State_of_Iraq_and_the_Levant, :en:Clopidogrel
* :en:Erotic_massage, :en:Speculum_(medical)
* :en:Neil_Nitin_Mukesh, :en:Mediastinum
* :en:Structural_equation_modeling, :en:Bully_algorithm
* :en:Original_Sin_(2001_film), :en:Halo_(optical_phenomenon)
* :en:Fly_(Breaking_Bad), :en:Rhetoric
* :en:Heruy_Welde_Sellase, :en:WJWD
* :en:Governess, :en:Melinda_Messenger
* :en:Main_Page, :en:Hamster_wheel
* :en:Chera_dynasty, :en:Federal_Security_Service
* :en:Main_Page, :en:Saladin	
 SELECT
 unique_pages
FROM pv_san.idents_buckets
WHERE pages_count = 2
 AND ips_count > 1
 AND project = 'en.wikipedia'
LIMIT 100;
=== 3 distinct pages ===
* :en:Heidenhain, :en:John_Gay, :en:Gay
* :en:Doctor_Who_(series_1), :en:Billie_Piper, :en:Zach_Redmond
* :en:Kartik_Poornima, :en:Chiranjeevi, :en:Renu_Desai
* :en:Buggery, :en:Thomas_Granger, :en:Buffalo_buffalo_Buffalo_buffalo_buffalo_buffalo_Buffalo_buffalo
* :en:List_of_programmes_broadcast_by_TV9_(Malaysia), :en:Common_stock, :en:Bali
* :en:Evolution_of_corporate_social_responsibility_in_India, :en:Delirium, :en:Trazodone
* :en:Sugar, :en:Carbon, :en:Easyday
* :en:Hoshizora_e_Kakaru_Hashi, :en:Wong_Sze_Phin, :en:Liew_Chin_Tong
* :en:Rashtriya_Swayamsevak_Sangh, :en:RSS, :en:Lucy_(Australopithecus)
* :en:Jessica_Jones, :en:Luke_Cage, :en:List_of_Girl_Meets_World_episodes
* :en:Lucy_(Australopithecus), :en:Quantico_(TV_series), :en:Priyanka_Chopra
* :en:Riyad_Mahrez, :en:Jamie_Vardy, :en:Acanthoscelides_obtectus
* :en:Elisabeth_Kübler-Ross, :en:Zootopia, :en:Shakira
* :en:Tamil_Muslim, :en:Ethane, :en:Girish_Kumar
* :en:John_Pollard, :en:Jonathan_Pollard, :en:Jawa_Moto
* :en:Philip_Yancey, :en:Nahko_and_Medicine_for_the_People, :en:BGM-71_TOW
* :en:Tim_Drake, :en:Cirrus_Vision_SF50, :en:Business_jet
* :en:Anonymous_(group), :en:Exuma_International_Airport, :en:Azzam_(yacht)
* :en:DJ_Qualls, :en:Twerking, :en:Attacks_on_parachutists
* :en:Restoration_(England), :en:The_Eolian_Harp, :en:Beriberi	
 SELECT
 unique_pages
FROM pv_san.idents_buckets
WHERE pages_count = 3
 AND ips_count > 1
 AND project = 'en.wikipedia'
LIMIT 100;
=== 4 distinct pages ===
* :en:Steve_Jobs_(2015_film), :en:Prehistory_and_origin_of_Stockholm, :en:Mariko_Yashida, :en:Attacks_on_parachutists
* :en:YouTube, :en:Aesthetics, :en:Walid_Atta, :en:Solar_cell
* :en:Kensington_Security_Slot, :en:Irish_Republic, :en:Republic_of_Ireland, :en:President_of_Ireland
* :en:Personal_protective_equipment, :en:René_Descartes, :en:Gram-negative_bacteria, :en:Fermentation_in_food_processing
* :en:Death_of_Jasmine_Fiore, :en:Gymnopilus, :en:Gymnopilus_luteofolius, :en:Gymnopilus_cyanopalmicola
* :en:Special:Search, :en:Main_Page, :en:BeagleBoard, :en:Banana_Pi
* :en:Main_Page, :en:Lists_of_songs, :en:25_(Adele_album), :en:List_of_songs_recorded_by_Adele
* :en:Jon_Hamm, :en:Minions_(film), :en:Romulan, :en:Vitruvian_Man
* :en:Solar_rotation, :en:Linux_Mint, :en:Out_of_the_box_(feature), :en:Email_address
* :en:Dot_product, :en:Spherical_coordinate_system, :en:Cross_product, :en:Order_(group_theory)
* :en:A_Day_in_the_Life, :en:List_of_songs_considered_the_best, :en:Six_degrees_of_separation, :en:Dhafer_Youssef
* :en:Spit_(landform), :en:Category:Festivals_in_the_Dominican_Republic, :en:Peter_Facinelli, :en:Maxwell_Lord
* :en:Opel_Astra, :en:Robin_Hood:_The_Legend_of_Sherwood, :en:Hiram_Bingham_III, :en:Padma_Lakshmi
* :en:Mark_Karpelès, :en:Silk_Road_(marketplace), :en:Mt._Gox, :en:Graeme_Le_Saux
* :en:Homelessness, :en:Francisca_Rojas, :en:Francisco_Rojas, :en:PeerBlock
* :en:Ecofeminism, :en:Intersectionality, :en:Mistake_(contract_law), :en:Misrepresentation
* :en:Main_Page, :en:Thanksgiving_day, :en:Whale, :en:ChannelGain
* :en:Coolie_(1983_Hindi_film), :en:Faisal_Khan, :en:Aamir_Khan, :en:Kiran_Rao
* :en:Sadaqah, :en:Reload_(Tom_Jones_album), :en:Tom_Jones_(singer), :en:Tom_Jones_discography
* :en:Canadian_Military_Pattern_truck, :en:Albert_Einstein, :en:International_Civil_Aviation_Organization, :en:Air_traffic_controller	
 SELECT
 unique_pages
FROM pv_san.idents_buckets
WHERE pages_count = 4
 AND ips_count > 1
 AND project = 'en.wikipedia'
LIMIT 100;
=== 5 distinct pages - Detailed analysis ===
* :en:Thanos, :en:Group_dynamics, :en:Jehoram_of_Israel, :en:Jehu, :en:The_Mysterious_Numbers_of_the_Hebrew_Kings
:: Last three seems session related, but the other two not. 
* :en:Vladimir_Putin, :en:BRLESC, :en:Vacuum_tube, :en:EDVAC, :en:ENIAC
:: The last four seems electronic related, the first is not.
* :en:Awan_(tribe), :en:Miley_Cyrus, :en:Tahj_Mowry, :en:Tamera_Mowry :en:Sister,_Sister_(TV_series)
:: The last three are related (Sister sister TV show), the first two not.
* :en:David_Mamet, :en:Demographics_of_the_world, :en:The_Expanse_(TV_series), :en:Transferrin, :en:Transferrin_saturation
:: The last two are related, the other three seem not.
* :en:Nguyễn_Cao_Kỳ, :en:G-Dragon, :en:YG_Entertainment, :en:Kim_Ji-soo_(singer), :en:Goldust
:: The middle three are related, the other two are not.
* :en:Daniel_Webster, :en:A_Modest_Proposal, :en:Norman_Mailer, :en:The_White_Negro, :en:Political_action_committee
:: Number 3 and 4 are related, but other three seem not.
* :en:1080p, :en:Airy_disk, :en:Diffraction, :en:Leeroy_Jenkins, :en:Laura_Shay
:: Number 2 and three relates, other three seem not.
* :en:St_Hugh's_College,_Oxford, :en:University_of_Oxford, :en:St_Edmund_Hall,_Oxford, :en:Campion_Hall,_Oxford, :en:Disability
:: The four first are related, the last one is not.
* :en:Ichthyophagi, :en:List_of_historians, :en:Secret_in_Their_Eyes, :en:The_Boy_(2016_film), :en:The_Boy_(2015_film)
:: The last two relate (same movie name), but the other three seem not.
* :en:William_Shakespeare, :en:Share_capital, :en:Madhu_Mantena, :en:Masaba_Gupta, :en:Apache_Hadoop
:: No strong link between the five pages.
* :en:Sefako_Makgatho, :en:Sefako_Makgatho_Health_Sciences_University, :en:List_of_2015_albums, :en:Khanyi_Dhlomo, :en:Brad_Davis_(actor)
:: First two are related, other three are unrelated.
* :en:Developing_country, :en:Thai_baht, :en:Lucy_(Australopithecus), :en:Prachi_Desai, :en:Gender_pay_gap_in_the_United_States
:: No strong link between the five pages.
* :en:Triple_H, :en:The_McMahon-Helmsley_Faction, :en:HHH, :en:Courteney_Cox, :en:Lucy_(Australopithecus)
:: First three are related, other two are not.
* :en:Islam, :en:Zhang_Yimou, :en:Wuxia, :en:Hero_(2002_film), :en:Warring_States_period
:: Last four are related, first is not.
* :en:Grassroots, :en:Commodore_64_peripherals, :en:Home_computer, :en:ZX81, :en:Timex_Sinclair
:: Last four are related, first is not.
* :en:Grant_Cardone, :en:Copyright_law_of_Jordan, :en:Anno_2205, :en:Buran_program, :en:Buran_programme
:: Last two are related, other three are not.
* :en:Gabriel_Byrne, :en:Cool_World, :en:List_of_Chicago_Fire_characters, :en:Chic, :en:Chicago_Fire_(TV_series)
:: First two and last two form groups , third alone.
* :en:Adolphe_Thiers, :en:High_Line_(New_York_City), :en:Ground_zero, :en:World_Trade_Center_site, :en:Chrysler_Building
:: Last four relate, first doesn't.
* :en:Edward_T._Hall, :en:Myopia, :en:Adele, :en:Firefox, :en:Tea_tree_oil
:: Unrelated pages.
* :en:The_Brink, :en:Baden-Württemberg, :en:Special_dividend, :en:Dividend, :en:Dividend_tax
:: Last three are related, first two are not.	
 SELECT
 unique_pages
FROM pv_san.idents_buckets
WHERE pages_count = 5
 AND ips_count > 1
 AND project = 'en.wikipedia'
LIMIT 100;
Category:Pageviews
Category:Data platform