✓ File Writeback ✕ Property Writeback ✓ Direct Return ✓ Stream Return ✕ Stats

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, specifying N numeric properties (features) of nodes to indicate the location of the node in an N-dimensional Euclidean space.

Concepts

Euclidean Distance

In 2-dimensional space, the formula to compute the Euclidean distance between points A(x₁, y₁) and B(x₂, y₂) is:

In 3-dimensional space, the formula to compute the Euclidean distance between points A(x₁, y₁, z₁) and B(x₂, y₂, z₂) is:

Generalize to N-dimensional space, the formula to compute the Euclidean distance is:

where xi₁ represents the i-th dimensional coordinates of the first point, xi₂ represents the i-th dimensional coordinates of the second point.

The Euclidean distance ranges from 0 to +∞; the smaller the value, the more similar 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 does not depend on their connectivity.

Syntax

• Command: algo(similarity)
• Parameters:

This algorithm has two calculation modes:

1. Pairing: when ids/uuids and ids2/uuids2 are both configured, pairing nodes in the first group with nodes in the second group (Cartesian product) to compute pair-wise similarities.
2. Selection: when only ids/uuids is configured, for each node in the group, computing pair-wise similarities between it and all other nodes in the graph in order to select the most similar nodes, the returned top_list includes all nodes that have similarity > 0 with it and is ordered by the descending similarity.

Examples

The example graph has 4 products (edges are ignored), each product has properties price, weight, weight and height:

File Writeback

algo(similarity).params({
  uuids: [1], 
  uuids2: [2,3,4],
  node_schema_property: [price,weight,width,height],
  type: "euclideanDistance"
}).write({
  file:{ 
    filename: "ed"
  }
})

Results: File ed

product1,product2,94.3822
product1,product3,143.962
product1,product4,165.179

algo(similarity).params({
  uuids: [1,2,3,4],
  node_schema_property: [price,weight,width,height],
  type: "euclidean"
}).write({
  file:{ 
    filename: "ed_list"
  }
})

Results: File ed_list

product1,product2:0.010484;product3:0.006898;product4:0.006018;
product2,product3:0.018082;product4:0.013309;product1:0.010484;
product3,product4:0.024091;product2:0.018082;product1:0.006898;
product4,product3:0.024091;product2:0.013309;product1:0.006018;

Direct Return

algo(similarity).params({
  uuids: [1], 
  uuids2: [2,3,4],
  node_schema_property: [price,weight,width,height],
  type: "euclideanDistance"
}) as distance
return distance
order by distance.similarity desc

Results: distance

algo(similarity).params({
  uuids: [1,2],
  type: "euclidean",
  node_schema_property: [price,weight,width,height],
  top_limit: 1
}) as top
return top

Results: top

Stream Return

algo(similarity).params({
  uuids: [3], 
  uuids2: [1,2,4],
  node_schema_property: [price,weight,width,height],
  type: "euclidean"
}).stream() as distance
where distance.similarity > 0.01
return distance

Results: distance

algo(similarity).params({
  uuids: [1,3],
  node_schema_property: [price,weight,width,height],
  type: "euclideanDistance",
  top_limit: 1
}).stream() as top
return top

Results: top