A parallel search algorithm for the SAT
Keywords:SAT, metric spaces, searches, MPI, BSP, distances evaluations
In order to be able to perform multimedia searches (like sounds, videos, images, etc.) we have to use data structures like the Spatial Approximation Tree (SAT). This structure is a nice example of a tree structure in which well-known tricks for tree parallelization simply do not work. It is too sparse, unbalanced and its performance is too dependent on the work-load generated by the queries being solved by means of searching the tree. The complexity measure is given by the number of distances computed to retrieve those objects close enough to the query. In this paper we examine some alternatives to parallelize this structure through the MPI library and the BSPpub library.
 C. Bohm, S.Berchtold, and D. Kein. Searching in highdimensional spaces: Index structures for improving the performance of multimedia databases. ACM Computing Surveys, 33(3):322-373,2001.
 E. Ch´avez and G. Navarro and R. Baeza-Yates and J.L. Marroquin. Searching in Metric Spaces. ACM Computing Surveys. 33(3):273-321, 2001.
 V. Gaede and O. Gunther. Multidimensional access methods. ACM Computing Surveys, 30(2):170-321,1998.
 M. Marín and G. Navarro. Distributed query processing using suffix arrays. In Proceedings of the 10th international Symposium on String Processing and Information Retrieval (SPIRE 2003), LNCS 2857, pages 311-325. Springer, 2003.
 G. Navarro. Searching in metric spaces by spatial approximation. The Very Large Databases Journal (VLDBJ), 11(1):28-46, 2002.
 G. Navarro and N. Reyes. Fully dynamic spatial approximation trees. In Proceedings of the 9th International Symposium on String Processing and Information Retrieval (SPIRE 2002), LNCS 2476, pages 254-270. Springer, 2002.
 G. Navarro and N. Reyes. Improved deletions in dynamic spatial approximation trees. In Proc. of the XXIII International Conference of the Chilean Computer Science Society (SCCC’09), pages 13-22, IEEE CS Press, 2003.
 Snir M., Otto S., Huss-Lederman S., Walker D., Dongarra J. MPI: The complete Reference, Cambridge MA: MIT Press, 1996.
 L. Valiant. A Bridging Model for Parallel Computation. Communications of the ACM, Vol. 33, Pp 103-111, 1990.
 WWW.BSP and Worldwilde Standard, http://www.bspworldwide.org
 WWW.BSP PUB Library at Paderborn Univertity,