Patent Document ID: 10073887
Application ID: 14791869
Patent Flag: 1

Claim One:
1. A method for identifying a set of nearest neighbors for a test object and predicting whether the test object is an outlier, the method comprising: receiving a test object; for each of a set of dataset objects, computing a pairwise distance between the test object and the dataset object, the dataset objects and test object being represented by nodes of a graph, edges of the graph representing pairwise distances between respective pairs of the objects; with a processor, iteratively selecting one of the dataset objects to add to a set of nearest neighbors until the set of nearest neighbors includes a predefined number of nearest neighbors, the selected dataset object at each iteration being a dataset object min_ind which is not currently in the set of nearest neighbors for which there is no other dataset object not currently in the set of nearest neighbors which has a smaller pairwise distance to any of a subset of objects than the selected dataset object, the subset of objects consisting of the test object and the dataset objects currently in the set of nearest neighbors; predicting whether the test object is an outlier with respect to the dataset, including: initializing a vector dist with the distance of the test object to each object in the dataset; initializing a value max_indrct with an initial value; initializing a value min_direct with an initial value greater than the initial value of max_indrct; initializing an updated vector with a first of two values for each of the objects in the dataset; and wherein at each iteration: if the value of the updated vector for min_ind has been set to a second of the two values, then the value max_indrct is set to a maximum of a current value of max_indrct and dist min _ ind , otherwise the value min_direct is set to a minimum of the current value of min_direct and dist min _ ind , where dist min _ ind is the value of the distance vector for the object min_ind in the dataset that is not yet in the set of nearest neighbors, which has the minimum distance to the test object, and for each dataset object not currently in the set of nearest neighbors, if a distance D min _ ind,i is less than the distance for that object stored in the vector dist, then the distance for that object stored in the vector dist is set to the distance D min _ ind,i , and the value of the updated vector for that dataset object is set to the second of the two values, where D min _ ind,i is the distance between that dataset object and the newly-added member of the set of nearest neighbors; the test object being predicted to be an outlier if max_indrct is not equal to its initial value and min_direct is greater than max_indrct, and outputting at least one of: the set of nearest neighbors; and information based thereon, the information including a prediction of whether the test object is an outlier with respect to the dataset.