K-nearest neighbor search method, k-nearest neighbor search program, and k-nearest neighbor search device
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
31 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
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. - View Dependent Claims (27, 28, 29, 30, 31)
-
Specification