Method of searching a set of real numbers for a nearest neighbor

摘要

A method of searching real numbers x[1] to x[n] for a nearest neighbor to a query point comprises: 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 comprises a series of buckets. The buckets respectively correspond to small one-dimensional spaces defined by dividing a one-dimensional space between a minimum real number x[1] and a maximum real number x[n] at regular intervals. Each of the buckets comprises 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 bucket further comprises data about the bucket index of a last filled bucket, the last filled bucket defined as a bucket whose bucket size is not zero and whose bucket index is closest to that of the concerned bucket. The search phase comprises the steps of: locating one of the buckets in which the query point q falls; checking the bucket size of the located bucket whether the bucket size thereof is zero or not; and searching the nearest neighbor by the use of the data in the bucket.