acmpesuecc / acmpesuecc/Onyx

Correctly Implement `PickRandomVertex` Efficiently

Aberta
#2 0 comentários 0 reações 0 responsáveis Ver no GitHub
Bounty: 900 enhancement
Linguagem predominante
Go
Estrelas
3
Forks
2
Métricas de merge de PRs
Nenhum PR com merge em 30d

Descrição

The current implementation of `PickRandomVertex` is not really correct. It only picks the "random" vertex from the first 100 keys of the `*badger.Iterator` which according to the badger documentation:
> Iteration happens in byte-wise lexicographical sorting order.

So its not really random.

What we ideally want is to pick a random vertex from all the vertices present in the graph. However, for this implementation, I am okay if the random vertex is picked only from all the source vertices ie all the keys in the badgerdb. Iterating over all the keys in badger using `*badger.Iterator` is very inefficient for large graphs. The [Stream](https://dgraph.io/docs/badger/get-started/#stream) framework of badger allows concurrent traversal of the whole graph. An Incorrect implementation using the stream framework is implemented in `PickRandomVertexIncorrectEfficient()`

Your task is to come up with a correct implementation of PickRandomVertex. You are not restricted to use the Stream framework but I haven't found any other ways to do it. If you do, knock yourself out.

Ref: https://github.com/dgraph-io/badger/issues/1120

**Note**: Please comment here/DM me on discord the proposed design before implementing it

Guia de contribuição

Abrir o guia de contribuição

Avaliação

Esta issue ainda não foi avaliada.

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.