GK_summary.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "#http://infolab.stanford.edu/~datar/courses/cs361a/papers/quantiles.pdf\n",
    "#creates a summary on the data that gaurantees e-quantiles\n",
    "def GK_summary (data, e):\n",
    "    S = []\n",
    "    s = 0\n",
    "    for n in range (0,len(data)):\n",
    "        if (n%(1/(2*e)) == 0 and s>4):\n",
    "            #COMPRRESS()\n",
    "            for i in range (s-4,0, -1):\n",
    "                t_i = S[i]\n",
    "                t_i_next = S[i+1]\n",
    "                g_i_star  = t_i[1]\n",
    "                descendents_list = []\n",
    "                descendent_index = i - 1\n",
    "                while ((BAND(S[descendent_index], n, e) < BAND(t_i, n, e)) and (descendent_index>=0)):\n",
    "                    g_i_star += S[descendent_index][1]\n",
    "                    descendents_list.append (descendent_index)\n",
    "                    descendent_index -= 1 \n",
    "                g_i_next = t_i_next[1]\n",
    "                delta_i_next = t_i_next[2]\n",
    "                if ((BAND(t_i, n, e)<= BAND (t_i_next, n, e)) and (g_i_star + g_i_next + delta_i_next <2*e*n)):\n",
    "                    S[i+1][1]+= g_i_star\n",
    "                    del S[i]\n",
    "                    s-=1          \n",
    "                    for j in range (len(descendents_list)):\n",
    "                        del S[descendents_list[j]]\n",
    "                        s-=1\n",
    "        #INSERT\n",
    "        v = data[n]\n",
    "        if (len(S)==0):\n",
    "            S.insert (0, [v, 1, 0])\n",
    "            s+=1\n",
    "        elif (v<S[0][0]):\n",
    "            S.insert (0, [v, 1, 0])\n",
    "            s+=1\n",
    "        elif (v>S[len(S)-1][0]):\n",
    "            S.append ([v, 1, 0])\n",
    "            s+=1\n",
    "        else:\n",
    "            for i in range (1,len(S)):\n",
    "                v_i_prior = S[i-1][0]\n",
    "                v_i = S[i][0]\n",
    "                if (v_i_prior<=v<v_i):\n",
    "                    S.insert (i, [v, 1, math.floor(2*e*n)])\n",
    "                    s+=1\n",
    "                    break;  \n",
    "    return S;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "#From bands section\n",
    "def BAND (t_i, n, e):\n",
    "    #first 1/2e observations are in their own band\n",
    "    if (n<(1/2*e)):\n",
    "        return -1\n",
    "    p = math.floor (2*e*n)\n",
    "    if (t_i[2]==p):\n",
    "        return 0\n",
    "    band = 0\n",
    "    for a in range (1,math.ceil(math.log(2*e*n))):\n",
    "        if ((p-2**a-(p%2**a))<t_i[2]<=(p-2**(a-1)-(p%2**(a-1)))):\n",
    "            band = a\n",
    "            break;\n",
    "    return band"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "#O((1/e)log(eN))\n",
    "def GK_quantile (S, e, q, N):\n",
    "    r = math.ceil(q*N)\n",
    "    r_min_v_i = 0\n",
    "    v_i = None\n",
    "    for i in range (len(S)):\n",
    "        r_min_v_i += S[i][1]\n",
    "        r_max_v_i = r_min_v_i + S[i][2]\n",
    "        if (((r-r_min_v_i)<=e*N) and ((r_max_v_i - r) <= e*N)):\n",
    "            v_i =  S[i][0]\n",
    "            break;\n",
    "    return v_i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}