Experimental study for other types of queries.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In our submission, the experimental study we carried out covered only star-chain queries. To be more represenative and comprehensive in the types of queries we consider, we present the experimental results for various other types of queries here. \n",
    "\n",
    "# Context\n",
    "\n",
    "The technical context and the background for this new set of experiments is the same as in the submission: we run the experiments in the exact same conditions, on a workload of 500 random queries generated using gMark. We generate three separate workloads: one featuring **only star/chain queries**, the second with **only chain queries**, the third using **a random mix of star/chain and star queries**, and the last one featuring **only star queries**.\n",
    "\n",
    "We then run our program to create the same 3 graphs mentioned in the submission, as well as two new data graphs:\n",
    "\n",
    "- The number of compatible cases found depending on the privacy size (utility size is fixed)\n",
    "- The number of compatible cases found depending on the utility size (privacy size is fixed)\n",
    "- The size of found candidate sets depending on the measure overlapping between policies\n",
    "- The size of found candidate sets depending on the privacy size (utility size is fixed)\n",
    "- The size of found candidate sets depending on the utility size (privacy size is fixed)\n",
    "\n",
    "This document references figures and results from Section 6 of the above mentioned submission (link available in the repository's README file).\n",
    "\n",
    "These experiments are performed using two versions of the implementation: one **using the standard implementation with both operations available** and another **with a simpler implementation (without the update operation, only deletions)**.\n",
    "\n",
    "\n",
    "\n",
    "# Standard (deletion + update) implementation\n",
    "\n",
    "We experiment using a code prototype featuring the complete algorithms `find-ops` and `find-ops-unit` as presented in the submission, i.e. creating sequences of deletion and update queries. Later on we present additional results in a simpler implementation.\n",
    "\n",
    "## Case 1: star/chain queries\n",
    "\n",
    "\n",
    "This is the case study presented in the submission (star-chain queries + complete algorithms). \n",
    "\n",
    "### Compatibility measures\n",
    "\n",
    "\n",
    "Incompatibility based on privacy size (fixed utility size) | Incompatibility based on utility size (fixed privacy size)\n",
    "- | - \n",
    "![Incompatibility based on privacy size (fixed utility size)](exp_update/exp_starchain/incomp_size_priv_3_3.png) | ![Incompatibility based on utility size (fixed privacy size)](exp_update/exp_starchain/incomp_size_util_3_3.png)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "### Candidate sets properties\n",
    "\n",
    "Size of candidate sets based on policy overlapping | Size of candidate sets based on privacy size (utility size fixed) | Size of candidate sets based on utility size (privacy size fixed)\n",
    "- | - | -\n",
    "![Size of candidate sets based on policy overlapping](exp_update/exp_starchain/cand_overlap_3_3.png) | ![Size of candidate sets based on privacy size (utility size fixed)](exp_update/exp_starchain/cand_size_priv_3_3.png) | ![Size of candidate sets based on utility size (privacy size fixed)](exp_update/exp_starchain/cand_size_util_3_3.png) \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Case 2: chain queries\n",
    "\n",
    "\n",
    "### Compatibility measures\n",
    "\n",
    "\n",
    "Incompatibility based on privacy size (fixed utility size) | Incompatibility based on utility size (fixed privacy size)\n",
    "- | - \n",
    "![Incompatibility based on privacy size (fixed utility size)](exp_update/exp_chain/incomp_size_priv_3_3.png) | ![Incompatibility based on utility size (fixed privacy size)](exp_update/exp_chain/incomp_size_util_3_3.png)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "### Candidate sets properties\n",
    "\n",
    "Size of candidate sets based on policy overlapping | Size of candidate sets based on privacy size (utility size fixed) | Size of candidate sets based on utility size (privacy size fixed)\n",
    "- | - | -\n",
    "![Size of candidate sets based on policy overlapping](exp_update/exp_chain/cand_overlap_3_3.png) | ![Size of candidate sets based on privacy size (utility size fixed)](exp_update/exp_chain/cand_size_priv_3_3.png) | ![Size of candidate sets based on utility size (privacy size fixed)](exp_update/exp_chain/cand_size_util_3_3.png) \n",
    "\n",
    "\n",
    "\n",
    "## Case 3: star and star/chain mix\n",
    "\n",
    "For this third case, the query workload consists in a randomly distributed set of star queries and star/chain queries.\n",
    "\n",
    "### Compatibility measures\n",
    "\n",
    "\n",
    "Incompatibility based on privacy size (fixed utility size) | Incompatibility based on utility size (fixed privacy size)\n",
    "- | - \n",
    "![Incompatibility based on privacy size (fixed utility size)](exp_update/exp_star_starchain/incomp_size_priv_3_3.png) | ![Incompatibility based on utility size (fixed privacy size)](exp_update/exp_star_starchain/incomp_size_util_3_3.png)\n",
    "\n",
    "\n",
    "\n",
    "### Candidate sets properties\n",
    "\n",
    "Size of candidate sets based on policy overlapping | Size of candidate sets based on privacy size (utility size fixed) | Size of candidate sets based on utility size (privacy size fixed)\n",
    "- | - | -\n",
    "![Size of candidate sets based on policy overlapping](exp_update/exp_star_starchain/cand_overlap_3_3.png) | ![Size of candidate sets based on privacy size (utility size fixed)](exp_update/exp_star_starchain/cand_size_priv_3_3.png) | ![Size of candidate sets based on utility size (privacy size fixed)](exp_update/exp_star_starchain/cand_size_util_3_3.png) \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Case 4: star queries\n",
    "\n",
    "\n",
    "### Compatibility measures\n",
    "\n",
    "\n",
    "Incompatibility based on privacy size (fixed utility size) | Incompatibility based on utility size (fixed privacy size)\n",
    "- | - \n",
    "![Incompatibility based on privacy size (fixed utility size)](exp_update/exp_star/incomp_size_priv_3_3.png) | ![Incompatibility based on utility size (fixed privacy size)](exp_update/exp_star/incomp_size_util_3_3.png)\n",
    "\n",
    "\n",
    "### Candidate sets properties\n",
    "\n",
    "Size of candidate sets based on privacy size (utility size fixed) | Size of candidate sets based on utility size (privacy size fixed)\n",
    "- | -\n",
    "![Size of candidate sets based on privacy size (utility size fixed)](exp_update/exp_star/cand_size_priv_3_3.png) | ![Size of candidate sets based on utility size (privacy size fixed)](exp_update/exp_star/cand_size_util_3_3.png) \n",
    "\n",
    "In the case of a workload consisting exclusively in star queries, the first graph is not relevant since every execution of the algorithm featuring policies with an overlapping measure over 0% results in an incompatible case. Compatible cases are then exclusively without any overlapping, which makes such a graph (candidate sets length over overlapping measure) irrelevant. We also note that the trend of incompatibility measurements is quite different than in the previous cases.\n",
    "\n",
    "This happens because of the particular structure of star queries. We think that our notion of overlapping tends to be quite strict for this class of queries, since we work with edge-based overlapping. Such a kind of overlapping is problematic when it happens with star queries, since the center of star is always involved and blocks possible deletions. This suggests another alternative for defining overlapping, a node-centered definition. \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# Simple (deletion-only) implementation\n",
    "\n",
    "This experimental study focus on a code prototype using a simpler version of the `find-ops-unit` algorithm presented in the submission, generating operation sequences featuring only deletion queries, rather than deletion and update queries.\n",
    "\n",
    "## Case 1: star/chain queries\n",
    "\n",
    "\n",
    "### Compatibility measures\n",
    "\n",
    "\n",
    "Incompatibility based on privacy size (fixed utility size) | Incompatibility based on utility size (fixed privacy size)\n",
    "- | - \n",
    "![Incompatibility based on privacy size (fixed utility size)](exp_delete/exp_starchain/incomp_size_priv_3_3.png) | ![Incompatibility based on utility size (fixed privacy size)](exp_delete/exp_starchain/incomp_size_util_3_3.png)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "### Candidate sets properties\n",
    "\n",
    "Size of candidate sets based on policy overlapping | Size of candidate sets based on privacy size (utility size fixed) | Size of candidate sets based on utility size (privacy size fixed)\n",
    "- | - | -\n",
    "![Size of candidate sets based on policy overlapping](exp_delete/exp_starchain/cand_overlap_3_3.png) | ![Size of candidate sets based on privacy size (utility size fixed)](exp_delete/exp_starchain/cand_size_priv_3_3.png) | ![Size of candidate sets based on utility size (privacy size fixed)](exp_delete/exp_starchain/cand_size_util_3_3.png) \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Case 2: chain queries\n",
    "\n",
    "\n",
    "\n",
    "### Compatibility measures\n",
    "\n",
    "\n",
    "Incompatibility based on privacy size (fixed utility size) | Incompatibility based on utility size (fixed privacy size)\n",
    "- | - \n",
    "![Incompatibility based on privacy size (fixed utility size)](exp_delete/exp_chain/incomp_size_priv_3_3.png) | ![Incompatibility based on utility size (fixed privacy size)](exp_delete/exp_chain/incomp_size_util_3_3.png)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "### Candidate sets properties\n",
    "\n",
    "Size of candidate sets based on policy overlapping | Size of candidate sets based on privacy size (utility size fixed) | Size of candidate sets based on utility size (privacy size fixed)\n",
    "- | - | -\n",
    "![Size of candidate sets based on policy overlapping](exp_delete/exp_chain/cand_overlap_3_3.png) | ![Size of candidate sets based on privacy size (utility size fixed)](exp_delete/exp_chain/cand_size_priv_3_3.png) | ![Size of candidate sets based on utility size (privacy size fixed)](exp_delete/exp_chain/cand_size_util_3_3.png) \n",
    "\n",
    "\n",
    "\n",
    "## Case 3: star and star/chain mix\n",
    "\n",
    "\n",
    "### Compatibility measures\n",
    "\n",
    "\n",
    "Incompatibility based on privacy size (fixed utility size) | Incompatibility based on utility size (fixed privacy size)\n",
    "- | - \n",
    "![Incompatibility based on privacy size (fixed utility size)](exp_delete/exp_star_starchain/incomp_size_priv_3_3.png) | ![Incompatibility based on utility size (fixed privacy size)](exp_delete/exp_star_starchain/incomp_size_util_3_3.png)\n",
    "\n",
    "\n",
    "\n",
    "### Candidate sets properties\n",
    "\n",
    "Size of candidate sets based on policy overlapping | Size of candidate sets based on privacy size (utility size fixed) | Size of candidate sets based on utility size (privacy size fixed)\n",
    "- | - | -\n",
    "![Size of candidate sets based on policy overlapping](exp_delete/exp_star_starchain/cand_overlap_3_3.png) | ![Size of candidate sets based on privacy size (utility size fixed)](exp_delete/exp_star_starchain/cand_size_priv_3_3.png) | ![Size of candidate sets based on utility size (privacy size fixed)](exp_delete/exp_star_starchain/cand_size_util_3_3.png) \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Case 4: star queries\n",
    "\n",
    "\n",
    "### Compatibility measures\n",
    "\n",
    "\n",
    "Incompatibility based on privacy size (fixed utility size) | Incompatibility based on utility size (fixed privacy size)\n",
    "- | - \n",
    "![Incompatibility based on privacy size (fixed utility size)](exp_delete/exp_star/incomp_size_priv_3_3.png) | ![Incompatibility based on utility size (fixed privacy size)](exp_delete/exp_star/incomp_size_util_3_3.png)\n",
    "\n",
    "\n",
    "### Candidate sets properties\n",
    "\n",
    "Size of candidate sets based on privacy size (utility size fixed) | Size of candidate sets based on utility size (privacy size fixed)\n",
    "- | -\n",
    "![Size of candidate sets based on privacy size (utility size fixed)](exp_delete/exp_star/cand_size_priv_3_3.png) | ![Size of candidate sets based on utility size (privacy size fixed)](exp_delete/exp_star/cand_size_util_3_3.png) \n",
    "\n",
    "The same remark as for the previous prototype also applies here, and the first graph is here irrelevant with this workload.\n",
    "\n",
    "\n",
    "\n",
    "# Conclusion\n",
    "\n",
    "We can observe than the trend of results in the case of chain queries, as well as a mix of star and star/chain queries is similar to what we previously observed in the case of star/chain queries ((a) compatibility rising when privacy size increases and decreasing when utility size increases; (b) quick decrease of candidate sets length when overlapping increases; (c) candidate sets length growing steadily when privacy size increases and stagnating or slowly decreasing when utility size increases). Otherwise, star queries provides slightly different results - if not similar, and presents an interesting problem of interest for the notion of overlapping that we use.\n",
    "\n",
    "We also note that using a simpler prototype, offering less operations to add to anonymizing sequences, does not change the trend of our results, but obviously provide way less anonymization alternatives.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}