Overview
In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points. In the graph, N numeric node properties (features) are specified to represent each node's position in an N-dimensional Euclidean space.
Concepts
Euclidean Distance
In 2-dimensional space, the formula to compute the Euclidean distance between points A(x1, y1) and B(x2, y2) is:
In 3-dimensional space, the formula to compute the Euclidean distance between points A(x1, y1, z1) and B(x2, y2, z2) is:
Generalized to N-dimensional space, the formula to compute the Euclidean distance is:
where xi1 represents the i-th dimensional coordinates of the first point, and xi2 represents the i-th dimensional coordinates of the second point.
Euclidean distance ranges from 0 to +∞; smaller values indicate greater similarity between the two nodes.
Normalized Euclidean Distance
Normalized Euclidean distance scales the Euclidean distance into range from 0 to 1; the closer to 1, the more similar the two nodes.
Ultipa adopts the following formula to normalize the Euclidean distance:
Considerations
- Theoretically, the calculation of Euclidean distance between two nodes is independent of their connectivity.
Example Graph
Run the following statements on an empty graph to define its structure and insert data:
ALTER GRAPH CURRENT_GRAPH ADD NODE {
product ({price int32, weight int32, width int32, height int32})
};
INSERT (:product {_id:"product1", price:50, weight:160, width:20, height:152}),
(:product {_id:"product2", price:42, weight:90, width:30, height:90}),
(:product {_id:"product3", price:24, weight:50, width:55, height:70}),
(:product {_id:"product4", price:38, weight:20, width:32, height:66});
create().node_schema("product");
create().node_property(@product, "price", int32).node_property(@product, "weight", int32).node_property(@product, "width", int32).node_property(@product, "height", int32);
insert().into(@product).nodes([{_id:"product1", price:50, weight:160, width:20, height:152}, {_id:"product2", price:42, weight:90, width:30, height:90}, {_id:"product3", price:24, weight:50, width:55, height:70}, {_id:"product4", price:38, weight:20, width:32, height:66}]);
Creating HDC Graph
To load the entire graph to the HDC server hdc-server-1 as my_hdc_graph:
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static"
}
hdc.graph.create("my_hdc_graph", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static"
}).to("hdc-server-1")
Parameters
Algorithm name: similarity
| Name | Type | Spec | Default | Optional | Description | |
|---|---|---|---|---|---|---|
ids/uuids |
_id/_uuid |
Yes | Specifies the first group of nodes by their _id or _uuid. If unset, all nodes in the graph are used as the first group of nodes. |
The algorithm supports two calculation modes:
|
||
ids2/uuids2 |
_id/_uuid |
Yes | Specifies the second group of nodes for pairwise similarity by their _id or _uuid. If only ids2/uuids2 is set (and ids/uuids is not), the algorithm returns no result. |
|||
type |
String | euclideanDistance,euclidean |
cosine |
No | Specifies the type of similarity to compute; use euclideanDistance to compute Euclidean Distance, and use euclidean to compute Normalized Euclidean Distance. |
|
node_schema_property |
[]"<@schema.?><property>" |
No | Specifies numeric node properties to form a vector for each node; all specified properties must belong to the same label (schema). | |||
return_id_uuid |
String | uuid,id,both |
uuid |
Yes | Includes _uuid, _id, or both to represent nodes in the results. |
|
order |
String | asc,desc |
Yes | Sorts the results by similarity. |
||
limit |
Integer | ≥-1 | -1 |
Yes | Limits the number of results returned. Set to -1 to include all results. |
|
top_limit |
Integer | ≥-1 | -1 |
Yes | Limits the number of results returned for each node specified with ids/uuids in selection mode. Set to -1 to include all results with a similarity greater than 0. This parameter is invalid in pairing mode. |
|
File Writeback
Computes similarities in pairing mode:
CALL algo.similarity.write("my_hdc_graph", {
return_id_uuid: "id",
ids: "product1",
ids2: ["product2", "product3", "product4"],
node_schema_property: ["price", "weight", "width", "height"],
type: "euclideanDistance"
}, {
file: {
filename: "euclideanDistance"
}
})
algo(similarity).params({
projection: "my_hdc_graph",
return_id_uuid: "id",
ids: "product1",
ids2: ["product2", "product3", "product4"],
node_schema_property: ["price", "weight", "width", "height"],
type: "euclideanDistance"
}).write({
file: {
filename: "euclideanDistance"
}
})
Result:
_id1,_id2,similarity
product1,product2,94.3822
product1,product3,143.962
product1,product4,165.179
Full Return
CALL algo.similarity.run("my_hdc_graph", {
return_id_uuid: "id",
ids: ["product1","product2"],
ids2: ["product2","product3","product4"],
node_schema_property: ["price", "weight", "width", "height"],
type: "euclideanDistance"
}) YIELD distance
RETURN distance
exec{
algo(similarity).params({
return_id_uuid: "id",
ids: ["product1","product2"],
ids2: ["product2","product3","product4"],
node_schema_property: ["price", "weight", "width", "height"],
type: "euclideanDistance"
}) as distance
return distance
} on my_hdc_graph
Result:
| _id1 | _id2 | similarity |
|---|---|---|
| product1 | product2 | 94.382202 |
| product1 | product3 | 143.961807 |
| product1 | product4 | 165.178696 |
| product2 | product3 | 54.304695 |
| product2 | product4 | 74.135010 |
Stream Return
CALL algo.similarity.stream("my_hdc_graph", {
return_id_uuid: "id",
ids: ["product1", "product3"],
node_schema_property: ["price", "weight", "width", "height"],
type: "euclideanDistance",
top_limit: 1
}) YIELD top
RETURN top
exec{
algo(similarity).params({
return_id_uuid: "id",
ids: ["product1", "product3"],
node_schema_property: ["price", "weight", "width", "height"],
type: "euclideanDistance",
top_limit: 1
}).stream() as top
return top
} on my_hdc_graph
Result:
| _id1 | _id2 | similarity |
|---|---|---|
| product1 | product4 | 165.178696 |
| product3 | product1 | 143.961807 |