Uploaded image for project: 'MariaDB Server'
  1. MariaDB Server
  2. MDEV-38721

one-pass HNSW search

    XMLWordPrintable

Details

    Description

      The idea here is to treat HNSW graph as a flat one-level non-hierarchical graph and search on all layers at once. Without actual flattening, so let's call it VF-HNSW, Virtually Flattened Hierarchical Navigable Small World.

      It can be simply described as "when searching on the Nth layer, instead of adding all node neighbors from the same layer to the candidate set, add all node neighbors on all layers to the candidate set". But this of course will cause too many unnecessary distance calculations, so an optimization would be "add neighbors from the layer k-1 only if any of the k layer neighbors was better than all k+1 layer neighbors".

      This will allow searching all layers in one traversal without overshooting the target.

      Attachments

        Activity

          People

            Unassigned Unassigned
            serg Sergei Golubchik
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

            Dates

              Created:
              Updated:

              Git Integration

                Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.