摘要：In order to be able to perform multimedia searches (likesounds, videos, images, etc.) we have to use data struc-tures like the Spatial Approximation Tree (SAT). Thisstructure is a nice example of a tree structure in whichwell-known tricks for tree parallelization simply do notwork. It is too sparse, unbalanced and its performance istoo dependent on the work-load generated by the queriesbeing solved by means of searching the tree. The com-plexity measure is given by the number of distances com-puted to retrieve those objects close enough to the query.In this paper we examine some alternatives to parallelizethis structure through the MPI library and the BSPpub li-brary
