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.

Sign up for GitHub

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

Jump to bottom

Support a more general Intersection in GIE Runtime #3745

Closed
BingqingLyu opened this issue Apr 24, 2024 · 1 comment
Closed

Support a more general Intersection in GIE Runtime #3745

BingqingLyu opened this issue Apr 24, 2024 · 1 comment
Assignees
@BingqingLyu
Labels
stale

Comments

@BingqingLyu
Copy link
Collaborator

Is your feature request related to a problem? Please describe.

We have supported a optimized intersection in pattern matching. E.g., for a triangle pattern with vertices a, b, c, we can first expand a->b, and then intersect a->c and b->c, to find the matchings for the triangle. However, currently, we cannot preserve the edge matchings for a->c and b->c during the intersection process (we only preserve the matchings for the vertices). Thus, we need to support a more general Intersection if the edge matchings are needed.
@BingqingLyu BingqingLyu self-assigned this Apr 24, 2024
@BingqingLyu BingqingLyu mentioned this issue Apr 24, 2024
Merged
@github-actions github-actions bot added the stale label May 12, 2024
@github-actions GitHub Actions
Copy link
Contributor

/cc @BingqingLyu, this issus/pr has had no activity for for a long time, could you folks help to review the status ?
To suppress further notifications,

  • for issues,
    • if it is waiting for further response from the reporter/author, please help to add the label requires-further-info,
    • if you have already started working on it, please add the label work-in-progress to the issue,
    • if this issue requires further designing discussion and not in current plan, or won't be fixed, please add the label requires-further-discussion or wontfix to the issue,
  • for pull requests,
    • if you are still working on it and it is not ready for reviewing, please convert this pull request as draft PR,
    • if you have decided to hold this development on, please add the requires-further-discussion label to the pull request.
      Thanks!

BingqingLyu added a commit that referenced this issue May 14, 2024
@BingqingLyu @zhanglei1949 @longbinlai
fix(interactive): support a general Intersect implementation in GIE…
348a2b7 
… Runtime (#3689)

<!--
Thanks for your contribution! please review
https://github.com/alibaba/GraphScope/blob/main/CONTRIBUTING.md before
opening an issue.
-->

## What do these changes do?

<!-- Please give a short brief about these changes. -->

As titled.

This pr mainly includes:

1. Refactor the convert logic of `Intersect` in
`GraphRelToProtoConverter` in Compiler
2. Refactor the parsing and processing logic of `Intersect` in assembly
in Runtime
3. Support a more general `Intersect` that can preserve the edges during
intersection, in Runtime
4. Add a micro benchmark framework, and testing for general_intersection
v.s. optimized_intersection. The results shows that, on ldbc dataset
(sf=1), to find matches for a triangle (a,b,c knows each other),
general_intersection's time cost is about 1.7\times of
optimized_intersection's, as the general_intersection further preserves
all matched edges during the intersection computation.

## Related issue number

<!-- Are there any issues opened that will be resolved by merging this
change? -->

Fixes #3685 #3745

---------

Co-authored-by: xiao.zl <xiaolei.zl@alibaba-inc.com>
Co-authored-by: Longbin Lai <longbin.lailb@alibaba-inc.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@BingqingLyu BingqingLyu

Labels
stale
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@BingqingLyu