A parallel search algorithm for the SAT

• Autores: Graciela Verónica Gil Costa, Alicia Marcela Printista, Nora Susana Reyes, Mauricio Marin Caihuan
• Localización: Journal of Computer Science and Technology, ISSN-e 1666-6038, Vol. 5, Nº. 4, 2005 (Ejemplar dedicado a: Sixteenth Issue), págs. 299-304
• Idioma: inglés
• Enlaces
  • Texto completo
• Resumen

  • 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.

• Referencias bibliográficas
  • References [1] D. Arroyuelo, F. Muñoz, G. Navarro, and N. Reyes. Memory-adaptative dynamic spatial approximation trees. In Proceedings of...
  • [2] C. Bohm, S.Berchtold, and D. Kein. Searching in highdimensional spaces: Index structures for improving the performance of multimedia databases....
  • [3] 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.
  • [4] V. Gaede and O. Gunther. Multidimensional access methods. ACM Computing Surveys, 30(2):170-321,1998.
  • [5] M. Marín and G. Navarro. Distributed query processing using suffix arrays. In Proceedings of the 10th international Symposium on String...
  • [6] G. Navarro. Searching in metric spaces by spatial approximation. The Very Large Databases Journal (VLDBJ), 11(1):28-46, 2002.
  • [7] G. Navarro and N. Reyes. Fully dynamic spatial approximation trees. In Proceedings of the 9th International Symposium on String Processing...
  • [8] G. Navarro and N. Reyes. Improved deletions in dynamic spatial approximation trees. In Proc. of the XXIII International Conference of...
  • [9] Snir M., Otto S., Huss-Lederman S., Walker D., Dongarra J. MPI: The complete Reference, Cambridge MA: MIT Press, 1996.
  • [10] L. Valiant. A Bridging Model for Parallel Computation. Communications of the ACM, Vol. 33, Pp 103-111, 1990.
  • [11] WWW.BSP and Worldwilde Standard, http://www.bspworldwide.org
  • [12] WWW.BSP PUB Library at Paderborn Univertity,