Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
A parallel search algorithm for the SAT
Keywords:
SAT, metric spaces, searches, MPI, BSP, distances evaluationsAbstract
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.
Downloads
Download data is not yet available.
References
[1] D. Arroyuelo, F. Muñoz, G. Navarro, and N. Reyes. Memory-adaptative dynamic spatial approximation trees. In Proceedings of the 10th International Symposium on String Processing and Information Retrieval (SPIRE 2003), LNCS 2857, pages 360-368. Springer, 2003.
[2] 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.
[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 Processing and Information Retrieval (SPIRE 2003), LNCS 2857, pages 311-325. Springer, 2003.
[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 and Information Retrieval (SPIRE 2002), LNCS 2476, pages 254-270. Springer, 2002.
[8] 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.
[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,
[2] 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.
[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 Processing and Information Retrieval (SPIRE 2003), LNCS 2857, pages 311-325. Springer, 2003.
[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 and Information Retrieval (SPIRE 2002), LNCS 2476, pages 254-270. Springer, 2002.
[8] 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.
[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,
Downloads
Published
2005-12-01
How to Cite
Gil Costa, G. V., Printista, A. M., Reyes, N. S., & Marin Cahiuan, J. M. (2005). A parallel search algorithm for the SAT. Journal of Computer Science and Technology, 5(04), p. 299–304. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/851
Issue
Section
Original Articles
