Nearest neighbor data method and system

• US 20020123987A1
• Filed: 01/18/2001
• Published: 09/05/2002
• Est. Priority Date: 01/18/2001
• Status: Abandoned Application

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Cox, James A.
• Application Number:
  US09/764,742
• Publication Number:
  US 20020123987A1
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/24553 of query operations
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers

Abstract

A computer-implemented multi-dimensional search method and system that searches for nearest neighbors of a probe data point. Nodes in a data tree are evaluated to determine which data points neighbor a probe data point. To perform this evaluation, the nodes are associated with ranges for the data points included in their respective branches. The data point ranges are used to determine which data points neighbor the probe data point. The top “k” data points are returned as the nearest neighbors to the probe data point.

Claims

1. A computer-implemented set query method that searches for data points neighboring a probe data point, comprising the steps of:

receiving a set query that seeks neighbors to a probe data point;

evaluating nodes in a data tree to determine which data points neighbor a probe data point,

wherein the nodes contain the data points,

wherein the nodes are associated with ranges for the data points included in their respective branches; and

determining which data points neighbor the probe data point based upon the data point ranges associated with a branch.

2. The method of claim 1 further comprising the step of:

determining distances between the probe data point and the data points of the tree based upon the ranges.

3. The method of claim 2 further comprising the step of:

determining nearest neighbors to the probe data point based upon the determined distances.

4. The method of claim 1 further comprising the steps of:

determining distances between the probe data point and the data points of the tree based upon the ranges; and

selecting as nearest neighbors a preselected number of the data points whose determined distances are less than the remaining data points.

5. The method of claim 1 further comprising the steps of:

selecting based upon the ranges which data points to determine distances from the probe data point;

determining distances between the probe data point and the selected data points of the tree; and

selecting as nearest neighbors a preselected number of the data points whose determined distances are less than the remaining data points.

6. The method of claim 5 wherein the ranges include minimum and maximum data point information for the nodes, said method further comprising the steps of:

selecting based upon the minimum and maximum data point information which data points to determine distances from the probe data point;

determining distances between the probe data point and the selected data points of the tree; and

selecting as nearest neighbors a preselected number of data points whose determined distances are less than the remaining data points.

7. The method of claim 1 wherein the ranges include minimum and maximum data point information for the nodes, said method further comprising the steps of:

selecting based upon the minimum and maximum data point information which data points to determine distances from the probe data point;

determining distances between the probe data point and the selected data points of the tree; and

selecting as nearest neighbors a preselected number of data points whose determined distances are less than the remaining data points.

8. The method of claim 1 wherein the data tree includes a root node, subnodes, and leaf nodes to contain the data points and the ranges, wherein the tree contains a split into first and second subnodes, wherein the first and second subnodes contain minimum and maximum data point information for the data points included in their respective branches, said method further comprising the steps of:

selecting the branch of the first subnode when the probe data point is less than the minimum of the first subnode;

determining distances between the probe data point and at least one data point contained in the branch of the first subnode; and

selecting as a nearest neighbor at least one data point in the first subnode branch whose determined distance is less than another data point contained in the branch of the first subnode.

9. The method of claim 8 further comprising the step of:

selecting as a nearest neighbor at least one data point in the first subnode branch whose determined distance is less than another data point contained in the branch of the second subnode.

10. The method of claim 1 wherein the data tree includes a root node, subnodes, and leaf nodes to contain the data points and the ranges, wherein the tree contains a split into first and second subnodes, wherein the first and second subnodes contain minimum and maximum data point information for the data points included in their respective branches, said method further comprising the steps of:

selecting the branch of the second subnode when the probe data point is greater than the maximum of the second subnode;

determining distances between the probe data point and at least one data point contained in the branch of the second subnode; and

selecting as a nearest neighbor at least one data point in the second subnode branch whose determined distance is less than another data point contained in the branch of the second subnode.

11. The method of claim 10 further comprising the step of:

selecting as a nearest neighbor at least one data point in the second subnode branch whose determined distance is less than another data point contained in the branch of the first subnode.

12. The method of claim 1 wherein the data tree includes a root node, subnodes, and leaf nodes to contain the data points and the ranges, wherein the tree contains a split into first and second subnodes, wherein the first and second subnodes contain minimum and maximum data point information for the data points included in their respective branches, said method further comprising the steps of:

determining when the probe data point is between the maximum of the first subnode and the minimum of the second subnode;

when the probe data point is between the maximum of the first subnode and the minimum of the second subnode, selecting the branch of either the first subnode or second subnode based upon which branch has the smallest minimum distance to expand;

determining distances between the probe data point and at least one data point contained in the selected branch; and

selecting as a nearest neighbor at least one data point in the selected branch whose determined distance is less than another data point contained in the other branch.

13. The method of claim 1 further comprising the step of:

constructing the data tree by partitioning the data points from a database into regions.

14. The method of claim 1 further comprising the steps of:

determining that the data points are categorical data points;

scaling the categorical data points into variables that are interval-scaled; and

storing the scaled categorical data points in the data tree.

15. The method of claim 1 further comprising the steps of:

determining that the data points are non-interval data points;

scaling the non-interval data points into variables that are interval-scaled; and

storing the scaled data points in the data tree.

16. The method of claim 1 further comprising the steps of:

performing principal components analysis upon the data points to generate orthogonal components; and

storing the orthogonal components in the data tree.

17. The method of claim 1 wherein the data points are an array of real-valued attributes, wherein the attributes represent dimensions, said method further comprising the step of:

constructing the data tree by storing in a node the range of the data points within the branch of the node and storing descendants of the node along the dimension that its parent node was split.

18. The method of claim 1 wherein the data points are an array of real-valued attributes, wherein the attributes represent dimensions, said method further comprising the step of:

constructing the data tree by storing in a node the minimum and maximum of the data points within the branch of the node.

19. The method of claim 18 further comprising the step of:

constructing the data tree by splitting a node into a left and right branch along the dimension with greatest range.

20. The method of claim 19 further comprising the step of:

selecting the right branch of the data tree to add a data point when the probe data point is greater than the minimum of the right branch.

21. The method of claim 19 further comprising the step of:

selecting the left branch of the data tree to add a data point when the probe data point is less than the maximum of the left branch.

22. The method of claim 19 further comprising the step of:

selecting either the left or right branch of the data tree to add a data point based on the number of points on the right branch, the number of points on the left branch, the distance to the minimum value on the right branch, and the distance to the maximum value on the left branch.

23. The method of claim 19 further comprising the step of:

constructing the data tree by partitioning along only one axis the data points into regions.

24. The method of claim 1 wherein the data points are stored in the data tree in a volatile computer memory, said method further comprising the step of:

evaluating the nodes in the data tree that are stored in the volatile computer memory.

25. The method of claim 1 wherein the data points are stored in the data tree in a random access memory, said method further comprising the step of:

evaluating the nodes in the data tree that are stored in the random access memory.

27. The apparatus of claim 26 wherein the distances are determined between the probe data point and the data points of the tree based upon the ranges, said apparatus further comprising:

a priority queue connected to the node range searching function module, wherein the priority queue contains storage locations for points having a preselected minimum distance from the probe data point.

28. The apparatus of claim 27 wherein the nearest neighbors to the probe data point are selected based upon the determined distances that are stored in the priority queue.

29. The apparatus of claim 26 wherein the ranges include minimum and maximum data point information for the nodes, wherein the node range searching function module selects based upon the minimum and maximum data point information which data points to determine distances from the probe data point, wherein the node range searching function module determines distances between the probe data point and the selected data points of the tree, wherein a preselected number of data points are selected as nearest neighbors whose determined distances are less than the remaining data points.

30. The apparatus of claim 26 wherein the data tree includes a root node, subnodes, and leaf nodes to contain the data points and the ranges, wherein the tree contains a split into first and second subnodes, wherein the first and second subnodes contain minimum and maximum data point information for the data points included in their respective branches,

wherein the branch of the first subnode is selected when the probe data point is less than the minimum of the first subnode,

wherein the distance is determined between the probe data point and at least one data point contained in the branch of the first subnode, and

wherein at least one data point in the first subnode branch is selected as a nearest neighbor whose determined distance is less than another data point contained in the branch of the first subnode.

31. The apparatus of claim 30 wherein at least one data point in the first subnode branch is selected as a nearest neighbor whose determined distance is less than another data point contained in the branch of the second subnode.

32. The apparatus of claim 26 wherein the data tree includes a root node, subnodes, and leaf nodes to contain the data points and the ranges, wherein the tree contains a split into first and second subnodes, wherein the first and second subnodes contain minimum and maximum data point information for the data points included in their respective branches,

wherein the branch of the second subnode is selected when the probe data point is greater than the maximum of the second subnode,

wherein a distance is determined between the probe data point and at least one data point contained in the branch of the second subnode, and

wherein at least one data point in the second subnode branch is selected as a nearest neighbor whose determined distance is less than another data point contained in the branch of the second subnode.

33. The apparatus of claim 32 wherein at least one data point in the second subnode branch is selected as a nearest neighbor whose determined distance is less than another data point contained in the branch of the first subnode.

34. The apparatus of claim 26 wherein the data tree includes a root node, subnodes, and leaf nodes to contain the data points and the ranges, wherein the tree contains a split into first and second subnodes, wherein the first and second subnodes contain minimum and maximum data point information for the data points included in their respective branches, said method further comprising:

means for determining when the probe data point is between the maximum of the first subnode and the minimum of the second subnode;

when the probe data point is between the maximum of the first subnode and the minimum of the second subnode, selecting the branch of either the first subnode or second subnode based upon which branch has the smallest minimum distance to expand;

means for determining distances between the probe data point and at least one data point contained in the selected branch; and

means for selecting as a nearest neighbor at least one data point in the selected branch whose determined distance is less than another data point contained in the other branch.

35. The apparatus of claim 26 wherein the data points are an array of real-valued attributes, wherein the attributes represent dimensions, wherein the data tree contains in a node the range of the data points within the branch of the node and storing descendants of the node along the dimension that its parent node was split.

36. The apparatus of claim 26 wherein the data points are an array of real-valued attributes, wherein the attributes represent dimensions, wherein the data tree contains in a node the minimum and maximum of the data points within the branch of the node.

37. The apparatus of claim 36 further comprising wherein the data tree contains splits for the nodes, wherein the splits are along the dimension with greatest range.

38. The apparatus of claim 37 further comprising:

a point adding function module connected to the data tree in order to select the right branch of the data tree to add a data point when the probe data point is greater than the minimum of the right branch.

39. The apparatus of claim 37 further comprising:

a point adding function module connected to the data tree in order to select the left branch of the data tree to add a data point when the probe data point is less than the maximum of the left branch.

40. The apparatus of claim 37 further comprising:

a point adding function module connected to the data tree in order to select either the left or right branch of the data tree to add a data point based on the number of points on the right branch, the number of points on the left branch, the distance to the minimum value on the right branch, and the distance to the maximum value on the left branch.

41. The apparatus of claim 26 further comprising a volatile computer memory to store the data points.

42. The apparatus of claim 26 further comprising a random access memory to store the data points.

26. A computer-implemented apparatus that searches for data points neighboring a probe data point, comprising:

a data tree having nodes that contain the data points,

wherein the nodes are associated with ranges for the data points included in their respective branches; and

a node range searching function module connected to the data tree in order to evaluate the ranges associated with the nodes to determine which data points neighbor a probe data point.

43. A computer memory to store a data tree data structure for use in searching for data points neighboring a probe data point, comprising:

the data tree data structure that contains nodes,

wherein the nodes include a root node, subnodes, and leaf nodes in order to contain the data points,

wherein the data tree data structure contains a split into first and second subnodes, wherein the first and second subnodes contain minimum and maximum data point information for the data points included in their respective branches,

wherein the ranges of the data tree data structure are evaluated in order to determine which data points in the data tree data structure neighbor a probe data point.

44. The memory of claim 43 wherein the computer memory is a volatile computer memory.

45. The memory of claim 43 wherein the computer memory is a random access memory.