Multimedia web searches using static SAT

Abstract

In this paper we describe the parallelization of a data structure used to perform multimedia web searches. Multimedia Web Engines have not been deeply studied and is a challenging issue. The data structure selected to index the queries is the Spatial Approximation Tree, where the complexity measure is given by the number of distance computed to retrieve those objects close enough to the query. We present a parallel method for load balancing the work performed by the processors. The method can adapt itself to the changes of the workload produced by the user queries. Empirical results with di fferent kind of databases show e fficient performance in a real cluster of PC. The algorithm is designed with the bulk-synchronous model of parallel computing