Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Correctly Implement PickRandomVertex Efficiently #2

Open
Smuzzy-waiii opened this issue Oct 15, 2024 · 0 comments
Open

Correctly Implement PickRandomVertex Efficiently #2

Smuzzy-waiii opened this issue Oct 15, 2024 · 0 comments
Labels
Bounty: 900 enhancement New feature or request

Comments

@Smuzzy-waiii
Copy link

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 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: dgraph-io/badger#1120

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

@Smuzzy-waiii Smuzzy-waiii added the enhancement New feature or request label Oct 15, 2024
@Smuzzy-waiii Smuzzy-waiii changed the title Correctly Implement PickRandomVertext Efficiently Correctly Implement PickRandomVertex Efficiently Oct 15, 2024
Smuzzy-waiii added a commit that referenced this issue Nov 12, 2024
However vertices arent removed on remove edge
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Bounty: 900 enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant