| In interactive web-based applications, service discovery and recommendation requires matching known or estimated preferences of system queries with properties of available services. To generate accurate recommendations, the properties of each query must be matched with those of existing services as accurately as possible. The available data is very large, and the matching must be computed in real time. Existing heuristics are quite ineffective.; We introduce novel algorithms that use "positive" nearest-neighbour matching, that is they find neighbours whose attribute values exceed those of the query. The algorithms use singular value decomposition as a dimension-reduction technique, and match in a collection of lower-dimensional spaces. The singular value decomposition approach requires careful application to work effectively in this setting.; Performance and quality of matches found are measured using an extensive experimental model, tested over a wide range of datasets from application in computational grids, publish/subscribe paradigms, mobile environments, and recommender systems. We show that reasonable matches can be found in time O (m log n), using O (nm) storage space, where n is the number of available services and m the number of attributes for which queries may express preferences. This is in contrast to "approximate nearest neighbour" techniques that require either time or storage exponential in m. |
