AKD.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# The Avoiding Query KDT, similar to the earliest LDK, but have compatible kdnode interface with NORA\n",
    "# This is used as an improvement solution to tackle the random query"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import import_ipynb\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# def overlap_query_ids(domain, idx):\n",
    "#     '''\n",
    "#     Parameter:\n",
    "#     @domain: the kdnode domain\n",
    "#     @idx: the index for queries\n",
    "#     '''\n",
    "#     lower = [domain[0] for domain in original_node[0]]\n",
    "#     upper = [domain[1] for domain in original_node[0]]\n",
    "#     border = tuple(lower + upper)\n",
    "#     overlapped_query_ids = list(idx.intersection(border))\n",
    "#     return overlapped_query_ids\n",
    "\n",
    "def query_domain_ratio(query, domain):\n",
    "    space_query = 1\n",
    "    for i in range(len(query)):\n",
    "        space_query *= (query[i][1] - query[i][0])\n",
    "        \n",
    "    space_domain = 1\n",
    "    for i in range(len(domain)):\n",
    "        space_domain *= (domain[i][1] - domain[i][0])\n",
    "        \n",
    "    return space_query / space_domain\n",
    "\n",
    "# this works for one dimension only !!! An implementation of query bounding.\n",
    "def getoverlap(al, au, bl, bu):\n",
    "    return max(0, min(au,bu)-max(al,bl))\n",
    "\n",
    "# currently not used.\n",
    "def bounding_union(query_collection):\n",
    "    \n",
    "    # should keep it ordered first by the lower interval !!!!!!\n",
    "    query_collection = query_collection[query_collection[:,0].argsort()]\n",
    "    \n",
    "    remaining_query = query_collection\n",
    "    bounded_intervals = []\n",
    "    \n",
    "    while len(remaining_query) != 0:\n",
    "        \n",
    "        initial_interval = [remaining_query[0][0], remaining_query[0][1]]\n",
    "        temp_interval = []\n",
    "        \n",
    "        for i in range(len(remaining_query)-1):\n",
    "            \n",
    "            overlap = getoverlap(initial_interval[0],initial_interval[1],remaining_query[i+1][0], remaining_query[i+1][1])\n",
    "            \n",
    "            # there is no overlap\n",
    "            if overlap == 0:\n",
    "                temp_interval.append([remaining_query[i+1][0], remaining_query[i+1][1]])\n",
    "            else: # update interval border\n",
    "                initial_interval[0] = min(initial_interval[0], remaining_query[i+1][0])\n",
    "                initial_interval[1] = max(initial_interval[1], remaining_query[i+1][1])\n",
    "                \n",
    "        bounded_intervals.append(initial_interval)\n",
    "        remaining_query = temp_interval\n",
    "    \n",
    "    return bounded_intervals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def AKD(dataset, queryset, data_threshold, accu_count_list, kdnode_dict, root_node, current_dim = 0, level = 0, show_step = False):\n",
    "    '''\n",
    "    This is a recursive algorithm.\n",
    "    Parameters:\n",
    "    @dataset: the dataset will not be changed, in the subsequent call, it's the dataset corresponding to the kdnode\n",
    "    @queryset: query in this domain\n",
    "    @root_node: for subsequent call, this is actually the child node itself\n",
    "    Reture:\n",
    "    @kdnodes[i][sub_domains, len(sub_dataset1), id, parent_id, left_child_id, right_child_id]\n",
    "    @is_valid: if any child node is not valid, the parent node will return itself as a whole for further processing\n",
    "                not valid here means, further processing will not help produce better partition(no enough space)\n",
    "    '''\n",
    "    \n",
    "    current_size = len(dataset)\n",
    "    if current_size <= data_threshold:\n",
    "        return [root_node], True # here we assume the children nodes are -1 and -1\n",
    "    \n",
    "    domains = root_node[0] # for ease of use in the following\n",
    "    total_size = len(dataset)\n",
    "    \n",
    "    if len(queryset) == 0:  # query in this domain\n",
    "        return [root_node], True\n",
    "    \n",
    "    # if the partition with single query is small enough\n",
    "    if len(queryset) == 1 and query_domain_ratio(queryset[0], domains) > 0.5:\n",
    "        return [root_node], False\n",
    "    \n",
    "    split_distance_each_dim = []\n",
    "    split_position_each_dim = [] # sorted index value in array\n",
    "    split_value_each_dim = []\n",
    "    \n",
    "    # for each dimension, we calculated the distance from median to its first non-cross split\n",
    "    for D in range(len(dataset[0])):\n",
    "\n",
    "        # median, with fast median algorithm\n",
    "        median = np.median(dataset[:,D])\n",
    "        median_low = domains[D][0]\n",
    "        median_up = domains[D][1]    \n",
    "\n",
    "        # split position\n",
    "        split_distance = 0\n",
    "        split_position = int(total_size / 2)\n",
    "\n",
    "        query_in_this_dim = queryset[:,D]\n",
    "        # bound the projected queries in this dimension\n",
    "        query_bound = bounding_union(query_in_this_dim)\n",
    "        \n",
    "        # check if the split position intersect some query boundings in this dim\n",
    "        for i in range(len(query_bound)):\n",
    "\n",
    "            # if intersect some query bounds (only possible to intersect one bounded query)\n",
    "            if median > query_bound[i][0] and median < query_bound[i][1]:\n",
    "\n",
    "                # check if the two end already exceeds domain, if yes, split from the middle\n",
    "                if query_bound[i][0] <= domains[D][0] and query_bound[i][1] >= domains[D][1]:\n",
    "                    split_distance = int(total_size / 2)\n",
    "                    break;\n",
    "                # if not exceeds, determine which side is closer to the median\n",
    "                else:\n",
    "                    # for the left side\n",
    "                    if query_bound[i][0] > domains[D][0]:\n",
    "                        median_low = query_bound[i][0]         \n",
    "                    # for the right side\n",
    "                    if query_bound[i][1] < domains[D][1]:\n",
    "                        median_up = query_bound[i][1]\n",
    "\n",
    "                # if not exceeds then choose the one that is closest from the median (in terms of #records!)\n",
    "                number_of_records_from_low_to_median = len(dataset[(dataset[:,D]>=median_low) & (dataset[:,D] < median)])\n",
    "                number_of_records_from_up_to_median = len(dataset[(dataset[:,D]<=median_up) & (dataset[:,D] > median)])\n",
    "                \n",
    "                if number_of_records_from_low_to_median <= number_of_records_from_up_to_median:\n",
    "                    median = median_low\n",
    "                    split_distance = number_of_records_from_low_to_median\n",
    "                else:\n",
    "                    median = median_up\n",
    "                    split_distance = number_of_records_from_up_to_median\n",
    "                    \n",
    "        # for each dimension, record its result\n",
    "        split_distance_each_dim.append(split_distance)\n",
    "        split_value_each_dim.append(median)\n",
    "\n",
    "    # aftern calculating the distance from median to its first non-cross split\n",
    "    split_distance_each_dim = np.asarray(split_distance_each_dim)\n",
    "    split_dimension = 0\n",
    "    split_value = 0\n",
    "    \n",
    "    # degradation mechansim (if no valid split position, then using round robin)\n",
    "    # if the median do not cross any historical query, split round robin to enhance robustness\n",
    "    if max(split_distance_each_dim) <= 10:\n",
    "        split_dimension = current_dim + 1\n",
    "        if split_dimension >= len(domains):\n",
    "            split_dimension %= len(domains)\n",
    "        split_value = np.median(dataset[:,split_dimension])\n",
    "    elif min(split_distance_each_dim) >= int((total_size / 2)-10): # if there is no valid split position\n",
    "        return [root_node], False\n",
    "    else:\n",
    "        split_dimension = np.argmin(split_distance_each_dim)  # get the split dimension\n",
    "        split_value = split_value_each_dim[split_dimension]\n",
    "        \n",
    "    # split the dataset according to the split position\n",
    "    sub_dataset1 = dataset[dataset[:,split_dimension] <= split_value]\n",
    "    sub_dataset2 = dataset[dataset[:,split_dimension] > split_value]\n",
    "    \n",
    "    if len(sub_dataset1) < data_threshold or len(sub_dataset2) < data_threshold:\n",
    "        return [root_node], True\n",
    "    \n",
    "    # change the domains\n",
    "    sub_domains1 = np.copy(domains)\n",
    "    sub_domains1[split_dimension][1] = split_value\n",
    "    sub_domains2 = np.copy(domains)\n",
    "    sub_domains2[split_dimension][0] = split_value\n",
    "    \n",
    "    sub_query1 = queryset[queryset[:,split_dimension,0] < split_value]\n",
    "    sub_query2 = queryset[queryset[:,split_dimension,1] > split_value]\n",
    "    \n",
    "    sub_kdnode_1 = [sub_domains1, len(sub_dataset1), accu_count_list[0] + 1, root_node[-4], -1, -1]\n",
    "    sub_kdnode_2 = [sub_domains2, len(sub_dataset2), accu_count_list[0] + 2, root_node[-4], -1, -1]\n",
    "    \n",
    "    root_node[-2] = sub_kdnode_1[-4]\n",
    "    root_node[-1] = sub_kdnode_2[-4]\n",
    "    \n",
    "    kdnode_dict.update({sub_kdnode_1[-4]: sub_kdnode_1})\n",
    "    kdnode_dict.update({sub_kdnode_2[-4]: sub_kdnode_2})\n",
    "    \n",
    "    accu_count_list[0] += 2\n",
    "    \n",
    "    # used to see the current depth\n",
    "    level += 1\n",
    "\n",
    "    # recursion\n",
    "    kdnodes = []\n",
    "    \n",
    "    # dataset, queryset, data_threshold, accu_count_list, kdnode_dict, root_node, level = 0, show_step\n",
    "    \n",
    "    kdnodes_1, is_valid_1 = AKD(sub_dataset1, sub_query1, data_threshold, accu_count_list, kdnode_dict, sub_kdnode_1, split_dimension, level, show_step)\n",
    "    kdnodes_2, is_valid_2 = AKD(sub_dataset2, sub_query2, data_threshold, accu_count_list, kdnode_dict, sub_kdnode_2, split_dimension, level, show_step)\n",
    "\n",
    "    # if one of the sub partition is not valid and contain queries\n",
    "    if (not is_valid_1 and len(sub_query1) > 0) or (not is_valid_2 and len(sub_query2) > 0):\n",
    "        return [root_node], True\n",
    "    \n",
    "    kdnodes = kdnodes_1 + kdnodes_2\n",
    "    return kdnodes, True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "importing Jupyter notebook from QueryGeneration.ipynb\n",
      "importing Jupyter notebook from Query.ipynb\n",
      "importing Jupyter notebook from Utils.ipynb\n"
     ]
    }
   ],
   "source": [
    "# = = = Global Configuration = = =\n",
    "\n",
    "scale_factor = 100\n",
    "prob_threshold = 1 / scale_factor\n",
    "total_dims = 16 # the dimensions of lineitem table\n",
    "domain_dims = 8 # the dimensions we used and maintain min max for\n",
    "chunk_size = 100000 # 0.1M \n",
    "\n",
    "# base_table_path = 'C:/Users/Cloud/iCloudDrive/HUAWEI_LKD/9a84f6cd-727f-4f10-ae95-10a0214e10a4-tpc-h-tool/2.18.0_rc2/dbgen/lineitem_'\n",
    "# table_path = base_table_path + str(scale_factor) + '.tbl'\n",
    "\n",
    "base_save_path = 'C:/Users/Cloud/iCloudDrive/HUAWEI_LKD/Dataset/Robust/dataset/lineitem_'\n",
    "save_path_data = base_save_path + str(scale_factor) + '_' + str(prob_threshold) + '.csv'\n",
    "save_path_domain = base_save_path + str(scale_factor) + '_' + str(prob_threshold) + '_domains.csv'\n",
    "\n",
    "# by default, the sampled size always equal to 6M (i.e., using scale factor 1), then for a higher scale factor, we need to divide it\n",
    "block_size = 1000000 // scale_factor # in original file, 1M rows take approximately 128MB\n",
    "\n",
    "# = = = Data Loading = = =\n",
    "dataset = np.genfromtxt(save_path_data, delimiter=',') # the sampled subset\n",
    "domains = np.genfromtxt(save_path_domain, delimiter=',') # the domain of that scale\n",
    "\n",
    "# Configuration\n",
    "used_dimensions = [1,2] # the second and third dimensions\n",
    "\n",
    "dataset = dataset[:,used_dimensions]\n",
    "domains = domains[used_dimensions]\n",
    "\n",
    "# = = = Query Loading = = =\n",
    "from QueryGeneration import *\n",
    "\n",
    "# = = = Query Generation = = =\n",
    "\n",
    "# Configuration\n",
    "total_queries = 100\n",
    "random_percentage = 0.20\n",
    "maximum_random_range = [int((domains[i,1] - domains[i,0])*0.1) for i in range(len(domains))]\n",
    "cluster_amount = 8\n",
    "maximum_range_dis = [int((domains[i,1] - domains[i,0])*0.1) for i in range(len(domains))]\n",
    "sigmas_percentage = [0.2,0.2]\n",
    "random_shift = False\n",
    "return_seperate = True\n",
    "\n",
    "# COMMENT THIS IF NOT GENERATING QUERIES\n",
    "# mixed_queris = generate_query_with_random(total_queries, random_percentage, domains, maximum_random_range, \n",
    "#                                           cluster_amount, maximum_range_dis, sigmas_percentage, random_shift, return_seperate)\n",
    "# plot_queries_2d_distribution_and_random(mixed_queris[1], mixed_queris[0], domains)\n",
    "# random_query = mixed_queris[0]\n",
    "# distribution_query = mixed_queris[1]\n",
    "\n",
    "# = = = Query Saving / Loading = = =\n",
    "\n",
    "# Configuration\n",
    "query_base_path = 'C:/Users/Cloud/iCloudDrive/HUAWEI_LKD/Dataset/NORA/query/'\n",
    "\n",
    "distribution_path = query_base_path + 'alpha_' + str(int(random_percentage*100)) +'_distribution.csv'\n",
    "random_path = query_base_path + 'alpha_' + str(int(random_percentage*100)) +'_random.csv'\n",
    "\n",
    "random_segmentation = int(total_queries * random_percentage / 2)\n",
    "distribution_segmentation = int(total_queries * (1 - random_percentage) / 2)\n",
    "\n",
    "### SELECT THIS ONE ###  save the generated queries\n",
    "# save_query(mixed_queris[0], random_path)\n",
    "# save_query(mixed_queris[1], distribution_path)\n",
    "# training_set = np.concatenate((random_query[0:random_segmentation], distribution_query[0:distribution_segmentation]), axis=0)\n",
    "# testing_set = np.concatenate((random_query[random_segmentation:], distribution_query[distribution_segmentation:]), axis = 0)\n",
    "\n",
    "### OR THIS ONE ###  load the generated query (if the query is generated from another domain, it should be regenerated!)\n",
    "distribution_query = load_query(distribution_path)\n",
    "random_query = load_query(random_path)\n",
    "training_set = np.concatenate((distribution_query[0:distribution_segmentation], random_query[0:random_segmentation]), axis=0)\n",
    "testing_set = np.concatenate((distribution_query[distribution_segmentation:], random_query[random_segmentation:]), axis = 0)\n",
    "\n",
    "from Query import *\n",
    "from Utils import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def kdnode_2_border(kdnode):\n",
    "    lower = [domain[0] for domain in kdnode[0]]\n",
    "    upper = [domain[1] for domain in kdnode[0]]\n",
    "    border = tuple(lower + upper) # non interleave\n",
    "    return border\n",
    "\n",
    "def query_2_border(query):\n",
    "    lower = [domain[0] for domain in query]\n",
    "    upper = [domain[1] for domain in query]\n",
    "    border = tuple(lower + upper) # non interleave\n",
    "    return border\n",
    "\n",
    "def GetEmptyHist(m, n):\n",
    "    hist = []\n",
    "    for i in range(m):\n",
    "        hist.append([])\n",
    "        for j in range(n):\n",
    "            hist[i].append([0,set()])\n",
    "    return hist\n",
    "\n",
    "def InserQueryIntoHist(index, SingleQuery, hist, domain, m, n, threshold):\n",
    "\n",
    "    dim1_step = (domain[0][1]-domain[0][0])/m\n",
    "    dim2_step = (domain[1][1]-domain[1][0])/n\n",
    "    \n",
    "    dim1_index_min = int((SingleQuery[0][0] - domain[0][0]) / dim1_step)\n",
    "    dim1_index_max = int((SingleQuery[0][1] - domain[0][0]) / dim1_step)\n",
    "    dim2_index_min = int((SingleQuery[1][0] - domain[1][0]) / dim1_step)\n",
    "    dim2_index_max = int((SingleQuery[1][1] - domain[1][0]) / dim1_step)\n",
    "    \n",
    "    if dim1_index_min >= m:\n",
    "        dim1_index_min = m-1\n",
    "    if dim1_index_max >= m:\n",
    "        dim1_index_max = m-1\n",
    "    if dim2_index_min >= n:\n",
    "        dim2_index_min = n-1\n",
    "    if dim2_index_max >= n:\n",
    "        dim2_index_max = n-1\n",
    "        \n",
    "    distribution_regions = []\n",
    "    for m in range(dim1_index_min, dim1_index_max+1):\n",
    "        for n in range(dim2_index_min, dim2_index_max+1):\n",
    "            hist[m][n][0] += 1\n",
    "            hist[m][n][1].add(index)\n",
    "            if hist[m][n][0]-1 < threshold and hist[m][n][0] >= threshold: # whether a region just become distribution query region\n",
    "                distribution_regions.append((m,n))\n",
    "            \n",
    "    return distribution_regions\n",
    "            \n",
    "    # also need to check whether a region just become a distribution query region\n",
    "            \n",
    "def RemoveQueryFromHist(index, SingleQuery, hist, domain, m, n, threshold):\n",
    "    \n",
    "    dim1_step = (domain[0][1]-domain[0][0])/m\n",
    "    dim2_step = (domain[1][1]-domain[1][0])/n\n",
    "    \n",
    "    dim1_index_min = int((SingleQuery[0][0] - domain[0][0]) / dim1_step)\n",
    "    dim1_index_max = int((SingleQuery[0][1] - domain[0][0]) / dim1_step)\n",
    "    dim2_index_min = int((SingleQuery[1][0] - domain[1][0]) / dim1_step)\n",
    "    dim2_index_max = int((SingleQuery[1][1] - domain[1][0]) / dim1_step)\n",
    "    \n",
    "    if dim1_index_min >= m:\n",
    "        dim1_index_min = m-1\n",
    "    if dim1_index_max >= m:\n",
    "        dim1_index_max = m-1\n",
    "    if dim2_index_min >= n:\n",
    "        dim2_index_min = n-1\n",
    "    if dim2_index_max >= n:\n",
    "        dim2_index_max = n-1\n",
    "            \n",
    "    random_regions = []\n",
    "    for m in range(dim1_index_min, dim1_index_max+1):\n",
    "        for n in range(dim2_index_min, dim2_index_max+1):\n",
    "            hist[m][n][0] -= 1\n",
    "            hist[m][n][1].remove(index)\n",
    "            if hist[m][n][0] < threshold and hist[m][n][0] + 1 >= threshold: # consider whether a region just become random query region\n",
    "                random_regions.append((m,n))\n",
    "            \n",
    "    return random_regions\n",
    "        \n",
    "\n",
    "# need to properly determine wheter m and n and threshold\n",
    "# perform binary search on this? to maximize the differen?\n",
    "# using DBSCAN related methods?\n",
    "def filter_distribution_query(fusion_queryset, domains, m, n, threshold):\n",
    "    \n",
    "    fusion_queryset = np.array(fusion_queryset)\n",
    "    \n",
    "    queryset_hist = GetEmptyHist(m, n)\n",
    "    for i in range(len(fusion_queryset)):\n",
    "        InserQueryIntoHist(i, fusion_queryset[i], queryset_hist, domains, m, n, threshold)\n",
    "        \n",
    "    filtered_distribution_query_index = []\n",
    "        \n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            if queryset_hist[i][j][0] >= threshold:\n",
    "                filtered_distribution_query_index += queryset_hist[i][j][1] # id\n",
    "            \n",
    "    filtered_distribution_query_index = set(filtered_distribution_query_index)\n",
    "    filtered_distribution_query_index = list(filtered_distribution_query_index)\n",
    "    distribution_query = fusion_queryset[filtered_distribution_query_index]\n",
    "    \n",
    "    return distribution_query, queryset_hist\n",
    "\n",
    "# only retrieve the leaf nodes\n",
    "def find_all_leafnode_ids(initial_id, kdnode_dict):\n",
    "    if kdnode_dict[initial_id][-1] == -1: # leaf node, has no child\n",
    "        return [initial_id]\n",
    "    else:\n",
    "        kid1 = kdnode_dict[initial_id][-2]\n",
    "        kid2 = kdnode_dict[initial_id][-1]\n",
    "        return find_all_leafnode_ids(kid1, kdnode_dict) + find_all_leafnode_ids(kid2, kdnode_dict)\n",
    "\n",
    "def find_all_subnode_ids(initial_id, kdnode_dict):\n",
    "    if kdnode_dict[initial_id][-1] == -1: # leaf node, has no child\n",
    "        return [initial_id]\n",
    "    else:\n",
    "        kid1 = kdnode_dict[initial_id][-2]\n",
    "        kid2 = kdnode_dict[initial_id][-1]\n",
    "        return [initial_id] + find_all_subnode_ids(kid1, kdnode_dict) + find_all_subnode_ids(kid2, kdnode_dict)\n",
    "\n",
    "def find_subset(dataset, domain):\n",
    "    constraints = []\n",
    "    for i in range(len(domain)):\n",
    "        constraint_1 = dataset[:,i] >= domain[i][0]\n",
    "        constraint_2 = dataset[:,i] < domain[i][1]\n",
    "        constraints.append(constraint_1)\n",
    "        constraints.append(constraint_2)\n",
    "    constraint = np.all(constraints, axis=0)\n",
    "    return dataset[constraint]\n",
    "    \n",
    "# we should index kdnodes by Rtree first (after initialization)\n",
    "# after a region just become random region\n",
    "def repartition_for_robustness(hist_indexes, m, n, dataset, domain, d_threshold, q_threshold, kdnode_idx, query_idx, \n",
    "                               kdnode_dict, accu_count_list):\n",
    "    \n",
    "    dim1_step = (domain[0][1]-domain[0][0])/m\n",
    "    dim2_step = (domain[1][1]-domain[1][0])/n\n",
    "    \n",
    "    kdnode_ids = []\n",
    "    \n",
    "    # first, find out all the overlap kdnodes\n",
    "    for i in range(len(hist_indexes)):\n",
    "        d1_lower = dim1_step * hist_indexes[i][0]\n",
    "        d1_upper = dim1_step * (hist_indexes[i][0]+1)\n",
    "        d2_lower = dim2_step * hist_indexes[i][1]\n",
    "        d2_upper = dim2_step * (hist_indexes[i][1]+1)\n",
    "    \n",
    "        # find the kdnode in this region\n",
    "        border = (d1_lower, d2_lower, d1_upper, d2_upper)\n",
    "        overlapped_kdnode_id = list(kdnode_idx.intersection(border))\n",
    "        kdnode_ids += overlapped_kdnode_id\n",
    "        \n",
    "    kdnode_ids = set(kdnode_ids)\n",
    "    \n",
    "    # second, try to process them\n",
    "    while len(kdnode_ids) > 0:\n",
    "        kid = kdnode_ids.pop()\n",
    "        kid_node = kdnode_dict[kid]\n",
    "        while True:\n",
    "            pid = kid_node[-3]\n",
    "            parent_kdnode = kdnode_dict[pid]    \n",
    "            parent_border = (parent_kdnode[0][0][0], parent_kdnode[0][1][0], parent_kdnode[0][0][1], parent_kdnode[0][1][1])\n",
    "            overlapped_query_id = list(query_idx.intersection(parent_border))\n",
    "            if len(overlapped_query_id) >= q_threshold:\n",
    "                break\n",
    "            else:\n",
    "                kid_node = parent_kdnode\n",
    "                if parent_kdnode[-3] == -1:\n",
    "                    break\n",
    "        \n",
    "        # remove all the sub kdnode ids under this region from the set, only leaf nodes should be considered\n",
    "        to_delete_leafnode_ids = find_all_leafnode_ids(kid_node[-4], kdnode_dict)\n",
    "        to_delete_leafnode_ids = set(to_delete_leafnode_ids)\n",
    "        kdnode_ids -= to_delete_leafnode_ids\n",
    "        \n",
    "        if kid_node[-5] < 2*d_threshold:\n",
    "            continue\n",
    "        \n",
    "        # remove the deleted kdnodes from kdnode_dict, including all the intermediate nodes\n",
    "        to_delete_subnode_ids = find_all_subnode_ids(kid_node[-4], kdnode_dict)\n",
    "        to_delete_subnode_ids.remove(kid_node[-4]) # keep the root\n",
    "        \n",
    "        \n",
    "        # repartition this region (kid_node) with KDT\n",
    "        temp_dataset = find_subset(dataset, kid_node[0])\n",
    "\n",
    "        #processed_kdnodes = TraditionalKDTree(temp_dataset, 0, kid_node[0], d_threshold, 0, kdnode_dict, accu_count_list, kid_node[-4])\n",
    "        processed_kdnodes = KDPartition(temp_dataset, 0, d_threshold, kid_node, kdnode_dict, accu_count_list)\n",
    "        \n",
    "        # process kdnode_idx, remove the deleted leaf nodes\n",
    "        for node_id in to_delete_leafnode_ids:\n",
    "            l1 = kdnode_dict[node_id][0][0][0]\n",
    "            l2 = kdnode_dict[node_id][0][1][0]\n",
    "            u1 = kdnode_dict[node_id][0][0][1]\n",
    "            u2 = kdnode_dict[node_id][0][1][1]\n",
    "            kdnode_idx.delete(node_id, (l1,l2,u1,u2))\n",
    "        \n",
    "        for node_id in to_delete_subnode_ids:\n",
    "            del kdnode_dict[node_id]\n",
    "        \n",
    "        # process kdnode_idx, add the newly created leaf nodes\n",
    "        for node in processed_kdnodes:\n",
    "            kdnode_idx.insert(node[2], (node[0][0][0], node[0][1][0], node[0][0][1],node[0][1][1]), node)\n",
    "        \n",
    "        \n",
    "# after a region just become distribution region\n",
    "def repartition_for_adaptation(total_queryset, hist_indexes, m, n, dataset, domain, d_threshold, q_threshold, kdnode_idx, query_idx, \n",
    "                               kdnode_dict, accu_count_list):\n",
    "    \n",
    "    dim1_step = (domain[0][1]-domain[0][0])/m\n",
    "    dim2_step = (domain[1][1]-domain[1][0])/n\n",
    "    \n",
    "    kdnode_ids = []\n",
    "    \n",
    "    # first, find out all the overlap kdnodes\n",
    "    for i in range(len(hist_indexes)):\n",
    "        d1_lower = dim1_step * hist_indexes[i][0]\n",
    "        d1_upper = dim1_step * (hist_indexes[i][0]+1)\n",
    "        d2_lower = dim2_step * hist_indexes[i][1]\n",
    "        d2_upper = dim2_step * (hist_indexes[i][1]+1)\n",
    "    \n",
    "        # find the kdnode in this region\n",
    "        border = (d1_lower, d2_lower, d1_upper, d2_upper)\n",
    "        overlapped_kdnode_id = list(kdnode_idx.intersection(border))\n",
    "        kdnode_ids += overlapped_kdnode_id\n",
    "        \n",
    "    kdnode_ids = set(kdnode_ids) # the leaf kdnodes to repartition\n",
    "    \n",
    "    while len(kdnode_ids) > 0:\n",
    "        kid = kdnode_ids.pop()\n",
    "        kid_node = kdnode_dict[kid]\n",
    "        parent_node = None\n",
    "        \n",
    "        while True:\n",
    "            pid = kid_node[-3]\n",
    "            parent_node = kdnode_dict[pid]\n",
    "            another_child_id = parent_node[-2]\n",
    "            if another_child_id == kid_node[-4]:\n",
    "                another_child_id = parent_node[-1]\n",
    "            \n",
    "            if another_child_id == -1:\n",
    "                break\n",
    "            \n",
    "            another_child_node = kdnode_dict[another_child_id]\n",
    "            another_child_border = (another_child_node [0][0][0], another_child_node [0][1][0], \n",
    "                                    another_child_node [0][0][1], another_child_node [0][1][1])      \n",
    "            \n",
    "            overlapped_query_id = list(query_idx.intersection(another_child_border))\n",
    "            if len(overlapped_query_id) < q_threshold or parent_node[-3] == -1:\n",
    "                break\n",
    "            else:\n",
    "                kid_node = parent_node\n",
    "        \n",
    "        # remove all the sub kdnode ids under this region from the set, only leaf nodes should be considered\n",
    "        to_delete_leafnode_ids = find_all_leafnode_ids(parent_node[-4], kdnode_dict) # delete the parent's subnodes!!! instead of kid's\n",
    "        to_delete_leafnode_ids = set(to_delete_leafnode_ids)\n",
    "        kdnode_ids -= to_delete_leafnode_ids\n",
    "        \n",
    "        if parent_node[-5] < 2*d_threshold:\n",
    "            continue\n",
    "    \n",
    "        # remove the deleted kdnodes from kdnode_dict, including all the intermediate nodes\n",
    "        to_delete_subnode_ids = find_all_subnode_ids(parent_node[-4], kdnode_dict)\n",
    "        to_delete_subnode_ids.remove(parent_node[-4]) # keep the root\n",
    "            \n",
    "        temp_dataset = find_subset(dataset, parent_node[0])\n",
    "        \n",
    "        # fileter queries only within the parent kdnode's domain \n",
    "        filtered_queryset_ids = list(query_idx.intersection(kdnode_2_border(parent_node)))\n",
    "        filtered_queryset = total_queryset[filtered_queryset_ids] # total_queryset should be in the form of numpy\n",
    "        #print('filtered_queryset size: ', len(filtered_queryset))\n",
    "        if len(filtered_queryset) == 0:\n",
    "            continue\n",
    "            \n",
    "        processed_kdnodes = LKD_Robust(temp_dataset, filtered_queryset, parent_node[0], d_threshold, (m,n), \n",
    "                                                   accu_count_list, kdnode_dict, parent_node)\n",
    "        \n",
    "        # perform KDT partition for the nodes generated by Qd-Tree methods\n",
    "        processed_kdnodes = post_kdnode_partition(processed_kdnodes, d_threshold, dataset, kdnode_dict, accu_count_list)\n",
    "        \n",
    " \n",
    "        # process kdnode_idx, remove the deleted leaf nodes\n",
    "        for node_id in to_delete_leafnode_ids:\n",
    "            l1 = kdnode_dict[node_id][0][0][0]\n",
    "            l2 = kdnode_dict[node_id][0][1][0]\n",
    "            u1 = kdnode_dict[node_id][0][0][1]\n",
    "            u2 = kdnode_dict[node_id][0][1][1]\n",
    "            kdnode_idx.delete(node_id, (l1,l2,u1,u2))\n",
    "        \n",
    "        for node_id in to_delete_subnode_ids:\n",
    "            del kdnode_dict[node_id]\n",
    "        \n",
    "        # process kdnode_idx, add the newly created leaf nodes\n",
    "        for node in processed_kdnodes:\n",
    "            kdnode_idx.insert(node[2], (node[0][0][0], node[0][1][0], node[0][0][1],node[0][1][1]), node)\n",
    "            \n",
    "from collections import defaultdict\n",
    "\n",
    "# updated version: only consider those overlap the core region a lot (i.e., more than 50%)\n",
    "def filter_distribution_query_V2(fusion_queryset, domains, m, n, threshold):\n",
    "    \n",
    "    fusion_queryset = np.array(fusion_queryset)\n",
    "    \n",
    "    queryset_hist = GetEmptyHist(m, n)\n",
    "    for i in range(len(fusion_queryset)):\n",
    "        InserQueryIntoHist(i, fusion_queryset[i], queryset_hist, domains, m, n, threshold)\n",
    "        \n",
    "    filtered_distribution_query_index = []\n",
    "    \n",
    "    bins_query_overlap_distribution = defaultdict(int)\n",
    "    bins_query_overlap_total = defaultdict(int)\n",
    "    \n",
    "    # find out which bin is distributive bin\n",
    "    # for each query, count the number of distributed bins it overlap\n",
    "    # then divide by the total bins it overlap\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            if queryset_hist[i][j][0] >= threshold:\n",
    "                filtered_distribution_query_index += queryset_hist[i][j][1] # id\n",
    "                for qid in queryset_hist[i][j][1]:\n",
    "                    bins_query_overlap_distribution[qid] += 1\n",
    "            for qid in queryset_hist[i][j][1]:\n",
    "                bins_query_overlap_total[qid] += 1\n",
    "    \n",
    "    filtered_distribution_query_index = set(filtered_distribution_query_index)\n",
    "    filtered_distribution_query_index = list(filtered_distribution_query_index)\n",
    "    \n",
    "    # check wheteher the overlap region takes more than half of the total\n",
    "    final_filtered_distribution_query_index = []\n",
    "    for qid in filtered_distribution_query_index:\n",
    "        if bins_query_overlap_distribution[qid] / bins_query_overlap_total[qid] >= 0.5:\n",
    "            final_filtered_distribution_query_index.append(qid)\n",
    "    \n",
    "    distribution_query = fusion_queryset[final_filtered_distribution_query_index]\n",
    "    \n",
    "    return distribution_query, queryset_hist\n",
    "\n",
    "def is_overlap(query1, query2):\n",
    "    for dim in range(len(query1)):\n",
    "        if query1[dim][0] > query2[dim][1] or query1[dim][1] < query2[dim][0]:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "def union_query(query1, query2):\n",
    "    union_query = [[min(query1[dim][0], query2[dim][0]), max(query1[dim][1], query2[dim][1])] for dim in range(len(query1))]\n",
    "    return union_query\n",
    "\n",
    "def query_bounding(distribution_query):\n",
    "    '''\n",
    "    for the distribution queries, we union them if there exist an overlap\n",
    "    '''\n",
    "    bounded_query = []\n",
    "    for query in distribution_query:\n",
    "        # check if it overlap with any query in the bounded query\n",
    "        union_tag = False\n",
    "        while True:\n",
    "            for i, bq in enumerate(bounded_query):\n",
    "                if is_overlap(query, bq):\n",
    "                    # union these 2 queris and remove the overlap queries\n",
    "                    query = union_query(query, bq)\n",
    "                    del bounded_query[i]\n",
    "                    union_tag = True\n",
    "                    break\n",
    "            if union_tag:\n",
    "                union_tag = False\n",
    "            else:\n",
    "                break\n",
    "        bounded_query.append(query)\n",
    "        #print(\"current bounded queries: \", bounded_query)\n",
    "    \n",
    "    return bounded_query"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "data_threshold = block_size\n",
    "accu_count_list = [0]\n",
    "kdnode_dict = {}\n",
    "root_node = [domains, len(dataset), 0, -1, -1, -1]\n",
    "\n",
    "filtered_queries, query_hist = filter_distribution_query_V2(training_set, domains, 1000, 1000, 2)\n",
    "filtered_queries = query_bounding(filtered_queries)\n",
    "filtered_queries = np.array(filtered_queries)\n",
    "adk_kdnode, is_valid = AKD(dataset, filtered_queries, data_threshold, accu_count_list, kdnode_dict, root_node, \n",
    "                           current_dim = 0, level = 0, show_step = False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[array([[1.00000e+00, 5.00355e+06],\n",
       "         [1.00000e+00, 2.52949e+05]]), 380428, 7, 5, -1, -1],\n",
       " [array([[1.00000e+00, 5.00355e+06],\n",
       "         [2.52949e+05, 3.79954e+05]]), 190217, 9, 8, -1, -1],\n",
       " [array([[1.00000e+00, 5.00355e+06],\n",
       "         [3.79954e+05, 4.43363e+05]]), 95107, 11, 10, -1, -1],\n",
       " [array([[1.00000e+00, 5.00355e+06],\n",
       "         [4.43363e+05, 4.74857e+05]]), 47552, 13, 12, -1, -1],\n",
       " [array([[1.00000000e+00, 5.00355000e+06],\n",
       "         [4.74857000e+05, 5.06353313e+05]]), 47551, 14, 12, 15, 16],\n",
       " [array([[1.00000000e+00, 5.00355000e+06],\n",
       "         [5.06353313e+05, 1.00000000e+06]]), 739473, 6, 3, -1, -1],\n",
       " [array([[5.00355000e+06, 1.00031980e+07],\n",
       "         [1.00000000e+00, 2.44113286e+05]]), 365718, 19, 17, -1, -1],\n",
       " [array([[ 5003550.        , 10003198.        ],\n",
       "         [  244113.28641594,   284908.77577889]]), 61558, 25, 23, 27, 28],\n",
       " [array([[ 5003550.        , 10003198.        ],\n",
       "         [  284908.77577889,   308200.        ]]), 34555, 26, 23, -1, -1],\n",
       " [array([[ 5003550., 10003198.],\n",
       "         [  308200.,   372544.]]), 96111, 24, 21, -1, -1],\n",
       " [array([[ 5003550., 10003198.],\n",
       "         [  372544.,   500345.]]), 192223, 22, 20, -1, -1],\n",
       " [array([[ 5003550.        , 10003198.        ],\n",
       "         [  500345.        ,   726195.40592001]]), 339424, 29, 18, -1, -1],\n",
       " [array([[5003550.        , 8056887.00925369],\n",
       "         [ 726195.40592001,  794551.        ]]), 64715, 35, 33, 37, 38],\n",
       " [array([[ 8056887.00925369, 10003198.        ],\n",
       "         [  726195.40592001,   794551.        ]]), 37971, 36, 33, -1, -1],\n",
       " [array([[ 5003550., 10003198.],\n",
       "         [  794551.,   863244.]]), 102684, 34, 31, -1, -1],\n",
       " [array([[ 5003550., 10003198.],\n",
       "         [  863244.,  1000000.]]), 205368, 32, 30, -1, -1],\n",
       " [array([[1.00031980e+07, 1.50003335e+07],\n",
       "         [1.00000000e+00, 4.99483000e+05]]), 750164, 41, 39, -1, -1],\n",
       " [array([[1.50003335e+07, 1.75007620e+07],\n",
       "         [1.00000000e+00, 2.49838000e+05]]), 187542, 45, 43, -1, -1],\n",
       " [array([[1.7500762e+07, 2.0000000e+07],\n",
       "         [1.0000000e+00, 2.4983800e+05]]), 187541, 46, 43, 47, 48],\n",
       " [array([[15000333.5, 20000000. ],\n",
       "         [  249838. ,   499483. ]]), 375081, 44, 42, -1, -1],\n",
       " [array([[10003198. , 14999253.5],\n",
       "         [  499483. ,   624946.5]]), 187541, 53, 51, -1, -1],\n",
       " [array([[10003198.       , 14999253.5      ],\n",
       "         [  624946.5      ,   675586.2294262]]), 76631, 55, 54, -1, -1],\n",
       " [array([[10003198.        , 11991928.90996604],\n",
       "         [  675586.2294262 ,   749558.        ]]), 43998, 57, 56, -1, -1],\n",
       " [array([[11991928.90996604, 14999253.5       ],\n",
       "         [  675586.2294262 ,   749558.        ]]), 66912, 58, 56, 59, 60],\n",
       " [array([[10003198. , 14999253.5],\n",
       "         [  749558. ,   812177. ]]), 93773, 63, 61, -1, -1],\n",
       " [array([[10003198., 11325585.],\n",
       "         [  812177.,   874504.]]), 24315, 67, 65, -1, -1],\n",
       " [array([[11325585.        , 12589113.49786483],\n",
       "         [  812177.        ,   874504.        ]]), 24314, 68, 65, -1, -1],\n",
       " [array([[12589113.49786483, 14999253.5       ],\n",
       "         [  812177.        ,   874504.        ]]), 45139, 66, 64, -1, -1],\n",
       " [array([[10003198. , 14999253.5],\n",
       "         [  874504. ,  1000000. ]]), 187540, 62, 52, -1, -1],\n",
       " [array([[14999253.5, 17493680. ],\n",
       "         [  499483. ,  1000000. ]]), 375082, 69, 50, -1, -1],\n",
       " [array([[17493680.        , 18746053.        ],\n",
       "         [  499483.        ,   712699.98778989]]), 79834, 73, 71, -1, -1],\n",
       " [array([[17493680.        , 18746053.        ],\n",
       "         [  712699.98778989,  1000000.        ]]), 107707, 74, 71, 75, 76],\n",
       " [array([[18746053., 20000000.],\n",
       "         [  499483.,  1000000.]]), 187540, 72, 70, -1, -1]]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "adk_kdnode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: [array([[1.0000000e+00, 1.0003198e+07],\n",
       "         [1.0000000e+00, 1.0000000e+06]]), 3000655, 1, 0, 3, 4],\n",
       " 2: [array([[1.0003198e+07, 2.0000000e+07],\n",
       "         [1.0000000e+00, 1.0000000e+06]]), 3000654, 2, 0, 39, 40],\n",
       " 3: [array([[1.00000e+00, 5.00355e+06],\n",
       "         [1.00000e+00, 1.00000e+06]]), 1500328, 3, 1, 5, 6],\n",
       " 4: [array([[5.0035500e+06, 1.0003198e+07],\n",
       "         [1.0000000e+00, 1.0000000e+06]]), 1500327, 4, 1, 17, 18],\n",
       " 5: [array([[1.00000000e+00, 5.00355000e+06],\n",
       "         [1.00000000e+00, 5.06353313e+05]]), 760855, 5, 3, 7, 8],\n",
       " 6: [array([[1.00000000e+00, 5.00355000e+06],\n",
       "         [5.06353313e+05, 1.00000000e+06]]), 739473, 6, 3, -1, -1],\n",
       " 7: [array([[1.00000e+00, 5.00355e+06],\n",
       "         [1.00000e+00, 2.52949e+05]]), 380428, 7, 5, -1, -1],\n",
       " 8: [array([[1.00000000e+00, 5.00355000e+06],\n",
       "         [2.52949000e+05, 5.06353313e+05]]), 380427, 8, 5, 9, 10],\n",
       " 9: [array([[1.00000e+00, 5.00355e+06],\n",
       "         [2.52949e+05, 3.79954e+05]]), 190217, 9, 8, -1, -1],\n",
       " 10: [array([[1.00000000e+00, 5.00355000e+06],\n",
       "         [3.79954000e+05, 5.06353313e+05]]), 190210, 10, 8, 11, 12],\n",
       " 11: [array([[1.00000e+00, 5.00355e+06],\n",
       "         [3.79954e+05, 4.43363e+05]]), 95107, 11, 10, -1, -1],\n",
       " 12: [array([[1.00000000e+00, 5.00355000e+06],\n",
       "         [4.43363000e+05, 5.06353313e+05]]), 95103, 12, 10, 13, 14],\n",
       " 13: [array([[1.00000e+00, 5.00355e+06],\n",
       "         [4.43363e+05, 4.74857e+05]]), 47552, 13, 12, -1, -1],\n",
       " 14: [array([[1.00000000e+00, 5.00355000e+06],\n",
       "         [4.74857000e+05, 5.06353313e+05]]), 47551, 14, 12, 15, 16],\n",
       " 15: [array([[1.00000000e+00, 5.00355000e+06],\n",
       "         [4.74857000e+05, 4.83714538e+05]]), 13362, 15, 14, -1, -1],\n",
       " 16: [array([[1.00000000e+00, 5.00355000e+06],\n",
       "         [4.83714538e+05, 5.06353313e+05]]), 34189, 16, 14, -1, -1],\n",
       " 17: [array([[5.0035500e+06, 1.0003198e+07],\n",
       "         [1.0000000e+00, 5.0034500e+05]]), 750165, 17, 4, 19, 20],\n",
       " 18: [array([[ 5003550., 10003198.],\n",
       "         [  500345.,  1000000.]]), 750162, 18, 4, 29, 30],\n",
       " 19: [array([[5.00355000e+06, 1.00031980e+07],\n",
       "         [1.00000000e+00, 2.44113286e+05]]), 365718, 19, 17, -1, -1],\n",
       " 20: [array([[ 5003550.        , 10003198.        ],\n",
       "         [  244113.28641594,   500345.        ]]), 384447, 20, 17, 21, 22],\n",
       " 21: [array([[ 5003550.        , 10003198.        ],\n",
       "         [  244113.28641594,   372544.        ]]), 192224, 21, 20, 23, 24],\n",
       " 22: [array([[ 5003550., 10003198.],\n",
       "         [  372544.,   500345.]]), 192223, 22, 20, -1, -1],\n",
       " 23: [array([[ 5003550.        , 10003198.        ],\n",
       "         [  244113.28641594,   308200.        ]]), 96113, 23, 21, 25, 26],\n",
       " 24: [array([[ 5003550., 10003198.],\n",
       "         [  308200.,   372544.]]), 96111, 24, 21, -1, -1],\n",
       " 25: [array([[ 5003550.        , 10003198.        ],\n",
       "         [  244113.28641594,   284908.77577889]]), 61558, 25, 23, 27, 28],\n",
       " 26: [array([[ 5003550.        , 10003198.        ],\n",
       "         [  284908.77577889,   308200.        ]]), 34555, 26, 23, -1, -1],\n",
       " 27: [array([[5003550.        , 6640538.01406581],\n",
       "         [ 244113.28641594,  284908.77577889]]), 20725, 27, 25, -1, -1],\n",
       " 28: [array([[ 6640538.01406581, 10003198.        ],\n",
       "         [  244113.28641594,   284908.77577889]]), 40833, 28, 25, -1, -1],\n",
       " 29: [array([[ 5003550.        , 10003198.        ],\n",
       "         [  500345.        ,   726195.40592001]]), 339424, 29, 18, -1, -1],\n",
       " 30: [array([[ 5003550.        , 10003198.        ],\n",
       "         [  726195.40592001,  1000000.        ]]), 410738, 30, 18, 31, 32],\n",
       " 31: [array([[ 5003550.        , 10003198.        ],\n",
       "         [  726195.40592001,   863244.        ]]), 205370, 31, 30, 33, 34],\n",
       " 32: [array([[ 5003550., 10003198.],\n",
       "         [  863244.,  1000000.]]), 205368, 32, 30, -1, -1],\n",
       " 33: [array([[ 5003550.        , 10003198.        ],\n",
       "         [  726195.40592001,   794551.        ]]), 102686, 33, 31, 35, 36],\n",
       " 34: [array([[ 5003550., 10003198.],\n",
       "         [  794551.,   863244.]]), 102684, 34, 31, -1, -1],\n",
       " 35: [array([[5003550.        , 8056887.00925369],\n",
       "         [ 726195.40592001,  794551.        ]]), 64715, 35, 33, 37, 38],\n",
       " 36: [array([[ 8056887.00925369, 10003198.        ],\n",
       "         [  726195.40592001,   794551.        ]]), 37971, 36, 33, -1, -1],\n",
       " 37: [array([[5003550.        , 6200693.95096428],\n",
       "         [ 726195.40592001,  794551.        ]]), 23505, 37, 35, -1, -1],\n",
       " 38: [array([[6200693.95096428, 8056887.00925369],\n",
       "         [ 726195.40592001,  794551.        ]]), 41210, 38, 35, -1, -1],\n",
       " 39: [array([[1.0003198e+07, 2.0000000e+07],\n",
       "         [1.0000000e+00, 4.9948300e+05]]), 1500328, 39, 2, 41, 42],\n",
       " 40: [array([[10003198., 20000000.],\n",
       "         [  499483.,  1000000.]]), 1500326, 40, 2, 49, 50],\n",
       " 41: [array([[1.00031980e+07, 1.50003335e+07],\n",
       "         [1.00000000e+00, 4.99483000e+05]]), 750164, 41, 39, -1, -1],\n",
       " 42: [array([[1.50003335e+07, 2.00000000e+07],\n",
       "         [1.00000000e+00, 4.99483000e+05]]), 750164, 42, 39, 43, 44],\n",
       " 43: [array([[1.50003335e+07, 2.00000000e+07],\n",
       "         [1.00000000e+00, 2.49838000e+05]]), 375083, 43, 42, 45, 46],\n",
       " 44: [array([[15000333.5, 20000000. ],\n",
       "         [  249838. ,   499483. ]]), 375081, 44, 42, -1, -1],\n",
       " 45: [array([[1.50003335e+07, 1.75007620e+07],\n",
       "         [1.00000000e+00, 2.49838000e+05]]), 187542, 45, 43, -1, -1],\n",
       " 46: [array([[1.7500762e+07, 2.0000000e+07],\n",
       "         [1.0000000e+00, 2.4983800e+05]]), 187541, 46, 43, 47, 48],\n",
       " 47: [array([[1.75007620e+07, 2.00000000e+07],\n",
       "         [1.00000000e+00, 1.42475814e+05]]), 106740, 47, 46, -1, -1],\n",
       " 48: [array([[17500762.        , 20000000.        ],\n",
       "         [  142475.81446018,   249838.        ]]), 80801, 48, 46, -1, -1],\n",
       " 49: [array([[10003198. , 14999253.5],\n",
       "         [  499483. ,  1000000. ]]), 750163, 49, 40, 51, 52],\n",
       " 50: [array([[14999253.5, 20000000. ],\n",
       "         [  499483. ,  1000000. ]]), 750163, 50, 40, 69, 70],\n",
       " 51: [array([[10003198. , 14999253.5],\n",
       "         [  499483. ,   749558. ]]), 375082, 51, 49, 53, 54],\n",
       " 52: [array([[10003198. , 14999253.5],\n",
       "         [  749558. ,  1000000. ]]), 375081, 52, 49, 61, 62],\n",
       " 53: [array([[10003198. , 14999253.5],\n",
       "         [  499483. ,   624946.5]]), 187541, 53, 51, -1, -1],\n",
       " 54: [array([[10003198. , 14999253.5],\n",
       "         [  624946.5,   749558. ]]), 187541, 54, 51, 55, 56],\n",
       " 55: [array([[10003198.       , 14999253.5      ],\n",
       "         [  624946.5      ,   675586.2294262]]), 76631, 55, 54, -1, -1],\n",
       " 56: [array([[10003198.       , 14999253.5      ],\n",
       "         [  675586.2294262,   749558.       ]]), 110910, 56, 54, 57, 58],\n",
       " 57: [array([[10003198.        , 11991928.90996604],\n",
       "         [  675586.2294262 ,   749558.        ]]), 43998, 57, 56, -1, -1],\n",
       " 58: [array([[11991928.90996604, 14999253.5       ],\n",
       "         [  675586.2294262 ,   749558.        ]]), 66912, 58, 56, 59, 60],\n",
       " 59: [array([[11991928.90996604, 13496763.5       ],\n",
       "         [  675586.2294262 ,   749558.        ]]), 33456, 59, 58, -1, -1],\n",
       " 60: [array([[13496763.5      , 14999253.5      ],\n",
       "         [  675586.2294262,   749558.       ]]), 33456, 60, 58, -1, -1],\n",
       " 61: [array([[10003198. , 14999253.5],\n",
       "         [  749558. ,   874504. ]]), 187541, 61, 52, 63, 64],\n",
       " 62: [array([[10003198. , 14999253.5],\n",
       "         [  874504. ,  1000000. ]]), 187540, 62, 52, -1, -1],\n",
       " 63: [array([[10003198. , 14999253.5],\n",
       "         [  749558. ,   812177. ]]), 93773, 63, 61, -1, -1],\n",
       " 64: [array([[10003198. , 14999253.5],\n",
       "         [  812177. ,   874504. ]]), 93768, 64, 61, 65, 66],\n",
       " 65: [array([[10003198.        , 12589113.49786483],\n",
       "         [  812177.        ,   874504.        ]]), 48629, 65, 64, 67, 68],\n",
       " 66: [array([[12589113.49786483, 14999253.5       ],\n",
       "         [  812177.        ,   874504.        ]]), 45139, 66, 64, -1, -1],\n",
       " 67: [array([[10003198., 11325585.],\n",
       "         [  812177.,   874504.]]), 24315, 67, 65, -1, -1],\n",
       " 68: [array([[11325585.        , 12589113.49786483],\n",
       "         [  812177.        ,   874504.        ]]), 24314, 68, 65, -1, -1],\n",
       " 69: [array([[14999253.5, 17493680. ],\n",
       "         [  499483. ,  1000000. ]]), 375082, 69, 50, -1, -1],\n",
       " 70: [array([[17493680., 20000000.],\n",
       "         [  499483.,  1000000.]]), 375081, 70, 50, 71, 72],\n",
       " 71: [array([[17493680., 18746053.],\n",
       "         [  499483.,  1000000.]]), 187541, 71, 70, 73, 74],\n",
       " 72: [array([[18746053., 20000000.],\n",
       "         [  499483.,  1000000.]]), 187540, 72, 70, -1, -1],\n",
       " 73: [array([[17493680.        , 18746053.        ],\n",
       "         [  499483.        ,   712699.98778989]]), 79834, 73, 71, -1, -1],\n",
       " 74: [array([[17493680.        , 18746053.        ],\n",
       "         [  712699.98778989,  1000000.        ]]), 107707, 74, 71, 75, 76],\n",
       " 75: [array([[17493680.        , 18746053.        ],\n",
       "         [  712699.98778989,   856388.        ]]), 53854, 75, 74, -1, -1],\n",
       " 76: [array([[17493680., 18746053.],\n",
       "         [  856388.,  1000000.]]), 53853, 76, 74, -1, -1]}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kdnode_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# = = = Visualization = = =\n",
    "from Utils import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAagAAAEYCAYAAAAJeGK1AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4zLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvnQurowAAHhdJREFUeJzt3X+8XHV95/HXWwJIRDABYSFJC5as\nu8C2KnkE1H0omm0Sbd2gC49e1krWTTcPEV21213A7cPcQNPC7j5KyyrYVFJ+VIGQYsm6AqZBqi0Q\niIpCoDR3RSFNlqA3IGoBg5/943zvMncyM3fu3DNzvjPzfj4e87gz33O+Zz5zcjKf+X7P93yPIgIz\nM7PcvKLqAMzMzBpxgjIzsyw5QZmZWZacoMzMLEtOUGZmliUnKDMzy1JPE5SkDZL2Snq4pmyupC2S\ndqa/c2qWXSxpTNJjkpbVlJ8m6aG07EpJSuWHSro5lW+TdEJNnZXpPXZKWllTfmJad2eqe0i394OZ\nmU2t1y2oa4HldWUXAVsjYiGwNb1G0snACHBKqnOVpINSnauB1cDC9JjY5ipgX0ScBFwBXJ62NRdY\nA5wOLAbW1CTCy4Er0vvvS9swM7OK9TRBRcTXgPG64hXAden5dcBZNeU3RcQLEfE4MAYslnQccERE\n3BvFVcbX19WZ2NYmYElqXS0DtkTEeETsA7YAy9Oyd6Z169/fzMwqNKvqAIBjI2IPQETskXRMKp8H\n3Fez3q5U9rP0vL58os6TaVv7JT0LHFVbXlfnKOCZiNjfYFsHkLSaouWGDtFpcZRn4ZgxAbnvRsdY\nrpxjzTm2Cd2Isext7uEHEfHamW4mhwTVjBqURYvyTuq02taBCyLWA+sBdLwidud+JOdPa0WsyXs/\nOsZy5RxrzrFN6EaMZW9T0vfL2E4Oo/ieSt12pL97U/kuYEHNevOB3al8foPySXUkzQKOpOhSbLat\nHwCvSevWb8vMzCqUQ4LaDEyMqlsJ3FZTPpJG5p1IMRji/tQd+JykM9I5pPPq6kxs62zgrnSe6k5g\nqaQ5aXDEUuDOtOyrad369zczswr1tItP0o3AmcDRknZRjKy7DNgoaRXwBHAOQETskLQReATYD1wQ\nES+lTZ1PMSLwMOD29AC4BrhB0hhFy2kkbWtc0qXAA2m9SyJiYrDGhcBNkn4P+FbahpmZVaynCSoi\nzm2yaEmT9dcB6xqUbwdObVD+PCnBNVi2AdjQoPy7FEPPzcwsIzl08ZmZmR3ACcrMzLLkBGVmZlly\ngjIzsyw5QZmZWZacoMzMLEtOUGZmliUnKDMzy5ITlJmZZckJyszMspTz7TbMbDrU6O4xMxB533bC\nBp9bUGZmliW3oMwGzUxbPmW3xMw65BaUmZllyQnKzMyy5ARlZmZZcoIyM7MsOUGZmVmWnKDMzCxL\nTlBmZpYlXwdlldNaX3djZgdygrLKxZq6C0vrLhTVaIN1GtBatbXedDmBmlXDXXxmZpYlJygz65w0\n/YdZm5ygzAZNJ0ljOglkhskmRjuqZkPICcrMzLLkQRJmg6LX92+KOLAVVRtD7bJG65pNwQnKzKzP\nDMvIUicoM7M+08nlFK0uw8g14fkclJmZZcktKDMrT7PzTD7/VK7p7s9en58siVtQZtYZJx3rMreg\nzMz61VQtoz7/EeEWlJlNT8SMHhqt+gMMoDYuto5RZnSBdRWcoMzMLEtOUGZmlqVsEpSkT0jaIelh\nSTdKeqWkuZK2SNqZ/s6pWf9iSWOSHpO0rKb8NEkPpWVXSkV7VtKhkm5O5dsknVBTZ2V6j52SVvby\nc5uZWWNZJChJ84D/CCyKiFOBg4AR4CJga0QsBLam10g6OS0/BVgOXCXpoLS5q4HVwML0WJ7KVwH7\nIuIk4Arg8rStucAa4HRgMbCmNhGameVk0mS7zc4p1Zf30XmnWlkkqGQWcJikWcBsYDewArguLb8O\nOCs9XwHcFBEvRMTjwBiwWNJxwBERcW9EBHB9XZ2JbW0ClqTW1TJgS0SMR8Q+YAsvJzWrgEaZfGLd\nzIZSFgkqIv4B+B/AE8Ae4NmI+ApwbETsSevsAY5JVeYBT9ZsYlcqm5ee15dPqhMR+4FngaNabMvM\nLG8D/iMuiwSVutRWACcCxwOvkvSbrao0KIsW5Z3WqY9ztaTtkrbz0xbRmZnZjGWRoIB/BTweEU9H\nxM+AW4G3AE+lbjvS371p/V3Agpr68ym6BHel5/Xlk+qkbsQjgfEW2zpARKyPiEURsYjZHX5SMzNr\nSy4J6gngDEmz03mhJcCjwGZgYlTdSuC29HwzMJJG5p1IMRji/tQN+JykM9J2zqurM7Gts4G70nmq\nO4GlkuakltzSVGZmZhXKYqqjiNgmaRPwTWA/8C1gPXA4sFHSKookdk5af4ekjcAjaf0LIuKltLnz\ngWuBw4Db0wPgGuAGSWMULaeRtK1xSZcCD6T1LomI8S5+XDMza0MWCQogItZQDPeu9QJFa6rR+uuA\ndQ3KtwOnNih/npTgGizbAGyYZsiWmRgFRssfThs02O4An5g2y0U2CcqGV6ObpdWXtXNDtV6mjFxv\n8GY2SJygrHKd3B20oYlWTqvWzUzvo5Pq18fc6m6lveCEaYPICcoGT5lXzU91Az539Zl1TS6j+MzM\nzCZxC8psJia6/ODAIT5mNiNOUJ2S+/2zFdG3k2Oa2cucoDoVJZ7c75KyT9x3YyBA15J8OwMlOjl/\n1KhuJsmwn34w9VOsVh0nKBs87SaMTBJLWar+wdSLkYzdfg8nzrx4kISZmWXJCcoGR8SB95Jq9KhZ\nv+OHWQ6a3bBwQLiLz4bXAP/H7jmp8ZRQM+UfA0PNLSgzy1dqIWitfH4o0WjNi3Zb9H2a6N2CsuHT\nhf+sWquezgU4bGKUogvXSWqoOEGZmfWrAe+mdoIys+6bqtVae33ZgH/pVkFrBaM1BX3SEnWCMjPr\nN9Pspp5q7Vy7Tp2grHJl/+eo6j9brv/JzfqVE9Qwmk4XSg9G/1Q9A8IgcHK0QeQENeAafXFNJx34\ni8/MquIENeAatk6mcefZ2vpOVmbWS05QZtZ9QzqBr82MZ5IwM7MsOUGZmVmW3MVnNiAqPUc4+vLT\nGG220sxMfD6fCx0eTlBmAyKb4fprurPZXnw6J7+8uIvPzMyy5ARlZmZZcoIyM7MsOUGZmVmWnKDM\nzCxLTlBmZpYlDzO3ynlor5k14gRllcvm+p0+5iRvg8hdfGZmliW3oMwGhFtRNmicoMwGhLtKZ85J\nPi/u4jMzsyxlk6AkvUbSJkl/J+lRSW+WNFfSFkk70985NetfLGlM0mOSltWUnybpobTsSqm4A5qk\nQyXdnMq3STqhps7K9B47Ja3s5eeulNT8YWZWsZy6+P4YuCMizpZ0CDAb+CSwNSIuk3QRcBFwoaST\ngRHgFOB44K8k/dOIeAm4GlgN3Ad8GVgO3A6sAvZFxEmSRoDLgd+QNJdi/uVFFBMmf0PS5ojY17uP\n3j2Nuiym0xHkLg8zq0oWCUrSEcDbgH8HEBEvAi9KWgGcmVa7DrgbuBBYAdwUES8Aj0saAxZL+h5w\nRETcm7Z7PXAWRYJawct3rdkEfDq1rpYBWyJiPNXZQpHUbuzaB+6hhuclpnE7hNraTlZm1ku5dPG9\nDnga+DNJ35L0OUmvAo6NiD0A6e8xaf15wJM19XelsnnpeX35pDoRsR94FjiqxbYOIGm1pO2StvPT\nTj+qmZm1I5cENQt4E3B1RLwR+AlFd14zjX7KR4vyTutMLoxYHxGLImIRs1tEZ2ZmM5ZLgtoF7IqI\nben1JoqE9ZSk4wDS37016y+oqT8f2J3K5zcon1RH0izgSGC8xbbMzKxCWSSoiPi/wJOSXp+KlgCP\nAJuBiVF1K4Hb0vPNwEgamXcisBC4P3UDPifpjHR+6by6OhPbOhu4KyICuBNYKmlOGiW4NJWZmVmF\nphwkIWkBxbmfxyLixw2WHw28OyKun2EsHwU+n0bwfRf4IEUC3ShpFfAEcA5AROyQtJEiie0HLkgj\n+ADOB64FDqMYHHF7Kr8GuCENqBinGAVIRIxLuhR4IK13ycSACTMzq07TBCXpUODPgfelop+nUXG/\nHRHP1qz6S8CfATNKUBHxIMVQ73pLmqy/DljXoHw7cGqD8udJCa7Bsg3AhunEa2Zm3dWqi+9C4FeB\nDwGnA78D/DqwXdLCHsRmZmZDrFWC+rfA70bEn0bE9oj4Y+BXgD3APZLe3JMIzcxsKLVKUAuA79QW\npMEMS4CtFLM3nNXF2MzMbIi1SlC7KUbHTRIRP4uIEeBPgVsophUyMzMrVasE9XXgA80WRsTHgU9R\njLYzMzMrVath5ldRTKZ6VET8sNEKEfEHkr5PMZjCzMysNE0TVBquvX2qDUTEF4AvlBmUmZlZFjNJ\nmJmZ1XOCMjOzLDlBmZlZlpygzMwsS05QZmaWpWnd8l3SK4HjgVfWL4uIR8oKyszMrK0EJWk+sB5Y\n1mgxxR1oDyoxLjMzG3LttqBuAF4HfAQYA17sWkTDTo3uQN+ZABjtwvYiStummVkz7SaoRcD7I2Jz\nN4PpKwKt7ezLP0bLDaXnJDRa4uY63I9mNtjaTVCPALO7GUjfCYg1HbYkSmzVVKXjz15Ha1XatoaZ\nk7wNonYT1EeBP5H0ZET8bTcDGiqNuspK7OKz4eIkVY5+2I/diDHHz91ugnoQuB/4mqQXgefqV4iI\nY8oMbCj0UzKaSKb9FPOQyb0l2g+tZcdYznuppF6idhPU54BzgE14kMRwcmIysx5rN0G9F/hERHy2\nm8H0lRkMkmC0/VVzHVCRY3eAmQ2WdhPU08AT3Qyk78xkkMR0rOn+W3SirE/uRGdmzbQ71dElwO9I\nOrybwZiZmU1otwX1a8BC4AlJ24Fn6pZHRPxGqZHlbiZdfGZmNqV2E9TRFIMjAA4GXtudcPpIr7r4\nBpyTvGWrzIFBnn2lI20lqIh4R7cDMbMMTfdL2l/EVqJpzWZuZjZ0ZpJ0c748o43YAiodqNU0QUn6\nMHBLRDydnrcUEVeVGpmZ5WOqL+mcv4itb7VqQX0a2E4xxPzTU2wnACcoM7N+0+zHRwY/OpomqIh4\nRaPnZmZmveBzUNZYj349TXnPKp90Nxtarc5BvW06G4qIr808nD4y4NdB5ZIWBnkfm1lrrVpQd1N8\nT018Q9R+Z4kDv8OG65bvg34d1ESrpqoWTGrBDfQ+LpETuQ2iVgnqX9Q8Pw7YANwB3ArsBY4B/g2w\nDPj33QrQzMyGU6tBEjsmnkv6feD6iPjdutXukPR7wMeBv+pOiGZmNozaHZ23BPjrJsv+GjizlGjM\nzMySdhPUOLCiybL3puUzJukgSd+S9KX0eq6kLZJ2pr9zata9WNKYpMckLaspP03SQ2nZlVJxMkPS\noZJuTuXbJJ1QU2dleo+dklaW8VnMzGxm2k1QlwEflvQlSaslnZX+/m/gQ2l5GT4GPFrz+iJga0Qs\nBLam10g6GRgBTgGWA1dJmhikcTWwmmL29YVpOcAqYF9EnARcAVyetjWXYjKP04HFwJraRDj0pGoe\nZjb02p0s9ipJ/wB8kmJWiVnAfuBB4H0R8ZczDUTSfIrbeqwDfjsVr+Dl7sPrKEYWXpjKb4qIF4DH\nJY0BiyV9DzgiIu5N27weOAu4PdUZTdvaBHw6ta6WAVsiYjzV2UKR1G5sHfBgj5zKZezcIO9jM2ut\n7Qt1I+I24DZJr6C43cbTEfHzEmP5I+C/AK+uKTs2Ivak998j6ZhUPg+4r2a9XansZ+l5fflEnSfT\ntvZLehY4qra8QZ1JJK2maJ3BkQM+BDqTO/kO8B4ulRN5F7lFX5lpT2EUET+PiKfKTE6Sfh3YGxHf\naLdKo9BalHdaZ3JhxPqIWBQRi5jdVpxmZtahXObYeyvwr1MX3U3AOyX9OfCUpOMA0t+9af1dwIKa\n+vOB3al8foPySXUkzQKOpBjc0WxbZjbMIsp7WEeySFARcXFEzI+IEygGP9wVEb8JbAYmRtWtBG5L\nzzcDI2lk3okUgyHuT92Bz0k6I51fOq+uzsS2zk7vEcCdwFJJc9LgiKWpzMwmeFDL4Mr43zT3yWIv\nAzZKWgU8AZwDxUXEkjYCj1AM1rggIl5Kdc4HrgUOoxgccXsqvwa4IQ2oGKdIhETEuKRLgQfSepdM\nDJgwM7PqZJegIuJuitF6RMQPKS4SbrTeOooRf/Xl24FTG5Q/T0pwDZZtoJjKycxquXtqcLXxb6u1\nqnSgUnYJysw645F85eiH/djLGKvcH05QnRrw66Cs/5R92YPWqtRt9sv/l9wvHyn736Ub1Ooeb9Pg\nBNWpPrjdRl8cyH0QYz/oly9/s+nIYhSfmZlZPScoMzPLkhOUmZllyQnKzMyy5ARlZmZZcoIyM7Ms\nOUGZmVmWnKDMzCxLTlBmZpYlJygzM8uSE5SZmWXJc/GZDQjPx2eDxgnKbEBMNenudCfmdcKzqjlB\nDYNOb9/sm9WZWYWcoKxy/qVekvofIv6BYX3OCWqYtPuF1WmLq0O9uh9Ur+891cv3c5K3QeRRfDYc\nJGK0+Nuzh5nNiBOUWZfEaNURmPU3JygzM8uSE5SZmWXJCcrMzLLkBGVmZllygjIzsyw5QZmZWZac\noGw4eFYFs77jmSTMBoRG6woazC4x3Rknyp6hoh9mvHCM+XCCMhsQvZzGaVD1ejqsTvRFjKPlJFB3\n8Zl1yQEtGjObFieoYTLkc8hplOJcVK8eZjYj7uLrlPqjH1hrRadflb36fL3cj73+N+uHY8QsV05Q\nnYo+6vNf01m1Xny6fuhP7wdOhDaI3MVnZmZZcoIyM7MsZZGgJC2Q9FVJj0raIeljqXyupC2Sdqa/\nc2rqXCxpTNJjkpbVlJ8m6aG07EqpOOsv6VBJN6fybZJOqKmzMr3HTkkre/fJzcysmSwSFLAf+E8R\n8c+BM4ALJJ0MXARsjYiFwNb0mrRsBDgFWA5cJemgtK2rgdXAwvRYnspXAfsi4iTgCuDytK25FGdp\nTgcWA2tqE6GZmVUjiwQVEXsi4pvp+XPAo8A8YAVwXVrtOuCs9HwFcFNEvBARjwNjwGJJxwFHRMS9\nERHA9XV1Jra1CViSWlfLgC0RMR4R+4AtvJzUzMysIlkkqFqp6+2NwDbg2IjYA0USA45Jq80Dnqyp\ntiuVzUvP68sn1YmI/cCzwFEttmVmZhXKapi5pMOBvwA+HhE/UvOLRhstiBblndapj281RfchHNks\ntGnq5MJYXwRqZkMgmxaUpIMpktPnI+LWVPxU6rYj/d2byncBC2qqzwd2p/L5Dcon1ZE0iyLFjLfY\n1gEiYn1ELIqIRczu5FOamVm7skhQ6VzQNcCjEfGHNYs2AxOj6lYCt9WUj6SReSdSDIa4P3UDPifp\njLTN8+rqTGzrbOCudJ7qTmCppDlpcMTSVNZbnjrHzGySXLr43gp8AHhI0oOp7JPAZcBGSauAJ4Bz\nACJih6SNwCMUIwAviIiXUr3zgWuBw4Db0wOKBHiDpDGKltNI2ta4pEuBB9J6l0TEeLc+qJmZtSeL\nBBURf0Pjc0EAS5rUWQesa1C+HTi1QfnzpATXYNkGYEO78ZqZWfdl0cVnZmZWzwnKzMyy5ARlZmZZ\ncoIyM7MsOUGZmVmWnKDMzCxLTlBmZpalLK6DMjqbk69XuhhbQMe3pDezBnL+LpkmJygzsz6jtc2T\n0CBNiuYEVbV+mmOv7FgH6JeeWS/Fmhb/F0cH5/+VE5S1zwnFzHrIgyTMzCxLbkHZ1LrYDam1Gqg+\nc7Ns9eJ0Qsm9LE5QnVLrE5VmZjYzTlCdiilOVFpbnOTNrBmfgzIzsyw5QZmZWZacoMzMLEtOUGZm\nliUnKDMzy5ITlJmZZckJyszMsuQEZWZmWfKFumZmw6APJ3t2C8rMzLLkBGVmZllyF5+Z2aCKeLlr\nr1c3Ry2xK9EJysxsGPgclJmZWTncgjIzG2S96tqb4C4+MzObUh9269VygjIz6zOtbvQ5SLdRdYIy\nM+szLe/mvaZ3cTRVUsvNgyTMzCxLTlBmZpYlJygzM8uSE5SZmWXJCSqRtFzSY5LGJF1UdTxmZsPO\nCQqQdBDwGeBdwMnAuZJOrjYqM7Ph5gRVWAyMRcR3I+JF4CZgRcUxmZkNNUWvp8HIkKSzgeUR8Vvp\n9QeA0yPiI3XrrQZWp5enAg/3NNDpOxr4QdVBTMExlsMxlsMxluP1EfHqmW7EF+oWGl1VdkDmjoj1\nwHoASdsjYlG3A5sJx1gOx1gOx1iOfomxjO24i6+wC1hQ83o+sLuiWMzMDCeoCQ8ACyWdKOkQYATY\nXHFMZmZDzV18QETsl/QR4E7gIGBDROyYotr67kc2Y46xHI6xHI6xHEMTowdJmJlZltzFZ2ZmWXKC\nMjOzLDlB1ZlqyiMVrkzLvyPpTe3W7WGM70+xfUfSPZJ+pWbZ9yQ9JOnBsoaCdhjjmZKeTXE8KOlT\n7dbtYYz/uSa+hyW9JGluWtar/bhB0l5JDa+5y+R4nCrGHI7HqWLM4XicKsYcjscFkr4q6VFJOyR9\nrME65R2TEeFHelAMkPg/wOuAQ4BvAyfXrfNu4HaKa6fOALa1W7eHMb4FmJOev2sixvT6e8DRGezH\nM4EvdVK3VzHWrf8e4K5e7sf0Pm8D3gQ83GR5pcdjmzFWejy2GWOlx2M7MWZyPB4HvCk9fzXw9938\njnQLarJ2pjxaAVwfhfuA10g6rs26PYkxIu6JiH3p5X0U13X10kz2RTb7sc65wI1diKOliPgaMN5i\nlaqPxyljzOB4bGc/NpPNfqxT1fG4JyK+mZ4/BzwKzKtbrbRj0glqsnnAkzWvd3Hgzm+2Tjt1exVj\nrVUUv2YmBPAVSd9QMXVTN7Qb45slfVvS7ZJOmWbdXsWIpNnAcuAvaop7sR/bUfXxOF1VHI/tqvJ4\nbFsux6OkE4A3AtvqFpV2TPo6qMnamfKo2TptTZdUgrbfR9I7KL4Q/mVN8VsjYrekY4Atkv4u/XLr\ndYzfBH4xIn4s6d3AXwIL26xbhum8z3uAv42I2l+3vdiP7aj6eGxbhcdjO6o+Hqej8uNR0uEUCfLj\nEfGj+sUNqnR0TLoFNVk7Ux41W6dX0yW19T6Sfhn4HLAiIn44UR4Ru9PfvcAXKZrdPY8xIn4UET9O\nz78MHCzp6Hbq9irGGiPUdaf0aD+2o+rjsS0VH49TyuB4nI5Kj0dJB1Mkp89HxK0NVinvmOz2SbV+\nelC0KL8LnMjLJ/FOqVvn15h8AvD+duv2MMZfAMaAt9SVvwp4dc3zeyhmca8ixn/CyxeKLwaeSPs0\nm/2Y1juS4rzAq3q9H2ve7wSan9yv9HhsM8ZKj8c2Y6z0eGwnxhyOx7RPrgf+qMU6pR2T7uKrEU2m\nPJL0obT8s8CXKUapjAE/BT7Yqm5FMX4KOAq4ShLA/ihmPz4W+GIqmwV8ISLuqCjGs4HzJe0H/hEY\nieIozmk/ArwX+EpE/KSmek/2I4CkGylGmB0taRewBji4JsZKj8c2Y6z0eGwzxkqPxzZjhIqPR+Ct\nwAeAhyQ9mMo+SfEjpPRj0lMdmZlZlnwOyszMsuQEZWZmWXKCMjOzLDlBmZlZlpygzMzs/5tq0tq6\nda+omcD27yU9U2YsTlBmmZB0qqSQdGZNWaShud14v0Mk/XdJX5f0j5I8pNcArqWYSmlKEfGJiHhD\nRLwB+J9Aowt3O+YEZZa3NwO3dGnbs4HforhW5Z4uvYf1mWgwaa2kX5J0R5rr7+uS/lmDqqVPYOsL\ndc0yFsVs0N3a9jOS5kbERCvtnd16L+t764EPRcROSacDV1FzvEj6RYoZIu4q803dgjKriKQPS3pS\n0k8k/S+Ke+3UrzOpi0/S3ZI2SfqgpMcl/VjSDZIOlbRY0v2p7G5JvzBVDOEr9W0KaWLYtwC3pNkj\n/oQDj9URYFNEvFTme7sFZVYBSSuAzwCfpZg5++3AhjarnwEcDXyUYoqZKyim5zkd+G/AT4ArKX71\ntnUuwayFVwDPpPNMzYwAF5T9xk5QZtX4r8AdEXF+en2npNdSnBOayuEUs4I/C8XtyoH/ALw9nT9A\n0vHAZyTNjoiflh69DY2I+FFqrZ8TEbeomPTvlyPi2wCSXg/MAe4t+73dxWfWY5IOorjR2211i9od\nAbV9IjklY8CLwN/UlQEc31GQNrTSpLX3Aq+XtEvSKuD9wCpJ3wZ2MPlOuOcCN3Wju9gtKLPeey3F\n/729deX1r5upv9bkReC5iPh5XRnAK6cfng2ziDi3yaKG3cURMdqtWNyCMuu9p4H9wDF15fWvzYaa\nE5RZj6WRTg8yuZsE4H0VhGOWLXfxmVXj94FbJV1NcYvut1PBiDtJ76K4C+sb0uuz06IHIuL7vY7H\nrJZbUGYViIgvUgwTfw/FMPM3AqsqCOVqipkqJt77lvR4RwWxmE3iO+qamVmW3IIyM7MsOUGZmVmW\nnKDMzCxLTlBmZpYlJygzM8uSE5SZmWXJCcrMzLLkBGVmZln6fyRGhNGtDoO0AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "visualize_kdnodes_and_query_2(adk_kdnode, training_set, [], domains)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}