This is an automated email from the ASF dual-hosted git repository.
domino pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/madlib.git
commit c0ae940bbebba4d934a8f48dbb4f84d285465841
Author: Orhan Kislal <okis...@apache.org>
AuthorDate: Thu Jul 2 14:33:38 2020 -0400
DBSCAN: Add indexing optimizations to improve the runtime
JIRA: MADLIB-1017
The brute force DBSCAN runs on N^2 time. To improve this,
we added two layers of indexing.
1. The data is broken into chunks with kd-tree
2. Each leaf of the kd-tree creates an rtree index for
efficient range queries.
In addition we added a separate process to reduce the number
of edges to consider during wcc operation.
---
src/ports/postgres/modules/dbscan/dbscan.py_in | 592 ++++++++++-
src/ports/postgres/modules/dbscan/dbscan.sql_in | 139 ++-
.../postgres/modules/dbscan/test/dbscan.sql_in | 1087 ++++++++++++++++++++
.../dbscan/test/unit_tests/test_dbscan.py_in | 3 +-
4 files changed, 1772 insertions(+), 49 deletions(-)
diff --git a/src/ports/postgres/modules/dbscan/dbscan.py_in
b/src/ports/postgres/modules/dbscan/dbscan.py_in
index e8d67a6..40e1205 100644
--- a/src/ports/postgres/modules/dbscan/dbscan.py_in
+++ b/src/ports/postgres/modules/dbscan/dbscan.py_in
@@ -26,6 +26,8 @@ from utilities.utilities import add_postfix
from utilities.utilities import NUMERIC, ONLY_ARRAY
from utilities.utilities import is_valid_psql_type
from utilities.utilities import is_platform_pg
+from utilities.utilities import num_features
+from utilities.utilities import get_seg_number
from utilities.validate_args import input_tbl_valid, output_tbl_valid
from utilities.validate_args import is_var_valid
from utilities.validate_args import cols_in_tbl_valid
@@ -33,74 +35,284 @@ from utilities.validate_args import get_expr_type
from utilities.validate_args import get_algorithm_name
from graph.wcc import wcc
+from math import log
+from math import floor
+from math import sqrt
+
+from scipy.spatial import distance
+
+try:
+ from rtree import index
+except ImportError:
+ RTREE_ENABLED=0
+else:
+ RTREE_ENABLED=1
+
BRUTE_FORCE = 'brute_force'
KD_TREE = 'kd_tree'
+DEFAULT_MIN_SAMPLES = 5
+DEFAULT_KD_DEPTH = 3
+DEFAULT_METRIC = 'squared_dist_norm2'
-def dbscan(schema_madlib, source_table, output_table, id_column, expr_point,
eps, min_samples, metric, algorithm, **kwargs):
+def dbscan(schema_madlib, source_table, output_table, id_column, expr_point,
+ eps, min_samples, metric, algorithm, depth, **kwargs):
with MinWarning("warning"):
- min_samples = 5 if not min_samples else min_samples
- metric = 'squared_dist_norm2' if not metric else metric
- algorithm = 'brute' if not algorithm else algorithm
+ min_samples = DEFAULT_MIN_SAMPLES if not min_samples else min_samples
+ metric = DEFAULT_METRIC if not metric else metric
+ algorithm = BRUTE_FORCE if not algorithm else algorithm
+ depth = DEFAULT_KD_DEPTH if not depth else depth
algorithm = get_algorithm_name(algorithm, BRUTE_FORCE,
[BRUTE_FORCE, KD_TREE], 'DBSCAN')
_validate_dbscan(schema_madlib, source_table, output_table, id_column,
- expr_point, eps, min_samples, metric, algorithm)
+ expr_point, eps, min_samples, metric, algorithm,
depth)
dist_src_sql = '' if is_platform_pg() else 'DISTRIBUTED BY (__src__)'
dist_id_sql = '' if is_platform_pg() else 'DISTRIBUTED BY
({0})'.format(id_column)
dist_reach_sql = '' if is_platform_pg() else 'DISTRIBUTED BY
(__reachable_id__)'
+ dist_leaf_sql = '' if is_platform_pg() else 'DISTRIBUTED BY
(__leaf_id__)'
- # Calculate pairwise distances
+ core_points_table = unique_string(desp='core_points_table')
+ core_edge_table = unique_string(desp='core_edge_table')
distance_table = unique_string(desp='distance_table')
- plpy.execute("DROP TABLE IF EXISTS {0}".format(distance_table))
+ plpy.execute("DROP TABLE IF EXISTS {0}, {1}, {2}".format(
+ core_points_table, core_edge_table, distance_table))
+ source_view = unique_string(desp='source_view')
+ plpy.execute("DROP VIEW IF EXISTS {0}".format(source_view))
sql = """
- CREATE TABLE {distance_table} AS
- SELECT __src__, __dest__ FROM (
- SELECT __t1__.{id_column} AS __src__,
- __t2__.{id_column} AS __dest__,
- {schema_madlib}.{metric}(
- __t1__.{expr_point}, __t2__.{expr_point}) AS
__dist__
- FROM {source_table} AS __t1__, {source_table} AS __t2__
- WHERE __t1__.{id_column} != __t2__.{id_column}) q1
- WHERE __dist__ < {eps}
- {dist_src_sql}
+ CREATE VIEW {source_view} AS
+ SELECT {id_column}, {expr_point} AS __expr_point__
+ FROM {source_table}
""".format(**locals())
plpy.execute(sql)
+ expr_point = '__expr_point__'
+
+ if algorithm == KD_TREE:
+ cur_source_table, border_table1, border_table2 = dbscan_kd(
+ schema_madlib, source_view, id_column, expr_point, eps,
+ min_samples, metric, depth)
+
+ sql = """
+ SELECT count(*), __leaf_id__ FROM {cur_source_table} GROUP BY
__leaf_id__
+ """.format(**locals())
+ result = plpy.execute(sql)
+ rt_counts_dict = {}
+ for i in result:
+ rt_counts_dict[i['__leaf_id__']] = int(i['count'])
+ rt_counts_list = []
+ for i in sorted(rt_counts_dict):
+ rt_counts_list.append(rt_counts_dict[i])
+
+ find_core_points_table =
unique_string(desp='find_core_points_table')
+ rt_edge_table = unique_string(desp='rt_edge_table')
+ rt_core_points_table = unique_string(desp='rt_core_points_table')
+ border_core_points_table =
unique_string(desp='border_core_points_table')
+ border_edge_table = unique_string(desp='border_edge_table')
+ plpy.execute("DROP TABLE IF EXISTS {0}, {1}, {2}, {3}, {4}".format(
+ find_core_points_table, rt_edge_table, rt_core_points_table,
+ border_core_points_table, border_edge_table))
+
+ sql = """
+ CREATE TABLE {find_core_points_table} AS
+ SELECT __leaf_id__,
+ {schema_madlib}.find_core_points( {id_column},
+ {expr_point}::DOUBLE
PRECISION[],
+ {eps},
+ {min_samples},
+ '{metric}',
+ ARRAY{rt_counts_list},
+ __leaf_id__
+ )
+ FROM {cur_source_table} GROUP BY __leaf_id__
+ {dist_leaf_sql}
+ """.format(**locals())
+ plpy.execute(sql)
+
+ sql = """
+ CREATE TABLE {rt_edge_table} AS
+ SELECT (unpacked_2d).src AS __src__, (unpacked_2d).dest AS __dest__
+ FROM (
+ SELECT {schema_madlib}.unpack_2d(find_core_points) AS
unpacked_2d
+ FROM {find_core_points_table}
+ ) q1
+ WHERE (unpacked_2d).src NOT IN (SELECT {id_column} FROM
{border_table1})
+ {dist_src_sql}
+ """.format(**locals())
+ plpy.execute(sql)
+
+ sql = """
+ CREATE TABLE {rt_core_points_table} AS
+ SELECT DISTINCT(__src__) AS {id_column} FROM {rt_edge_table}
+ """.format(**locals())
+ plpy.execute(sql)
+
+ # # Start border
+ sql = """
+ CREATE TABLE {border_edge_table} AS
+ SELECT __src__, __dest__ FROM (
+ SELECT __t1__.{id_column} AS __src__,
+ __t2__.{id_column} AS __dest__,
+ {schema_madlib}.{metric}(
+ __t1__.{expr_point}, __t2__.{expr_point}) AS
__dist__
+ FROM {border_table1} AS __t1__, {border_table2} AS
__t2__)q1
+ WHERE __dist__ < {eps}
+ """.format(**locals())
+ plpy.execute(sql)
+
+ sql = """
+ CREATE TABLE {border_core_points_table} AS
+ SELECT * FROM (
+ SELECT __src__ AS {id_column}, count(*) AS __count__
+ FROM {border_edge_table} GROUP BY __src__) q1
+ WHERE __count__ >= {min_samples}
+ {dist_id_sql}
+ """.format(**locals())
+ plpy.execute(sql)
+
+ # Build common tables
+ sql = """
+ CREATE TABLE {distance_table} AS
+ SELECT * FROM {rt_edge_table}
+ UNION
+ SELECT * FROM {border_edge_table}
+ """.format(**locals())
+ plpy.execute(sql)
+ sql = """
+ CREATE TABLE {core_points_table} AS
+ SELECT {id_column} FROM {border_core_points_table}
+ UNION
+ SELECT {id_column} FROM {rt_core_points_table}
+ """.format(**locals())
+ plpy.execute(sql)
+
+ sql = """
+ CREATE TABLE {core_edge_table} AS
+ SELECT __t1__.__src__, __t1__.__dest__
+ FROM {rt_edge_table} __t1__ ,
+ (SELECT array_agg({id_column}) AS arr
+ FROM {core_points_table}) __t2__
+ WHERE __t1__.__dest__ = ANY(arr)
+ UNION
+ SELECT __t1__.__src__, __t1__.__dest__
+ FROM {border_edge_table} __t1__ ,
+ (SELECT array_agg({id_column}) AS arr
+ FROM {core_points_table}) __t2__
+ WHERE __t1__.__src__ = ANY(arr) AND __t1__.__dest__ = ANY(arr)
+ """.format(**locals())
+ plpy.execute(sql)
+
+ plpy.execute("DROP TABLE IF EXISTS {0}, {1}, {2}, {3}, {4}, {5},
{6}, {7}".format(
+ find_core_points_table, rt_edge_table, rt_core_points_table,
+ border_core_points_table, border_edge_table,
+ cur_source_table, border_table1, border_table2))
+
+ else:
+
+ # Calculate pairwise distances
+ sql = """
+ CREATE TABLE {distance_table} AS
+ SELECT __src__, __dest__ FROM (
+ SELECT __t1__.{id_column} AS __src__,
+ __t2__.{id_column} AS __dest__,
+ {schema_madlib}.{metric}(
+ __t1__.{expr_point}, __t2__.{expr_point}) AS
__dist__
+ FROM {source_view} AS __t1__, {source_view} AS __t2__)q1
+ WHERE __dist__ < {eps}
+ {dist_src_sql}
+ """.format(**locals())
+ plpy.execute(sql)
+
+ # Find core points
+ sql = """
+ CREATE TABLE {core_points_table} AS
+ SELECT * FROM (
+ SELECT __src__ AS {id_column}, count(*) AS __count__
+ FROM {distance_table} GROUP BY __src__) q1
+ WHERE __count__ >= {min_samples}
+ {dist_id_sql}
+ """.format(**locals())
+ plpy.execute(sql)
+
+ # Find the connections between core points to form the clusters
+ sql = """
+ CREATE TABLE {core_edge_table} AS
+ SELECT __src__, __dest__
+ FROM {distance_table} AS __t1__, (SELECT
array_agg({id_column}) AS arr
+ FROM {core_points_table})
__t2__
+ WHERE __t1__.__src__ = ANY(arr) AND __t1__.__dest__ = ANY(arr)
+ {dist_src_sql}
+ """.format(**locals())
+ plpy.execute(sql)
- # Find core points
- # We use __count__ + 1 because we have to add the point itself to the
count
- core_points_table = unique_string(desp='core_points_table')
- plpy.execute("DROP TABLE IF EXISTS {0}".format(core_points_table))
sql = """
- CREATE TABLE {core_points_table} AS
- SELECT * FROM (SELECT __src__ AS {id_column}, count(*) AS __count__
- FROM {distance_table} GROUP BY __src__) q1
- WHERE __count__ + 1 >= {min_samples}
- {dist_id_sql}
+ SELECT count(*) FROM {core_points_table}
""".format(**locals())
+ core_count = plpy.execute(sql)[0]['count']
+ _assert(core_count != 0, "DBSCAN: Cannot find any core
points/clusters.")
+
+ # Start snowflake creation
+ if is_platform_pg():
+ sql = """
+ SELECT count(*) FROM {core_edge_table}
+ """.format(**locals())
+ count = plpy.execute(sql)[0]['count']
+
+ counts_list = [int(count)]
+ seg_id = 0
+ group_by_clause = ''
+ dist_clause = ''
+
+ else:
+ sql = """
+ SELECT count(*), gp_segment_id FROM {core_edge_table} GROUP BY
gp_segment_id
+ """.format(**locals())
+ count_result = plpy.execute(sql)
+ seg_num = get_seg_number()
+ counts_list = [0]*seg_num
+ for i in count_result:
+ counts_list[int(i['gp_segment_id'])] = int(i['count'])
+ seg_id = 'gp_segment_id'
+ group_by_clause = 'GROUP BY gp_segment_id'
+ dist_clause = 'DISTRIBUTED BY (seg_id)'
+
+ snowflake_table = unique_string(desp='snowflake_table')
+ sf_edge_table = unique_string(desp='sf_edge_table')
+
+ plpy.execute("DROP TABLE IF EXISTS {0}, {1}".format(
+ snowflake_table, sf_edge_table))
+ sql = """
+ CREATE TABLE {snowflake_table} AS
+ SELECT {seg_id}::INTEGER AS seg_id,
+ {schema_madlib}.build_snowflake_table( __src__,
+ __dest__,
+ ARRAY{counts_list},
+ {seg_id}
+ ) AS __sf__
+ FROM {core_edge_table} {group_by_clause}
+ {dist_clause}
+ """.format(**locals())
plpy.execute(sql)
- # Find the connections between core points to form the clusters
- core_edge_table = unique_string(desp='core_edge_table')
- plpy.execute("DROP TABLE IF EXISTS {0}".format(core_edge_table))
sql = """
- CREATE TABLE {core_edge_table} AS
- SELECT __src__, __dest__
- FROM {distance_table} AS __t1__, (SELECT array_agg({id_column}) AS
arr
- FROM {core_points_table}) __t2__
- WHERE __t1__.__src__ = ANY(arr) AND __t1__.__dest__ = ANY(arr)
- {dist_src_sql}
- """.format(**locals())
+ CREATE TABLE {sf_edge_table} AS
+ SELECT seg_id, (unpacked_2d).src AS __src__, (unpacked_2d).dest AS
__dest__
+ FROM (
+ SELECT seg_id,
+ {schema_madlib}.unpack_2d(__sf__) AS unpacked_2d
+ FROM {snowflake_table}
+ ) q1
+ {dist_clause}
+ """.format(**locals())
plpy.execute(sql)
# Run wcc to get the min id for each cluster
- wcc(schema_madlib, core_points_table, id_column, core_edge_table,
'src=__src__, dest=__dest__',
- output_table, None)
+ wcc(schema_madlib, core_points_table, id_column, sf_edge_table,
+ 'src=__src__, dest=__dest__', output_table, None)
+
plpy.execute("""
ALTER TABLE {0}
ADD COLUMN is_core_point BOOLEAN,
@@ -147,7 +359,7 @@ def dbscan(schema_madlib, source_table, output_table,
id_column, expr_point, eps
sql = """
UPDATE {output_table} AS __t1__
SET __points__ = {expr_point}
- FROM {source_table} AS __t2__
+ FROM {source_view} AS __t2__
WHERE __t1__.{id_column} = __t2__.{id_column}
""".format(**locals())
plpy.execute(sql)
@@ -165,8 +377,9 @@ def dbscan(schema_madlib, source_table, output_table,
id_column, expr_point, eps
plpy.execute(sql)
output_summary_table = add_postfix(output_table, '_summary')
- plpy.execute("DROP TABLE IF EXISTS {0}".format(output_summary_table))
+ # Drop the summary table from wcc
+ plpy.execute("DROP TABLE IF EXISTS {0}".format(output_summary_table))
sql = """
CREATE TABLE {output_summary_table} AS
SELECT '{id_column}'::VARCHAR AS id_column,
@@ -175,9 +388,114 @@ def dbscan(schema_madlib, source_table, output_table,
id_column, expr_point, eps
""".format(**locals())
plpy.execute(sql)
- plpy.execute("DROP TABLE IF EXISTS {0}, {1}, {2}, {3}".format(
+ plpy.execute("DROP VIEW IF EXISTS {0}".format(source_view))
+ plpy.execute("DROP TABLE IF EXISTS {0}, {1}, {2}, {3}, {4},
{5}".format(
distance_table, core_points_table, core_edge_table,
- reachable_points_table))
+ reachable_points_table, snowflake_table, sf_edge_table))
+
+def dbscan_kd(schema_madlib, source_table, id_column, expr_point, eps,
+ min_samples, metric, depth):
+
+ n_features = num_features(source_table, expr_point)
+
+ # If squared_dist_norm2 is used, we assume eps is set for the squared
distance
+ # That means the border only needs to be sqrt(eps) wide
+ local_eps = sqrt(eps) if metric == DEFAULT_METRIC else eps
+
+ kd_array, case_when_clause, border_cl1, border_cl2 = build_kd_tree(
+ schema_madlib, source_table, expr_point, depth, n_features, local_eps)
+
+ kd_source_table = unique_string(desp='kd_source_table')
+ kd_border_table1 = unique_string(desp='kd_border_table1')
+ kd_border_table2 = unique_string(desp='kd_border_table2')
+
+ dist_leaf_sql = '' if is_platform_pg() else 'DISTRIBUTED BY (__leaf_id__)'
+ plpy.execute("DROP TABLE IF EXISTS {0}, {1}, {2}".format(kd_source_table,
kd_border_table1, kd_border_table2))
+
+ output_sql = """
+ CREATE TABLE {kd_source_table} AS
+ SELECT *,
+ CASE {case_when_clause} END AS __leaf_id__
+ FROM {source_table}
+ {dist_leaf_sql}
+ """.format(**locals())
+ plpy.execute(output_sql)
+
+ border_sql = """
+ CREATE TABLE {kd_border_table1} AS
+ SELECT *
+ FROM {source_table}
+ WHERE {border_cl1}
+ """.format(**locals())
+ plpy.execute(border_sql)
+
+ border_sql = """
+ CREATE TABLE {kd_border_table2} AS
+ SELECT *
+ FROM {source_table}
+ WHERE {border_cl2}
+ """.format(**locals())
+ plpy.execute(border_sql)
+
+ return kd_source_table, kd_border_table1, kd_border_table2
+
+
+def build_kd_tree(schema_madlib, source_table, expr_point,
+ depth, n_features, eps, **kwargs):
+ """
+ KD-tree function to create a partitioning
+ Args:
+ @param schema_madlib Name of the Madlib Schema
+ @param source_table Training data table
+ @param output_table Name of the table to store kd tree
+ @param expr_point Name of the column with training data
+ or expression that evaluates to a
+ numeric array
+ @param depth Depth of the kd tree
+ @param n_features Number of features
+ @param eps The eps value defined by the user
+ """
+ with MinWarning("error"):
+
+ clauses = [' TRUE ']
+ border_cl1 = ' FALSE '
+ border_cl2 = ' FALSE '
+ clause_counter = 0
+ kd_array = []
+ for curr_level in range(depth):
+ curr_feature = (curr_level % n_features) + 1
+ for curr_leaf in range(pow(2,curr_level)):
+ clause = clauses[clause_counter]
+ cutoff_sql = """
+ SELECT percentile_disc(0.5)
+ WITHIN GROUP (
+ ORDER BY ({expr_point})[{curr_feature}]
+ ) AS cutoff
+ FROM {source_table}
+ WHERE {clause}
+ """.format(**locals())
+
+ cutoff = plpy.execute(cutoff_sql)[0]['cutoff']
+ cutoff = "NULL" if cutoff is None else cutoff
+ kd_array.append(cutoff)
+ clause_counter += 1
+ clauses.append(clause +
+ "AND ({expr_point})[{curr_feature}] < {cutoff}
".
+ format(**locals()))
+ clauses.append(clause +
+ "AND ({expr_point})[{curr_feature}] >= {cutoff}
".
+ format(**locals()))
+ border_cl1 = border_cl1 + """ OR
(({expr_point})[{curr_feature}] >= {cutoff} - {eps}
+ AND ({expr_point})[{curr_feature}]
<= {cutoff} + {eps})
+ """.format(**locals())
+ border_cl2 = border_cl2 + """ OR
(({expr_point})[{curr_feature}] >= {cutoff} - (2*{eps})
+ AND ({expr_point})[{curr_feature}]
<= {cutoff} + (2*{eps}))
+ """.format(**locals())
+
+ n_leaves = pow(2, depth)
+ case_when_clause = '\n'.join(["WHEN {0} THEN
{1}::INTEGER".format(cond, i)
+ for i, cond in
enumerate(clauses[-n_leaves:])])
+ return kd_array, case_when_clause, border_cl1, border_cl2
def dbscan_predict(schema_madlib, dbscan_table, source_table, id_column,
@@ -209,8 +527,189 @@ def dbscan_predict(schema_madlib, dbscan_table,
source_table, id_column,
""".format(**locals())
result = plpy.execute(sql)
+def find_core_points_transition(state, id_in, expr_points, eps, min_samples,
metric, n_rows, leaf_id, **kwargs):
+
+ SD = kwargs['SD']
+ if not state:
+ data = {}
+ SD['counter{0}'.format(leaf_id)] = 0
+ else:
+ data = SD['data{0}'.format(leaf_id)]
+
+ data[id_in] = expr_points
+ SD['counter{0}'.format(leaf_id)] = SD['counter{0}'.format(leaf_id)]+1
+ SD['data{0}'.format(leaf_id)] = data
+ ret = [[-1,-1],[-1,-1]]
+
+ my_n_rows = n_rows[leaf_id]
+
+ if SD['counter{0}'.format(leaf_id)] == my_n_rows:
+
+ core_counts = {}
+ core_lists = {}
+ p = index.Property()
+ p.dimension = len(expr_points)
+ idx = index.Index(properties=p)
+ ret = []
+
+ if metric == 'dist_norm1':
+ fn_dist = distance.cityblock
+ elif metric == 'dist_norm2':
+ fn_dist = distance.euclidean
+ else:
+ fn_dist = distance.sqeuclidean
+
+ for key1, value1 in data.items():
+ idx.add(key1,value1+value1,key1)
+
+ for key1, value1 in data.items():
+
+ v1 = []
+ v2 = []
+ for coor in value1:
+ v1.append(coor-eps)
+ v2.append(coor+eps)
+
+ # Array concat
+ v = v1+v2
+ hits = idx.intersection(v)
+
+ if key1 not in core_counts:
+ core_counts[key1] = 0
+ core_lists[key1] = []
+
+ for key2 in hits:
+ value2 = data[key2]
+ dist = fn_dist(value1, value2)
+ if dist <= eps:
+ core_counts[key1] += 1
+ core_lists[key1].append(key2)
+
+ for key1, value1 in core_counts.items():
+ if value1 >= min_samples:
+ for key2 in core_lists[key1]:
+ ret.append([key1,key2])
+
+ return ret
+
+def find_core_points_merge(state1, state2, **kwargs):
+
+ if not state1:
+ return state2
+ elif not state2:
+ return state1
+ else:
+ plpy.error("dbscan Error: A kd-tree leaf should be on a single
segment.")
+
+
+def find_core_points_final(state, **kwargs):
+
+ return state
+
+
+# The snowflake table is used to reduce the size of the edge table.
+# Note that the sole purpose of the edge table is finding the connected
+# components. Which means removing some of the edges is fine as long as the
+# component is intact.
+
+# We call it snowflake because the end result will look like a point in the
+# middle with a bunch of edges coming out of it to the other connected points.
+
+# Example:
+# Edges: [1,2] [1,3] [1,4] [2,3] [2,4] [3,1] [3,4] [5,6] [6,7] [7,8] [7,5]
+# Result: 1 and 5 are snowflake cores
+# Edges: [1,2] [1,3] [1,4] [5,6] [5,7] [5,8]
+
+# This is a proto-wcc operation (creates connected components) but we still
+# need to run the actual wcc to combine snowflakes from different segments.
+
+def sf_transition(state, src, dest, n_rows, gp_segment_id, **kwargs):
+
+ SD = kwargs['SD']
+ if not state:
+ data = []
+ SD['counter'] = 0
+ else:
+ data = SD['data']
+
+ counter = SD['counter']
+
+ data.append([src,dest])
+ ret = [[-1,-1],[-1,-1]]
+
+ my_n_rows = n_rows[gp_segment_id]
+
+ if len(data) == my_n_rows:
+
+ cl_ids = {}
+ clid_counter = 1
+ cl_counts = {}
+ for i in data:
+
+ key1 = i[0]
+ key2 = i[1]
+
+ cl_id_k1 = cl_ids[key1] if key1 in cl_ids else None
+ cl_id_k2 = cl_ids[key2] if key2 in cl_ids else None
+
+ if not cl_id_k1 and not cl_id_k2:
+ cl_ids[key1] = clid_counter
+ cl_ids[key2] = clid_counter
+ cl_counts[clid_counter] = 2
+ clid_counter += 1
+ elif cl_id_k1 and not cl_id_k2:
+ cl_ids[key2] = cl_id_k1
+ cl_counts[cl_ids[key1]] += 1
+ elif not cl_id_k1 and cl_id_k2:
+ cl_ids[key1] = cl_id_k2
+ cl_counts[cl_ids[key2]] += 1
+ else:
+ if cl_id_k1 != cl_id_k2:
+ if cl_counts[cl_id_k1] > cl_counts[cl_id_k2]:
+ for chkey,chvalue in cl_ids.items():
+ if chvalue == cl_id_k2:
+ cl_ids[chkey] = cl_id_k1
+ cl_counts[cl_id_k1] += cl_counts[cl_id_k2]
+ cl_counts[cl_id_k2] = 0
+ else:
+ for chkey,chvalue in cl_ids.items():
+ if chvalue == cl_id_k1:
+ cl_ids[chkey] = cl_id_k2
+ cl_counts[cl_id_k2] += cl_counts[cl_id_k1]
+ cl_counts[cl_id_k1] = 0
+
+ if cl_ids:
+
+ running_cl_id = -1
+ running_sf_center = -1
+ ret = []
+ for vertex_id, vertex_cl in sorted(cl_ids.items(), key=lambda
item: item[1]):
+
+ # Check if we are still in the same snowflake
+ if vertex_cl != running_cl_id:
+
+ running_sf_center = vertex_id
+ running_cl_id = vertex_cl
+ else:
+ ret.append([running_sf_center,vertex_id])
+
+ SD['data'] = data
+
+ return ret
+
+def sf_merge(state1, state2, **kwargs):
+
+ if state1:
+ return state1
+ else:
+ return state2
+
+def sf_final(state, **kwargs):
+
+ return state
+
def _validate_dbscan(schema_madlib, source_table, output_table, id_column,
- expr_point, eps, min_samples, metric, algorithm):
+ expr_point, eps, min_samples, metric, algorithm, depth):
input_tbl_valid(source_table, 'dbscan')
output_tbl_valid(output_table, 'dbscan')
@@ -235,6 +734,10 @@ def _validate_dbscan(schema_madlib, source_table,
output_table, id_column,
fn_dist_list = ['dist_norm1', 'dist_norm2', 'squared_dist_norm2',
'dist_angle', 'dist_tanimoto']
_assert(metric in fn_dist_list, "dbscan Error: metric has to be one of the
madlib defined distance functions")
+ _assert(algorithm == BRUTE_FORCE or RTREE_ENABLED == 1,
+ "dbscan Error: Cannot use kd_tree without the necessary python module:
rtree")
+ _assert(depth > 0, "dbscan Error: depth has to be a positive number")
+
def _validate_dbscan_predict(schema_madlib, dbscan_table, source_table,
id_column, expr_point, output_table):
@@ -282,7 +785,8 @@ SELECT {schema_madlib}.dbscan(
min_samples, -- The minimum size of a cluster
metric, -- The name of the function to use to calculate the
-- distance
- algorithm -- The algorithm to use for dbscan.
+ algorithm, -- The algorithm to use for dbscan: brute or kd_tree
+ depth -- The depth for the kdtree algorithm
);
-----------------------------------------------------------------------
diff --git a/src/ports/postgres/modules/dbscan/dbscan.sql_in
b/src/ports/postgres/modules/dbscan/dbscan.sql_in
index f4539b2..7e1df05 100644
--- a/src/ports/postgres/modules/dbscan/dbscan.sql_in
+++ b/src/ports/postgres/modules/dbscan/dbscan.sql_in
@@ -377,7 +377,8 @@ CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.dbscan(
eps DOUBLE PRECISION,
min_samples INTEGER,
metric VARCHAR,
- algorithm VARCHAR
+ algorithm VARCHAR,
+ depth INTEGER
) RETURNS VOID AS $$
PythonFunction(dbscan, dbscan, dbscan)
$$ LANGUAGE plpythonu VOLATILE
@@ -390,9 +391,23 @@ CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.dbscan(
expr_point VARCHAR,
eps DOUBLE PRECISION,
min_samples INTEGER,
+ metric VARCHAR,
+ algorithm VARCHAR
+) RETURNS VOID AS $$
+ SELECT MADLIB_SCHEMA.dbscan($1, $2, $3, $4, $5, $6, $7, $8, NULL);
+$$ LANGUAGE sql VOLATILE
+m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `');
+
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.dbscan(
+ source_table VARCHAR,
+ output_table VARCHAR,
+ id_column VARCHAR,
+ expr_point VARCHAR,
+ eps DOUBLE PRECISION,
+ min_samples INTEGER,
metric VARCHAR
) RETURNS VOID AS $$
- SELECT MADLIB_SCHEMA.dbscan($1, $2, $3, $4, $5, $6, $7, NULL);
+ SELECT MADLIB_SCHEMA.dbscan($1, $2, $3, $4, $5, $6, $7, NULL, NULL);
$$ LANGUAGE sql VOLATILE
m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `');
@@ -404,7 +419,7 @@ CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.dbscan(
eps DOUBLE PRECISION,
min_samples INTEGER
) RETURNS VOID AS $$
- SELECT MADLIB_SCHEMA.dbscan($1, $2, $3, $4, $5, $6, NULL, NULL);
+ SELECT MADLIB_SCHEMA.dbscan($1, $2, $3, $4, $5, $6, NULL, NULL, NULL);
$$ LANGUAGE sql VOLATILE
m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `');
@@ -415,7 +430,7 @@ CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.dbscan(
expr_point VARCHAR,
eps DOUBLE PRECISION
) RETURNS VOID AS $$
- SELECT MADLIB_SCHEMA.dbscan($1, $2, $3, $4, $5, NULL, NULL, NULL);
+ SELECT MADLIB_SCHEMA.dbscan($1, $2, $3, $4, $5, NULL, NULL, NULL, NULL);
$$ LANGUAGE sql VOLATILE
m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `');
@@ -456,3 +471,119 @@ CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.dbscan_predict(
PythonFunction(dbscan, dbscan, dbscan_predict_help)
$$ LANGUAGE plpythonu VOLATILE
m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `');
+
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.sf_merge(
+ state1 INTEGER[][],
+ state2 INTEGER[][]
+) RETURNS INTEGER[][] AS $$
+PythonFunctionBodyOnlyNoSchema(`dbscan', `dbscan')
+ return dbscan.sf_merge(**globals())
+$$ LANGUAGE plpythonu
+m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `');
+
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.sf_final(
+ state INTEGER[][]
+) RETURNS INTEGER[][] AS $$
+PythonFunctionBodyOnlyNoSchema(`dbscan', `dbscan')
+ return dbscan.sf_final(**globals())
+$$ LANGUAGE plpythonu
+m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `');
+
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.sf_transition(
+ state INTEGER[],
+ src BIGINT,
+ dest BIGINT,
+ n_rows INTEGER[],
+ gp_segment_id INTEGER
+
+) RETURNS INTEGER[][] AS $$
+PythonFunctionBodyOnlyNoSchema(`dbscan', `dbscan')
+ return dbscan.sf_transition(**globals())
+$$ LANGUAGE plpythonu
+m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `');
+
+DROP AGGREGATE IF EXISTS MADLIB_SCHEMA.build_snowflake_table(
+ BIGINT,
+ BIGINT,
+ INTEGER[],
+ INTEGER);
+CREATE AGGREGATE MADLIB_SCHEMA.build_snowflake_table(
+ BIGINT,
+ BIGINT,
+ INTEGER[],
+ INTEGER
+)(
+ STYPE=INTEGER[][],
+ SFUNC=MADLIB_SCHEMA.sf_transition,
+ m4_ifdef(`__POSTGRESQL__', `', `prefunc=MADLIB_SCHEMA.sf_merge,')
+ FINALFUNC=MADLIB_SCHEMA.sf_final
+);
+
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.find_core_points_transition(
+ state INTEGER[],
+ id_in BIGINT,
+ expr_points DOUBLE PRECISION[],
+ eps DOUBLE PRECISION,
+ min_samples INTEGER,
+ metric VARCHAR,
+ n_rows INTEGER[],
+ leaf_id INTEGER
+
+) RETURNS INTEGER[][] AS $$
+PythonFunctionBodyOnlyNoSchema(`dbscan', `dbscan')
+ return dbscan.find_core_points_transition(**globals())
+$$ LANGUAGE plpythonu
+m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `');
+
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.find_core_points_merge(
+ state1 INTEGER[][],
+ state2 INTEGER[][]
+) RETURNS INTEGER[][] AS $$
+PythonFunctionBodyOnlyNoSchema(`dbscan', `dbscan')
+ return dbscan.find_core_points_merge(**globals())
+$$ LANGUAGE plpythonu
+m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `');
+
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.find_core_points_final(
+ state INTEGER[][]
+) RETURNS INTEGER[] AS $$
+PythonFunctionBodyOnlyNoSchema(`dbscan', `dbscan')
+ return dbscan.find_core_points_final(**globals())
+$$ LANGUAGE plpythonu
+m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `');
+
+--id_in, expr_points, eps, min_samples, metric, n_rows, leaf_id,
+DROP AGGREGATE IF EXISTS MADLIB_SCHEMA.find_core_points(
+ BIGINT,
+ DOUBLE PRECISION[],
+ DOUBLE PRECISION,
+ INTEGER,
+ VARCHAR,
+ INTEGER[],
+ INTEGER);
+CREATE AGGREGATE MADLIB_SCHEMA.find_core_points(
+ BIGINT,
+ DOUBLE PRECISION[],
+ DOUBLE PRECISION,
+ INTEGER,
+ VARCHAR,
+ INTEGER[],
+ INTEGER
+)(
+ STYPE=INTEGER[][],
+ SFUNC=MADLIB_SCHEMA.find_core_points_transition,
+ m4_ifdef(`__POSTGRESQL__', `',
`prefunc=MADLIB_SCHEMA.find_core_points_merge,')
+ FINALFUNC=MADLIB_SCHEMA.find_core_points_final
+);
+
+DROP TYPE IF EXISTS MADLIB_SCHEMA.unpacked_2d CASCADE;
+CREATE TYPE MADLIB_SCHEMA.unpacked_2d AS (
+ src BIGINT,
+ dest BIGINT);
+
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.unpack_2d (packed INTEGER[][])
+ RETURNS SETOF MADLIB_SCHEMA.unpacked_2d
+AS $$
+ return packed
+$$ LANGUAGE plpythonu VOLATILE
+m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `');
diff --git a/src/ports/postgres/modules/dbscan/test/dbscan.sql_in
b/src/ports/postgres/modules/dbscan/test/dbscan.sql_in
index 621251a..0e79e98 100644
--- a/src/ports/postgres/modules/dbscan/test/dbscan.sql_in
+++ b/src/ports/postgres/modules/dbscan/test/dbscan.sql_in
@@ -51,6 +51,12 @@ SELECT dbscan_predict('out1', 'dbscan_train_data', 'id_in',
'data', 'out1_predic
SELECT assert(count(DISTINCT cluster_id) = 2, 'Incorrect cluster count') FROM
out1_predict;
+DROP TABLE IF EXISTS out1, out1_summary, out1_predict;
+SELECT
dbscan('dbscan_train_data','out1','id_in','data',20,4,'dist_norm2','brute');
+
+DROP TABLE IF EXISTS out1, out1_summary, out1_predict;
+SELECT
dbscan('dbscan_train_data','out1','id_in','data',20,4,'dist_norm1','brute');
+
DROP TABLE IF EXISTS dbscan_train_data2;
CREATE TABLE dbscan_train_data2 (pid int, points double precision[]);
INSERT INTO dbscan_train_data2 VALUES
@@ -107,3 +113,1084 @@ SELECT assert(count(DISTINCT cluster_id) = 3, 'Incorrect
cluster count') FROM db
SELECT dbscan_predict('dbscan_result', 'dbscan_test_data2', 'pid', 'points',
'dbscan_predict_out');
SELECT assert(count(DISTINCT cluster_id) = 3, 'Incorrect cluster count') FROM
dbscan_predict_out;
+
+DROP TABLE IF EXISTS dbscan_train_data3;
+CREATE TABLE dbscan_train_data3 (
+id_in integer,
+data0 integer,
+data1 integer);
+copy dbscan_train_data3 (id_in, data0, data1) FROM stdin delimiter '|';
+1|1|1
+2|2|2
+3|3|3
+4|4|4
+5|4|8
+6|17|8
+7|19|8
+8|19|9
+9|19|10
+10|3|111
+11|3|112
+12|3|113
+13|8|113
+\.
+
+DROP TABLE IF EXISTS out1, out1_summary;
+SELECT
dbscan('dbscan_train_data3','out1','id_in','ARRAY[data0,data1]',20,4,'squared_dist_norm2','brute');
+
+DROP TABLE IF EXISTS dbscan_result, dbscan_result_summary, dbscan_predict_out;
+SELECT dbscan(
+'dbscan_train_data2', -- source table
+'dbscan_result', -- output table
+'pid', -- point id column
+'points', -- data point
+ 1.75, -- epsilon
+ 4, -- min samples
+'dist_norm2', -- metric
+'brute_force'); -- algorithm
+
+-- Test kd-tree
+
+DROP TABLE IF EXISTS dbscan_result, dbscan_result_summary;
+SELECT dbscan(
+'dbscan_train_data2', -- source table
+'dbscan_result', -- output table
+'pid', -- point id column
+'points', -- data point
+ 1.75, -- epsilon
+ 4, -- min samples
+'dist_norm2', -- metric
+'kd_tree', -- algorithm
+2); -- depth
+
+SELECT * FROM dbscan_result ORDER BY pid;
+
+
+CREATE TABLE dbscan_kd_test_data (
+ row_id integer,
+ row_vec double precision[]
+);
+COPY dbscan_kd_test_data (row_id, row_vec) FROM stdin DELIMITER '|';
+1 | {-123.932588658681,312.674262022751,24.5140517556683}
+2 | {-1011.71837586596,294.857038270306,-596.339561040807}
+3 | {51.8496080463916,-392.173152861615,188.5097494329}
+4 | {799.127036569478,607.197217229762,-273.651240009801}
+5 | {382.754942347373,-730.542867226352,-16.353747006894}
+6 | {-184.468870153144,-221.332003547174,-591.35952658191}
+7 | {726.513984734646,156.985561437554,248.190787632731}
+8 | {-513.344896244817,310.773265404381,104.080456390778}
+9 | {868.906770040562,81.5471578992944,133.417529135344}
+10 | {304.7305636991,-465.597195927162,-692.38269341934}
+11 | {146.202397090308,643.426041147766,251.311062888657}
+12 | {613.839242557284,243.372738740541,-344.926416003253}
+13 | {-279.919780960877,830.688490188374,1106.70854171082}
+14 | {-239.941313060048,-150.729513285438,-644.486977709577}
+15 | {864.059606049879,229.761999686115,98.6393846787974}
+16 | {137.027023944766,-872.639896518612,-484.121630800583}
+17 | {-93.3532574414556,-2.83052851435212,-156.831074125122}
+18 | {386.756957145158,252.495312534386,-639.330396910652}
+19 | {210.12451616637,197.83940894125,121.228834110555}
+20 | {786.057957303133,-78.1737488754506,-293.537312267519}
+21 | {-338.401548335188,-500.885224226621,259.552625635757}
+22 | {-1037.65134435009,354.929835928489,-523.731062929561}
+23 | {649.665190518576,-201.744043329729,-383.714123375157}
+24 | {807.715272986264,527.719510934861,-238.925155968575}
+25 | {268.191717463272,288.453191375757,-292.660016634391}
+26 | {-767.046262696949,1054.28570038854,186.785685210919}
+27 | {603.597270228634,-426.717913313373,324.192854724388}
+28 | {-790.646063944855,613.794909920021,550.899642687981}
+29 | {-358.978123286781,-213.107177187055,297.623829646779}
+30 | {649.852832534744,-122.747853286041,-338.070280521321}
+31 | {289.975381104444,52.5492690561587,615.373688551293}
+32 | {219.2134287942,640.352925517431,-795.284581991311}
+33 | {14.9784107468498,-88.4494781406069,-123.072306109659}
+34 | {612.022594601429,-185.543004824301,-420.069777109188}
+35 | {-610.292592609088,239.789613935357,-673.520045033667}
+36 | {597.003206042794,197.782402998881,-376.678467551101}
+37 | {-56.8423068877579,232.889540939775,-233.929448140762}
+38 | {-933.879560389274,243.309855746838,-898.095254476934}
+39 | {340.465735117938,-578.405302034855,183.553117253541}
+40 | {-246.878364743862,-291.805796246968,-436.136662769966}
+41 | {993.304698488409,346.890205803306,17.6842057114629}
+42 | {172.133516798735,333.3442277846,-242.843618338439}
+43 | {747.733954731529,-356.07131864678,179.589467597229}
+44 | {679.345380618229,-2.68044668758962,-120.148391244667}
+45 | {488.894449728494,24.5452925443855,775.17536040857}
+46 | {260.731153450907,-868.175147049231,6.81574295503747}
+47 | {228.857968968147,70.8801925885408,369.851765182293}
+48 | {252.759302911726,153.249295308294,-638.37262532948}
+49 | {269.683805099097,51.0370679682875,712.091481303516}
+50 | {-269.268132926522,746.729882052773,195.702023539655}
+51 | {71.874274025531,759.649148831518,491.611002746426}
+52 | {-1663.96137606517,90.8133823647075,158.780074279377}
+53 | {-257.774920797097,-1030.22503446527,438.046739208405}
+54 | {752.215292509861,146.919523983795,-147.598607179812}
+55 | {177.381727903258,-818.519450864293,193.311594615948}
+56 | {166.741559741122,-163.118628708694,-404.900637540065}
+57 | {-1323.27537778783,-10.4967284230377,294.326001051292}
+58 | {549.909097625585,-596.903824692408,-301.850694344547}
+59 | {-269.916901585881,-627.64977878287,750.090432540072}
+60 | {775.624254458252,748.972003078806,-203.81676894634}
+61 | {-436.226974986994,-437.004875894216,-30.9748235460759}
+62 | {613.909837635605,48.4334189055091,-283.321027026525}
+63 | {-278.298037765777,378.436027806079,-257.853892045902}
+64 | {-1202.56287057624,259.014693113529,-200.71700430311}
+65 | {-576.994841464984,-523.386659017049,-230.554592593487}
+66 | {590.512151325561,398.065888838862,-347.231929394332}
+67 | {-242.822744756977,234.108323204393,-553.377918691274}
+68 | {943.6070753902,527.274570985321,-139.520854405628}
+69 | {-206.014801247102,528.178478241241,486.935420937639}
+70 | {-1231.88609517802,153.935968150265,190.638604939725}
+71 | {226.418944290168,514.65522108823,153.940917502731}
+72 | {406.242837506357,-413.34465423586,-431.049640725801}
+73 | {926.165945865784,292.497866770696,-32.5080388329608}
+74 | {98.0573027347866,141.647767296212,-689.77208317581}
+75 | {56.0959548637969,352.466952034086,850.195823590721}
+76 | {-845.263692780283,416.03103508814,-172.788128651063}
+77 | {342.859916548665,913.856416969682,685.48442034131}
+78 | {870.402457998673,726.676162243837,-182.971969280292}
+79 | {902.084234723884,490.477847071824,-337.824139748125}
+80 | {448.69419403979,-265.157573745948,-475.977013656683}
+81 | {-514.145412080225,413.261678856384,423.685005329721}
+82 | {-1066.01057897006,223.132531695535,-377.510836697104}
+83 | {-1021.50193347937,562.090253650298,-115.416784003661}
+84 | {-214.665103199501,32.8354197166855,-655.755578142951}
+85 | {278.049567196342,-697.129051950011,331.983924953855}
+86 | {179.724335008794,372.581626915806,-69.9806579428635}
+87 | {267.843845960723,21.7937867013737,700.60305984757}
+88 | {155.422832917542,-918.852392503608,-563.676251121922}
+89 | {-1177.23091561181,341.471135494987,636.07808560086}
+90 | {-67.9351579896963,-883.142952530624,-700.374252405142}
+91 | {-553.619481648191,-211.465410119479,-521.307252570533}
+92 | {145.858752083652,-658.631751181041,-353.373990023229}
+93 | {185.193850071249,-561.658346810616,296.077972874417}
+94 | {-163.225970575355,229.836951327697,-595.344875329231}
+95 | {203.55885535432,149.585670575698,-364.601983510134}
+96 | {-1235.84629981963,185.498736396646,-355.528834988744}
+97 | {658.286726835515,-592.635303407991,-50.7071498078878}
+98 | {136.841617763444,143.047237706469,-404.61280361507}
+99 | {158.811144857791,449.009048224879,1005.07753726789}
+100 | {927.860188757477,398.986993124426,-107.630193699315}
+101 | {312.494434150204,-144.984356964967,-106.847512834076}
+102 | {41.6384585803,-721.261854728639,-104.693423095052}
+103 | {866.942830053234,299.976907656981,18.1379345809771}
+104 | {316.089900119565,-798.289231608766,-187.177103552882}
+105 | {717.715398540749,33.5083707168619,146.963160971621}
+106 | {877.89816548212,823.178371173346,-335.256678447164}
+107 | {-470.579659565495,103.395254167218,139.275891941627}
+108 | {-256.599091223439,643.184223168957,118.114881878856}
+109 | {-448.281040797465,416.581677353488,367.177889179331}
+110 | {185.696099582541,-170.62108058618,-52.5855121896673}
+111 | {-64.6644999941366,-596.187534494299,503.632110740989}
+112 | {-747.037751783091,-212.088537754028,640.399855603188}
+113 | {995.797175264268,275.696395459126,-2.6031804563241}
+114 | {781.811070203258,901.88973031654,-342.469279381926}
+115 | {-1371.06472904863,0.254753126924469,28.1590955689618}
+116 | {161.638509349012,-826.99415058209,-415.359079451205}
+117 | {60.2440795907806,-1031.48434296339,129.80450714383}
+118 | {-632.754078578421,595.954722549919,-52.1965000148961}
+119 | {-792.275358264915,273.965086375479,31.4263876136518}
+120 | {-1371.55837611464,350.041174628846,-849.606882071275}
+121 | {-577.31215410232,-218.006790696498,459.303941542333}
+122 | {-1541.60323702349,782.610438668886,403.995959184054}
+123 | {341.476380596273,499.411480471099,-269.729378826935}
+124 | {173.23061521224,-721.191535815391,-414.764004342643}
+125 | {928.779761572521,355.688704910061,46.5382786373071}
+126 | {209.724942648269,560.612581086384,-197.447200573214}
+127 | {-313.973068774299,31.0882298202861,33.9370433613805}
+128 | {251.221805066445,-319.825003528556,-727.848057451017}
+129 | {923.27529093008,452.927865196981,-46.3175300513252}
+130 | {94.1001366827434,424.393803256897,-696.672177048828}
+131 | {290.777077215229,386.875089358842,705.238902783636}
+132 | {78.3104427987785,-593.999773769646,-693.89660403862}
+133 | {530.165597614355,303.568827698029,21.8307597880683}
+134 | {745.989685666099,-350.914161320458,-1.63452735343602}
+135 | {230.625054830844,-151.878827428637,719.675931469744}
+136 | {-4.88204686109166,632.429483520486,-10.3403865486221}
+137 | {347.376793331603,466.684675808313,1034.79903899528}
+138 | {555.922207006474,522.362209958336,-508.643912795811}
+139 | {-554.897605831554,670.651132833643,138.629544715331}
+140 | {238.571508235037,-537.280329277,-636.905112765466}
+141 | {676.103107062802,12.4799973194849,121.540894483029}
+142 | {518.526499029932,-68.0671987185693,-419.148640255824}
+143 | {275.950298846445,-658.732193051554,122.825937733362}
+144 | {248.543173029081,-118.945164499253,26.9352643130976}
+145 | {337.688653144682,297.961306208333,564.011462067362}
+146 | {382.85599052658,-6.85388913061074,-562.125695427939}
+147 | {-52.4475318190431,644.109608617153,-483.134594336694}
+148 | {149.841502399512,-205.951679756533,-658.23250424851}
+149 | {404.217286019655,-311.921368597925,-218.012332084879}
+150 | {-329.815477358164,574.875649505225,1073.31425379999}
+151 | {330.611675991508,-151.669569164386,-347.609167073519}
+152 | {-297.017584051949,-222.609475176527,-624.101650686011}
+153 | {877.728101693063,599.633343871781,-95.7768256174856}
+154 | {691.095600886416,-227.89716818059,-142.628393241196}
+155 | {64.222822214952,-708.804914430627,559.913142173742}
+156 | {-154.985650210882,5.57199213748102,-800.386729632886}
+157 | {-769.054471295342,55.2932504282974,-50.5244199234928}
+158 | {-222.466780840431,467.825974075828,-282.72979171046}
+159 | {26.7916368906677,-368.256797039103,437.004516621924}
+160 | {-196.978340559212,52.6103592942436,-307.534384366573}
+161 | {310.51748558234,-104.166567060538,358.418634774962}
+162 | {-623.271552287036,946.354651233934,-89.9314144559954}
+163 | {289.402893273542,-721.731189379299,547.006877006168}
+164 | {421.5331349382,-254.457678817215,-448.030003277579}
+165 | {-612.061742515849,-657.322569404473,390.311217087443}
+166 | {-121.306790800733,138.125351085248,-654.746049688596}
+167 | {368.719660673043,-559.117366768125,-453.662659305552}
+168 | {119.812637986994,-771.28373582792,-406.250648502737}
+169 | {674.236906483308,130.687745297242,-76.6053685891544}
+170 | {-1022.79757969621,311.718315630086,-183.127390880452}
+171 | {202.338403452415,-860.307354892633,424.079844438539}
+172 | {-387.045718709377,232.529857640182,-265.836636378781}
+173 | {18.2125290669655,-906.569503580754,217.379400495216}
+174 | {686.03338296649,249.199448995659,-318.359885821749}
+175 | {980.894478237984,374.335582889807,33.9180784285859}
+176 | {324.922851226244,204.369620341049,-509.807691878582}
+177 | {530.081614602026,-415.709203779453,440.205908751018}
+178 | {925.363130959933,580.025078187357,-364.204601054662}
+179 | {-373.610131759552,-0.718393149850969,-603.127464106215}
+180 | {-687.995822021562,301.193093975771,284.730186445072}
+181 | {717.48690071556,357.084745476417,49.2505276798374}
+182 | {-254.244391140987,-441.008028494252,-65.0781968354926}
+183 | {-559.738812937771,592.422666536987,850.671057509993}
+184 | {313.921519762085,-953.05201460759,-38.196695019816}
+185 | {822.255207617371,212.696989807625,152.074132442933}
+186 | {-57.1317994970976,-795.313449329732,-450.834310152401}
+187 | {80.1667539451294,103.965773324679,293.437236704695}
+188 | {-635.575347681524,1145.31289171765,-375.223593239241}
+189 | {-159.541032167873,-196.203058439151,209.473048650684}
+190 | {-138.287980061376,67.8680801733663,-143.560064410083}
+191 | {-72.2155149533544,716.065722326693,-169.735463109537}
+192 | {407.908223041248,75.1313796781743,-528.873217927684}
+193 | {-1221.59208595602,138.061907094,-364.082619035294}
+194 | {13.3646914711573,-710.166502673975,-440.617088418329}
+195 | {-334.036655083391,-909.653603753016,425.174731451375}
+196 | {350.182349053338,-275.273598905502,-365.819929719917}
+197 | {-335.440697739989,-974.019605374756,797.236889156825}
+198 | {434.72369147896,511.559583754292,-491.097670859027}
+199 | {195.605291564488,645.61974621394,907.884362939621}
+200 | {-35.1737342414631,-398.968243796021,-373.632014143764}
+201 | {702.533333143816,120.535262693352,45.6569065767321}
+202 | {752.813997164527,487.750382767263,-290.896418153567}
+203 | {252.82093856,315.982951678391,-594.328951375259}
+204 | {-180.523516820434,-100.062549981327,28.0950313606483}
+205 | {286.858685263634,-301.422784988896,-501.539242778488}
+206 | {767.039697015571,780.113526935977,-236.554781739303}
+207 | {-1100.92518978373,377.745584580959,501.617939247464}
+208 | {-198.275146379448,-230.174105952237,-311.191311266055}
+209 | {986.975527136794,480.742909440388,-204.500898956358}
+210 | {-1322.09260615232,674.524354191798,660.109907134343}
+211 | {-278.385549939677,83.3551636151832,381.828965334432}
+212 | {964.905378912989,639.312856721136,-199.672820275921}
+213 | {594.413326401024,-307.924682001146,340.886251028796}
+214 | {-389.516990600771,312.961545355854,-443.264875424668}
+215 | {-210.28684651554,-888.474814698773,644.54276721249}
+216 | {-298.281566534085,872.747832807321,356.881877402889}
+217 | {-606.672716216157,9.20886088515567,473.597430667058}
+218 | {53.3306046761978,-682.815972379101,-153.981938157605}
+219 | {-166.164426700657,87.9674705749968,36.356362610877}
+220 | {-244.670274987449,224.989819322353,-369.881804224672}
+221 | {-381.347893104584,732.3849554511,-179.712174063503}
+222 | {-757.726594354378,-319.322511141291,-423.767627054307}
+223 | {-713.348202375684,-471.709482641208,488.018014589984}
+224 | {118.736181360627,-839.71877329138,-390.068049479781}
+225 | {10.8784288145688,-87.4897784701692,-143.365488561671}
+226 | {-293.506303853627,438.241052243718,-508.269091008473}
+227 | {394.34862896922,-671.585113656735,646.208496624259}
+228 | {484.593179470938,-532.272038085391,-58.2469420293706}
+229 | {224.398148966515,-121.32531002782,567.759078846576}
+230 | {-1054.65585735268,173.204339573606,690.673929900579}
+231 | {405.421717506233,-540.089300175202,-323.715660127428}
+232 | {947.953934214412,697.910938365625,-155.603791955845}
+233 | {-112.61761811219,-76.7013995353192,43.330990838962}
+234 | {-110.300872290683,146.621004555421,-836.233454271909}
+235 | {-895.507800234031,129.053214877903,216.127565778741}
+236 | {-228.738512691034,687.73671096529,67.1144690673398}
+237 | {28.9333252900687,161.537483761917,-235.717915596879}
+238 | {56.9141559972235,-865.972027912909,-103.487553156228}
+239 | {-182.441743993424,-287.49201467789,-25.1443406587628}
+240 | {10.1173252174403,260.10641628891,-330.763664296458}
+241 | {730.370055906335,151.824642697818,172.980422573513}
+242 | {-791.96924586964,-486.685916440648,58.5737220929955}
+243 | {-651.740131262894,950.198601442712,382.29610037216}
+244 | {84.5978038634731,-1120.86404693992,87.3944812524254}
+245 | {-942.198864996848,119.970703442216,714.344958413139}
+246 | {-59.3495582750651,509.613622506798,-413.669293188925}
+247 | {-187.47239025722,301.309716611758,507.378137262389}
+248 | {449.207763462859,-462.637114567643,30.3798672941953}
+249 | {610.456778807888,198.519818741946,333.300259367063}
+250 | {-927.933637336285,422.103101959924,605.889195417107}
+251 | {131.419211797127,-225.686366734672,325.392488111269}
+252 | {1005.50237913565,514.951885957742,-169.477238517533}
+253 | {365.992584121997,794.437829227493,207.335684319584}
+254 | {-647.725418987958,206.031579182044,-834.994754871832}
+255 | {-149.519090037423,618.58797362626,589.222469754598}
+256 | {-81.6208935759235,677.326281876909,-158.853684654441}
+257 | {704.581717074611,460.268957486136,-312.431299453742}
+258 | {136.760600914922,-761.315656574841,-565.773388934528}
+259 | {542.792534835575,-343.614858427223,136.395307493572}
+260 | {109.99160427489,-56.7054394290818,-610.381077528243}
+261 | {90.3449573058456,-130.001349478866,-81.4654506128783}
+262 | {-512.665406165849,-366.304920154402,-682.481809089526}
+263 | {-22.1796104306038,348.788172041955,-361.757908670545}
+264 | {76.241248309695,-1059.8098209341,-76.7624576831485}
+265 | {174.156857158579,-408.43442275703,550.26449991691}
+266 | {-178.515270017749,151.704124192512,-483.205858719553}
+267 | {-305.456786757011,769.044055844025,642.100602670379}
+268 | {476.698119462161,-517.298391047742,351.767173123356}
+269 | {510.895510245851,-395.70285923919,-75.6995982438582}
+270 | {910.31363595359,753.438810488909,-201.073732609609}
+271 | {872.315398041446,361.200236795391,-25.1554621518617}
+272 | {420.635022939196,-498.313838582602,-363.494121244324}
+273 | {-177.269675345942,-910.590607973394,273.616506061199}
+274 | {76.3436012931424,249.507611236412,-311.616111454328}
+275 | {181.02110956064,502.001710756496,-45.9732382995407}
+276 | {-63.0962293442747,-780.625207934631,-400.56043160221}
+277 | {981.770911041083,343.643026129044,-45.3128733900144}
+278 | {-584.10315976854,179.10155610122,-634.497970435302}
+279 | {-269.063997536307,607.785493848366,-138.82045235882}
+280 | {-143.842051235726,267.439579485124,391.680207380163}
+281 | {519.947653297392,-640.07913909545,-65.9119266364107}
+282 | {-302.825650890623,613.330438844525,323.149242956132}
+283 | {232.67661526524,-451.996375814583,525.372103301078}
+284 | {-1724.69142566052,469.14069830831,210.787459128411}
+285 | {-432.91731598958,507.186190366737,896.327861511646}
+286 | {512.803901693912,-389.637573788805,93.5784757999194}
+287 | {-593.69828108371,63.8644494977606,-137.746169721704}
+288 | {471.074607299921,108.754186932717,-411.435753246054}
+289 | {452.773319967048,-770.671241689298,317.087466913385}
+290 | {305.932511972531,-651.098205568271,-316.141242583735}
+291 | {977.054737633027,618.644320281761,-115.25507944907}
+292 | {216.268672749371,759.996507131981,-126.711772022954}
+293 | {412.330061730791,-272.453268307611,-28.7773794667325}
+294 | {-1953.04707833322,476.159268458845,-234.938228291953}
+295 | {-513.985270392564,-631.995115846413,-90.3506179653199}
+296 | {268.866635204195,543.6049855296,-505.242368473939}
+297 | {-1138.74636015926,172.469648648152,-16.9395066721298}
+298 | {59.5415772641756,-776.895893581939,-493.697596549044}
+299 | {-229.255970499488,661.44241505883,1197.43170214103}
+300 | {-522.949598745089,-342.317003623386,-484.998256429935}
+301 | {624.989850092813,357.393515363269,-94.9682976203501}
+302 | {224.794668460843,-913.97461218077,-287.470841579596}
+303 | {21.5354377920639,106.440907559115,-838.753380401963}
+304 | {-1709.19699654119,494.920585053875,-633.078748065034}
+305 | {473.307143995647,-404.502856191805,515.309755581454}
+306 | {345.507875665702,-683.330311742503,-391.63805296806}
+307 | {-575.126012646451,203.543730284027,322.43512177424}
+308 | {449.965321262723,-643.208033329854,-172.754076264661}
+309 | {-477.666830107041,322.555087605572,-617.20061990134}
+310 | {859.269255540004,742.191701261763,-115.601622432398}
+311 | {953.084751563622,311.086906299598,117.197429899017}
+312 | {-533.95874304058,-333.343383145402,-547.428511085023}
+313 | {-99.0047559561135,-22.3743009879742,390.158118403224}
+314 | {554.003376594728,-333.462614002376,-86.9157912182443}
+315 | {-204.918957237642,-553.862611836255,305.328359992685}
+316 | {904.176359288498,674.81720881397,-284.096063512534}
+317 | {48.3170123014491,181.072994538896,965.858917574502}
+318 | {-402.646920810498,71.7321514794017,-905.891618668266}
+319 | {316.071778240667,414.467710167676,-24.4071264681002}
+320 | {420.375999198925,-394.580048143078,-531.063040785746}
+321 | {-1143.2405560093,192.170059526702,10.2142627272553}
+322 | {-82.1574799683772,549.18794975444,-66.7873090337897}
+323 | {-86.6843680661668,-533.742046243743,520.800757467371}
+324 | {-732.462588539979,-511.317061626004,-129.023018378612}
+325 | {211.61766491859,-879.400072352874,18.8060794504145}
+326 | {-618.251764970305,167.834857909278,-751.837053445814}
+327 | {-932.19298572634,112.642111591201,-113.205670720154}
+328 | {217.799288140231,649.51363123181,-298.262130770787}
+329 | {-579.729436575179,-107.261563652181,-182.81984256084}
+330 | {10.9853516640163,-933.859056652432,-572.992269231245}
+331 | {-259.487025812284,621.876082410585,606.326130070292}
+332 | {-226.420065155714,-467.174708376193,-592.015255267082}
+333 | {-234.275753696963,263.682256649359,710.748924089039}
+334 | {-435.690010838885,364.232806735142,410.974538778665}
+335 | {-104.446304939002,-684.723255984144,492.257736613582}
+336 | {169.599760568186,-94.4527184243665,-498.79464837813}
+337 | {389.455569029528,-540.058098966027,147.307024243665}
+338 | {53.3633506608499,-917.061067048708,-209.881780422017}
+339 | {84.3340525251708,-846.534146760375,23.1895795357894}
+340 | {-487.01079563553,186.842869085594,-610.373270842639}
+341 | {-138.978436313878,-442.490101205001,317.106236958948}
+342 | {-328.79647787375,676.604732005631,32.9361799414727}
+343 | {526.271176162738,-224.808938453964,63.0636831011326}
+344 | {272.268287296183,515.44547331077,-720.103805154437}
+345 | {131.198118009859,-729.164107511484,435.135916675743}
+346 | {879.680977081302,611.871374709576,-298.732567622536}
+347 | {102.955964016661,-83.4479454272387,77.9817162387275}
+348 | {-575.575141974943,148.489645623754,-875.842674004145}
+349 | {54.1594086939664,454.948215813284,-273.072469733803}
+350 | {3.29900166719316,-807.146134342838,-60.5812027037688}
+351 | {210.898908783065,-782.763118712499,328.505060726155}
+352 | {814.917941505118,580.830644674071,-374.931026234055}
+353 | {-567.184556693858,502.395568338215,591.607469728492}
+354 | {274.352219545012,-533.679758619067,-148.910928356681}
+355 | {475.770029556265,-487.421606475358,442.470787421646}
+356 | {793.326603478998,747.726036145896,-334.901159161955}
+357 | {397.160150860322,247.792371866122,973.010172900265}
+358 | {912.08162203896,587.750642399583,-407.569115619358}
+359 | {757.407515416379,111.429168144541,88.3346513127937}
+360 | {-1147.80574236177,347.732758888107,-134.171075165781}
+361 | {426.476473600079,1006.08974535188,320.548644203402}
+362 | {-80.181270006828,388.473752328192,78.4836479169393}
+363 | {296.389241896439,-795.635604972469,-1.32765192613692}
+364 | {585.725104788188,-286.221043364657,-449.181824894238}
+365 | {468.46375035446,-465.050290975735,-47.9302751309938}
+366 | {-407.274360878147,286.087533292467,-416.990898155993}
+367 | {896.800820591847,355.332196656719,-74.6670347455514}
+368 | {-770.916334777547,-331.128740178432,-489.506461194702}
+369 | {487.23346870336,395.98491362138,-89.7939429685944}
+370 | {159.802388147014,-910.373448564408,-156.768640472894}
+371 | {811.799760343949,179.615268597205,252.11012706447}
+372 | {-394.462406985416,-892.850886240543,213.72266953489}
+373 | {427.651272074627,-550.933926519887,363.911287477545}
+374 | {349.468856169766,-658.095359107168,-395.182358571423}
+375 | {91.8942379383517,-714.650026866811,386.740787696337}
+376 | {-612.80795859733,124.624448066035,-757.303297464803}
+377 | {51.9458649009602,339.111132036119,515.418968673663}
+378 | {-182.372929416926,-942.634599879938,-353.210262722814}
+379 | {-3.00264985984875,422.419995813511,-277.327479182083}
+380 | {558.363569929053,-323.733119319969,-421.920371621665}
+381 | {-457.242915381044,-689.899338664912,175.336585993796}
+382 | {-372.570961209771,146.202955799612,-933.650070181235}
+383 | {805.930772865,375.884310411012,-138.901130087469}
+384 | {85.9160249656279,-813.107718860409,-186.936525847028}
+385 | {488.780876269051,-535.473552091837,118.208058872337}
+386 | {-586.255389057148,252.421345038034,-822.097168743349}
+387 | {-178.470004161705,406.653950902725,870.019014572561}
+388 | {244.203984199115,-773.270794074194,-59.2940071964743}
+389 | {637.898975584093,-33.550813018246,-264.250861402128}
+390 | {466.616403072951,-520.1278750033,-397.050714489564}
+391 | {-71.2259285094823,779.563308372759,122.848856111467}
+392 | {-281.896058287109,120.399971301,-610.201579225824}
+393 | {114.895391715427,557.80021416049,1015.71679522396}
+394 | {170.697354824239,376.763871054044,-755.908649127931}
+395 | {608.284681616519,222.796273143494,133.371130885525}
+396 | {-621.486736924824,-132.213765473724,-656.097082118266}
+397 | {60.0945474374745,257.403209911627,124.871604057035}
+398 | {813.165419335817,709.576424661116,-187.723055815793}
+399 | {819.084753114636,261.847855944848,119.519599599984}
+400 | {-1591.11699504515,451.765744812528,-1084.07381389854}
+401 | {100.836235499064,45.1692677870091,6.71665535390334}
+402 | {71.9987686033297,-301.119651193113,-491.952724311063}
+403 | {-21.4854801941939,-856.538863769626,-139.635850856623}
+404 | {39.0185291983767,105.225584647705,-582.08435334705}
+405 | {-341.551324381422,553.102678536304,820.957715337237}
+406 | {-238.676040878439,596.475062006686,227.261170544244}
+407 | {677.263400995669,170.262695934152,145.576375698915}
+408 | {9.12547146156543,180.359657967512,-474.355893841514}
+409 | {974.819226687325,354.914104145955,54.4817971994358}
+410 | {402.484050808457,-540.802516168123,-511.981328227048}
+411 | {248.703388970545,1025.1097083336,-327.058213775947}
+412 | {384.936221959771,-577.775139993188,-467.827571287516}
+413 | {723.903716050944,-238.987348866713,153.015184484788}
+414 | {311.735600106838,-697.566335453892,-433.343668594933}
+415 | {142.965482466729,-52.6980268671412,-260.243588842275}
+416 | {160.100840549061,284.92268295551,-1039.92792558982}
+417 | {1037.91913083568,380.670628839144,-296.113412462725}
+418 | {598.781959566029,74.6568609444189,-327.133335149884}
+419 | {630.543696264649,13.7310638518728,-104.839389382329}
+420 | {279.455929621923,-530.179625285714,-295.21631527422}
+421 | {240.524050325161,-129.052470215072,59.8165377851838}
+422 | {-365.39673502932,-344.301581001411,-809.503633420073}
+423 | {757.022813817618,-343.907582190206,114.039518486389}
+424 | {448.695736428793,-388.271140062866,-405.061996855199}
+425 | {-22.9058631343533,-316.126520650765,940.560436920855}
+426 | {-285.944464167464,222.898868288105,-260.716629656138}
+427 | {-252.422413155871,-957.087166358264,340.821797196074}
+428 | {-1882.99623836936,283.860272366386,-949.66481016547}
+429 | {297.317599060629,-495.565601466887,818.961050509237}
+430 | {-1751.20369603674,528.424487540286,307.132966165625}
+431 | {-37.4735324946073,278.70780796336,-53.5821730245203}
+432 | {-297.250461444078,-464.538273141524,-525.056551841106}
+433 | {21.0822385591843,37.6738929377201,-364.606782787189}
+434 | {106.79125804557,663.62222729765,-102.002776618213}
+435 | {317.675657314467,-448.737176823445,513.396745496883}
+436 | {-1408.19500897142,321.700273685132,-54.2088816106459}
+437 | {304.198522094964,-576.206616646692,198.669138225353}
+438 | {356.951292873271,9.85404025181337,-407.831348441305}
+439 | {-221.909854717695,-841.613794951758,403.942929593813}
+440 | {218.042303966432,178.348618480596,-817.881655620234}
+441 | {-1281.52525297999,484.907607886733,479.550559714883}
+442 | {436.772103628282,-447.130350411483,16.7184813389559}
+443 | {302.501938748731,-664.783713642657,140.078437332494}
+444 | {797.719888084189,652.632396688113,-231.580100785436}
+445 | {671.021288192126,43.8037318602946,364.996137996503}
+446 | {78.0541237451137,192.503273867577,-523.868141832414}
+447 | {-507.766602721028,-794.065415138739,334.15690710198}
+448 | {775.369058341192,724.559087933035,-214.452129063896}
+449 | {41.1337435670084,85.9255709310885,-707.848065045515}
+450 | {-327.416878634682,-444.05722199435,-753.713951362636}
+451 | {853.338544612389,505.014033820954,-205.624425866576}
+452 | {-1002.36407430723,-132.22009219999,-285.390713565312}
+453 | {-567.409601190117,563.747137108595,266.524796551915}
+454 | {-938.006315891387,297.032920646306,-675.158621015533}
+455 | {961.818194458522,187.035646668105,80.7153213265519}
+456 | {920.262135557397,626.854702922905,-201.949915458484}
+457 | {391.18639216917,369.816664878082,-51.4420798649837}
+458 | {-103.084166591067,235.213055217911,-871.466065470742}
+459 | {-1731.3593866932,428.340451016334,601.81251144488}
+460 | {156.258981912923,-405.204302714197,757.312436486708}
+461 | {172.798332662283,-781.412726975732,43.4703643500116}
+462 | {-124.682756051884,-921.427433695609,-298.206171901951}
+463 | {-1558.28885353475,259.291320165662,-140.708674430952}
+464 | {587.588583579763,16.0557213142602,-477.32466112425}
+465 | {-1135.48391353965,530.957523534048,509.033267407822}
+466 | {-500.467763528005,82.7787061301719,-797.6607116279}
+467 | {934.490371788019,413.428351079979,-62.0748950410273}
+468 | {-149.852971522378,-491.939622292473,-257.656477147412}
+469 | {163.894796836653,-246.14078953069,421.152391826798}
+470 | {-76.3779189268282,-132.503316507637,-797.355624915202}
+471 | {543.14213671445,174.569465816672,52.6134105626089}
+472 | {314.937627269956,-264.234359593651,-590.479129807736}
+473 | {546.15063150275,547.633844305612,181.384651896172}
+474 | {-944.106446131244,164.389365176612,-809.484208317295}
+475 | {-276.186861195802,-9.8405419754517,199.633793865809}
+476 | {791.364382250026,548.002078881368,-110.412431254201}
+477 | {284.644372998784,-365.707960764279,-131.729414070876}
+478 | {-374.09830051264,271.232542687002,-686.163451202625}
+479 | {601.222343461796,-547.2063133236,202.274933700423}
+480 | {-280.427483990363,311.020571420288,711.439299780444}
+481 | {-436.855918970441,-118.961280113762,411.287720459391}
+482 | {0.0619362573841019,-613.411489239433,-741.524353321055}
+483 | {470.436747536129,-524.083028409058,-125.386248166657}
+484 | {-67.4736991006526,-202.700377449104,-276.265738206689}
+485 | {862.866782034975,235.414401144183,90.0181307538263}
+486 | {-100.271266503223,65.685905648072,-758.606729986432}
+487 | {-131.352342426162,373.824056926479,915.740636292545}
+488 | {403.639716730026,-238.171790881127,-467.416652344398}
+489 | {102.819198484512,-28.2337285940254,199.513494729884}
+490 | {-534.968448925461,-154.668908660873,-431.786355519681}
+491 | {-268.801488941952,1011.0360953516,713.340221161693}
+492 | {612.854737665278,293.81451879556,-234.987108685438}
+493 | {868.39687689543,625.312718569827,-261.927933097171}
+494 | {-115.841061090447,145.44978761855,-629.960180769146}
+495 | {-742.716726862378,-110.944154329836,243.862343855349}
+496 | {-696.765398498195,513.604507873028,286.655758708002}
+497 | {-348.559217543603,417.992832411208,40.2621854458962}
+498 | {255.442132148284,-109.825759789379,-514.155335068317}
+499 | {240.668020929643,96.5495834371956,-193.529205276749}
+500 | {161.778520522418,493.088434044576,-415.078841990247}
+501 | {537.98282866316,-416.190864455458,405.687115218173}
+502 | {519.603416047613,30.4761366609198,-431.26608235468}
+503 | {379.990921318087,104.636868379266,565.272268175705}
+504 | {507.378152405232,537.168306367709,-646.204900798443}
+505 | {-827.448932617718,890.035438895891,594.183981629764}
+506 | {83.4049722059482,-862.535852280356,-408.232510081187}
+507 | {-88.5778015857495,-369.962514991262,60.5695210709452}
+508 | {781.529266195112,544.422561791657,-220.789887426653}
+509 | {768.33208089506,539.461342013196,-159.147489128926}
+510 | {242.566667445008,-193.691582116201,-673.81650400549}
+511 | {873.8500235162,642.0637612669,-95.3078907020974}
+512 | {500.47906726696,-42.5019390689841,-405.327641941716}
+513 | {-327.281911677433,-370.293512759609,696.43168522638}
+514 | {345.913420985134,47.6687163480349,-598.305161489094}
+515 | {162.823315690785,261.505008975881,181.135923306452}
+516 | {-667.951715009782,253.179770306784,-758.191348300609}
+517 | {-144.000312618501,-73.8748237749109,716.232140026597}
+518 | {-51.1239346934185,282.01033219148,-448.488895854982}
+519 | {716.442507138459,-353.272640285148,0.443485880870652}
+520 | {-1266.6496127886,-15.4913605859475,-1147.2759930605}
+521 | {-172.372321032924,-786.417609286374,608.963496121262}
+522 | {-229.223699918035,-684.823473695096,-532.459739108545}
+523 | {95.9540356019813,-968.302794194312,137.230124614101}
+524 | {644.338916226092,85.7056872485926,-353.626433977497}
+525 | {-1085.0326373211,485.199014490097,643.874796083576}
+526 | {305.972671419631,-523.323561583324,-538.083491743727}
+527 | {-1539.36566040091,368.706699637933,521.6721072456}
+528 | {-283.79977934535,-176.434892817145,-900.179421139601}
+529 | {-392.692039150683,-72.3569901055291,202.550453384228}
+530 | {476.253376286256,-144.448740562,-626.750123205185}
+531 | {121.504776321947,76.9880186866473,-123.922361323709}
+532 | {164.31720052523,-532.616811055046,-587.148108120281}
+533 | {189.21160216675,66.4197423705866,603.289923857094}
+534 | {620.334559053582,218.041698198341,-223.167941440271}
+535 | {-151.181758164764,-58.9804039718364,197.258913841692}
+536 | {541.904120938559,472.889622044987,-394.007556797846}
+537 | {102.068131652237,-380.50094602482,-205.112730226358}
+538 | {362.573820900631,228.483864225012,-604.170006608295}
+539 | {892.026322790356,622.444621838802,-70.78996087841}
+540 | {-245.491308288221,122.437932642964,-207.19244860805}
+541 | {455.21945753944,87.3752982445442,296.452478803704}
+542 | {189.210285587865,-827.273441606126,-516.926833028529}
+543 | {-1080.50965146605,400.010887102887,-161.403863951123}
+544 | {419.67278649724,279.050060280213,-600.145701661747}
+545 | {-635.403768062795,710.357930936592,295.55997918132}
+546 | {284.767887286605,399.97078868494,-609.565262903434}
+547 | {15.4369450522308,810.696689083784,346.147980467543}
+548 | {350.252936960078,-193.907568404985,-590.246954499399}
+549 | {-880.535141733092,275.790767050874,-376.306447239928}
+550 | {-143.624447544623,390.542314777442,-191.504791342555}
+551 | {-44.2351327705973,-799.988624102526,427.653063975339}
+552 | {-359.949943608878,434.261049905488,-761.041522532282}
+553 | {592.852886718428,616.724334583424,-375.859331006478}
+554 | {768.894080748696,683.047728137268,-186.417419854248}
+555 | {-932.417227755271,30.0983878468402,975.507600704357}
+556 | {-196.781214442567,272.187097606848,-820.059937123286}
+557 | {916.575634088825,331.944654183797,2.94581689808976}
+558 | {-211.699689990266,433.823723117561,-159.713657489908}
+559 | {519.56407444555,-16.4489680356125,217.180095325832}
+560 | {69.6819731557514,548.628981797799,-852.744844880397}
+561 | {716.796845017736,224.501803508143,58.6507020762773}
+562 | {-55.4873029253347,428.667926264752,-544.267802973001}
+563 | {42.1691649583717,-655.321187917958,442.111719673265}
+564 | {-114.923557727401,474.423304534672,-646.673741072495}
+565 | {-125.155294086934,-978.827178305164,225.037143184466}
+566 | {-283.797668333994,-241.229670724137,-943.620033014558}
+567 | {311.803888967382,-506.350589153477,498.592374114051}
+568 | {310.157702231061,-451.223824584861,-322.721772262693}
+569 | {73.172226020791,152.324006296347,-638.157632986994}
+570 | {73.2048252209965,-455.190348427268,-783.707221698963}
+571 | {-652.205359408259,-271.591926409946,-372.664778800866}
+572 | {168.630394011291,329.796662312575,-499.223812655727}
+573 | {902.585638275337,443.550682752982,174.906371961038}
+574 | {864.166281484128,538.882040992784,-241.260029947795}
+575 | {626.628828899153,347.093925018816,296.301832291863}
+576 | {356.184473030271,547.540311323295,-567.516424889957}
+577 | {434.175160350566,-352.936727898286,703.319606290386}
+578 | {-1179.33300404813,-72.9249566249252,-886.393226272171}
+579 | {14.4366417012208,58.2560787766943,-97.179167162361}
+580 | {319.365469319519,76.034719757136,-659.110975504371}
+581 | {168.067665284458,-698.35706526995,345.948025535119}
+582 | {119.79527723948,291.812910699053,-355.599233074834}
+583 | {-671.32415880786,-101.04836562843,375.269981539745}
+584 | {579.396901651801,62.0264748285509,-415.011790800176}
+585 | {241.259250503728,-134.321622200352,-199.885018060763}
+586 | {234.790251106492,-850.587058438898,-423.02582781811}
+587 | {402.300909938414,-66.5243376369359,-99.6767397592658}
+588 | {687.596000761602,526.495642838798,-151.187027928361}
+589 | {734.993041120701,493.081698503795,306.176167242505}
+590 | {362.497646598856,-292.746392935886,-751.895132621691}
+591 | {481.976228753779,-397.65977354182,-61.7242242520729}
+592 | {-780.849606659576,-6.55058676896115,-1026.60390190804}
+593 | {181.554573317411,-346.432972594644,135.995327805793}
+594 | {822.524571998913,532.479269835051,-227.39554858261}
+595 | {-26.1135089403867,387.467605133604,559.269025361976}
+596 | {638.215359001091,-195.763675261362,-334.062405460751}
+597 | {-1053.62194519563,-146.889657978386,566.123017500278}
+598 | {-47.0908770819274,476.926617435656,-838.351806127496}
+599 | {-516.408268920451,-166.287519847036,-716.48533236721}
+600 | {266.828765182438,-545.370380487119,-338.096407854331}
+601 | {784.812170844362,-221.534631768067,87.1486330234546}
+602 | {388.218868725628,-104.829926926614,-568.288701181723}
+603 | {-144.055382809268,799.623188763903,553.582513888885}
+604 | {-705.22746697173,252.154856527435,-993.137266274926}
+605 | {935.253861523358,256.737752022904,93.8523017887398}
+606 | {317.418671889213,-138.973266427214,-537.60563491324}
+607 | {9.98943341635767,-478.954820713277,316.059280490539}
+608 | {-136.498177249765,152.48287607055,-817.33346796983}
+609 | {-355.261578923076,-969.811576443126,643.170832468971}
+610 | {824.437684399933,602.482632546088,-255.1756670267}
+611 | {-72.9385008739971,-670.202440329946,233.109091415797}
+612 | {591.240557923025,290.729136389335,-197.369073840949}
+613 | {-1074.94603124509,58.2913119590264,429.287996929066}
+614 | {150.920765799806,-73.6431193715648,58.6089460822138}
+615 | {232.290394286259,-340.119423732257,-592.82850239833}
+616 | {109.653464304067,37.3029779953881,-419.243598328699}
+617 | {-652.504745214437,-987.526892705446,323.914882376124}
+618 | {264.615957112295,-472.904126366273,-399.750835650877}
+619 | {815.549180760655,148.08362510736,118.905440162934}
+620 | {-42.2369658686152,176.290856364818,-807.550749955292}
+621 | {-1305.46780276718,331.959554837604,1058.70300291939}
+622 | {397.139401171252,-452.116560520818,-410.163804552289}
+623 | {-811.438572693068,48.9950683406568,504.519394078102}
+624 | {-73.4798216205107,60.1879926733432,-1046.41562557193}
+625 | {427.416896622735,-572.772583952523,78.1069832603096}
+626 | {-151.426509894568,-14.3770624539062,-173.044994438471}
+627 | {-420.658631781462,-875.581235328708,-572.54625221803}
+628 | {170.425884573121,-346.466270310908,-253.854556756585}
+629 | {221.60371416113,305.692687248867,638.555373900102}
+630 | {-53.1605460066107,-186.793092079822,-232.220196593119}
+631 | {537.45725190819,309.891778396188,236.506277619151}
+632 | {409.472863726917,-72.3260802521748,-698.92456093397}
+633 | {-68.2226238081198,-825.259486138194,138.337246394617}
+634 | {-684.934478334922,83.4352251708351,-834.557557263317}
+635 | {756.687776375493,-61.9810724479211,195.300148360529}
+636 | {-18.1980211150009,-298.399790012271,-927.544605943432}
+637 | {589.899222804789,-521.15724346812,-111.779359536369}
+638 | {672.50092941365,564.632471347428,-141.919435493338}
+639 | {850.072560959019,179.958657275544,85.7574750717463}
+640 | {-1202.24227712896,213.36832280069,-698.745581906982}
+641 | {-183.866583149882,-619.207802320413,447.87514669701}
+642 | {765.930843449081,232.031668223761,-307.656667402113}
+643 | {-422.227382847039,382.409792839879,-755.339309453088}
+644 | {-310.872796387575,341.413463046036,-118.22262020165}
+645 | {847.859975754991,318.748242107191,-13.8509459045839}
+646 | {-268.792451270834,-39.5950404580584,152.133441084019}
+647 | {510.025687513682,864.236887871042,264.156891394987}
+648 | {364.29190490714,-306.549352604555,-367.667181633398}
+649 | {980.323805826002,482.727516410779,-50.8174976674377}
+650 | {-53.6085395989408,235.683783881355,-978.480310144991}
+651 | {606.807080667966,83.5420838482681,447.125989172952}
+652 | {133.36095080274,-502.239955876612,-645.385743063501}
+653 | {78.8677299944965,356.130556273136,-39.0674768056663}
+654 | {543.794216994294,126.84171828776,-425.249900318297}
+655 | {565.527784820136,-716.294427538868,173.578904473763}
+656 | {6.25408752941046,-718.077776940994,-666.503014358111}
+657 | {-1148.38202263509,33.4190780083834,-809.975305028368}
+658 | {-142.953067220135,137.596935126068,-642.88461331632}
+659 | {-212.3298852913,-8.99210991934292,197.29318808034}
+660 | {99.9197771633391,-80.1004027328411,-533.527819938508}
+661 | {290.890368407894,240.064301938402,121.287239561789}
+662 | {541.98446051682,-5.2586800218402,-402.055947256177}
+663 | {-676.02810341811,131.867540879266,112.162519576817}
+664 | {130.808634311517,-507.487002988064,-642.374475800659}
+665 | {230.511443444686,-475.989615308983,-78.6672792418933}
+666 | {-312.826818314322,88.5513216611647,-982.152462768792}
+667 | {-583.786134806007,-142.089948693085,-502.918921526684}
+668 | {-406.319373183606,24.0486825245026,-915.160311122739}
+669 | {-920.553065615433,79.0309534902843,721.788326979133}
+670 | {-1347.37298222037,423.414750857922,-668.297146789149}
+671 | {-687.112861773791,639.896116590061,206.990978842629}
+672 | {873.036351521083,631.924117317063,-417.413348435987}
+673 | {-157.929675154414,220.32998320163,-576.998603206917}
+674 | {-193.192084722822,144.301182380499,-875.534778194533}
+675 | {622.425970210891,573.360398504796,28.9427662213165}
+676 | {-225.789041133218,779.484688230156,243.825632340858}
+677 | {870.23020451346,517.378407842839,-93.3498265927583}
+678 | {-515.292383322542,-851.548304832859,259.778494416528}
+679 | {941.995812677439,270.522798292907,39.5112635374139}
+680 | {-514.475849467379,420.892107324055,-216.346757649015}
+681 | {77.8091171185693,-547.749875213624,-407.684655854756}
+682 | {-999.013057056375,-290.809640190755,-714.911869544184}
+683 | {343.931090477165,-218.681721463089,440.473475328689}
+684 | {52.8931788156299,-775.543035090581,-391.01255115995}
+685 | {-260.24437390078,275.141250622516,-587.08278394113}
+686 | {330.151255242658,695.85048680871,-670.728887945738}
+687 | {252.579864974913,-507.057264597949,581.153041533289}
+688 | {35.7077393105128,-845.186376441932,-184.623989603058}
+689 | {471.502381368152,382.226516888085,416.236017746721}
+690 | {-1352.6742744236,285.043215022361,-557.029447359714}
+691 | {-241.355218830733,-50.5611936819873,514.280315326515}
+692 | {836.944818583833,626.358814163905,-385.611731065728}
+693 | {-280.302346926537,-685.967164035308,663.905944365916}
+694 | {-52.7660340318387,148.269546359626,-325.585027466883}
+695 | {502.514274951011,135.897659564071,489.441550225534}
+696 | {-3.23854682060494,588.530864519724,-136.494564217061}
+697 | {330.527332906732,665.393326585891,-191.038661109675}
+698 | {-301.896721929371,-700.362043815007,-140.726279234646}
+699 | {849.34063463065,820.217015726992,-305.643780780746}
+700 | {-686.61349685413,257.518777413837,52.1904650850033}
+701 | {165.751209975237,-560.405630309918,-411.794888343739}
+702 | {-897.932437471349,-387.185026921975,-779.129775707054}
+703 | {-1181.85964399957,-36.9622139018686,35.3508143390579}
+704 | {-144.506348435805,-954.273219254946,-482.486557339571}
+705 | {-451.756404847454,-382.60111247033,-32.3856430898621}
+706 | {393.565542269047,582.761232010015,-747.281110333803}
+707 | {205.730676244875,-400.458764232173,580.859857848137}
+708 | {298.206411081284,-625.672285062076,-216.619405912087}
+709 | {498.863479062784,275.163704984379,462.253241420261}
+710 | {-1186.37217306509,82.3606492857581,-376.467796190978}
+711 | {845.02999773937,373.87265698297,10.3796397683702}
+712 | {795.04197516292,694.915027748931,-299.88696724297}
+713 | {-511.622098904875,316.846316270853,-1384.49445355605}
+714 | {-581.81089604332,357.259403713998,-957.772699715654}
+715 | {308.448199880885,652.345576911107,-33.1282016213211}
+716 | {-88.6037239955771,585.735601135617,-237.722614167953}
+717 | {-412.501356004621,240.133803027536,-836.395897149958}
+718 | {-616.84406667083,-985.056004919844,-662.414669713013}
+719 | {127.439524819779,-454.907582594598,752.271005359503}
+720 | {-1115.98999337498,385.788081909961,459.486723919306}
+721 | {615.950589945837,20.6099165311995,284.060935582237}
+722 | {-654.616709512482,-43.9888758160641,-971.276073443275}
+723 | {-483.363036514028,-225.901535084434,870.570080144211}
+724 | {15.5127891588682,-727.654464198775,-585.406431665874}
+725 | {-108.895403268249,-1002.81721594152,642.275809392752}
+726 | {262.702883934253,724.002541453453,-813.419207177602}
+727 | {257.737789859145,288.979192735909,687.435830001004}
+728 | {98.8219054912978,-806.398092393137,-266.701901658543}
+729 | {637.635535498514,-17.7691751827907,32.6506795138847}
+730 | {-617.156026381906,-754.558488512803,98.1616560565632}
+731 | {285.047854385652,-794.187493636105,90.5510094938665}
+732 | {83.2758119407126,550.529799987187,-280.905970549652}
+733 | {24.4925798814172,1227.35235066648,-38.4237799816534}
+734 | {-1152.92006498557,507.53052098479,-594.957470722601}
+735 | {-15.4945103647813,-5.77437150457105,503.793283640471}
+736 | {-368.193131051375,-111.508621653183,-964.369749111357}
+737 | {457.15100444115,299.279944999075,553.256854803106}
+738 | {-465.399915191364,150.427169904131,-1097.95507143817}
+739 | {772.687044980818,17.0199025757928,177.923243789027}
+740 | {-551.126454679043,-252.875869022386,-1062.41906777601}
+741 | {65.9393677048679,312.055119776043,334.452215630698}
+742 | {-16.3614135946173,-802.4918909632,-361.175794842372}
+743 | {-382.233558269935,-657.056744533811,-134.585071893798}
+744 | {-1401.1123493289,399.290432560378,-820.911944814856}
+745 | {743.902166961853,-376.714040322118,269.244510415971}
+746 | {-976.256716514129,181.839400567698,-1122.33831481136}
+747 | {729.962207685051,-121.25141589894,-78.4837511980305}
+748 | {801.689359824297,604.461825017797,-242.934405720971}
+749 | {-239.714128974731,197.488491360865,1003.01572679399}
+750 | {-121.902399042688,-521.194746597473,-500.249880848591}
+751 | {352.028771288608,-712.233479485391,433.021021277982}
+752 | {-522.211711994086,267.082447110575,-137.043444503691}
+753 | {-256.228167670777,914.120589620596,928.363155345899}
+754 | {186.111427787902,-593.492154603143,-704.515472245221}
+755 | {687.765442368681,-248.842544571159,101.105517234741}
+756 | {-7.42215276099878,-744.132553934954,-636.020896987028}
+757 | {-993.315463432948,-350.287272288958,-85.0065021188535}
+758 | {-704.341587412894,320.787633047779,-477.60988673104}
+759 | {-192.064982976327,-135.328070114122,341.026049507009}
+760 | {-555.972900391362,-182.67671553349,-975.641553501842}
+761 | {122.211910109399,-48.9825658356263,851.724538113818}
+762 | {72.2527997728746,264.748618302844,-514.781773594674}
+763 | {111.093738759592,-395.130232029224,-67.998855943799}
+764 | {-476.981054473196,-1142.41969610554,-133.222701166732}
+765 | {-118.162616796479,-707.521161723014,680.261680101437}
+766 | {791.028323185663,976.480079330705,-333.548621084679}
+767 | {-170.543885705758,421.096199519982,288.609974276743}
+768 | {-75.2824499514624,784.158847868556,66.8720078123507}
+769 | {-312.477081141435,529.778345922751,506.153960642743}
+770 | {-140.467271951247,275.892172821479,-698.739305199582}
+771 | {327.525759644703,-254.103115043571,-90.0624029970732}
+772 | {-202.273021165821,294.670621410991,-328.422396870613}
+773 | {-370.983717005777,-987.686513955396,-417.594575703646}
+774 | {386.639139253936,-842.887739495258,-33.7093551788008}
+775 | {-715.109031931664,389.232185871099,-817.910232558157}
+776 | {439.598558801408,63.4120835293936,-287.269430332954}
+777 | {-517.269564843596,-163.803517616261,-313.545369849965}
+778 | {-93.2423558504878,162.931117753995,-498.917189573652}
+779 | {431.466149138303,-210.753036330402,249.148236840926}
+780 | {755.738214073895,833.095167459982,-244.414770051082}
+781 | {865.668825803853,235.730351689529,8.22940980015358}
+782 | {-1331.45147377059,420.494408119913,-844.064968417156}
+783 | {92.8194184688646,-530.619250597068,-86.5579646450627}
+784 | {752.802841215897,803.482610490353,-237.917922864814}
+785 | {325.375964963828,270.670712052602,-60.9043182736513}
+786 | {-148.723674487471,-136.252224264115,-934.145292001353}
+787 | {473.173576488087,-602.785719296802,446.416142889058}
+788 | {-1279.12955693586,368.317395497577,-599.132199035168}
+789 | {78.4758787000064,-240.368252057123,-383.954951457365}
+790 | {-62.9989644262882,605.718701660693,-171.708857473058}
+791 | {-1055.90134525364,706.075357842101,262.254734291975}
+792 | {98.5705676011739,429.057476164339,-691.955630771352}
+793 | {17.7646160632793,413.968515813905,653.365092467441}
+794 | {-206.556254279997,-887.717201375341,-146.305604840786}
+795 | {-164.119805076113,228.689386401408,-772.219111291815}
+796 | {414.248920457798,-211.836657183096,-273.847838906537}
+797 | {338.623154294465,114.329759373197,-59.3491523129584}
+798 | {-86.9895503405777,-843.567781385826,-298.192245121943}
+799 | {424.706576259844,-768.389009352601,452.867425214894}
+800 | {-312.619017620356,225.162607884703,-296.576173741536}
+801 | {70.3225512804919,-746.928196744248,-26.1678616717768}
+802 | {130.801906106136,-7.41785193427119,-315.669873580279}
+803 | {-208.937565082164,-324.734430451578,-175.705864485773}
+804 | {269.209174957207,-413.31409696441,-379.32979391202}
+805 | {-146.440433429308,-746.566644697438,169.681141217744}
+806 | {-98.1865592862545,293.178114737507,-231.781813698896}
+807 | {55.2409071909099,-980.167902848414,209.647072309194}
+808 | {253.333886601357,313.824682925761,-85.5189109115365}
+809 | {506.226185285863,-40.1959802389049,464.373336772295}
+810 | {809.577892263547,861.45971643036,-215.839866118099}
+811 | {-127.501838813553,13.7606419092008,9.81166198036121}
+812 | {100.649385158365,535.402445153727,-297.696857369913}
+813 | {274.27129108479,-840.14978195816,246.183017694331}
+814 | {-46.2854105687034,-199.715277217276,-358.904601912}
+815 | {-317.612426215132,1013.27995833572,-195.972353125572}
+816 | {-592.669748005772,570.312717322712,-39.6696864647711}
+817 | {-183.32093275676,1.31431239038281,-432.592777277904}
+818 | {337.833279730974,528.211136254314,-623.328289554593}
+819 | {-735.395548062007,86.9211483220829,119.9815847401}
+820 | {65.8498260682315,-757.562619642572,2.39793582114106}
+821 | {-76.1270117276792,-704.420087008563,870.195269195728}
+822 | {673.153753463738,639.88193206633,-454.003688426263}
+823 | {734.963353258147,-34.0943104718832,-74.3105177344389}
+824 | {0.175356462046616,160.857688018079,-580.427435426889}
+825 | {670.296349323709,-417.040492813342,441.61009990097}
+826 | {-1056.41357483245,126.609182567558,-1312.0391473084}
+827 | {-424.180333321663,-643.25483835206,233.423144627609}
+828 | {466.898896326053,-420.08074245939,-579.250884083244}
+829 | {-74.7189473935087,15.034277211623,118.290747416653}
+830 | {-324.941424696505,137.908224611397,-1105.19424274368}
+831 | {-93.7013380576266,1114.26230555569,538.566075969567}
+832 | {-242.933097992659,262.532078370072,-527.82237064497}
+833 | {106.773554853935,400.863266839726,-32.8800302899553}
+834 | {810.486836855214,924.031574914851,-302.673020708143}
+835 | {194.118465939629,-646.730924029044,-190.873544856654}
+836 | {764.351771602829,871.295219387592,-256.666991280228}
+837 | {-338.12393509507,283.55802623005,311.726627547816}
+838 | {-466.40177076557,545.407979381489,-287.408360798957}
+839 | {968.504615554743,327.954827223635,31.7681441869798}
+840 | {391.707569107936,-532.380674206322,-275.86406390686}
+841 | {65.7021231446265,843.151077104383,559.67404061885}
+842 | {-567.177823811457,98.4930770461428,-875.98951292245}
+843 | {-240.118585971328,-300.838521730066,445.233509109663}
+844 | {418.201360145544,399.889097018551,-537.915494854176}
+845 | {-651.15101193177,150.372810155743,-564.664638540817}
+846 | {-330.583751126287,380.381840532071,-372.133597890078}
+847 | {-551.85634649832,154.054657421656,274.758631759727}
+848 | {-371.455048621029,-1102.69056338744,-430.917808715693}
+849 | {-130.47529038127,-394.838231074815,275.057811972018}
+850 | {-1060.26324641447,286.611706602539,-815.603364284879}
+851 | {62.1746241751155,-415.284270989495,-411.3867298436}
+852 | {-405.331291358957,-1075.09449084042,-148.726367084367}
+853 | {451.897766908103,125.320647911046,-739.30584198508}
+854 | {283.59004204622,-641.73340366849,-529.832523011986}
+855 | {-66.8087280568449,-840.483138170074,3.59682564469361}
+856 | {-263.963709783891,-997.851945054542,-210.813156805968}
+857 | {431.241623806907,283.397130411643,639.432948267423}
+858 | {-168.275986538782,505.612344383228,-553.775573458303}
+859 | {460.068764110312,154.42154916592,-100.25663764682}
+860 | {-1239.90429918057,-182.442148510248,-971.337478998153}
+861 | {-1218.44650382102,418.694861236223,-782.376852814258}
+862 | {-77.9133518017871,545.018440272665,-194.294222758201}
+863 | {229.294001177911,407.767136271776,26.0827164658991}
+864 | {412.914188924056,-83.6439104970493,1.54359214999199}
+865 | {790.718365913513,59.7384836228951,28.7154465281105}
+866 | {-5.48507964432512,291.654543970409,-811.098733254866}
+867 | {-165.919947526991,289.875243524126,292.364754837454}
+868 | {-167.375722479374,613.092100689566,-278.683456284648}
+869 | {341.718962754608,-548.242683325337,309.72519454169}
+870 | {-675.579998628862,333.467479469418,-646.112261936097}
+871 | {512.019063790617,-5.54559146504928,479.898401608288}
+872 | {836.651491393135,742.2026583897,-226.399785349779}
+873 | {-1108.11349044238,-147.062239095242,609.157329950429}
+874 | {-725.62791705556,72.1425852058642,-580.773478663935}
+875 | {-566.224825353205,1309.33346974762,594.256064249778}
+876 | {-126.79487393261,487.707611051203,731.290882155773}
+877 | {546.40534615193,213.385563958301,611.992597498893}
+878 | {-366.243550951903,-910.866981589853,159.443519482858}
+879 | {569.496838307133,149.961653997492,356.685198146741}
+880 | {507.716765551222,7.34702805600455,-355.359084765486}
+881 | {394.123751555144,-671.462063714369,-366.14868086596}
+882 | {-38.6488071929475,-154.286438280787,-880.504141292461}
+883 | {-589.557305555902,-512.229022221349,231.881620454893}
+884 | {-316.658657884754,-1013.33752998367,-6.41567293990953}
+885 | {841.851655717041,348.141475648719,-39.5611426262697}
+886 | {10.7432309312682,577.299299960637,-890.492189606733}
+887 | {-448.226731715486,706.879476744785,765.890898316826}
+888 | {-231.049430727141,-999.575788984889,-439.126313777873}
+889 | {513.233149842738,-557.336687924548,215.462476662483}
+890 | {-422.569036066866,-92.7411934690458,-1019.06978581727}
+891 | {-354.713381991472,593.353157871147,665.111737111218}
+892 | {829.459986815253,716.972654975171,-217.808641883368}
+893 | {659.464235144996,179.788802266547,-152.07574399922}
+894 | {-678.466506006046,-96.4996475975826,-1004.7768490759}
+895 | {319.837097695739,-359.256061382087,-183.770586453406}
+896 | {-980.392695556109,529.977607638414,593.525985290871}
+897 | {-281.215470593302,-761.594803054393,-582.170711897283}
+898 | {-144.252902903399,-827.468036490074,-427.449281249836}
+899 | {470.986531363633,-728.97316952651,18.0771610026469}
+900 | {567.403835752947,-76.2941909526237,-444.947095107438}
+901 | {706.979063088001,-122.990116697311,169.916170692656}
+902 | {-169.355845797254,-69.6519275347317,-935.629625907535}
+903 | {-1095.1881777081,-40.1076699026012,-28.4895306711101}
+904 | {-325.425033010691,-37.9773679477537,-1137.74021773175}
+905 | {121.144734585384,-973.551137332752,550.435525948308}
+906 | {764.358362457224,542.318707634552,-349.470962164379}
+907 | {69.5829273901727,-339.32260636416,452.352573883547}
+908 | {-753.559120382882,255.578645615065,-1100.81919687931}
+909 | {24.0516335176814,-633.271597059063,504.249377001862}
+910 | {-925.308321496954,816.479919860698,187.4210905229}
+911 | {-649.12384284262,110.462925525243,498.103866666845}
+912 | {53.3954042803347,-589.227962634671,-651.474095127237}
+913 | {61.5231729618868,42.7462095939035,204.207659943438}
+914 | {-109.593266644938,222.110495510898,-1121.18101363853}
+915 | {-368.777444792403,-850.791777272896,247.704255588821}
+916 | {609.904271854888,102.798032373011,-367.975183926057}
+917 | {-615.567316414998,347.783538492958,464.041756094257}
+918 | {-418.550308335065,-6.39308583179094,-942.942306601689}
+919 | {593.29782987191,7.14428259594825,-129.452424838944}
+920 | {766.282831800326,777.418680818332,-229.98945439678}
+921 | {910.871465093998,691.556240536251,-278.163103269148}
+922 | {363.756713117458,-103.646264143244,-629.877819008462}
+923 | {684.85729898907,99.9670312067313,-157.903680092398}
+924 | {-60.3358824480383,252.675035153166,-871.167796865807}
+925 | {-405.985302220507,575.81044293744,939.65456899225}
+926 | {-135.492919910059,169.769233366734,-644.970382666706}
+927 | {-612.826318036153,-618.352794635246,312.997041550876}
+928 | {-1150.29163503576,251.710635211856,-810.50261115671}
+929 | {203.904368544106,-704.306352186695,-195.539824379942}
+930 | {-211.543711079523,-759.836014744651,-389.405291990594}
+931 | {-561.969825889784,-920.051467685321,-247.450057350689}
+932 | {-228.056291514799,-134.809348798831,-829.240640688308}
+933 | {80.4099326615248,-585.118027311074,547.355539704245}
+934 | {407.895377434929,-337.774506937713,-230.945335874607}
+935 | {-251.725881007582,-450.146025443781,147.229648756053}
+936 | {443.595739248501,277.803085645711,-459.216384421689}
+937 | {768.266603164227,-179.654780125608,381.223855323766}
+938 | {166.465493793124,-591.925555021857,-543.426085751739}
+939 | {254.441140212917,1003.751364105,373.243684882407}
+940 | {502.105685500678,139.011252682558,-490.769761272359}
+941 | {-173.81499182828,-836.919014533662,230.344091140366}
+942 | {831.790172041626,508.080813733292,-41.0500303912222}
+943 | {-443.91709126997,-709.639129724882,-125.214642690726}
+944 | {8.5224803747858,19.6415647013969,-854.790815607621}
+945 | {-779.385468123768,-517.967219232449,-117.675516357504}
+946 | {393.199145881257,-591.144506833762,-481.538620710119}
+947 | {-419.171453919274,463.336246952451,-232.771166907718}
+948 | {562.330851272274,-21.8805888541834,-395.909966818373}
+949 | {508.714577280977,47.952079022558,-371.758551504665}
+950 | {-1168.98687052981,-177.933528879234,-1023.41481902235}
+951 | {230.705173537601,-542.41757534927,-101.617919339639}
+952 | {771.190402165315,643.151079698103,-173.623387841553}
+953 | {-703.379699970943,-157.293618533999,178.264693772853}
+954 | {-19.8131229865762,-37.4224645789017,607.509596117244}
+955 | {30.1536483473821,-820.597428853329,-512.659298974536}
+956 | {442.38951618994,55.6176726462379,-679.162185031076}
+957 | {-392.956221476116,823.541061780575,115.475096991448}
+958 | {-313.03909612127,27.8869991039227,-705.934651444036}
+959 | {-418.066387660349,133.826725499763,211.307502089971}
+960 | {673.057151986376,821.903487354505,-553.916942551824}
+961 | {-628.095524032583,183.871294980084,838.730359337866}
+962 | {787.6017509309,631.591626340498,-81.140155017458}
+963 | {456.240130031983,-788.155327129433,70.5708912206144}
+964 | {407.537028743856,488.887145778841,-701.490756029475}
+965 | {296.178266153442,415.296860360723,-540.197723478973}
+966 | {-454.486872247235,137.017262747375,-703.369464286931}
+967 | {12.0533578650523,-20.3279556880276,436.832189495814}
+968 | {-247.610468001537,-920.35322321143,-590.866819710663}
+969 | {622.537777303333,-360.736203031848,264.654366201194}
+970 | {-348.329085994667,-631.821666405665,-134.669630661862}
+971 | {-375.038237944054,495.640789505547,778.400549391501}
+972 | {428.593147056118,-378.744763158628,-332.730134314595}
+973 | {-468.388921819793,-361.345703589705,46.0774374659003}
+974 | {166.597168427257,132.896266718624,-839.80238946382}
+975 | {-32.6131648090045,70.054597422148,797.079234432721}
+976 | {-404.939656433141,935.044983762568,429.472443689896}
+977 | {51.2459618889678,36.4230119431423,58.7371984585452}
+978 | {237.03156256896,52.9828961935876,-709.931077483125}
+979 | {729.431809942643,54.8817088875761,187.494175010928}
+980 | {-544.166598323061,60.6414836687122,-1017.20817237116}
+981 | {611.011402727611,-315.690616609018,155.838302306684}
+982 | {-410.903183807051,-817.431881448712,-498.941051349443}
+983 | {584.942305350026,436.336379432393,140.18491884502}
+984 | {-62.2576273119263,-43.2935301637635,688.864964048942}
+985 | {-443.659607538172,45.6100114145606,604.826905400621}
+986 | {469.538524301448,33.8965252398074,-472.681333118967}
+987 | {-739.771306341606,-628.667466347046,154.43004104212}
+988 | {6.16975042506824,-814.046180611434,-564.054638448502}
+989 | {-412.718322652751,-810.953990028575,111.578197740358}
+990 | {-371.788909598942,131.714123700478,-899.574111680826}
+991 | {-496.135296949346,-830.199985428607,233.364349557065}
+992 | {-432.547935230597,-506.358842797757,265.069576509392}
+993 | {-287.340085685258,817.939734530848,249.620152949832}
+994 | {794.082931481233,529.711329496276,-43.9666712275483}
+995 | {-51.9104170952357,-938.769614779545,235.101660342489}
+996 | {-182.538603056643,-655.29591247686,-311.602065173997}
+997 | {155.382900972205,130.042892062227,-22.6827886036227}
+998 | {-524.406687025992,-14.7069741427976,-1160.50595918993}
+999 | {-255.495117367138,744.521374636333,446.551897876606}
+1000 | {306.590358490976,149.581073128642,-724.558878908178}
+\.
+
+DROP TABLE IF EXISTS dbscan_result, dbscan_result_summary;
+SELECT dbscan('dbscan_kd_test_data','dbscan_result','row_id','row_vec',50, 3,
'dist_norm2', 'br');
+
+DROP TABLE IF EXISTS dbscan_result_kd, dbscan_result_kd_summary;
+SELECT dbscan('dbscan_kd_test_data','dbscan_result_kd','row_id','row_vec',50,
3, 'dist_norm2', 'kd', 2);
+
+SELECT assert(count(row_id) = 50 AND count(distinct cluster_id) = 11,
'Incorrect cluster counts for brute')
+FROM dbscan_result;
+
+SELECT assert(count(row_id) = 50 AND count(distinct cluster_id) = 11,
'Incorrect cluster counts for kd')
+FROM dbscan_result_kd;
+
+CREATE TABLE temp_result AS
+SELECT row_id
+FROM dbscan_result
+WHERE cluster_id = (SELECT cluster_id FROM dbscan_result WHERE row_id = 4);
+
+SELECT assert(count(*) = 6, 'Clusters do not match')
+FROM dbscan_result_kd
+WHERE cluster_id = (SELECT cluster_id FROM dbscan_result_kd WHERE row_id = 4)
+ AND row_id IN (SELECT row_id FROM temp_result);
diff --git
a/src/ports/postgres/modules/dbscan/test/unit_tests/test_dbscan.py_in
b/src/ports/postgres/modules/dbscan/test/unit_tests/test_dbscan.py_in
index e04de94..1aa0681 100644
--- a/src/ports/postgres/modules/dbscan/test/unit_tests/test_dbscan.py_in
+++ b/src/ports/postgres/modules/dbscan/test/unit_tests/test_dbscan.py_in
@@ -55,7 +55,8 @@ class DBSCANTestCase(unittest.TestCase):
'eps' : 20,
'min_samples' : 4,
'metric' : 'squared_dist_norm2',
- 'algorithm' : 'brute'
+ 'algorithm' : 'brute',
+ 'depth': 2
}
import dbscan.dbscan
self.module = dbscan.dbscan
