System and method for identifying approximate k-nearest neighbors in web scale clustering
The present teaching relates to method, system, medium, and implementations for identifying k nearest neighbors. One or more KNN lists corresponding to one or more source data points are received. Each KNN list includes K neighbors of a source data point and each of the K neighbors is a data point represented by an index. Neighbor pairs and reverse neighbor pairs are generated based on the one or more KNN lists. The neighbor pairs and reverse neighbor pairs having the same source data point are grouped to generate a grouped pairs of neighbors for the source data point. A local join operation is performed based on grouped pairs of neighbors for each source data point to generate a combined neighborhood for the source data point, which is then sent to a KNN server, where combined neighborhoods generated by multiple local join executors are integrated to update a plurality of global KNN lists.
1 . A method for generating k-nearest neighbors (KNN) via distributed parallel local join operations, the method comprising:
receiving, by each of a plurality of local join executors from an executor controller controlling all of the plurality of local join executors, a parallel assignment of a corresponding subset of data points in a dataset;
determining in parallel with others of the plurality of local join executors, by each of the plurality of local join executors, distances between the data points within the subset;
selecting, by each of the plurality of local join executors based on the distances and an operational parameter provided by the executor controller, a certain number of nearest neighbors within the corresponding assigned subset of data points;
identifying, by each of the plurality of local join executors in parallel with others of the plurality of local join executors, based on the nearest neighbors, neighbor pairs and reverse neighbor pairs with respect to the data points;
grouping, by each of the plurality of local join executors, the neighbor pairs and reverse neighbor pairs having a same data point to generate grouped neighbor pairs for each of the data points;
performing, by each of the plurality of local join executors in parallel with others of the plurality of local join executors, a respective local join operation based on the grouped neighbor pairs to generate a combined neighborhood for each of the data points; and
sending, by each of the plurality of local join executors to a KNN server, the combined neighborhoods to integrate local join results from the plurality of local join executors to generate the KNNs across all data points in the dataset so that the integration performed by the KNN server is based on indices of the data points and the distances without needing to access feature vectors for the data points thereby enhancing speed or operational efficiency of the plurality of local join executors.
2 . The method of claim 1 , wherein the parallel assignment is determined based on a capacity or current workload of each of the plurality of local join executors.
3 . The method of claim 1 , wherein the parallel assignment is coordinated via the executor controller.
4 . The method of claim 1 , wherein the determining distances in parallel is coordinated via the executor controller.
5 . The method of claim 1 , wherein the information associated with the certain number of nearest neighbors sent from the plurality of local join executors are integrated by the KNN server to generate the KNNs.
6 . The method of claim 5 , wherein the KNN server comprises a plurality of distributed KNN servers managed by a KNN server controller.
7 . The method of claim 6 , wherein the plurality of distributed KNN servers integrate in parallel, the information associated with the certain number of nearest neighbors sent from the plurality of local join executors to generate the KNNs.
8 . A non-transitory, computer-readable medium having information recorded thereon for generating k-nearest neighbors (KNN) via distributed parallel local join operations, wherein the information, when read by a machine, causes the machine to perform operations comprising:
receiving, by each of a plurality of local join executors from an executor controller controlling all of the plurality of local join executors, a parallel assignment of a corresponding subset of data points in a dataset;
determining in parallel with others of the plurality of local join executors, by each of the plurality of local join executors, distances between the data points within the subset;
selecting, by each of the plurality of local join executors based on the distances and an operational parameter provided by the executor controller, a certain number of nearest neighbors within the corresponding assigned subset of data points;
identifying, by each of the plurality of local join executors in parallel with others of the plurality of local join executors, based on the nearest neighbors, neighbor pairs and reverse neighbor pairs with respect to the data points;
grouping, by each of the plurality of local join executors, the neighbor pairs and reverse neighbor pairs having a same data point to generate grouped neighbor pairs for each of the data points;
performing, by each of the plurality of local join executors in parallel with others of the plurality of local join executors, a respective local join operation based on the grouped neighbor pairs to generate a combined neighborhood for each of the data points; and
sending, by each of the plurality of local join executors to a KNN server, the combined neighborhoods to integrate local join results from the plurality of local join executors to generate the KNNs across all data points in the dataset so that the integration performed by the KNN server is based on indices of the data points and the distances without needing to access feature vectors for the data points thereby enhancing speed or operational efficiency of the plurality of local join executors.
9 . The medium of claim 8 , wherein the parallel assignment is determined based on a capacity or current workload of each of the plurality of local join executors.
10 . The medium of claim 8 , wherein the parallel assignment is coordinated via the executor controller.
11 . The medium of claim 8 , wherein the determining distances in parallel is coordinated via the executor controller.
12 . The medium of claim 8 , wherein the information associated with the certain number of nearest neighbors sent from the plurality of local join executors are integrated by the KNN server to generate the KNNs.
13 . The medium of claim 12 , wherein the KNN server comprises a plurality of distributed KNN servers managed by a KNN server controller.
14 . The medium of claim 13 , wherein the plurality of distributed KNN servers integrate in parallel, the information associated with the certain number of nearest neighbors sent from the plurality of local join executors to generate the KNNs.
15 . A system for generating k-nearest neighbors (KNN) via distributed parallel local join operations, the system comprising:
memory storing computer program instructions; and
one or more processors that, in response to executing the computer program instructions, effectuate operations comprising:
receiving, by each of a plurality of local join executors from an executor controller controlling all of the plurality of local join executors, a parallel assignment of a corresponding subset of data points in a dataset;
determining in parallel with others of the plurality of local join executors, by each of the plurality of local join executors, distances between the data points within the subset;
selecting, by each of the plurality of local join executors based on the distances and an operational parameter provided by the executor controller, a certain number of nearest neighbors within the corresponding assigned subset of data points;
identifying, by each of the plurality of local join executors in parallel with others of the plurality of local join executors, based on the nearest neighbors, neighbor pairs and reverse neighbor pairs with respect to the data points;
grouping, by each of the plurality of local join executors, the neighbor pairs and reverse neighbor pairs having a same data point to generate grouped neighbor pairs for each of the data points;
performing, by each of the plurality of local join executors in parallel with others of the plurality of local join executors, a respective local join operation based on the grouped neighbor pairs to generate a combined neighborhood for each of the data points; and
sending, by each of the plurality of local join executors to a KNN server, the combined neighborhoods to integrate local join results from the plurality of local join executors to generate the KNNs across all data points in the dataset so that the integration performed by the KNN server is based on indices of the data points and the distances without needing to access feature vectors for the data points thereby enhancing speed or operational efficiency of the plurality of local join executors.
16 . The system of claim 15 , wherein the parallel assignment is determined based on a capacity or current workload of each of the plurality of local join executors.
17 . The system of claim 15 , wherein the parallel assignment is coordinated via the executor controller.
18 . The system of claim 15 , wherein the determining distances in parallel is coordinated via the executor controller.
19 . The system of claim 15 , wherein the information associated with the certain number of nearest neighbors sent from the plurality of local join executors are integrated by the KNN server to generate the KNNs.
20 . The system of claim 19 , wherein the KNN server comprises a plurality of distributed KNN servers managed by a KNN server controller, and
wherein the plurality of distributed KNN servers integrate in parallel, the information associated with the certain number of nearest neighbors sent from the plurality of local join executors to generate the KNNs.