A generation device according to the subject application includes an acquiring unit and a generating unit. The acquiring unit acquires multiple pieces of vector information that correspond to each search target during the proximity search. The generating unit generates multiple pieces of centroid information, in which each piece of vector information is related in accordance with a distance for vector quantization, based on multiple pieces of vector information acquired by the acquiring unit such that a difference in the number of pieces of vector information related to each piece of centroid information falls within a predetermined value.