Change Password

Please enter the password.
Please enter the password. Between 8-64 characters. Not identical to your email address. Contain at least 3 of: uppercase, lowercase, numbers, and special characters.
Please enter the password.
Submit

Change Nickname

Current Nickname:
Submit

Apply New License

License Detail

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

The MAC address of the server you want to deploy.

Please complete this required field.

Please complete this required field.

Cancel
Apply
ID
Product
Status
Cores
Applied Validity Period(days)
Effective Date
Excpired Date
Mac Address
Apply Comment
Review Comment
Close
Profile
  • Full Name:
  • Phone:
  • Company:
  • Company Email:
  • Country:
  • Language:
Change Password
Apply

You have no license application record.

Apply
Certificate Issued at Valid until Serial No. File
Serial No. Valid until File

Not having one? Apply now! >>>

Product Created On ID Amount (USD) Invoice
Product Created On ID Amount (USD) Invoice

No Invoice

Graph Database Benchmarks Demystified (Part 2)

Download PDF File

This section is dedicated to query results validation of 3 types of operations:

  • K-hop
  • Shortest-Path
  • Graph Algorithms

Let’s start with K-hop queries. First, let’s be clear of the definition of K-hop, there have been 2 types of K-hop:

  1. Kth-Hop Neighbors, which are exactly K hops away from the source vertex
  2. All Neighbors from the 1st Hop all the way to the Kth Hop

No matter which type of K-hop you are looking at, 2 essential points affect the correctness of the query:

  1. K-hop should be implemented using BFS, instead of DFS
  2. Results Deduplication: The results will not contain duplicated vertices on the same hop or across different hops (Many graph DBMS do have this dedup problem as we speak.)

Some vendors use DFS to find shortest paths, this approach has 2 fatal problems:

  1. Outright Wrong: There is a high probability that the results are wrong as DFS can’t guarantee a vertex belongs to the right hop (depth).
  2. Inefficient: On large and densely populated datasets, it’s impractical to traverse all possible paths, for instance, Twitter-2010 has many hotspot nodes having millions of neighbors, any 2-hop or deeper queries mean astronomical computational complexity!

Let’s validate the 1-Hop result of vertex ID=27960125 in Twitter-2010, first, we start from the source file which shows 8 edges (rows of connecting neighbors), but, what exactly is its 1-hop?

The correct answer is 7! Because the node 27960125 has a neighbor ID=27498091 which appears twice, because there are 2 edges in between these 2 vertices. If we deduplicate, we have 7.

To expand here on K-hop queries, it is possible to launch K-hop per edge direction, the screenshots below show 4 ways for running K-hop: regular bidirectional K-hop, outbound K-hop, inbound K-hop and K-hop with all neighbors. These queries combined can help validate any K-hop query.

If we compare with publicly accessible Tigergraph’s K-hop query results, the vertex ID=27960125 has only 6 1-hop neighbors (shown in Graph 9), and the similar counting mistakes prevail throughout the entire published results on Github.

Please complete the following information to download this book
*
公司名称不能为空
*
公司邮箱必须填写
*
你的名字必须填写
*
你的电话必须填写