Case 1:14-cv-02396-PGG-SN Document 239-15 Filed 11/12/20 Page 1 of 12
`
`
`
`
`
`
`
`
`Exhibit 33
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Case 1:14-cv-02396-PGG-SN Document 239-15 Filed 11/12/20 Page 2 of 12
`
`h41166
`s 00000/00045/00437
`d D 1.2 00/07/26 15:47:10 erling 2 1
`c cleanup
`e
`s 00482/00000/00000
`d D 1.1 00/07/26 15:36:26 erling 1 0
`c date and time created 00/07/26 15:36:26 by erling
`e
`
`U
`f e 0
`t
`T
`I1
`
`//
`/1 KD is a library for Approximate Nearest Neighbor searching,
`// based on the use of standard and priority search in kd-trees
`// and balanced box-decomposition (bbd) trees. Here are some
`/1 references:
`//
`/1 kd-trees:
`/1 Friedman, Bentley, and Finkel, "An algorithm for finding
`// best matches in logarithmic expected time," ACM
`// Transactions on Mathematical Software, 3(3):209-226, 1977.
`//
`// priority search in kd-trees:
`// Arya and Mount, "Algorithms for fast vector quantization,"
`/1 Proc. of DCC '93: Data Compression Conference, eds. J. A.
`// Storer and M. Cohn, IEEE Press, 1993, 381-390.
`/1
`/1 approximate nearest neighbor search and bbd trees:
`// Arya, Mount, Netanyahu, Silverman, and Wu, "An optimal
`// algorithm for approximate nearest neighbor searching,"
`// 5th Ann. ACM-SIAM Symposium on Discrete Algorithms,
`// 1994, 573-582.
`//
`
`
`
`#ifndef KD_H
`#define KD_H
`
`/I
`// basic includes
`//
`#include <stdlib.h>
`#include <stdio.h>
`#include <math.h>
`#ifdef unix
`#include <values.h>
`
`// standard libs
`// standard I/O (for NULL)
`// math includes
`
`// special values
`
`Exhibit /
`Name: 001--
`C.RR, CCP, CSR No, 9667
`
`Date: 7
`Lana L Loper,
`
`Confidential - Outside Counsel Only
`
`AUDMAG01085773
`
`

`

`Case 1:14-cv-02396-PGG-SN Document 239-15 Filed 11/12/20 Page 3 of 12
`
`#else
`#define MAXFLOAT HUGE_VAL
`#endif
`#include "mfErrors.h"
`
`#define KDversion "0.1" // KD version number
`
`//
`// KDbool
`// This is a simple boolean type. Although ANSI C++ is supposed
`// to support the type bool, many compilers do not have it.
`/./
`
`
`
`
`// KD boolean type (non ANSI C++)
`typedef enum
`{
`
`KDfalse = 0,
`KDtrue = 1
`} KDbool;
`
`
`
`/1
`// Basic Types: KDcoord, KDdist, KDidx
`// KDcoord and KDdist are the types used for representing
`// point coordinates and distances. They can be modified by the
`user, with some care. It is assumed that they are both numeric
`// types, and that KDdist is generally of an equal or higher type
`/1 from KDcoord. A variable of type KDdist should be large
`/1 enough to store the sum of squared components of a variable
`// of type KDcoord for the number of dimensions needed in the
`// application. For example, the following combinations are
`// legal:
`//
`/I KDcoord KDdist
`//
`// short short, int, long, float, double
`// int int, long, float, double
`// long long, float, double
`// float float, double
`// double double
`//
`// It is the user's responsibility to make sure that overflow does
`/1 not occur in distance calculation.
`//
`// The code assumes that there is an infinite distance, KD_DIST_INF
`// (as large as any legal distance). Possible values are given below:
`//
`
`Examples:
`//
`
`KDdist: double, float, long, int, short
`//
`
`KD_DIST_INF: MAXDOUBLE, MAXFLOAT, MAXLONG, MAXINT, MAXSHORT
`//
`
`P
`
`Confidential - Outside Counsel Only
`
`AUDMAG01085774
`
`

`

`Case 1:14-cv-02396-PGG-SN Document 239-15 Filed 11/12/20 Page 4 of 12
`
`/1
`//
`// KDidx is a point index. When the data structure is built,
`// the points are given as an array. Nearest neighbor results are
`// returned as an index into this array. To make it clearer when
`// this is happening, we define the integer type KDidx.
`//
`//
`
`
`
`typedef float KDcoord; /* coordinate data type */
`typedef float KDdist, /* distance data type */
`typedef int KDidx; /* point index */
`
`/* largest possible distance */
`/*const KDdistKD_DIST_INF = MAXFLOAT;*/
`#define KD _ DIST_ INF (KDdist) MAXFLOAT
`//
`/I Self match?
`// In some applications, the nearest neighbor of a point is not
`// allowed to be the point itself. This occurs, for example, when
`// computing all nearest neighbors in a set. By setting the
`// parameter KD_ALLOW_SELF_MATCH to KDfalse, the nearest neighbor
`// is the closest point whose distance from the query point is
`/1 strictly positive.
`//
`
`
`
`
`
`/*const KDbool KD_ALLOW_SELF_MATCH = KDtrue;*/
`#define KD_ALLOW_SELF_MATCH (KDbool) KDtrue
`
`
`
`//
`// Norms and metrics:
`// KD supports any Minkowski norm for defining distance. In
`/1 particular, for any p >= 1, the L_p Minkowski norm defines the
`// length of a d-vector (v0, v1, ..., v(d-1)) to be
`//
`// (1vOlAp + 1v1lAp + + lv(d-1)1Ap)^(1/p),
`//
`// (where A denotes exponentiation, and 1.1 denotes absolute
`/1 value). The distance between two points is defined to be
`/1 the norm of the vector joining them. Some common distance
`// metrics include
`//
`// Euclidean metric p = 2
`// Manhattan metric p = 1
`// Max metric p = infinity
`//
`// In the case of the max metric, the norm is computed by
`// taking the maxima of the absolute values of the components.
`// KD is highly "coordinate-based" and does not support general
`
`Confidential - Outside Counsel Only
`
`AUDMAG01085775
`
`

`

`Case 1:14-cv-02396-PGG-SN Document 239-15 Filed 11/12/20 Page 5 of 12
`
`/1 distances functions (e.g. those obeying just the triangle
`// inequality). It also does not support distance functions
`// based on inner-products.
`/1
`// For the purpose of computing nearest neighbors, it is not
`// necessary to compute the final power (1/p). Thus the only
`// component that is used by the program is lv(i)IAP.
`//
`// KD parameterizes the distance computation through the following
`// macros. (Macros are used rather than procedures for efficiency.)
`// Recall that the distance between two points is given by the length
`// of the vector joining them, and the length or norm of a vector v
`// is given by formula:
`//
`// Iv' = ROOT(POW(v0) # POW(v1) # # POW(v(d-1)))
`//
`// where ROOT, POW are unary functions and # is an associative and
`// commutative binary operator satisfying:
`//
`// POW: coord --> dist
`// ** #: dist x dist --> dist
`// ROOT:dist (>0) --> double
`//
`/I For early termination in distance calculation (partial distance
`// calculation) we assume that POW and # together are monotonically
`// increasing on sequences of arguments, meaning that for all
`// v0..vk and y:
`//
`// POW(v0) #...# POW(vk) <= (POW(v0) #...# POW(vk)) # POW(y).
`/1
`// Due to the use of incremental distance calculations in the code
`// for searching k-d trees, we assume that there is an incremental
`II update function D1FF(x,y) for #, such that if:
`/1
`// s=x0#. #xi#. #xk
`//
`// then if s' is s with xi replaced by y, that is,
`//
`// s'=x0#...#y#...#xk
`//
`// can be computed by:
`//
`// s' = s # DIFF(xi,y).
`//
`// Thus, if # is + then DIFF(xi,y) is (yi-x). For the L_infinity
`// norm we make use of the fact that in the program this function
`// is only invoked when y > xi, and hence DIFF(xi,y)=y.
`//
`// Finally, for approximate nearest neighbor queries we assume
`
`Confidential - Outside Counsel Only
`
`AUDMAG01085776
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Case 1:14-cv-02396-PGG-SN Document 239-15 Filed 11/12/20 Page 6 of 12
`
`II that POW and ROOT are related such that
`//
`/I v*ROOT(x) = ROOT(POW(v)*x)
`//
`// Here are the values for the various Minkowski norms:
`//
`// L_p: p even: p odd:
`/1
`. // POW(v) = v^p POW(v) = IvIAp
`// ROOT(x) = )(Tip) ROOT(x) = x^(1 /p)
`//
`// DIFF(x,y) = y - x DIFF(x,y) = y - x
`//
`I/ L_inf:
`// POW(v) = Zvi
`// ROOT(x) = x
`// # = max
`/1 DIFF(x,y) = y
`//
`// By default the Euclidean norm is assumed. To change the norm,
`uncomment the appropriate set of macros below.
`
`I/
`//
`
`
`
`ll Use the following for the Euclidean norm
`//
`
`#define KD_POW(v) ((v)*(v))
`#define KD_ROOT(x) sqrt(x)
`#define KD_SUM(x,y) ((x) (y))
`#define KD_DIFF(x,y) ((y) - (x))
`/I
`// Use the following for the L_1 (Manhattan) norm
`//
`
`// #define KD_POW(v) fabs(v)
`// #define KD_ROOT(x) (x)
`// #define KD_SUM(x,y) ((x) (y))
`// #define KD_DIFF(x,y) ((y) - (x))
`
`/1 Use the following for a general L_p norm
`//
`
`/1 #define KD_POW(v) pow(fabs(v),p)
`//#define KD_ROOT(x) pow(fabs(x),1/p)
`//#define KD_SUM(x,y) ((x) (y))
`#define KD_DIFF(x,y) ((y) - (x))
`
`Confidential - Outside Counsel Only
`
`AUDMAG01085777
`
`

`

`Case 1:14-cv-02396-PGG-SN Document 239-15 Filed 11/12/20 Page 7 of 12
`
`II Use the following for the Linfinity (Max) norm
`//
`
`
`// #define KD_POW(v)
`
`// #define KD_ROOT(x)
`
`// #define KD_SUM(x,y)
`// #define KD_DIFF(x,y) (y)
`
`fabs(v)
`(x)
`((x) > (y) ‘? (x) : (y))
`
`
`
`//
`// Array types
`//
`/I KDpoint:
`// A point is represented as a (dimensionless) vector of
`// coordinates, that is, as a pointer to KDcoord. It is the
`// user's responsibility to be sure that each such vector has
`// been allocated with enough components. Because only
`// pointers are stored, the values should not be altered
`// through the lifetime of the nearest neighbor data structure.
`// KDpointArray is a dimensionless array of KDpoint.
`// KDdistArray is a dimensionless array of KDdist.
`// KDidxArray is a dimensionless array of KDidx. This is used for
`// storing buckets of points in the search trees, and for returning
`// the results of k nearest neighbor queries.
`//
`
`
`
`typedef KDcoord *KDpoint;
`typedef KDpoint *KDpointArray;
`typedef KDdist *KDdistArray;
`typedef KDidx *KDidxArray,
`
`// a point
`// an array of points
`// an array of distances
`// an array of point indices
`
`
`
`/1
`// Point operations:
`/1
`/1 annDist() computes the (squared) distance between a pair
`// of points. Distance calculations for queries are NOT
`// performed using this routine (for reasons of efficiency).
`//
`// Because points (somewhat like strings in C) are stored
`// as pointers. Consequently, creating and destroying
`// copies of points may require storage allocation. These
`II procedures do this.
`//
`// annAllocPt() and annDeallocPt() allocate a deallocate
`// storage for a single point, and return a pointer to it.
`II The argument to AllocPt() is used to initialize all
`// components.
`//
`// annAllocPts() allocates an array of points as well a place
`II to store their coordinates, and initializes the points to
`// point to their respective coordinates. It allocates point
`
`Confidential - Outside Counsel Only
`
`AUDMAG01085778
`
`

`

`Case 1:14-cv-02396-PGG-SN Document 239-15 Filed 11/12/20 Page 8 of 12
`
`storage in a contiguous block large enough to store all the
`/I points. It performs no initialization.
`//
`// annDeallocPt() deallocates a point allocated by annAllocPt().
`/1 annDeallocPts() deallocates points allocated by annAllocPts().
`/1
`/1 annCopyPt() allocates space and makes a copy of a given point.
`//
`
`
`KDdist annDist(
`int dim,
`KDpoint p,
`KDpoint q);
`
`KDpoint annAllocPt(
`int dim,
`KDcoord c);
`
`KDpointArray annAllocPts(
`int n,
`int dim);
`
`void annDeallocPt(
`KDpoint *0;
`
`// dimension of space
`// points
`
`// dimension
`// coordinate value (all equal)
`
`// number of points
`// dimension
`
`// deallocate 1 point
`
`void annDeallocPts(
`KDpointArray *pa); // point array
`
`KDpoint annCopyPt( // copy point
`int dim, // dimension
`KDpoint source); // point to copy
`
`
`//
`// Generic approximate nearest neighbor search structure.
`// KD supports a few different data structures for
`/1 approximate nearest neighbor searching. All these
`// data structures at a minimum support single and k-nearest
`// neighbor queries described here. The nearest neighbor
`// query returns an integer identifier and the distance
`1/ to the nearest neighbor(s).
`//
`
`
`
`//
`/1 kd-tree:
`// The basic search data structure supported by ann is a kd-tree.
`// The tree basically consists of a root pointer. We also store
`// the dimension of the space (since it is needed for many routines
`I/ that access the structure). The number of data points and the
`// bucket size are stored, but they are mostly information items,
`
`
`
`Confidential - Outside Counsel Only
`
`AUDMAG01085779
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Case 1:14-cv-02396-PGG-SN Document 239-15 Filed 11/12/20 Page 9 of 12
`
`// and do not affect the data structure's function. We also store
`// the bounding box for the point set.
`//
`// kd-trees support two searching algorithms, standard search
`// (which searches nodes in tree traversal order) and priority
`// search (which searches nodes in order of increasing distance
`// from the query point). For many distributions the standard
`/1 search seems to work just fine, but priority search is safer
`// for worst-case performance.
`H
`// The nearest neighbor index returned is the index in the
`// array pa[] which is passed to the constructor.
`//
`//
`
`
`
`I/
`// Some types and objects used by kd-tree functions
`II See kd_tree.h and kd_tree.cc for definitions
`
`//
`// kd-tree splitting rules
`kd-trees supports a collection of different splitting rules.
`II
`In addition to the standard kd-tree splitting rule proposed
`II
`by Friedman, Bentley, and Finkel, we have introduced a
`H
`number of other splitting rules, which seem to perform
`/I
`as well or better (for the distributions we have tested).
`II
`II
`/I
`II
`II
`11
`II
`II
`II
`
`The splitting methods given below allow the user to tailor
`the data structure to the particular data set. They are
`are described in greater details in the kd_split.cc source
`file. The method KD_KD_SUGGEST is the method chosen (rather
`subjectively) by the implementors as the one giving the
`fastest performance, and is the default splitting method.
`
`/I
`D2
`// Brute-force nearest neighbor search:
`// For the sake of comparison and validation we include a
`// trivial brute-force nearest neighbor algorithm. It is
`II simple but inefficient. The value of epsilon is ignored
`// when performing nearest neighbor calculations, since all
`// are done exactly. This data structure is very slow, and
`// should not be used for most applications. It was implemented
`// by the authors to help validate the more complex data
`// structures below.
`//
`// The nearest neighbor index returned is the index in the
`// array pa[] which is passed to the constructor.
`
`Confidential - Outside Counsel Only
`
`AUDMAG01085780
`
`

`

`Case 1:14-cv-02396-PGG-SN Document 239-15 Filed 11/12/20 Page 10 of 12
`
`/1
`
`typedef struct ann_brute_force
`{
`
`int dim; // dimension
`int n_pts; II number of points
`KDpointArray pts; // point array
`KDbruteForce;
`
`/*
`* annkBFS
`* q query point
`* k number of near neighbors to return
`* nn_idx nearest neighbor array (returned)
`* dd dist to near neighbors (returned)
`* eps error bound
`
`MFError /*int*/ annkBFS(KDbruteForce* pBF, KDpoint q, int k,
`KDidxArray nn_idx, KDdistArray dd, double eps);
`
`/1
`
`E2
`// Orthogonal (axis aligned) rectangle
`/I Orthogonal rectangles are represented by two points, one
`// for the lower left corner (min coordinates) and the other
`// for the upper right corner (max coordinates).
`//
`// The constructor initializes from either a pair of coordinates,
`/1 pair of points, or another rectangle. Note that all constructors
`// allocate new point storage. The destructor deallocates this
`II storage.
`//
`/1 BEWARE: Orthogonal rectangles should be passed ONLY BY REFERENCE.
`/1 (C++'s default copy constructor will not allocate new point
`// storage, then on return the destructor free's storage, and then
`// you get into big trouble in the calling procedure.)
`//
`
`
`typedef struct ann_north_rect
`{
`
`KDpoint lo; /1 rectangle lower bounds
`KDpoint hi; /1 rectangle upper bounds
`} NorthRect;
`
`NorthRect* NorthRectCreateEmpty(int dd);
`NorthRect* NorthRectCreateFromCoords(int dd, KDcoord I, KDcoord h);
`NorthRect* NorthRectCreateFromRect(int dd, NorthRect* pR);
`NorthRect* NorthRectCreateFromPoints(int dd, KDpoint I, KDpoint h);
`void NorthRectDestroy(NorthRect* pNR);
`
`Confidential - Outside Counsel Only
`
`AUDMAG01085781
`
`

`

`Case 1:14-cv-02396-PGG-SN Document 239-15 Filed 11/12/20 Page 11 of 12
`
`void annAssignRect( // assign one rect to another
`int dim, // dimension (both must be same)
`NorthRect *dest, // destination (modified)
`const NorthRect *source); // source
`
`#include "kd_tree.h"
`
`typedef struct kd_tree
`{
`
`int dim; /* dimension of space */
`int n_pts; /* number of points in tree */
`int bkt_size; /* bucket size */
`KDpointArray pts; /* the points */
`KDidxArray pidx; /* point indices (to pts) */
`/*KDkd_ptr root; */ /* root of kd-tree */
`KDkd_node* root; I* root of kd-tree*/
`KDpoint bnd_box_lo; /* bounding box low point */
`KDpoint bnd_box_hi; /* bounding box high point */
`} KDTree;
`
`/*
`* Was KDkd_tree() construct 1
`KDTree* KDTreeCreateEmpty(int n, int dd, int bs r= 1 (default)*/);
`
`*1
`
`/*
`* Was KDkd_tree() construct 2
`*/
`KDTree* KDTreeCreateFromPoints(KDpointArray aPoints, int n,
`int dd, int bs r= 1 (default)*/);
`
`MFError annkTreeSearch(KDTree* pKDT, KDpoint q, int k,
`KDidxArray nn_idx, KDdistArray dd, double eps);
`
`void KDTreeDestroy(KDTree* pKDT);
`
`D2
`typedef struct point set
`{
`short utype; /* discriminator */
`union
`{
`
`kdTree;
`
`KDTree
`KDbruteForce bfs;
`} uval;
`} KDPointSet;
`E2
`
`Confidential - Outside Counsel Only
`
`AUDMAG01085782
`
`

`

`Case 1:14-cv-02396-PGG-SN Document 239-15 Filed 11/12/20 Page 12 of 12
`
`D2
`
`E2
`II
`// Other functions
`//
`
`void annMaxPtsVisit( // limit max. pts to visit in search
`int maxPts); // the limit
`
`#endif
`E1
`
`Confidential - Outside Counsel Only
`
`AUDMAG01085783
`
`