Rank-order service providers based on desired service properties

• US 8,185,536 B2
• Filed: 01/30/2009
• Issued: 05/22/2012
• Est. Priority Date: 01/30/2009
• Status: Active Grant

• Current Assignee: The Conundrum IP LLC (UiPath Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Basu, Sujoy, Singhal, Sharad, Graupner, Sven, Ozonat, Mehmet Kivanc, Young, Donald E.
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US12/363,698
• Publication Number:
  US 20100198840A1
• Time in Patent Office: 1,208 Days
• Field of Search: 707/737, 707/777, 707/754, 707748- 74
• US Class Current: 707/749
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing

Abstract

Candidate service providers for a desired service are ranked. Terms describing service requirements for a desired service are determined. Service capability documents describing the services of the candidate service providers are determined using the terms describing the service requirements. Using singular value decomposition (SVD) and a metric, similarities between the terms describing the service requirements and the service capability documents are determined. The candidate service providers are ranked based on the similarities.

Claims

1. A computer readable medium including code that when executed by a computer system performs a method of determining a ranking of candidate service providers, the method comprising:

determining terms describing service requirements for a desired service;

determining service capability documents describing services of candidate service providers using the terms describing the service requirements for the desired service;

using singular value decomposition (SVD) and a metric to determine similarities between the terms describing the service requirements and the service capability documents; and

ranking the candidate service providers based on the similarities.

2. The computer readable medium of claim 1, wherein using SVD and a metric to determine similarities between the terms describing the service requirements and the service capability documents further comprises:

determining a term-by-document matrix from the service capability documents, wherein a dimension of the matrix is t number of terms by d number of documents;

using SVD to determine matrices T, S, and D^t, wherein S is a diagonal matrix of singular values ordered in descending order, and T and D^t are matrices of eigen vectors; and

selecting top k singular values from S, wherein k is a number of the top k singular values;

determining a matrix T<sub>t×

k</sub> containing first k columns of T; and

determining a matrix S<sub>k×

k</sub> containing an intersection of the first k rows and the first k columns of S.

3. The computer readable medium of claim 2, wherein using SVD and a metric to determine similarities between the terms describing the service requirements and the service capability documents further comprises:

determining a vector of terms for each of the service capability documents from the matrix;

determining a vector of terms from the terms describing the service requirements;

mapping the vector of terms for each of the service capability documents by determining a product of D and S, wherein individual rows of the product of D and S are the mappings; and

mapping the vector of terms for the service requirements to a factor space by multiplying its transpose by the matrix T<sub>t×

k</sub>.

4. The computer readable medium of claim 3, wherein using SVD and a metric to determine similarities between the terms describing the service requirements and the service capability documents the method further comprises:

using the metric to compare the mapped vectors of each of the service capability documents to the mapped vector for the term vector including the terms describing the service requirements; and

based on the comparisons, determining the similarities between the terms describing the service requirements and the service capability documents.

5. The computer readable medium of claim 4, wherein the metric is a distance metric used to measure distances between the vectors in the factor space.

6. The computer readable medium of claim 3, wherein the factor space is a lower dimensional space than a space having a number of dimensions equal to the t number of terms in the matrix and a space having a number of dimensions equal to the d number of documents in the matrix.

7. The computer readable medium of claim 6, wherein the distance metric is cosine similarity.

8. The computer readable medium of claim 1, wherein the metric is associated with frequency of terms.

9. The computer readable medium of claim 1, wherein determining terms describing service requirements for a desired service further comprises:

receiving a service description document including the service requirements for the desired service; and

extracting the terms describing the service requirements which are determined to be relevant to the service requirements.

10. The computer readable medium of claim 1, wherein determining service capability documents describing services of candidate service providers further comprises:

inputting the terms describing the service requirements into an Internet search engine; and

determining the service capability documents from search results of the Internet search engine running a query including the terms describing the service requirements.

11. The computer readable medium of claim 10, wherein the method further comprises:

extracting terms from the service capability documents determined to be relevant to describing services of the service capability documents; and

using the extracted terms from the service capability documents and the terms describing the service requirements for the SVD and the ranking of the candidate service providers.

12. The computer readable medium of claim 11, wherein the method further comprises:

normalizing the service capability documents into a single document format prior to the extracting of the terms from the service capability documents; and

using the normalized service capability documents for the extracting of the terms from the service capability documents.

13. A computer readable medium including code that when executed by a computer system performs a method of determining a ranking of candidate service providers, the method comprising:

determining terms describing service requirements for a desired service;

determining service capability documents describing services of candidate service providers using the terms describing the service requirements for the desired service;

determining a matrix from the terms describing the service requirements and from terms extracted from the service capability documents;

using SVD to decompose the matrix, wherein the matrix decomposed using represents a factor space;

mapping vectors of terms describing the service capability documents and a vector of the terms describing the service requirements to the factor space;

determining similarities between each of the service capability documents and the service requirements based on a metric associated with the mapped vectors; and

ranking the candidate service providers based on the similarities.

14. The computer readable medium of claim 13, wherein is a term-by-document matrix and a dimension of the matrix is t number of terms by d number of documents, the method further comprising:

using SVD to determine matrices T, S, and D^t, wherein S is a diagonal matrix of singular values ordered in descending order, and T and D^t are matrices of eigen vectors; and

selecting top k singular values from S, wherein k is a number of the top k singular values;

determining a matrix T<sub>t×

k</sub> containing first k columns of T; and

determining a matrix S<sub>k×

k</sub> containing an intersection of the first k rows and the first k columns of S.

15. The computer readable medium of claim 14, wherein mapping vectors of terms further comprises:

mapping the vector of terms for each of the service capability documents by determining a product of D and S, wherein individual rows of the product of D and S are the mappings; and

mapping the vector of terms for the service requirements to a factor space by multiplying its transpose by the matrix T<sub>t×

k</sub>.

16. The computer readable medium of claim 13, wherein the metric is a distance metric used to measure distances between the vectors in the factor space.

17. The computer readable medium of claim 16, wherein the distance metric is cosine similarity.

18. The computer readable medium of claim 13, wherein the factor space is a lower dimensional space than a space having a number of dimensions equal to the t number of terms in the matrix and a space having a number of dimensions equal to the d number of documents in the matrix.

19. A computer system comprising:

an interface receiving a set of service description documents; and

one or more processors executing code to perform a method including

determining terms describing service requirements for a desired service, wherein the service capability documents describe services of candidate service providers and were identified using the terms describing the service requirements for the desired service;

using singular value decomposition (SVD) and a metric to determine similarities between the terms describing the service requirements and the service capability documents; and

ranking the candidate service providers based on the similarities.

20. The computer system of claim 19, wherein using singular value decomposition (SVD) and a metric to determine similarities between the terms describing the service requirements and the service capability documents further comprises:

determining a matrix from the terms describing the service requirements and from terms extracted from the service capability documents;

using SVD to decompose the matrix, wherein the matrix decomposed using represents a factor space; and

mapping vectors of terms describing the service capability documents and a vector of the terms describing the service requirements to the factor space, wherein the similarities between the terms describing the service requirements and the service capability documents is determined from a comparison of the mapped vectors using the metric.