Euclidean Distance

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:

The algorithm has two calculation modes:

1. Pairing: when both ids/uuids and ids2/uuids2 are configured, pairing each node in ids/uuids with each node in ids2/uuids2 (ignore the same node) and computing pair-wise similarities.
2. Selection: when only ids/uuids is configured, for each target node in it, computing pair-wise similarities between it and all other nodes in the graph. The returned results include all or limited number of nodes that have similarity > 0 with the target node 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

UQL
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

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

UQL
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

File
product1,product2,0.010484
product1,product3,0.006898
product1,product4,0.006018
product2,product3,0.018082
product2,product4,0.013309
product2,product1,0.010484
product3,product4,0.024091
product3,product2,0.018082
product3,product1,0.006898
product4,product3,0.024091
product4,product2,0.013309
product4,product1,0.006018

Direct Return

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

Results: distance

UQL
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

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

Results: distance

UQL
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