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.

Example Graph

To create this graph:

// Runs each row separately in order in an empty graphset
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 hdc_sim_prop:

CALL hdc.graph.create("hdc-server-1", "hdc_sim_prop", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_sim_prop", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

Parameters

Algorithm name: similarity

The algorithm has two calculation modes:

1. Pairing: When both ids/uuids and ids2/uuids2 are configured, each node in ids/uuids is paired with each node in ids2/uuids2 (excluding self-pairing), and pairwise similarities are computed.
2. Selection: When only ids/uuids is configured, pairwise similarities are computed between each target node and all other nodes in the graph. The results include all or a limited number of nodes with a similarity > 0 to the target node, ordered in descending similarity.

File Writeback

Computes similarities in pairing mode:

CALL algo.similarity.write("hdc_sim_prop", {
  params: {
    return_id_uuid: "id",
    ids: "product1",
    ids2: ["product2", "product3", "product4"],
    node_schema_property: ["price", "weight", "width", "height"],
    type: "euclideanDistance"
  },
  return_params: {
    file: {
      filename: "euclideanDistance"
    }
  }
})

algo(similarity).params({
  projection: "hdc_sim_prop",
  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("hdc_sim_prop", {
  params: {
    return_id_uuid: "id",
    ids: ["product1","product2"], 
    ids2: ["product2","product3","product4"],
    node_schema_property: ["price", "weight", "width", "height"],
    type: "euclideanDistance"
  },
  return_params: {}
}) 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 hdc_sim_prop

Result:

Stream Return

CALL algo.similarity("hdc_sim_prop", {
  params: {
    return_id_uuid: "id",
    ids: ["product1", "product3"], 
    node_schema_property: ["price", "weight", "width", "height"],
    type: "euclideanDistance",
    top_limit: 1    
  },
  return_params: {
  	stream: {}
  }
}) 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 hdc_sim_prop

Result: