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

`

`Case 1:14-cv-02396-PGG-SN Document 239-16 Filed 11/12/20 Page 2 of 7
`
`h47185
`s 00006/00024/00234
`d D 1.2 00/07/26 15:47:12 erling 2 1
`c cleanup
`e
`s 00258/00000/00000
`d D 1.1 00/07/26 15:36:30 erling 1 0
`c date and time created 00/07/26 15:36:30 by erling
`e
`u
`U
`f e 0
`
`T
`I 1
`#include "KDx.h"
`#include "kd_search.h" // kd-search declarations
`
`
`//
`// Approximate nearest neighbor searching by kd-tree search
`// The kd-tree is searched for an approximate nearest neighbor.
`/1 The point is returned through one of the arguments, and the
`// distance returned is the squared distance to this point.
`//
`// The method used for searching the kd-tree is an approximate
`// adaptation of the search algorithm described by Friedman,
`I/ Bentley, and Finkel, "An algorithm for finding best matches
`// in logarithmic expected time," ACM Transactions on Mathematical
`Software, 3(3):209-226, 1977).
`
`//
`// The algorithm operates recursively. When first encountering a
`// node of the kd-tree we first visit the child which is closest to
`/1 the query point. On return, we decide whether we want to visit
`// the other child. If the box containing the other child exceeds
`// 1/(1+eps) times the current best distance, then we skip it (since
`// any point found in this child cannot be closer to the query point
`// by more than this factor.) OthenNise, we visit it recursively.
`// The distance between a box and the query point is computed exactly
`(not approximated as is often done in kd-tree), using incremental
`// distance updates, as described by Arya and Mount in "Algorithms
`// for fast vector quantization," Proc. of DCC '93: Data Compression
`// Conference, eds. J. A. Storer and M. Cohn, IEEE Press, 1993,
`// 381-390.
`//
`// The main entry points is annkSearch() which sets things up and
`// then call the recursive routine ann_search(). This is a recursive
`// routine which performs the processing for one node in the kd-tree.
`// There are two versions of this virtual procedure, one for splitting
`nodes and one for leaves. When a splitting node is visited, we
`
`Confidential - Outside Counsel Only
`
`Exhibit 1(
`
`
`
`Date: Name:
`ana L Loper, RMR, CRR, CCP, CSR No. 9667
`
`AUDMAG01085789
`
`

`

`Case 1:14-cv-02396-PGG-SN Document 239-16 Filed 11/12/20 Page 3 of 7
`
`determine which child to visit first (the closer one), and visit
`the other child on return. When a leaf is visited, we compute
`the distances to the points in the buckets, and update information
`on the closest points.
`
`Some trickery is used to incrementally update the distance from
`a kd-tree rectangle to the query point. This comes about from
`the fact that which each successive split, only one component
`(along the dimension that is split) of the squared distance to
`the child rectangle is different from the squared distance to
`the parent rectangle.
`
`To keep argument lists short, a number of global variables
`are maintained which are common to all the recursive calls.
`These are given below.
`
`/1
`/I
`
`//
`/1
`//
`/I
`/I
`/I
`/I
`I/
`I/
`
`/I
`I/
`/I
`/1
`
`int KDkdDim;
`KDpoint KDkdQ;
`double KDkdMaxErr;
`KDpointArray KDkdPts;
`KDmin_k *KDkdPointMK;
`
`// dimension of space
`// query point
`// max tolerable squared error
`// the points
`// set of k closest points
`
`I/
`// annkSearch - search for the k nearest neighbors
`//
`
`
`D2
`MFError annkSearch(KDPointSet* pPS, KDpoint q, int k,
`KDidxArray nn_idx, KDdistArray dd, double eps)
`E2
`I2
`MFError annkSearch(KDTree* kdTree, KDpoint q, int k, KDidxArray nn_idx,
`KDdistArray dd, double eps)
`E2
`
`{
`
`MFError err = MF_SUCCESS;
`
`D2
`if (pPS == 0)
`E2
`I2
`if (kdTree == NULL)
`E2
`
`D2
`
`return MF_INTERNAL_PROGRAM_ERROR;
`
`-•?-; - , I
`
`Confidential - Outside Counsel Only
`
`•
`
`it/
`
`Piwa •
`
`AUDMAG01085790
`
`

`

`Case 1:14-cv-02396-PGG-SN Document 239-16 Filed 11/12/20 Page 4 of 7
`
`if (pPS->utype == BFS)
`{
`
`if ((err = annkBFS(&pPS->uval.bfs, q, k, nn_idx, dd, eps)) !=
`MF_SUCCESS)
`return err;
`
`}
`else if (pPS->utype == KDT)
`{
`
`if ((err = annkTreeSearch(&pPS->uval.kdTree, q, k, nn_idx, dd, eps)) I=
`MF_SUCCESS)
`return err;
`
`}
`else
`return MF_INTERNAL_PROGRAM_ERROR;
`
`E2
`
`I2
`if ((err = annkTreeSearch(kdTree, q, k, nn_idx, dd, eps)) != MF_SUCCESS)
`return err;
`
`E2
`return MF_SUCCESS;
`
`}
`
`D2
`MFError annkBFS(KDbruteForce* pBF, KDpoint q, int k,
`KDidxArray nn_idx, KDdistArray dd, double eps)
`{
`
`/*TRACE("In annkBFS stub\n");*/
`return MF_FAILURE;
`
`}
`
`E2
`MFError annkTreeSearch(KDTree* pKDT, KDpoint q, int k,
`KDidxArray nn_idx, KDdistArray dd, double eps)
`{
`
`int i,
`
`KDkdDim = pKDT->dim; 1* copy arguments to static equivs*/
`KDkdQ = q;
`KDkdPts = pKDT->pts;
`KDptsVisited = 0; /* initialize count of points visited */
`
`if (k > pKDT->n_pts)
`return MF FAILURE; /* return error code */
`
`KDkdMaxErr = KD_POW(1.0 + eps);
`KDkdPointMK = KDminKCreate(k); r create set for closest k points */
`
`Confidential - Outside Counsel Only
`
`AUDMAG01085791
`
`

`

`
`
`
`
`Case 1:14-cv-02396-PGG-SN Document 239-16 Filed 11/12/20 Page 5 of 7
`
`if (pKDT->root->uType == KDLEAF)
`{
`
`kdLeafSearch(pKDT->root, annBoxDistance(q,
`pKDT->bnd_box_lo, pKDT->bnd_box_hi, pKDT->dim));
`r replace KDkd_leaf::ann_search below w kdLeafSearch() */
`
`}
`else if (pKDT->root->uType == KDSPLIT)
`{
`
`kdSplitSearch(pKDT->root, annBoxDistance(q,
`pKDT->bnd_box_lo, pKDT->bnd_box_hi, pKDT->dim));
`
`/* replace KDkd_split::ann_search below w kdSplitSearch() */
`
`}
`
`for (i = 0; i < k; i+-F)
`{ r extract the k-th closest points */
`dd[i] = ith_smallest_key(KDkdPointMK, i);
`nn_idx[i] = ith_smallest_info(KDkdPointMK,i);
`
`}
`Free(KDkdPointMK); /* deallocate closest point set */
`
`return MF_SUCCESS;
`
`}
`
`/I
`// kd_split::ann_search - search a splitting node
`//
`
`
`void kdSplitSearch(KDkd_node* pN, KDdist box_dist)
`{
`
`KDcoord cut_diff;
`KDcoord box_diffl;
`KDcoord box_diff2;
`
`// check dist calc termination condition
`if (KDmaxPtsVisited && KDptsVisited > KDmaxPtsVisited)
`return;
`
`// distance to cutting plane
`cut_diff = KDkdQ[pN->cut_dim] - pN->cut_val;
`
`if (cut_diff < 0)
`
`// left of cutting plane
`{
`if (pN->child[LO]->uType == KDLEAF)
`kdLeafSearch(pN->child[LO], box_dist);
`else
`
`Confidential - Outside Counsel Only
`
`AUDMAG01085792
`
`

`

`Case 1:14-cv-02396-PGG-SN Document 239-16 Filed 11/12/20 Page 6 of 7
`
`kdSplitSearch(pN->child[LOJ, box_dist);
`
`box_diff1 = pN->cd_bnds[LO] - KDkdQ[pN->cut_dim];
`if (box_diff1 < 0) // within bounds - ignore
`box_diff1 = 0;
`
`// distance to further box
`box_dist = (KDdist) KD_SUM(box_dist,
`KD_DIFF(KD_POVV(box_diff1), KD_POW(cut_diff)));
`
`// visit further child if close enough
`if (box_dist * KDkdMaxErr < max_key(KDkdPointMK))
`{
`
`if (pN->child[HI]->uType == KDLEAF)
`kdLeafSearch(pN->child[1-111, box_dist);
`else
`kdSplitSearch(pN->child[1-11], box_dist);
`
`}
`else
`// right of cutting plane
`if (pN->child[HI]->uType == KDLEAF)
`kdLeafSearch(pN->child[HI], box_dist);
`else
`kdSplitSearch(pN->child[H1], box_dist);
`
`box_diff2 = KDkdO[pN->cut_dim] - pN->cd_bnds[HI];
`if (box_diff2 < 0) // within bounds - ignore
`box_diff2 = 0;
`
`// distance to further box
`box_dist = (KDdist) KD_SUM(box_dist,
`KD_DIFF(KD_POW(box_diff2), KD_POW(cut_diff)));
`
`// visit further child if close enough
`if (box_dist * KDkdMaxErr < max_key(KDkdPointMK))
`{
`
`if (pN->child[LO]->uType == KDLEAF)
`kdLeafSearch(pN->child[L0], box_dist);
`
`else
`kdSplitSearch(pN->child[L0], box_dist);
`
`//
`// kdLeafSearch - search points in a leaf node
`// Note: The unreadability of this code is the result of
`some fine tuning to replace indexing by pointer operations.
`//
`
`
`
`
`Confidential - Outside Counsel Only
`
`AUDMAG01085793
`
`

`

`Case 1:14-cv-02396-PGG-SN Document 239-16 Filed 11/12/20 Page 7 of 7
`
`void kdLeafSearch(KDkd_node* pN, KDdist box_dist)
`{
`
`register KDdist dist;
`register KDcoord* pp;
`register KDcoord* qq;
`register KDdist min_dist;
`register KDcoord t;
`register int d;
`
`// distance to data point
`// data coordinate pointer
`// query coordinate pointer
`// distance to k-th closest point
`
`min_dist = max_key(KDkdPointMK); // k-th smallest distance so far
`
`pp = KDkdPts[pN->bkt[0]];
`qq = KDkdQ;
`dist = 0;
`
`// first coord of next data point
`// first coord of query point
`
`#if 0
`t = *(qq++) - *(pp++); dist += et;
`t = *(qq++) - *(pp++); dist += et;
`t = *(qq++) - *(pp++); dist += et;
`t = *(qq++) - *(pp++); dist += et;
`t = *(qq++) - *(pp++); dist += rt;
`t = *(qq++) - *(pp++); dist += t*t;
`t = *(qq++) - *(pp++); dist += rt;
`t = *(qq+-F) - *(pp++); dist += rt;
`t = *(qq++) - *(pp++); dist += t*t;
`t = *(qq++) - *(pp++); dist += tat;
`t = *(qq++) - *(pp++); dist += rt;
`t = *(qq++) - *(pp++); dist += rt;
`t = *(qq++) - *(pp++); dist += rt;
`t = *(qq++) - *(pp++); dist += et;
`if (dist < min_dist)
`insert(KDkdPointMK, dist, pN->bkt[0]);
`
`#else
`for(d = 0; d < KDkdDim; d++)
`{
`
`t = *(qq++) - *(pp++); // compute length and adv coordinate
`// exceeds dist to k-th smallest?
`if( (dist = KD_SUM(dist, KD_POW(t))) > min_dist) {
`break;
`
`}
`
`}
`
`if (d >= KDkdDim)
`insert(KDkdPointMK, dist, pN->bkt[0]);
`
`#endif
`}
`
`E1
`
`Confidential - Outside Counsel Only
`
`AUDMAG01085794
`
`