K-nearest neighbor search method, k-nearest neighbor search program, and k-nearest neighbor search device

• US 8,090,745 B2
• Filed: 01/30/2009
• Issued: 01/03/2012
• Est. Priority Date: 02/19/2008
• Status: Active Grant

• Current Assignee: Hitachi Solutions Limited (Hitachi, Ltd.)
• Original Assignee: Hitachi, Ltd., Hitachi Solutions Limited (Hitachi, Ltd.)
• Inventors: Hayashi, Hideki, Ito, Daisuke, Tanizaki, Masaaki, Kimura, Kouji, Kajiyama, Hisanori
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Casanova, Jorge A
• Application Number:
  US12/362,962
• Publication Number:
  US 20090210413A1
• Time in Patent Office: 1,068 Days
• Field of Search: 707/797
• US Class Current: 707/797
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 18/24147 Distances to closest patterns, e.g. nearest neighbour classification

Abstract

Provided is a k-nearest neighbor search method of searching for a query number k of nearest points to an arbitrary point in a DBMS for creating a spatial index from multidimensional points, comprising setting a search conditions, judging which of a lowest branch and an intermediate branch of the spatial index a nearest region to the query point is, calculating, when the nearest region is judged to be the lowest branch, a distance between the query point and a child region of the nearest region, storing information of a divided region which has become a calculation target, calculating, when the nearest region is judged to be the intermediate region, a distance between the query point and a point included in the nearest region, storing information of the point which has become a calculation target, finishing search processing when the search conditions are satisfied, and obtaining a search result from the DBMS.

Claims

1. A k-nearest neighbor search method of searching a database for a query number k of nearest points to a query point, the database including multidimensional points and a spatial index where a region including the points is divided into a plurality of regions to set child regions in the region, a tree structure including branches and leaf nodes being created from the points and the region,

the search method comprising:

setting the query point and the query number as search conditions;

judging whether a nearest region to the query point is a lowest branch or an intermediate branch of the spatial index;

calculating, when the nearest region is judged to be an intermediate branch having a child region, a distance between the query point and the child region of the nearest region as a region distance;

storing information on a region which has become a calculation target of the region distance to obtain a nearest region to the region;

calculating, when a result of the judging shows that the nearest region is a lowest branch having no child region, a distance between the query point and a point included in the nearest region as a point distance;

storing information on the point which has become a calculation target of the point distance;

repeating, until the search conditions are satisfied, search processing from the judging to the storing the information on the point which has become the calculation target of the point distance, and finishing the search processing when the search conditions are satisfied; and

obtaining, after finishing the search processing, a record of the stored point as a search result from a database management system for managing the database.

2. The k-nearest neighbor search method according to claim 1, wherein the spatial index manages regions into which a multidimensional space is hierarchically divided by surfaces passing through axes by a tree structure, stores information on the divided regions in branches, each of the divided regions corresponding to the branches including a divided region corresponding to a branch positioned as a child of the branch, and stores information on a point included in a divided region corresponding to the lowest branch in a leaf node adjacent to the branch.

3. The k-nearest neighbor search method according to claim 2, wherein:

the multidimensional points comprise points each being locatable by one coordinate in a two-dimensional space; and

in the spatial index, the points are divided into a plurality of regions by one of a quadtree and an R-tree.

4. The k-nearest neighbor search method according to claim 2, wherein:

the multidimensional points comprise points each being locatable by one coordinate in a three-dimensional space; and

in the spatial index, the points are divided into a plurality of regions by one of an octree and an R-tree.

5. The k-nearest neighbor search method according to claim 2, wherein:

the spatial index contains attribute information on the point in the information on the point to manage the information by a leaf node;

the setting the query point and the query number as the search conditions comprises setting the query point, the query number, and the attribute information as search conditions;

the calculating the distance between the query point and the point included in the nearest region comprises storing only points matching the attribute information of the search condition; and

the obtaining the record of the stored point as the search result from the database management system comprises obtaining k nearest points to the query point that match the attribute information.

6. The k-nearest neighbor search method according to claim 2, wherein the setting the query point and the query number as the search conditions comprises receiving a coordinate column name, the query point and the query number of a table of the database which becomes a search target as arguments in one of a language and a function.

7. The k-nearest neighbor search method according to claim 2, wherein:

the initial setting manager sets the query point, the query number, and an interruption condition as search conditions, and interrupts, even in a situation where the query number is not reached, the search processing if the interruption condition is satisfied; and

the result manager is capable of obtaining up to k nearest points to the query point.

8. The k-nearest neighbor search method according to claim 7, wherein:

the interruption condition is described by a query distance indicating a maximum distance of points which become a search result;

the region distance calculator records only information on divided points having distances equal to or shorter than the query distance in the region manager;

the point distance calculator records only information on points having distances equal to or shorter than the query distance in the point manager; and

the result manager is accordingly capable of obtaining up to k nearest points to the query point that have distances equal to or shorter than the query distance from the database management system.

9. The k-nearest neighbor search method according to claim 7, wherein:

the interruption condition is described by maximum processing time indicating maximum time expended for the search processing;

the search processing is interrupted when an elapsed execution time of the search processing becomes equal to the maximum processing time; and

the result manager obtains up to k nearest points to the query point from the database management system.

10. The k-nearest neighbor search method according to claim 7, wherein the k-nearest neighbor search executed in the database management system is describable by one of a query language and function that takes a coordinate column name, the query point, the query number, the attribute information and the maximum processing time of a table which becomes a search target as arguments.

11. The k-nearest neighbor search method according to claim 2, wherein:

the initial setting manager sets the query point, the query number, attribute information and an interruption condition as search condition;

the point distance calculator records only points matching the attribute information of the search conditions in the point manager;

even in a situation where the query number is not reached, the search processing is interrupted if the interruption condition is satisfied; and

the result manager obtains up to k points matching the attribute information from the database management system.

12. The k-nearest neighbor search method according to claim 11, wherein:

the interruption condition is described by a query distance indicating a maximum distance of points which become a search result;

the region distance calculator records only information on divided points having distances equal to or shorter than the query distance in the region manager;

the point distance calculator records only information on points having distances equal to or shorter than the query distance in the point manager; and

the result manager is accordingly capable of obtaining up to k nearest points to the query point that match the attribute information and have distances equal to or shorter than the query distance from the database management system.

13. The k-nearest neighbor search method according to claim 11, wherein:

the interruption condition is described by maximum processing time indicating maximum time expended for the search processing;

the search processing is interrupted when an elapsed execution time of the search processing becomes equal to the maximum processing time; and

the result manager obtains up to k nearest points to the query point that match the attribute information and have distances equal to or shorter than the query distance from the database management system.

14. The k-nearest neighbor search method according to claim 1, wherein the calculating the distance between the query point and the child region of the nearest region comprises obtaining, for the distance between the query point and the child region, a distance between the query point and a point nearest to the query point among points on a boundary line of the child region as a region distance, and setting the region distance to 0 when the child region includes the query point.

15. The k-nearest neighbor search method according to claim 14, wherein the obtaining the nearest region to the region comprises storing, as pieces of information on the region, a region pointer indicating a storing position of information on one of a region and a child region in the database management system and the region distance of the region, selecting information on the nearest region which becomes a judging target of the judging which of the lowest branch and the intermediate branch of the spatial index the nearest region is, and then deleting the region.

16. The k-nearest neighbor search method according to claim 15, wherein the region manager manages the information on the divided regions by a heap structure, and sets a heap condition for the heap structure that a region distance of a divided region corresponding to a node of the heap structure is equal to or shorter than a region distance of a divided region corresponding to a child of the node.

17. The k-nearest neighbor search method according to claim 16, wherein the k-nearest neighbor search executed in the database management system is describable by one of a query language and function that takes a coordinate column name, the query point, the query number and maximum processing time of a table which becomes a search target as arguments.

18. The k-nearest neighbor search method according to claim 14, wherein the calculating the distance between the query point and the point included in the nearest region comprises defining a shortest distance between the query point and the point as the point distance, and calculating the point distance.

19. The k-nearest neighbor search method according to claim 18, wherein the storing the information on the point which has become the calculation target of the point distance comprises deleting, in a case of storing, as pieces of information on the point for up to k points, a pointer indicating a storage position of the point in the database management system and a point distance, and storing a point for which point distance calculation is finished when pieces of information on k points are already stored, a piece of information on a point having a longest point distance among k+1 points, and storing pieces of information on remaining k points.

20. The k-nearest neighbor search method according to claim 18, wherein the finishing the search processing comprises finishing the search processing when a shortest region distance among regions stored in the storing the information on the region which has become the calculation target of the region distance is longer than a longest point distance among points stored in the storing the information on the point which has become the calculation target of the point distance.

21. The k-nearest neighbor search method according to claim 20, wherein the point manager manages the information on the points by a heap structure, and sets a heap condition for the heap structure that a point distance of a point corresponding to a node of the heap structure is equal to or longer than a point distance of a point corresponding to a child of the node.

22. The k-nearest neighbor search method according to claim 21, wherein the termination checker finishes the search processing when a region distance of a divided point positioned in a root of the heap structure of the region manager is longer than a point distance of a point positioned in a root of the heap structure of the point manager.

23. The k-nearest neighbor search method according to claim 22, wherein the k-nearest neighbor search executed in the database management system is describable by one of a query language and function that takes a coordinate column name, the query point, the query number, the attribute information and a query distance of a table which becomes a search target as arguments.

24. The k-nearest neighbor search method according to claim 21, wherein the k-nearest neighbor search executed in the database management system is describable by one of a query language and function that takes a coordinate column name, the query point, the query number, attribute information and an interruption condition of a table which becomes a search target as arguments.

25. A non-transitory storage medium storing a program for receiving a query point which becomes a search start point and searching for a query number k of nearest points to the query point in a database including multidimensional points and a spatial index where a region including the points is divided into a plurality of regions to set child regions in the region, and a tree structure including branches and leaf nodes is created from the points and the region, and a database management system for managing the database,

the program controlling a computer to execute:

setting the query point and the query number as search conditions;

judging which of a lowest branch and an intermediate branch of the spatial index a nearest region to the query point is;

calculating, when the nearest region is judged to be the intermediate branch having a child region, a distance between the query point and the child region of the nearest region as a region distance;

storing information on a region which has become a calculation target of the region distance to obtain a nearest region to the region;

calculating, when a result of the judging which of the lowest branch and the intermediate branch shows that the nearest region is the lowest branch having no child region, a distance between the query point and a point included in the nearest region as a point distance;

storing information on the point which has become a calculation target of the point distance;

repeating, until the search conditions are satisfied, search processing from the judging which of the lowest branch and the intermediate branch of the spatial index the nearest region to the query point is to the storing the information on the point which has become the calculation target of the point distance, and finishing the search processing when the search conditions are satisfied; and

obtaining, after the finishing the search processing, a record of the stored point as a search result from the database management system.

26. A k-nearest neighbor search device for receiving a query point which becomes a search start point and searching for a query number k of nearest points to the query point, comprising:

a processor for performing calculation processing;

a storage device for storing information;

a database including multidimensional points and a spatial index where a region including the points is divided into a plurality of regions to set child regions in the region and a tree structure including branches and leaf nodes is created from the points and the region;

a database management system for managing the database;

an initial setting manager for setting the query point and the query number as search conditions by the processor;

a lowest branch checker for judging which of a lowest branch and an intermediate branch of the spatial index a nearest region to the query point is by the processor;

a region distance calculator for calculating, when the nearest region is judged to be the intermediate branch having a child region, a distance between the query point and the child region of the nearest region as a region distance by the processor;

a region manager for storing information on a region which has become a calculation target of the region distance to obtain a nearest region to the region by the processor;

a point manager for calculating, when a result of the judging which of the lowest branch and the intermediate branch shows that the nearest region is the lowest branch having no child region, a distance between the query point and a point included in the nearest region as a point distance by the processor;

a point distance calculator for storing information on the point which has become a calculation target of the point distance in the storage device by the processor;

a termination checker for repeating, until the search conditions are satisfied, search processing from the lowest branch checker to the point manager, and finishing the search processing when the search conditions are satisfied by the processor; and

a result manager for obtaining, after the finishing the search processing, a record of the stored point as a search result from the database management system by the processor.

27. The k-nearest neighbor search device according to claim 26, wherein:

the initial setting manager sets the query point, the query number, and an interruption condition as search conditions;

the termination checker interrupts, even in a situation where the query number is not reached, the search processing when the interruption condition is satisfied; and

the result manager obtains up to k nearest points to the query point.

28. The k-nearest neighbor search device according to claim 27, wherein:

the interruption condition includes any one of a query distance indicating a longest distance from the query point to the point and maximum processing time indicating maximum time expended for the search processing;

if the interruption condition is the query distance,

the region distance calculator stores only information on divided regions having distances equal to or shorter than the query distance in the region manager;

the point distance calculator stores only information on points having distances equal to or shorter than the query distance in the point manager; and

the result manager obtains up to k nearest points to the query point that have distances equal to or shorter than the query distance from the database management system; and

if the interruption condition is the maximum processing time,

the termination checker interrupts the search processing when elapsed time of the search processing becomes equal to the maximum processing time; and

the result manager obtains up to k nearest points to the query point from the database management system.

29. The k-nearest neighbor search method according to claim 28, wherein the k-nearest neighbor search executed in the database management system is describable in one of a query language and function that takes a coordinate column name, the query point, the query number and a query distance of a table which becomes a search target as arguments.

30. The k-nearest neighbor search method according to claim 27, wherein the k-nearest neighbor search executed in the database management system is describable in one of a query language and function that takes a coordinate column name, the query point, the query number and an interruption condition of a table which becomes a search target as arguments.

31. The k-nearest neighbor search method according to claim 26, wherein the k-nearest neighbor search executed in the database management system is describable in one of a query language and function that takes a coordinate column name, the query point, the query number and attribute information of a table which becomes a search target as arguments.