Patent ID: 8271518

Claim:
A nearest neighbor search method of searching a set of real numbers x[i] (i: 1 to n) for a nearest neighbor to a query point q, comprising: a construction phase in which a database of the real numbers x[i] (i: integers from 1 to n, assigned in ascending order of the real numbers) is prepared in a main memory unit of a computing device; a search phase in which the computing device searches the nearest neighbor to the query point q by the use of the database, wherein: 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, whereby the number of the buckets and the number of the small one-dimensional spaces are the same integral number m; the buckets have unique bucket indexes from the first bucket B[1] to the last bucket B[m]; each of the buckets comprises data about real number(s) falling in one of the small one-dimensional spaces corresponding to the bucket concerned; each of the buckets further comprises data about its bucket size, the bucket size defined by the number of real number(s) falling in one of the small one-dimensional spaces which corresponds to the bucket concerned; each of the buckets excepting the first bucket B[1] 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; and the search phase comprises: a first step of locating one of the buckets corresponding to one of the small one-dimensional spaces in which the query point q falls; a second step of checking the bucket size of the located bucket whether the bucket size thereof is zero or not; and a third step of searching the nearest neighbor by the use of the data of real number(s) included in: the located bucket if the checked bucket size is not zero; or a bucket with a bucket index equal to the bucket index of the last filled bucket included in the located bucket if the checked bucket size is zero.