METHOD OF SEARCHING NEAREST NEIGHBOR VALUE OF QUERY POINT FROM ARBITRARY SET OF REAL NUMBERS

摘要

PPROBLEM TO BE SOLVED: To search the nearest neighbor value of a query point from an arbitrary set of real members at high speed. PSOLUTION: A method of searching the nearest neighbor value to a query point q from the a set of real numbers (x(1), x(2), x(3), ... x(n)) includes: a step for preparing a database for search and a step for searching the database for search. The database for search comprises a series of buckets obtained by dividing the section (x(1) to x(n)) of the set of real numbers into m buckets without any space and at equal intervals. Each bucket stores a bucket number and a bucket size being the number of real numbers included in the bucket. Each bucket stores a last filled bucket whose bucket size is not zero and which shows the bucket number of a bucket that is close to the concerned bucket. The search step calculates buckets to which the query point q belongs, and calculates a nearest neighbor value from the inside of the bucket when the bucket size of the bucket is not zero. It calculates a nearest neighbor value from the last filled bucket when the bucket size is zero. PCOPYRIGHT: (C)2011,JPO&INPIT