System and method to work with multiple pair-wise related entities

• US 20070255707A1
• Filed: 04/25/2007
• Published: 11/01/2007
• Est. Priority Date: 04/25/2006
• Status: Abandoned Application

• Current Assignee: Data Relation Limited
• Original Assignee: Data Relation Limited
• Inventors: Ankaoua, Philippe, Tresser, Yuval, Tresser, Ygael, Rockmore, Daniel, Cohen, Erik
• Application Number:
  US11/790,489
• Publication Number:
  US 20070255707A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/288 Entity relationship models
• CPC Class Codes: G06F 16/337 Profile generation, learning or modification
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: H04N 21/4668 for recommending content, e.g. movies

Abstract

The invention uses pair-wise relations such as dissimilarity, similarity or correlation to identify related items by translating the relations into a set of points in a geometric space, where each point in the set of points represents an item, and where the distance between any two points directly corresponds to the dissimilarity value of the two items represented by the two points. A family of graphs is computed from the Voronoï diagram for the set of points. This family of graphs may be used for a variety of applications, including recommendation systems. For some applications, clustering may be used to assist in visualizing and identifying relations among items. In the case of recommendation systems, graphs reflecting customer preferences are clustered to identify customers with similar tastes.

Claims

1. A computer-implemented method for visualization of relations among data items, comprising:

storing pair-wise relation values in a database, each of the pair-wise relation values representing a relation between two of the data items, such that the pair-wise relation values have a partial ordering;

translating the data items to a set of points in a geometric space, each point corresponding to a data item, such that the partial ordering of the pair-wise relation values is preserved by a distance metric on the geometric space;

computing a one-parameter family of graphs on the set of points, such that a graph is computed for a value of a parameter, the value of the parameter being chosen according to pre-defined performance criteria;

displaying at least one member of the one-parameter family of graphs to a user, where the at least one member is chosen according to the performance criteria.

2. The method of claim 1, where the one-parameter family of graphs is computed such that for two values of the parameter the graph computed for the higher of the two values of the parameter contains the graph computed for the lower of the two values of the parameter, for a first value of the parameter the graph computed for the first value of the parameter is a Gabriel graph for the set of points, for a second value of the parameter the graph computed for the second value of the parameter is a Delone graph for the set of points, the first value of the parameter being less than the second value of the parameter.

3. The method of claim 1, where the pair-wise relation values express at least one of dissimilarity, similarity, or correlation between data items.

4. The method of claim 1, where the geometric space is Euclidean.

5. The method of claim 4, where the dimension of a Euclidean space is chosen according to a criterion chosen from the list including the ability to visualize the displayed graph and the closeness of the approximation to isotony in the translating of the data items.

6. The method of claim 1, where the step of translating the data items to a set of points in a geometric space further comprises performing one of multi-dimensional scaling or structural similarity analysis on the pair-wise relation values.

7. The method of claim 1, the step of computing the one-parameter graph family further comprising the steps of:

computing Delone spheres, the Delone sphere being a sphere of dimension one less than the dimension of the geometric space that is circumscribed to points in a defining subset of points from the set of points, a size of the defining subset of points being one plus the dimension of the geometric space, the Delone sphere being computed such that no point from the set of points other than the defining subset of points is contained in a closure of a ball bounded by the Delone sphere;

computing a Delone graph by identifying, for each Delone sphere, each edge such that endpoints of the edge are contained in the defining subset of points for the Delone sphere;

computing a Gabriel graph by identifying each edge of the Delone graph, endpoints of the edge being a first point from the set of points and a second point from the set of points, the first and second points defining a zero-dimensional sphere such that no other points from the set of points are on a closure of an interior of a ball of dimension equal to the dimension of the geometric space, the ball having the same center and same radius as the zero-dimensional sphere;

selecting intermediate subsets of points, where, for each Delone sphere, the intermediate subset of points is a subset of the defining subset of points for the Delone sphere such that a size of the intermediate subset of points is a whole number h+1 where h is greater than 1 and less than the dimension of the geometric space, the intermediate subset of points being selected if a closed ball of the same dimension as the geometric space, the closed ball having the same center and the same radius as a sphere with dimension h−

1 circumscribed to the points in the proper subset of the defining subset of points, contains no point from the set of points other than the points in the intermediate subset of points;

for each edge in the Delone graph, computing the minimal circumscribed sphere for the edge, where the minimal circumscribed sphere is computed by;

choosing a selected intermediate subset such that the selected intermediate subset is contained in the defining subset of points containing the endpoints of the edge, where there is no such selected intermediate subset having smaller size, setting the minimal circumscribed sphere equal to the sphere with dimension h−

1 circumscribed to the points in the selected intermediate subset;

if no such selected intermediate subset exists, setting the minimal circumscribed sphere equal to the Delone sphere for the defining subset of points containing the endpoints of the edge;

for each edge in the Delone graph, computing a distance between a midpoint of the edge and the center of the minimal circumscribed sphere for the edge;

for each edge in the Delone graph, computing a computed ratio of the distance and a length of the edge;

determining the maximal computed ratio over all edges in the Delone graph; and

for a parameter value, computing a graph for the parameter value by adding to the computed graph each edge from the Delone graph such that a ratio of the computed ratio for the edge and the maximal computed ratio is less than or equal to the parameter value.

8. The method of claim 1, further comprising, before the step of displaying, clustering the data points on at least one graph in the one-parameter family of graphs.

9. The method of claim 8, where the displayed graphs are the graphs on which clustering has been performed.

10. The method of claim 1, where the data items are nodes in an input graph, the pair-wise relation values being an inverse measure of connectedness between two data items, the pair-wise relation value for the two data items being determined in such a way that the pair-wise relation value for the two data items is directly related to a number of paths between the two data items and lengths of the paths between the two data items.

11. The method of claim 10, where the dimension of the geometric space is 2 and the displayed graph is further chosen such the displayed graph is planar, the displayed graph having an edge between two data items if the two data items are connected by an edge in the input graph.

12. The method of claim 10, where, if no member of the one-parameter graph family is planar, the displayed graph is made so that it can be represented on a surface by replacing each crossing with a handle.

13. The method of claim 10, where the input graph represents components of a circuit.

14. The method of claim 1, further comprising providing input pair-wise relation values that are correlations of data items, setting the pair-wise relation value for two data items to the absolute value of the input pair-wise relation value for the two data items, and computing output pair-wise relation values such that for two data items, the output pair-wise relation value of the two data items equals the pair-wise relation value of the two data items if the two data items are connected by an edge in the displayed graph and equals 0 otherwise.

15. The method of claim 14, where the data items represent at least one of prices of securities, prices of commodities, macroeconomic data, or other data used in financial markets.

16. The method of claim 15, where the output pair-wise relation values are used to visualize the overall correlation structure of the data items.

17. The method of claim 15, where the output pair-wise relation values are used to compute prices of derivative securities, the price of the derivative securities depending on the prices of the data items.

18. The method of claim 1, where the pair-wise relation values are pair-wise measures of traffic between two data items, the data items representing one of nodes in a network or entities in a market.

19. A computer-implemented method for recommending items to customers comprising:

storing pair-wise relation values for each customer in a first database, each of the pair-wise relation values representing a relation between two of the data items determined by the customer, such that the pair-wise relation values have a partial ordering;

performing for each customer the steps of;

translating the set of pair-wise relation values into a set of points in a geometric space, each point corresponding to an item, such that the partial ordering of the pair-wise relation values is preserved by a distance metric on the geometric space;

computing a one-parameter family of graphs on the set of points, such that a graph is computed for a value of a parameter, the value of the parameter being chosen according to pre-defined performance criteria;

clustering customers, where distance between two customers is the distance between the two customers identified graphs; and

providing a recommendation means for recommending items to customers based on the computed clusters of customers.

20. The method of claim 19, the recommendation means comprising, upon a customer request for recommended items, performing the steps of:

creating a list of items, where the items are preferred by the other customers in the customer'"'"'s cluster, such that the customer has no known preference for the items; and

sending the list of items to the customer.

21. The method of claim 19, the recommendation means comprising, upon a customer request for recommended items, displaying clusters to which the customer belongs in such a way as to allow browsing of items preferred by customers in the displayed clusters.

22. The method of claim 19, where the one-parameter family of graphs is computed such that for two values of the parameter the graph computed for the higher of the two values of the parameter contains the graph computed for the lower of the two values of the parameter, for a first value of the parameter the graph computed for the first value of the parameter is a Gabriel graph for the set of points, for a second value of the parameter the graph computed for the second value of the parameter is a Delone graph for the set of points, the first value of the parameter being less than the second value of the parameter.

23. The method of claim 19, where the pair-wise relation values express at least one of dissimilarity, similarity, or correlation between items.

24. The method of claim 19, where the geometric space is Euclidean.

25. The method of claim 24, where the dimension of a Euclidean space is chosen according to a criterion chosen from the list including the ability to visualize the displayed graph and the closeness of the approximation to isotony in the translating of the data items.

26. The method of claim 19, where the step of translating the data items to a set of points in a geometric space further comprises performing one of multi-dimensional scaling or structural similarity analysis on the pair-wise relation values.

27. The method of claim 19, where the items include a first element and a second element, such that a pair-wise relation value between an item and the first element indicates a customer'"'"'s preference for the item and a pair-wise relation value between an item and the second element indicates a customer'"'"'s distaste for the item.

28. The method of claim 19, the step of computing the one-parameter graph family further comprising the steps of:

computing Delone spheres, the Delone sphere being a sphere of dimension one less than the dimension of the geometric space that is circumscribed to points in a defining subset of points from the set of points, a size of the defining subset of points being one plus the dimension of the geometric space, the Delone sphere being computed such that no point from the set of points other than the defining subset of points is contained in a closure of a ball bounded by the Delone sphere;

computing a Delone graph by identifying, for each Delone sphere, each edge such that endpoints of the edge are contained in the defining subset of points for the Delone sphere;

computing a Gabriel graph by identifying each edge of the Delone graph, endpoints of the edge being a first point from the set of points and a second point from the set of points, the first and second points defining a zero-dimensional sphere such that no other points from the set of points are on a closure of an interior of a ball of dimension equal to the dimension of the geometric space, the ball having the same center and same radius as the zero-dimensional sphere;

selecting intermediate subsets of points, where, for each Delone sphere, the intermediate subset of points is a subset of the defining subset of points for the Delone sphere such that a size of the intermediate subset of points is a whole number h+1 where h is greater than 1 and less than the dimension of the geometric space, the intermediate subset of points being selected if a closed ball of the same dimension as the geometric space, the closed ball having the same center and the same radius as a sphere with dimension h−

1 circumscribed to the points in the proper subset of the defining subset of points, contains no point from the set of points other than the points in the intermediate subset of points;

for each edge in the Delone graph, computing the minimal circumscribed sphere for the edge, where the minimal circumscribed sphere is computed by;

choosing a selected intermediate subset such that the selected intermediate subset is contained in the defining subset of points containing the endpoints of the edge, where there is no such selected intermediate subset having smaller size, setting the minimal circumscribed sphere equal to the sphere with dimension h−

1 circumscribed to the points in the selected intermediate subset;

if no such selected intermediate subset exists, setting the minimal circumscribed sphere equal to the Delone sphere for the defining subset of points containing the endpoints of the edge;

for each edge in the Delone graph, computing a distance between a midpoint of the edge and the center of the minimal circumscribed sphere for the edge;

for each edge in the Delone graph, computing a computed ratio of the distance and a length of the edge;

determining the maximal computed ratio over all edges in the Delone graph; and

for a parameter value, computing a graph for the parameter value by adding to the computed graph each edge from the Delone graph such that a ratio of the computed ratio for the edge and the maximal computed ratio is less than or equal to the parameter value.

29. The method of claim 19, where a customer'"'"'s relation values are updated as information is gathered about the customer'"'"'s opinions about items.

30. The method of claim 29, where the steps of translating the set of pair-wise relation values into a set of points in a geometric space, computing a one-parameter family of graphs, choosing a parameter value based on performance criteria, identifying a member of the one-parameter graph family determined by the parameter value, and clustering customers are performed for the customer each time the customer'"'"'s relation values are updated.

31. The method of claim 19, where the items are one of:

pieces of music, collections of music, music genres, musical artists, particular recordings of pieces of music, videos, movies, books, groceries, or webpages.

32. A system for visualization of relations among data items, comprising:

a database for storing pair-wise relation values, each of the pair-wise relation values representing a relation between two of the data items, such that the pair-wise relation values have a partial ordering;

a translation module for translating the data items to a set of points in a geometric space, each point corresponding to a data item, such that the partial ordering of the pair-wise relation values is preserved by a distance metric on the geometric space;

a graph family module for computing a one-parameter family of graphs on the set of points, such that a graph is computed for a value of a parameter, the value of the parameter being chosen according to pre-defined performance criteria;

a display module for displaying at least one member of the one-parameter family of graphs to a user, where the at least one member is chosen according to the performance criteria.

33. The system of claim 32, where the graph family module computes the one-parameter family of graphs such that for two values of the parameter the graph computed for the higher of the two values of the parameter contains the graph computed for the lower of the two values of the parameter, for a first value of the parameter the graph computed for the first value of the parameter is a Gabriel graph for the set of points, for a second value of the parameter the graph computed for the second value of the parameter is a Delone graph for the set of points, the first value of the parameter being less than the second value of the parameter.

34. The system of claim 32, where the pair-wise relation values express at least one of dissimilarity, similarity, or correlation between data items.

35. The system of claim 32, where the geometric space is Euclidean.

36. The system of claim 35, where the translation module chooses the dimension of a Euclidean space according to a criterion chosen from the list including the ability to visualize the displayed graph and the closeness of the approximation to isotony in the translating of the data items.

37. The system of claim 32, where the translation module performs the translating the data items to a set of points in a geometric space by performing one of multi-dimensional scaling or structural similarity analysis on the pair-wise relation values.

38. The system of claim 32, wherein the graph family module computes the one-parameter graph family by:

computing Delone spheres, the Delone sphere being a sphere of dimension one less than the dimension of the geometric space that is circumscribed to points in a defining subset of points from the set of points, a size of the defining subset of points being one plus the dimension of the geometric space, the Delone sphere being computed such that no point from the set of points other than the defining subset of points is contained in a closure of a ball bounded by the Delone sphere;

computing a Delone graph by identifying, for each Delone sphere, each edge such that endpoints of the edge are contained in the defining subset of points for the Delone sphere;

computing a Gabriel graph by identifying each edge of the Delone graph, endpoints of the edge being a first point from the set of points and a second point from the set of points, the first and second points defining a zero-dimensional sphere such that no other points from the set of points are on a closure of an interior of a ball of dimension equal to the dimension of the geometric space, the ball having the same center and same radius as the zero-dimensional sphere;

selecting intermediate subsets of points, where, for each Delone sphere, the intermediate subset of points is a subset of the defining subset of points for the Delone sphere such that a size of the intermediate subset of points is a whole number h+1 where h is greater than 1 and less than the dimension of the geometric space, the intermediate subset of points being selected if a closed ball of the same dimension as the geometric space, the closed ball having the same center and the same radius as a sphere with dimension h−

1 circumscribed to the points in the proper subset of the defining subset of points, contains no point from the set of points other than the points in the intermediate subset of points;

for each edge in the Delone graph, computing the minimal circumscribed sphere for the edge, where the minimal circumscribed sphere is computed by;

choosing a selected intermediate subset such that the selected intermediate subset is contained in the defining subset of points containing the endpoints of the edge, where there is no such selected intermediate subset having smaller size, setting the minimal circumscribed sphere equal to the sphere with dimension h−

1 circumscribed to the points in the selected intermediate subset;

if no such selected intermediate subset exists, setting the minimal circumscribed sphere equal to the Delone sphere for the defining subset of points containing the endpoints of the edge;

for each edge in the Delone graph, computing a distance between a midpoint of the edge and the center of the minimal circumscribed sphere for the edge;

for each edge in the Delone graph, computing a computed ratio of the distance and a length of the edge;

determining the maximal computed ratio over all edges in the Delone graph; and

for a parameter value, computing a graph for the parameter value by adding to the computed graph each edge from the Delone graph such that a ratio of the computed ratio for the edge and the maximal computed ratio is less than or equal to the parameter value.

39. The system of claim 32, further including a clustering module for clustering the data points on at least one graph in the one-parameter family of graphs.

40. The system of claim 39, where the displayed graphs are the graphs on which clustering has been performed.

41. The system of claim 32, where the data items are nodes in an input graph, the pair-wise relation values being an inverse measure of connectedness between two data items, the pair-wise relation value for the two data items being determined in such a way that the pair-wise relation value for the two data items is directly related to a number of paths between the two data items and lengths of the paths between the two data items.

42. The system of claim 41, where the dimension of the geometric space is 2 and the displayed graph is further chosen such the displayed graph is planar, the displayed graph having an edge between two data items if the two data items are connected by an edge in the input graph.

43. The system of claim 41, where, if no member of the one-parameter graph family is planar, the display module makes the displayed graph so that it can be represented on a surface by replacing each crossing with a handle.

44. The system of claim 41, where the input graph represents components of a circuit.

45. The system of claim 32, further comprising providing input pair-wise relation values that are correlations of data items, setting the pair-wise relation value for two data items to the absolute value of the input pair-wise relation value for the two data items, and computing output pair-wise relation values such that for two data items, the output pair-wise relation value of the two data items equals the pair-wise relation value of the two data items if the two data items are connected by an edge in the displayed graph and equals 0 otherwise.

46. The system of claim 45, where the data items represent at least one of prices of securities, prices of commodities, macroeconomic data, or other data used in financial markets.

47. The system of claim 46, where the output pair-wise relation values are used to visualize the overall correlation structure of the data items.

48. The system of claim 46, where the output pair-wise relation values are used to compute prices of derivative securities, the price of the derivative securities depending on the prices of the data items.

49. The system of claim 32, where the pair-wise relation values are pair-wise measures of traffic between two data items, the data items representing one of nodes in a network or entities in a market.

50. A system for recommending items to customers comprising:

a database storing pair-wise relation values for each customer, each of the pair-wise relation values representing a relation between two of the data items determined by the customer, such that the pair-wise relation values have a partial ordering;

a clustering module for clustering customers by performing for each customer;

translating the set of pair-wise relation values into a set of points in a geometric space, each point corresponding to an item, such that the partial ordering of the pair-wise relation values is preserved by a distance metric on the geometric space;

computing a one-parameter family of graphs on the set of points, such that a graph is computed for a value of a parameter, the value of the parameter being chosen according to pre-defined performance criteria;

clustering customers, where distance between two customers is the distance between the two customers identified graphs; and

a recommendation module for recommending items to customers based on the computed clusters of customers.

51. The system of claim 50, the recommendation module, upon receiving a customer request for recommended items, recommending items by:

creating a list of items, where the items are preferred by the other customers in the customer'"'"'s cluster, such that the customer has no known preference for the items; and

sending the list of items to the customer.

52. The system of claim 50, the recommendation module, upon a customer request for recommended items, displaying clusters to which the customer belongs in such a way as to allow browsing of items preferred by customers in the displayed clusters.

53. The system of claim 50, where the one-parameter family of graphs is computed such that for two values of the parameter the graph computed for the higher of the two values of the parameter contains the graph computed for the lower of the two values of the parameter, for a first value of the parameter the graph computed for the first value of the parameter is a Gabriel graph for the set of points, for a second value of the parameter the graph computed for the second value of the parameter is a Delone graph for the set of points, the first value of the parameter being less than the second value of the parameter.

54. The system of claim 50, where the pair-wise relation values express at least one of dissimilarity, similarity, or correlation between items.

55. The system of claim 50, where the geometric space is Euclidean.

56. The system of claim 55, where the clustering module chooses the dimension of a Euclidean space according to a criterion chosen from the list including the ability to visualize the displayed graph and the closeness of the approximation to isotony in the translating of the data items.

57. The system of claim 50, where the clustering module performs the step of translating the data items to a set of points in a geometric space by performing one of multi-dimensional scaling or structural similarity analysis on the pair-wise relation values.

58. The system of claim 50, where the items include a first element and a second element, such that a pair-wise relation value between an item and the first element indicates a customer'"'"'s preference for the item and a pair-wise relation value between an item and the second element indicates a customer'"'"'s distaste for the item.

59. The system of claim 50, the step of computing the one-parameter graph family further comprising the steps of:

computing Delone spheres, the Delone sphere being a sphere of dimension one less than the dimension of the geometric space that is circumscribed to points in a defining subset of points from the set of points, a size of the defining subset of points being one plus the dimension of the geometric space, the Delone sphere being computed such that no point from the set of points other than the defining subset of points is contained in a closure of a ball bounded by the Delone sphere;

computing a Delone graph by identifying, for each Delone sphere, each edge such that endpoints of the edge are contained in the defining subset of points for the Delone sphere;

computing a Gabriel graph by identifying each edge of the Delone graph, endpoints of the edge being a first point from the set of points and a second point from the set of points, the first and second points defining a zero-dimensional sphere such that no other points from the set of points are on a closure of an interior of a ball of dimension equal to the dimension of the geometric space, the ball having the same center and same radius as the zero-dimensional sphere;

selecting intermediate subsets of points, where, for each Delone sphere, the intermediate subset of points is a subset of the defining subset of points for the Delone sphere such that a size of the intermediate subset of points is a whole number h+1 where h is greater than 1 and less than the dimension of the geometric space, the intermediate subset of points being selected if a closed ball of the same dimension as the geometric space, the closed ball having the same center and the same radius as a sphere with dimension h−

1 circumscribed to the points in the proper subset of the defining subset of points, contains no point from the set of points other than the points in the intermediate subset of points;

for each edge in the Delone graph, computing the minimal circumscribed sphere for the edge, where the minimal circumscribed sphere is computed by;

choosing a selected intermediate subset such that the selected intermediate subset is contained in the defining subset of points containing the endpoints of the edge, where there is no such selected intermediate subset having smaller size, setting the minimal circumscribed sphere equal to the sphere with dimension h−

1 circumscribed to the points in the selected intermediate subset;

if no such selected intermediate subset exists, setting the minimal circumscribed sphere equal to the Delone sphere for the defining subset of points containing the endpoints of the edge;

for each edge in the Delone graph, computing a distance between a midpoint of the edge and the center of the minimal circumscribed sphere for the edge;

for each edge in the Delone graph, computing a computed ratio of the distance and a length of the edge;

determining the maximal computed ratio over all edges in the Delone graph; and

for a parameter value, computing a graph for the parameter value by adding to the computed graph each edge from the Delone graph such that a ratio of the computed ratio for the edge and the maximal computed ratio is less than or equal to the parameter value.

60. The system of claim 50, where a customer'"'"'s relation values are updated as information is gathered about the customer'"'"'s opinions about items.

61. The system of claim 60, where the clustering module, performs translating the set of pair-wise relation values into a set of points in a geometric space, computing a one-parameter family of graphs, choosing a parameter value based on performance criteria, identifying a member of the one-parameter graph family determined by the parameter value, and clustering customers for the customer each time the customer'"'"'s relation values are updated.

62. The system of claim 50, where the items are one of:

pieces of music, collections of music, music genres, musical artists, particular recordings of pieces of music, videos, movies, books, groceries, or webpages.

63. A computer-readable medium encoding instructions for performing a method for visualization of relations among data items, comprising:

storing pair-wise relation values in a database, each of the pair-wise relation values representing a relation between two of the data items, such that the pair-wise relation values have a partial ordering;

translating the data items to a set of points in a geometric space, each point corresponding to a data item, such that the partial ordering of the pair-wise relation values is preserved by a distance metric on the geometric space;

computing a one-parameter family of graphs on the set of points, such that a graph is computed for a value of a parameter, the value of the parameter being chosen according to pre-defined performance criteria;

displaying at least one member of the one-parameter family of graphs to a user, where the at least one member is chosen according to the performance criteria.

64. The computer-readable medium of claim 63, where the one-parameter family of graphs is computed such that for two values of the parameter the graph computed for the higher of the two values of the parameter contains the graph computed for the lower of the two values of the parameter, for a first value of the parameter the graph computed for the first value of the parameter is a Gabriel graph for the set of points, for a second value of the parameter the graph computed for the second value of the parameter is a Delone graph for the set of points, the first value of the parameter being less than the second value of the parameter.

65. The computer-readable medium of claim 63, where the pair-wise relation values express at least one of dissimilarity, similarity, or correlation between data items.

66. The computer-readable medium of claim 63, where the geometric space is Euclidean.

67. The computer-readable medium of claim 66, where the dimension of a Euclidean space is chosen according to a criterion chosen from the list including the ability to visualize the displayed graph and the closeness of the approximation to isotony in the translating of the data items.

68. The computer-readable medium of claim 63, where the step of translating the data items to a set of points in a geometric space further comprises performing one of multi-dimensional scaling or structural similarity analysis on the pair-wise relation values.

69. The computer-readable medium of claim 63, the step of computing the one-parameter graph family further comprising the steps of:

computing Delone spheres, the Delone sphere being a sphere of dimension one less than the dimension of the geometric space that is circumscribed to points in a defining subset of points from the set of points, a size of the defining subset of points being one plus the dimension of the geometric space, the Delone sphere being computed such that no point from the set of points other than the defining subset of points is contained in a closure of a ball bounded by the Delone sphere;

computing a Delone graph by identifying, for each Delone sphere, each edge such that endpoints of the edge are contained in the defining subset of points for the Delone sphere;

computing a Gabriel graph by identifying each edge of the Delone graph, endpoints of the edge being a first point from the set of points and a second point from the set of points, the first and second points defining a zero-dimensional sphere such that no other points from the set of points are on a closure of an interior of a ball of dimension equal to the dimension of the geometric space, the ball having the same center and same radius as the zero-dimensional sphere;

selecting intermediate subsets of points, where, for each Delone sphere, the intermediate subset of points is a subset of the defining subset of points for the Delone sphere such that a size of the intermediate subset of points is a whole number h+1 where h is greater than 1 and less than the dimension of the geometric space, the intermediate subset of points being selected if a closed ball of the same dimension as the geometric space, the closed ball having the same center and the same radius as a sphere with dimension h−

1 circumscribed to the points in the proper subset of the defining subset of points, contains no point from the set of points other than the points in the intermediate subset of points;

for each edge in the Delone graph, computing the minimal circumscribed sphere for the edge, where the minimal circumscribed sphere is computed by;

choosing a selected intermediate subset such that the selected intermediate subset is contained in the defining subset of points containing the endpoints of the edge, where there is no such selected intermediate subset having smaller size, setting the minimal circumscribed sphere equal to the sphere with dimension h−

1 circumscribed to the points in the selected intermediate subset;

if no such selected intermediate subset exists, setting the minimal circumscribed sphere equal to the Delone sphere for the defining subset of points containing the endpoints of the edge;

for each edge in the Delone graph, computing a distance between a midpoint of the edge and the center of the minimal circumscribed sphere for the edge;

for each edge in the Delone graph, computing a computed ratio of the distance and a length of the edge;

determining the maximal computed ratio over all edges in the Delone graph; and

for a parameter value, computing a graph for the parameter value by adding to the computed graph each edge from the Delone graph such that a ratio of the computed ratio for the edge and the maximal computed ratio is less than or equal to the parameter value.

70. The computer-readable medium of claim 63, further comprising, before the step of displaying, clustering the data points on at least one graph in the one-parameter family of graphs.

71. The computer-readable medium of claim 70, where the displayed graphs are the graphs on which clustering has been performed.

72. The computer-readable medium of claim 63, where the data items are nodes in an input graph, the pair-wise relation values being an inverse measure of connectedness between two data items, the pair-wise relation value for the two data items being determined in such a way that the pair-wise relation value for the two data items is directly related to a number of paths between the two data items and lengths of the paths between the two data items.

73. The computer-readable medium of claim 72, where the dimension of the geometric space is 2 and the displayed graph is further chosen such the displayed graph is planar, the displayed graph having an edge between two data items if the two data items are connected by an edge in the input graph.

74. The computer-readable medium of claim 72, where, if no member of the one-parameter graph family is planar, the displayed graph is made so that it can be represented on a surface by replacing each crossing with a handle.

75. The computer-readable medium of claim 72, where the input graph represents components of a circuit.

76. The computer-readable medium of claim 63, further comprising providing input pair-wise relation values that are correlations of data items, setting the pair-wise relation value for two data items to the absolute value of the input pair-wise relation value for the two data items, and computing output pair-wise relation values such that for two data items, the output pair-wise relation value of the two data items equals the pair-wise relation value of the two data items if the two data items are connected by an edge in the displayed graph and equals 0 otherwise.

77. The computer-readable medium of claim 76, where the data items represent at least one of prices of securities, prices of commodities, macroeconomic data, or other data used in financial markets.

78. The computer-readable medium of claim 77, where the output pair-wise relation values are used to visualize the overall correlation structure of the data items.

79. The computer-readable medium of claim 77, where the output pair-wise relation values are used to compute prices of derivative securities, the price of the derivative securities depending on the prices of the data items.

80. The computer-readable medium of claim 63, where the pair-wise relation values are pair-wise measures of traffic between two data items, the data items representing one of nodes in a network or entities in a market.

81. A computer-readable medium encoding instructions for performing a method for recommending items to customers comprising:

storing pair-wise relation values for each customer in a first database, each of the pair-wise relation values representing a relation between two of the data items determined by the customer, such that the pair-wise relation values have a partial ordering;

performing for each customer the steps of;

translating the set of pair-wise relation values into a set of points in a geometric space, each point corresponding to an item, such that the partial ordering of the pair-wise relation values is preserved by a distance metric on the geometric space;

computing a one-parameter family of graphs on the set of points, such that a graph is computed for a value of a parameter, the value of the parameter being chosen according to pre-defined performance criteria;

clustering customers, where distance between two customers is the distance between the two customers identified graphs; and

providing a recommendation means for recommending items to customers based on the computed clusters of customers.

82. The computer-readable medium of claim 81, the recommendation means comprising, upon a customer request for recommended items, performing the steps of:

creating a list of items, where the items are preferred by the other customers in the customer'"'"'s cluster, such that the customer has no known preference for the items; and

sending the list of items to the customer.

83. The computer-readable medium of claim 81, the recommendation means comprising, upon a customer request for recommended items, displaying clusters to which the customer belongs in such a way as to allow browsing of items preferred by customers in the displayed clusters.

84. The computer-readable medium of claim 81, where the one-parameter family of graphs is computed such that for two values of the parameter the graph computed for the higher of the two values of the parameter contains the graph computed for the lower of the two values of the parameter, for a first value of the parameter the graph computed for the first value of the parameter is a Gabriel graph for the set of points, for a second value of the parameter the graph computed for the second value of the parameter is a Delone graph for the set of points, the first value of the parameter being less than the second value of the parameter.

85. The computer-readable medium of claim 81, where the pair-wise relation values express at least one of dissimilarity, similarity, or correlation between items.

86. The computer-readable medium of claim 81, where the geometric space is Euclidean.

87. The computer-readable medium of claim 86, where the dimension of a Euclidean space is chosen according to a criterion chosen from the list including the ability to visualize the displayed graph and the closeness of the approximation to isotony in the translating of the data items.

88. The computer-readable medium of claim 81, where the step of translating the data items to a set of points in a geometric space further comprises performing one of multi-dimensional scaling or structural similarity analysis on the pair-wise relation values.

89. The computer-readable medium of claim 81, where the items include a first element and a second element, such that a pair-wise relation value between an item and the first element indicates a customer'"'"'s preference for the item and a pair-wise relation value between an item and the second element indicates a customer'"'"'s distaste for the item.

90. The computer-readable medium of claim 81, the step of computing the one-parameter graph family further comprising the steps of:

computing Delone spheres, the Delone sphere being a sphere of dimension one less than the dimension of the geometric space that is circumscribed to points in a defining subset of points from the set of points, a size of the defining subset of points being one plus the dimension of the geometric space, the Delone sphere being computed such that no point from the set of points other than the defining subset of points is contained in a closure of a ball bounded by the Delone sphere;

computing a Delone graph by identifying, for each Delone sphere, each edge such that endpoints of the edge are contained in the defining subset of points for the Delone sphere;

computing a Gabriel graph by identifying each edge of the Delone graph, endpoints of the edge being a first point from the set of points and a second point from the set of points, the first and second points defining a zero-dimensional sphere such that no other points from the set of points are on a closure of an interior of a ball of dimension equal to the dimension of the geometric space, the ball having the same center and same radius as the zero-dimensional sphere;

selecting intermediate subsets of points, where, for each Delone sphere, the intermediate subset of points is a subset of the defining subset of points for the Delone sphere such that a size of the intermediate subset of points is a whole number h+1 where h is greater than 1 and less than the dimension of the geometric space, the intermediate subset of points being selected if a closed ball of the same dimension as the geometric space, the closed ball having the same center and the same radius as a sphere with dimension h−

1 circumscribed to the points in the proper subset of the defining subset of points, contains no point from the set of points other than the points in the intermediate subset of points;

for each edge in the Delone graph, computing the minimal circumscribed sphere for the edge, where the minimal circumscribed sphere is computed by;

choosing a selected intermediate subset such that the selected intermediate subset is contained in the defining subset of points containing the endpoints of the edge, where there is no such selected intermediate subset having smaller size, setting the minimal circumscribed sphere equal to the sphere with dimension h−

1 circumscribed to the points in the selected intermediate subset;

if no such selected intermediate subset exists, setting the minimal circumscribed sphere equal to the Delone sphere for the defining subset of points containing the endpoints of the edge;

for each edge in the Delone graph, computing a distance between a midpoint of the edge and the center of the minimal circumscribed sphere for the edge;

for each edge in the Delone graph, computing a computed ratio of the distance and a length of the edge;

determining the maximal computed ratio over all edges in the Delone graph; and

for a parameter value, computing a graph for the parameter value by adding to the computed graph each edge from the Delone graph such that a ratio of the computed ratio for the edge and the maximal computed ratio is less than or equal to the parameter value.

91. The computer-readable medium of claim 81, where a customer'"'"'s relation values are updated as information is gathered about the customer'"'"'s opinions about items.

92. The computer-readable medium of claim 91, where the steps of translating the set of pair-wise relation values into a set of points in a geometric space, computing a one-parameter family of graphs, choosing a parameter value based on performance criteria, identifying a member of the one-parameter graph family determined by the parameter value, and clustering customers are performed for the customer each time the customer'"'"'s relation values are updated.

93. The computer-readable medium of claim 81, where the items are one of:

pieces of music, collections of music, music genres, musical artists, particular recordings of pieces of music, videos, movies, books, groceries, or webpages.