KDTreeTable

require.mx('mxjs/base/algorithms/kdtree.js');

This library provides k-d tree functionality for searching tables. The dimensions of the k-d trees are table columns. The k-d tree can then be searched based on those dimensions. Compared to the built-in k-d tree, the search functions provided by this k-d tree require the caller to provide a function that determines the distances between two points in the k-dimensional space. That is, you provide the definition of distance when performing searches such as findNearestNeighbour or findAtLeastXWithinRange.

QuickRef

Status	Name
	KDTree generateKDTree ( Object options ) Construct a new KDTree. The options object may use the following properties: inputTable {Table} the table that the k-d tree will index. ID {String} the name of the identifier column in the input table. dimensions {Object} dimensions to use for the k-d tree. dimensionOrder {Array} (optional).
	KDTree generateKDTreeTables ( Object options ) Construct a new KDTree, and write that tree to a table. The options object may use the following properties: indicesTable {Table} the table to write the k-d tree to. inputTable {Table} the table that the k-d tree will index. ID {String} the name of the identifier column in the input table. dimensions {Object} dimensions to use for the k-d tree. dimensionOrder {Array} (optional).
	String getDescriptionFromSettings ( String storedSettings ) Get a description of the KDTree described by stored settings.
	KDTree readKDTreeTables ( Table KDTreeTable, Table IndexedTable, String StoredSettings ) Create a KDTree from a given k-d tree table.

---

Library Functions

---

Category: Examples

These k-d trees can also be saved into tables, which can then be used to search the k-d tree from other locations (e.g. a k-d tree can be generated once, and searched from multiple table calculations).

A k-d tree storage Table must have the following:

• StoredSettings: OUT Value (Text)
• ID: OUT Column (IDs)
• Order: OUT Column (Numbers)
• SplitValue: OUT Column (Numbers)

When the k-d tree storage Table is read from another table calculation, it must have no Filter, no Group By, and must be ordered by the Order column in the storage table, as IN Column Ascending: Numbers. The following columns must be readable:

• ID
• SplitValue

The StoredSettings Value must also be provided to the read function (see readKDTreeTables).

Generate a k-d tree:

 const LibKDTreeTable = require.mx('mxjs/base/algorithms/kdtree.js');

 const KDTree = LibKDTreeTable.generateKDTree({
   // Input table (to index/search)
   "inputTable": Events,

   // ID field of the input table
   "ID": "id",

   // Dimensions to use (the keys can be anything you like).
   // Point data (i.e. location in this case) is handled automatically (all three
   // dimensions are used internally).
   "dimensions": {
     "time": "read_date",
     "location": "read_location",
     "localMagnitude": "read_localMagnitude"
   }
 });

Save a k-d tree to table:

KDTree.writeToTable(KDTreeIndices);

Get a description of a stored k-d tree:

 // If the k-d tree storage table is named KDTreeIndices

 const LibKDTreeTable = require.mx('mxjs/base/algorithms/kdtree.js');

 // The stored settings (saved as a Value in KDTreeIndices) must be read by
 // attaching them to an IN Value Bunch. It doesn't matter what the name is,
 // you just need to pass the value to the function below.
 const Settings = KDTreeIndicesValues.read_StoredSettings();
 const Description = LibKDTreeTable.getDescriptionFromSettings(Settings);
 print(Description);

Read from a k-d tree table:

 // If the k-d tree storage table is named KDTreeIndices

 const LibKDTreeTable = require.mx('mxjs/base/algorithms/kdtree.js');

 // The stored settings (saved as a Value in KDTreeIndices) must be read by
 // attaching them to an IN Value Bunch. It doesn't matter what the name is,
 // you just need to pass the value to the readKDTreeTables function (below).
 const Settings = KDTreeIndicesValues.read_StoredSettings();

 // Events is the same table that was used when the k-d tree was generated in the
 // example above. It does not need to be in the same order. However, all rows
 // that were present originally must still be present when the k-d tree is read
 // (it's OK if there are additional rows).
 const KDTree = LibKDTreeTable.readKDTreeTables(KDTreeIndices, Events, Settings);

Search the k-d tree:

 // If the k-d tree storage table is named KDTreeIndices

 // Define a function that gives the distance between two k-dimension points.
 // Anything that produces a value >= 0 is OK. You do not need to use all of the
 // dimensions that the k-d tree uses.
 const distanceFn = function(a, b) {
   var timeDelta = Math.abs(b.time-a.time);
   var distance = glMatrix.vec3.distance(a.location, b.location);
   // ignoring localMagnitude
   return (distance/100) + (timeDelta)/1234;
 };

 // Define the centre point to search from. All dimensions MUST be specified.
 const searchPoint = {
   "location": [-6295.24, 2925.71, -1037.15],
   "time": 3283779811001,
   "localMagnitude": 0.0401228
 };


 // Find the index of the single row closest to the search point.
 const closestIdx = KDTree.findNearestNeighbour(distanceFn, searchPoint);


 // Find all points within a specified distance (10) from the centre point.
 // The points are returned in ascending order of distance (i.e. closest first).
 const radius = 10;
 const inRange = KDTree.findAllWithinRange(distanceFn, searchPoint, radius);

 for (let i = 0; i < inRange.indices.length; ++i) {
   print("row " + inRange.indices[i] + " at distance " + inRange.distances[i]);
 }


 // Find the closest 20 (Xnum) points within distance 50 (Rmax) of searchPoint.
 // If there are more than 20 points within 10 (Rmin), find all of them.
 // The points are returned in ascending order of distance (i.e. closest first).
 const Rmin = 10;
 const Rmax = 50;
 const Xnum = 20;
 const friends = KDTree.findAtLeastXWithinRange(distanceFn, searchPoint, Rmin, Rmax, Xnum);

 for (let i = 0; i < friends.indices.length; ++i) {
   print("row " + friends.indices[i] + " at distance " + friends.distances[i]);
 }


 // Find all points in a hyperrectangle (in an unspecified order).
 // Note that no distance function is used.
 // Each dimension must specify a [minimum, maximum].
 const hyperrectangle = {
   "location": [[-6400, 2600, -1200], [-6280, 3000, -1000]],
   "time": [0, 3283779811001],
   "localMagnitude": [0, 1]
 };

 const foundIndices = KDTree.listNodesInHyperrectangle(hyperrectangle);

 for (let i = 0; i < foundIndices.length; ++i) {
   print("row " + i + " is in the hyperrectangle");
 }

---

Class: KDTree

A k-d tree that indexes a table.

Status	Name
	Object findAllWithinRange ( Function distanceFn, Object centrePoint, Number radius, Object ↑results, Function predicateFn ) Find all points (rows) that are within the distance radius from centrePoint (according to the given distance function).
	Object findAtLeastXWithinRange ( Function distanceFn, Object centrePoint, Number Rmin, Number Rmax, Number Xnum, Object ↑results, Function predicateFn ) Find all points (rows) that are within the distance Rmin from centrePoint (according to the given distance function). If there are less than Xnum points found, then continue finding the next closest point until either there are Xnum points found, or the next closest point would be beyond Rmax.
	Number findNearestNeighbour ( Function ↓distanceFn, Object ↓centrePoint, Array ↑bestDistance ) Find the single closest point (row) to the given centrePoint, according to the given distance function.
	String getDescription ( ) Get a description of this KDTree (including the name of the ID field, the dimensions that it uses, and examples of search points and distance functions).
	Array listNodesInHyperrectangle ( Object Hyperrectangle ) Find all points (rows) that lie within a hyperrectangle (a k-orthotope).
	writeToTable ( Table indicesTable ) Write this k-d tree into a table, so that it can be used in other table calculations.

---