Query.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import statistics\n",
    "# === Performance Evaluation ===\n",
    "#\n",
    "# evaluate the blocks of data to be fetched, when physical data of kdnodes are seperate !!!\n",
    "# @queries: a collection of queries contains the lower and upper value in all dimensions; numpy object\n",
    "# @kdnodes: the kdnodes generated above; array object\n",
    "\n",
    "def Query(queries, kdnodes, alpha = 0):\n",
    "    \n",
    "    '''\n",
    "    assume the queries are combined with distribution (first) and random (second)\n",
    "    where the percentage of random query is alpha\n",
    "    '''\n",
    "    counts_partitions = []\n",
    "    counts_records = []\n",
    "    counts_total = 0\n",
    "    \n",
    "    count_single_query = 0;\n",
    "    count_single_query_records = 0\n",
    "    \n",
    "    # number of dimensions\n",
    "    dims = int(len(queries[0]))\n",
    "    \n",
    "    dis_rand_split_index = len(queries) * (1 - alpha)\n",
    "    distribution_query_cost = 0\n",
    "    random_query_cost = 0\n",
    "    \n",
    "    # for each query\n",
    "    for i in range(len(queries)):\n",
    "        \n",
    "        count_single_query = 0\n",
    "        count_single_query_records = 0\n",
    "        \n",
    "        intersected_partitions = []\n",
    "        \n",
    "        # check for intersection for each kdnode\n",
    "        for j in range(len(kdnodes)):\n",
    "            \n",
    "            intersection_tag = True\n",
    "            \n",
    "            # for each dimension\n",
    "            for k in range(dims):\n",
    "                \n",
    "                # an intersection holds if it intersecs in all dimensions\n",
    "                if queries[i][k][0] >= kdnodes[j][0][k][1] or queries[i][k][1] <= kdnodes[j][0][k][0]:\n",
    "                    intersection_tag = False\n",
    "                    break\n",
    "                \n",
    "            # if the query intersect with this kdnode\n",
    "            if intersection_tag:\n",
    "                intersected_partitions.append(j)\n",
    "                count_single_query += 1\n",
    "                count_single_query_records += kdnodes[j][1] # number of records in this partition\n",
    "                \n",
    "        if i < dis_rand_split_index:\n",
    "            distribution_query_cost += count_single_query_records\n",
    "        else:\n",
    "            random_query_cost += count_single_query_records\n",
    "        \n",
    "        print(\"Query\", i, \" Cost: \", count_single_query_records, \" Intersected Partitions:\", intersected_partitions)\n",
    "        \n",
    "        counts_partitions.append(count_single_query)\n",
    "        counts_records.append(count_single_query_records)\n",
    "        counts_total += count_single_query_records\n",
    "    \n",
    "    #print(\"blocks IO: \", counts)\n",
    "    print(\"average partitions each query overlap(average): \", statistics.mean(counts_partitions))\n",
    "    print(\"average records each query retrieve(average): \", statistics.mean(counts_records))\n",
    "    print(\"total records that all the queries retrieve: \", counts_total)\n",
    "    \n",
    "    avg_dist_cost = distribution_query_cost / dis_rand_split_index\n",
    "    print(\"average distribution query cost:\", avg_dist_cost)\n",
    "    avg_rand_cost = random_query_cost / (len(queries) - dis_rand_split_index)\n",
    "    print(\"average random query cost:\", avg_rand_cost)\n",
    "    \n",
    "    return statistics.mean(counts_records)\n",
    "\n",
    "# # === Performance Evaluation (dense) ===\n",
    "# #\n",
    "# # evaluate the blocks of data to be fetched, when physical data of kdnodes are dense !!!\n",
    "# # @queries: a collection of queries contains the lower and upper value in all dimensions; numpy object\n",
    "# # @kdnodes: the kdnodes generated above; array object\n",
    "# #\n",
    "# def QueryDense(queries, dense_kdnodes):\n",
    "    \n",
    "#     counts = []\n",
    "#     count_single_query = 0;\n",
    "    \n",
    "#     # number of dimensions\n",
    "#     dims = int(len(queries[0]))\n",
    "    \n",
    "#     # for each query\n",
    "#     for i in range(len(queries)):\n",
    "        \n",
    "#         pages = []\n",
    "        \n",
    "#         # check for intersection for each kdnode\n",
    "#         for j in range(len(dense_kdnodes)):\n",
    "            \n",
    "#             # for each dimension\n",
    "#             intersection_tag = True\n",
    "#             for k in range(dims):\n",
    "                \n",
    "#                 # an intersection holds if it intersecs in all dimensions\n",
    "#                 if queries[i][k][0] >= dense_kdnodes[j][0][k][1] or queries[i][k][1] <= dense_kdnodes[j][0][k][0]:\n",
    "#                     intersection_tag = False\n",
    "#                     break\n",
    "                \n",
    "#             # if the query intersect with this kdnode\n",
    "#             if intersection_tag:\n",
    "#                 pages.extend(dense_kdnodes[j][1]) # remember to remove repeated\n",
    "        \n",
    "#         counts.append(len(set(pages)))\n",
    "    \n",
    "#     #print(\"blocks IO: \", counts)\n",
    "#     print(\"blocks IO(average): \", statistics.mean(counts))    \n",
    "\n",
    "# # === Physical Storage ===\n",
    "# #\n",
    "# # Reform the kdnodes from seperate physcial stroage to dense, continous physical storage\n",
    "# #\n",
    "# # @kdnodes: the previous generated kdnodes, already in order; array\n",
    "# # @threshold: the maximum page size \n",
    "# #\n",
    "# # return @dense_kdnodes: array\n",
    "\n",
    "# def DenseKDNodes(kdnodes, threshold):\n",
    "    \n",
    "#     dense_kdnodes = []\n",
    "#     previous_records = 0\n",
    "#     current_records = 0\n",
    "#     page_count = 0\n",
    "    \n",
    "#     for i in range(len(kdnodes)):\n",
    "#         previous_records = current_records\n",
    "#         current_records += kdnodes[i][1]\n",
    "#         if current_records > threshold:\n",
    "#             # determine how many pages exceeds\n",
    "#             remaining = kdnodes[i][1] - (threshold - previous_records)\n",
    "#             num_pages = math.ceil(remaining / threshold) # num of new pages required\n",
    "#             pages = [i+page_count for i in range(num_pages+1)]\n",
    "#             page_count += num_pages\n",
    "#             current_records = remaining % threshold\n",
    "#             dense_kdn = [kdnodes[i][0],pages]\n",
    "#             dense_kdnodes.append(dense_kdn)\n",
    "#         else:\n",
    "#             dense_kdn = [kdnodes[i][0],[page_count]]\n",
    "#             dense_kdnodes.append(dense_kdn)\n",
    "                         \n",
    "#     return dense_kdnodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Example of usage (Performance Evaluation Learned)\n",
    "#Query(testing_set, kdnodes)\n",
    "\n",
    "# # Example of usage (Physical Storage)\n",
    "# dense_kdnodes = DenseKDNodes(kdnodes, block_size)\n",
    "\n",
    "# # Example of usage (Performance Evaluation (dense))\n",
    "# QueryDense(testing_set, dense_kdnodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# this is designed for incremental query?\n",
    "def QueryWithKdnodeIndex(single_query, kdnode_index, kdnode_dict):\n",
    "    pass"
   ]
  }
 ],
 "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.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}