Nearest-neighbor search (NN-search) plays a key role for content-based retrieval. But NN-search over high-dimensional features is of linear complexity and query response times is not satisfactory for large collections of images. We have investigated parallel NN-search in a Network of Workstations (NOW) based on the VA-File. We have identified various design alternatives for such a search engine and have evaluated them. Because of the scan-based nature of the VA-File, one might expect an improvement almost linear in the number of components. But the best speedup we have observed is by 30 with only three components. The effect is due to the elimination of the IO-bottleneck. From another perspective, our solution provides interactive-time similarity search, i.e. a search through 1 GB feature data lasts about one second in a NOW with three components.