Large-Scale Resource Selection in Grids

Abstract. Grid resource selection requires matching job requirements to available resources. This is a difficult problem when the number of attributes for each resource is large. We present an algorithm that uses the Singular Value Decomposition to encode each resource’s properties by a single value. Jobs are matched by using the same encoding to produce a value that can be rapidly compared to those of the resources. We show that reasonable matches can be found in time O(m log n) where n is the number of resources and m the number of attributes for which a job might have requirements. This is in contrast to “approximate nearest neighbor ” techniques which require either time or storage exponential in m