Overload List
| # | Signature | Description |
|---|---|---|
| 1 | void ClusteredKNN(TMtx srcData, TMtx srcCompareData, Int32 K, TMtxInt dstNearIdx, TMtx dstNearDistance) | Exact brute-force K-NN without multi-threading. |
| 2 | void ClusteredKNN(TMtxForLoop computeThreads, TMtx srcData, TMtx srcCompareData, Int32 K, TMtxInt dstNearIdx, TMtx dstNearDistance) | Exact brute-force K-NN with support for symmetric and asymetric multi-threading. |
Overload 1: void ClusteredKNN(TMtx srcData, TMtx srcCompareData, Int32 K, TMtxInt dstNearIdx, TMtx dstNearDistance)
Exact brute-force K-NN without multi-threading.
| # | Name | Description |
|---|---|---|
| 1 | srcData | A matrix where each row is one vector of the original data. |
| 2 | srcCompareData | A matrix where each row is one vector. We want to find K vectors from srcData for each srcCompareData vector. |
| 3 | K | The number of nearest neighbours/rows from SrcData to find for each row in SrcCompareData. |
| 4 | dstNearIdx | Contains K indexes of rows from srcData for each row in SrcCompareData on output. The actual distances are stored in dstNearDistance parameter. |
| 5 | dstNearDistance | Contains K distance of rows from srcData for each row in SrcCompareData on output. The distances are not sorted. |
Result: stored in self (calling object)
Remarks:
K-nearest-neighbours will be computing the square of L2-Norm (distance) between rows in srcData and rows in srcCompareData to find K nearest rows from srcData for each row in the srcCompareData matrix. The SrcData.Cols and SrcCompareData.Cols need to match in size or an exception will be raised. The sizes of dstNearIdx, dstNearDistance and dstNearLargestIdx are set automatically.
Performance notes:
- This variant does not use threads and is suitable for user-side multi-threading.
- The algorithm assumes existence of 32KB L1 cache. This is true for all Intel CPUs since Sandy Bridge and AMD Zen. The performance will drop by roughly 10x, if not present.
- The algorithms efficiency grows with the size of srcData and especially of the srcCompareData matrices.
Examples
Matrix Data;
Matrix cmpData;
Matrix nearDistance;
MatrixInt nearIdx;
data = [new double[] {1,2,3},
new double[] {2,3,1},
new double[] {3,2,1}];
cmpData = [new double[] {2,2,3},
new double[] {2,3,4}];
ClusteredKNN(computeThreads, Data, cmpData, 2, nearIdx, nearDistance);
// Results:
// nearIdx = [[0, 1], // data rows 0 and 1 are closest vectors to cmpData row 0.
// [0, 1]] // data rows 0 and 1 are closest vectors to cmpData row 1.
// nearDistance = [[1 5], // [0,0] = sqr(2-1) + sqr(2-2) + sqr(3-3), distance from cmpData row 0 to Data row 0 is 1
// [3, 9]] // [1,0] = sqr(2-1) + sqr(3-2) + sqr(4-3), distance from cmpData row 1 to Data row 0 is 3Overload 2: void ClusteredKNN(TMtxForLoop computeThreads, TMtx srcData, TMtx srcCompareData, Int32 K, TMtxInt dstNearIdx, TMtx dstNearDistance)
Exact brute-force K-NN with support for symmetric and asymetric multi-threading.
| # | Name | Description |
|---|---|---|
| 1 | computeThreads | A TMtxFoorLoop object, which is a threading library. ComputeThreads.BlockGranularity is required to be set to 4 for this algorithm. Additionally this object allows the user to specify thread-count and thread-affinity etc.. |
| 2 | srcData | A matrix where each row is one vector of the original data. |
| 3 | srcCompareData | A matrix where each row is one vector. We want to find K vectors from srcData for each srcCompareData vector. |
| 4 | K | The number of nearest neighbours/rows from SrcData to find for each row in SrcCompareData. |
| 5 | dstNearIdx | Contains K indexes of rows from srcData for each row in SrcCompareData on output. The actual distances are stored in dstNearDistance parameter. |
| 6 | dstNearDistance | Contains K distance of rows from srcData for each row in SrcCompareData on output. The distances are not sorted. |
Result: stored in self (calling object)
Remarks:
K-nearest-neighbours will be computing the square of L2-Norm (euclidian norm or the distance) between rows in srcData and rows in srcCompareData to find K nearest rows from srcData for each row in the srcCompareData matrix. The SrcData.Cols and SrcCompareData.Cols need to match in size or an exception will be raised. The sizes of dstNearIdx and dstNearDistance are set automatically.
Performance notes:
- The ideal ComputeThreads.ThreadCount passed to the routine will equal the number of hyper-threaded cores.
- The algorithm assumes existence of 32KB L1 cache. This is true for all Intel CPUs since Sandy Bridge and AMD Zen. The performance will drop by roughly 10x, if not present.
- MtxVec.Controller.ThreadDimension is to be set to value larger than ComputeThreads.ThreadCount or an error will be raised.
- computeThreads.BlockGranularity needs to be 4 or an error will be raised.
- Multi-threading is performed only across the srcCompareData rows. If that matrix has less than 10-20 rows, the user can still perform multi-threading in his own code. The maximum performance gain in this case however will scale with thread count only up to the systems memory channel count (2-8).
- The algorithm is set to scale linearly with core count (32, 64, 128 etc...), provided that srcCompareData.Rows is large enough.
- For a 950 000 x 950 000 problem with, K = 50, Vector length = 30, 32bit float, on 8 SkyLake cores, the expected time to finish is 90s.
- The speed-up over naive and not threaded KNN implementation starts at around 10x for small problems in grows to 1000x and more for very large problems.
- Double precision is about 1.5x slower than single precision.
Examples
Matrix Data;
Matrix cmpData;
Matrix nearDistance;
MatrixInt nearIdx;
TMtxForLoop threads;
// 1.) Create once ahead of time. This is the thread pool and is slow to create.
threads = TMtxForLoop.Create;
threads.ThreadCount = Controller.CpuCores*2; //hyperthreaded core count
threads.BlockGranularity = 4; //required
// 2.) This sets the "minimum" required. Also slow and needs to be set upfront and
// it can only be done before any allocations are made by MtxVec.
Controller.ThreadDimension = Max(threads.ThreadCount + 1, Controller.ThreadDimension);
// 3.) Compiler assertions switch needs to be "off", when compling the source code
data = [new double[] {1,2,3},
new double[] {2,3,1},
new double[] {3,2,1}];
cmpData = [new double[] {2,2,3},
new double[] {2,3,4}];
ClusteredKNN(threads, Data, cmpData, 2, nearIdx, nearDistance);
// Results:
// nearIdx = [[0, 1], // data rows 0 and 1 are closest vectors to cmpData row 0.
// [0, 1]] // data rows 0 and 1 are closest vectors to cmpData row 1.
// nearDistance = [[1, 5], // [0,0] = sqr(2-1) + sqr(2-2) + sqr(3-3), distance from cmpData row 0 to Data row 0 is 1
// [3, 9]] // [1,0] = sqr(2-1) + sqr(3-2) + sqr(4-3), distance from cmpData row 1 to Data row 0 is 3
threads.Free;