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. A plurality of combined neighborhoods are received from a plurality of local join executors. Each combined neighborhood represents a neighborhood of a source data point and has one or more pairs of neighbors, each of which includes the source data point, a neighbor of the source point, and a distance in-between. A plurality of KNN lists corresponding to a plurality of source data points are obtained. Each KNN list includes K neighbors to a corresponding source data point, each of which is represented by an index of the neighbor and a distance between the source data point and the neighbor. The plurality of KNN lists are updated based on the plurality of combined neighborhoods to generate updated KNN lists.
1 . A method implemented on at least one machine including at least one processor, memory, and communication platform capable of connecting to a network for identifying k-nearest neighbors (KNN) in clustering for unsupervised learning, the method comprising:
receiving, by a KNN server, from a plurality of distributed local join executors, a plurality of combined neighborhoods generated respectively by the corresponding distributed local join executors in parallel by:
generating neighbor pairs and reverse neighbor pairs based on one or more KNN lists corresponding to one or more source data points,
grouping neighbor pairs and reverse neighbor pairs having a same source data point to generate a grouped pairs of neighbors for the source data point, and
performing a local joint operation based on grouped pairs of neighbors for each of the one or more source data points to generate the combined neighborhood for the source data point;
obtaining, by the KNN server, a plurality of global KNN lists corresponding to a plurality of source data points, wherein each of the plurality of global KNN lists includes K neighbors to a corresponding source data point, each of the K neighbors is represented by an index of the neighbor and a distance between the source data point and the neighbor;
updating, by the KNN server, the plurality of global KNN lists to generate updated global KNN lists by replacing an existing neighbor included in one of the plurality of global KNN lists with an eligible candidate neighbor in a combined neighborhood of a corresponding source data point based on a distance between the source data point and the existing neighbor and a distance between the source data point and the eligible candidate neighbor of the source data point; and
transmitting, by the KNN server, the updated global KNN lists to the plurality of distributed local join executors to improve scalability of clustering for unsupervised learning.
2 . The method of claim 1 , further comprising sending the updated global KNN lists to the plurality of distributed local join executors for generating updated combined neighborhoods for the plurality of source data points in a next iteration.
3 . The method of claim 1 , wherein the step of updating comprises:
for each of the global KNN lists for a source data point,
identifying a corresponding combined neighborhood having pairs of eligible candidate neighbors of the source data point,
identifying a neighbor in the global KNN list that has an existing distance larger than that in a pair of neighbors in the combined neighborhood, and
repeating the steps of identifying a neighbor until no neighbor in the global KNN list with an existing distance larger than that in any pair of neighbors in the combined neighborhood exists.
4 . The method of claim 3 , further comprising:
determining a change count for each of the updated global KNN lists, wherein the change count represents a number of replacements made to the corresponding global KNN list; and
transmitting the change count for each of the updated global KNN lists to facilitate a determination of whether to carry out the next iteration.
5 . The method of claim 1 , wherein the distance in each of the one or more pairs of neighbors in a combined neighborhood for a source data point is smaller than a maximum distance (maxDist) value, defined with respect to the source data point.
6 . The method of claim 5 , wherein the maxDist value relating to the global KNN list for the source data point corresponds to a maximum distance between the source data point to a neighbor in the global KNN list.
7 . Machine readable and non-transitory medium having information recorded thereon for identifying k-nearest neighbors (KNN) in clustering for unsupervised learning, wherein the information, when read by the machine, causes the machine to perform the steps of:
receiving, by a KNN server, from a plurality of distributed local join executors, a plurality of combined neighborhoods generated respectively by the corresponding distributed local join executors in parallel by:
generating neighbor pairs and reverse neighbor pairs based on one or more KNN lists corresponding to one or more source data points,
grouping neighbor pairs and reverse neighbor pairs having a same source data point to generate a grouped pairs of neighbors for the source data point, and
performing a local joint operation based on grouped pairs of neighbors for each of the one or more source data points to generate the combined neighborhood for the source data point;
obtaining, by the KNN server, a plurality of global KNN lists corresponding to a plurality of source data points, wherein each of the plurality of global KNN lists includes K neighbors to a corresponding source data point, each of the K neighbors is represented by an index of the neighbor and a distance between the source data point and the neighbor;
updating, by the KNN server, the plurality of global KNN lists to generate updated global KNN lists by replacing an existing neighbor included in one of the plurality of global KNN lists with an eligible candidate neighbor in a combined neighborhood of a corresponding source data point based on a distance between the source data point and the existing neighbor and a distance between the source data point and the eligible candidate neighbor of the source data point; and
transmitting, by the KNN server, the updated global KNN lists to the plurality of distributed local join executors to improve scalability of clustering for unsupervised learning.
8 . The medium of claim 7 , wherein the information, when read by the machine, further causes the machine to perform the step of sending the updated global KNN lists to the plurality of distributed local join executors for generating updated combined neighborhoods for the plurality of source data points in a next iteration.
9 . The medium of claim 7 , wherein the step of updating comprises:
for each of the global KNN lists for a source data point,
identifying a corresponding combined neighborhood having pairs of eligible candidate neighbors of the source data point,
identifying a neighbor in the global KNN list that has an existing distance larger than that in a pair of neighbors in the combined neighborhood, and
repeating the steps of identifying a neighbor until no neighbor in the global KNN list with an existing distance larger than that in any pair of neighbors in the combined neighborhood exists.
10 . The medium of claim 9 , wherein the information, when read by the machine, causes the machine to further perform the steps of:
determining a change count for each of the updated global KNN lists, wherein the change count represents a number of replacements made to the corresponding global KNN list; and
transmitting the change count for each of the updated global KNN lists to facilitate a determination of whether to carry out the next iteration.
11 . The medium of claim 7 , wherein the distance in each of the one or more pairs of neighbors in a combined neighborhood for a source data point is smaller than a maximum distance (maxDist) value, defined with respect to the source data point.
12 . The medium of claim 11 , wherein the maxDist value relating to the global KNN list for the source data point corresponds to a maximum distance between the source data point to a neighbor in the global KNN list.
13 . A system for identifying k-nearest neighbors (KNN) in clustering for unsupervised learning, comprising:
a KNN list update controller implemented by a processor and configured for receiving, from a plurality of distributed local join executors, a plurality of combined neighborhoods generated respectively by the corresponding distributed local join executors in parallel by:
generating neighbor pairs and reverse neighbor pairs based on one or more KNN lists corresponding to one or more source data points,
grouping neighbor pairs and reverse neighbor pairs having a same source data point to generate a grouped pairs of neighbors for the source data point, and
performing a local joint operation based on grouped pairs of neighbors for each of the one or more source data points to generate the combined neighborhood for the source data point;
a KNN list updater implemented by a processor and configured for
obtaining a plurality of global KNN lists corresponding to a plurality of source data points, wherein each of the plurality of global KNN lists includes K neighbors to a corresponding source data point, each of the K neighbors is represented by an index of the neighbor and a distance between the source data point and the neighbor, and
updating the plurality of global KNN lists to generate updated global KNN lists by replacing an existing neighbor included in one of the plurality of global KNN lists with an eligible candidate neighbor in a combined neighborhood of a corresponding source data point based on a distance between the source data point and the existing neighbor and a distance between the source data point and the eligible candidate neighbor of the source data point; and
a transmitter implemented by a processor and configured for transmitting the updated global KNN lists to the plurality of distributed local join executors to improve scalability of clustering for unsupervised learning.
14 . The system of claim 13 , further comprising an updated global KNN list transmitter implemented by a processor and configured for sending the updated KNN lists to the plurality of distributed local join executors for generating updated combined neighborhoods for the plurality of source data points in a next iteration.
15 . The system of claim 13 , wherein the KNN list updater updates the global KNN lists by:
for each of the global KNN lists for a source data point,
identifying a corresponding combined neighborhood having pairs of eligible candidate neighbors of the source data point,
identifying a neighbor in the global KNN list that has an existing distance larger than that in a pair of neighbors in the combined neighborhood, and
repeating the steps of identifying a neighbor until no neighbor in the global KNN list with an existing distance larger than that in any pair of neighbors in the combined neighborhood exists.
16 . The system of claim 15 , further comprising a list-based change counter implemented by a processor and configured for:
determining a change count for each of the updated global KNN lists, wherein the change count represents a number of replacements made to the corresponding global KNN list; and
transmitting the change count for each of the updated global KNN lists to facilitate a determination of whether to carry out the next iteration.
17 . The system of claim 13 , wherein the distance in each of the one or more pairs of neighbors in a combined neighborhood for a source data point is smaller than a maximum distance (maxDist) value, defined with respect to the source data point, and the maxDist value relating to the global KNN list for the source data point corresponds to a maximum distance between the source data point to a neighbor in the global KNN list.