Nowadays the need to process lots of complex multimedia databases is more frequent. Recent investigations such as MAM-SOM* and SAM-SOM* families propose the combination of Self-Organizing Maps (SOM) with Access Methods for a faster similarity information retrieval. In this investigation we present experimental results using recent Access Methods such as Slim-Tree and Omni-Sequential that show the improvement acquired by these techniques and their properties in contrast with a traditional SOM network, observing up to 90% of performance improvement. © 2006 IEEE.