For fast ε-similarity search, various index structures have been proposed. Yi et al. proposed a concept multi-modality support and suggested inequalities by which ε-similarity search by L1, L2 and L∞, norm can be realized. We proposed an extended inequality which allows us to realize ε-similarity search by arbitrury Lp norm using an index based on Lq 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 Lp 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 ε-similarity search by arbitrary Lp 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 Lp norm is realized and the index structure has good search performance. © 2007 IEEE.