Nearest neighbor search method

摘要

A method of searching real numbers for a nearest neighbor to a query point includes a construction phase in which a database of the real numbers is prepared; and a search phase in which the nearest neighbor is searched by the use of the database. The database includes a series of buckets that respectively correspond to small one-dimensional spaces defined by dividing a one-dimensional space between a minimum real number and a maximum real number at regular intervals. The buckets include data about real number(s) falling in one of the small one-dimensional spaces corresponding to the bucket concerned, and the number of the real number(s). The search phase includes locating one of the buckets in which the query point falls; checking the bucket size of the located bucket whether the bucket size thereof is zero; and searching the nearest neighbor by the use of the data in the bucket.