mm-GNAT: index structure for arbitrary Lp norm

For fast epsiv-similarity search, various index structures have been proposed. Yi et at. proposed a concept multi-modality support and suggested inequalities by which epsiv-similarity search by L₁, L₂ and L_infin norm can be realized. We proposed an extended inequality which allows us to realize epsiv-similarity search by arbitrary L_p norm using an index based on L_q norm. In these investigations a search radius of a norm is converted into that of other norm. In this paper, we propose an index structure which allows search by arbitrary L_p norm, called mm-GNAT (multi-modality support GNAT), without extending search radius. The index structure is based on GNAT (geometric near-neighbor access tree). We show that epsiv-similarity search by arbitrary L_p norm is realized on mm-GNAT. In addition, we performed search experiments on mm-GNAT with artificial data and music data. The results show that the search by arbitrary L_p norm is realized and the index structure has good search performance.