We address a problem of improving the search efficiency of range queries based on Manhattan distance. To this end, we propose a new pivot generation method (the PGM method) formulated as an iterative algorithm, where its convergence is guaranteed within a finite number of iterations. In our experiments using three databases of hand-written characters, newspaper articles and book reviews, we confirmed that our proposed method overcomes a representative conventional method (the BNC method) whose pivots are limited to objects in the datasets, in terms of improvements of objective function values, computation times of pivot selection or generation, the range query performance with arbitrary range setting, and qualitative comparison of visualization results. Moreover, we experimentally show that the PGM method works much better than the BNC method in the case of sparse high-dimensional objects, rather than the case of dense low-dimensional ones.
展开▼