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

Performance: Isomorphism check is slow on 30_000 triples #38

Open
jeswr opened this issue Mar 6, 2023 · 1 comment
Open

Performance: Isomorphism check is slow on 30_000 triples #38

jeswr opened this issue Mar 6, 2023 · 1 comment
Labels
enhancement New feature or request

Comments

@jeswr
Copy link

jeswr commented Mar 6, 2023

To check that 30_000 triples are isomorphic to itself takes 12min even though parsing the file only takes 30ms (found by running https://github.com/jeswr/rdf-iso-test/blob/master/test.ts).

I appreciate that the algorithm for checking isomorphism is probably in the realm of squared to exponential complexity, but I think that there are optimizations that could be made here to reduce the complexity class such as:

  1. Loading the graphs into a store so that we can do index lookups rather than iterating through all of the quads in places like hashTerm.

  2. All the string and term comparisons could then also be replaced by equality checks between ids.

  3. The signature can then be in terms of ids of the form s_p_o_g and the sha1hex can probably then be removed.

cc @josd - this is what was causing what seemed like a halt in the eye-js test suite.

@jeswr jeswr changed the title Performance: Isomorphism check is slow Performance: Isomorphism check is slow on 30_000 triples Mar 6, 2023
@rubensworks
Copy link
Owner

Indeed, the computational complexity for isomorphism checking is pretty high.
Some optimizations may be possible indeed!

RDF canonicalization may perform better for very large graphs. (not fully sure what the computational complexity of it is)

@rubensworks rubensworks added the enhancement New feature or request label Mar 6, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

2 participants