中科微点-全球专利检索

  1. Login
  2. Sign Up

Search Results

31 records (took 0.017 seconds)

    Efficient, in-memory, relational representation for heterogeneous graphs
    13.
    发明授权
    Efficient, in-memory, relational representation for heterogeneous graphs 有权

    公开(公告)号：US11120082B2

    公开(公告)日：2021-09-14

    申请号：US15956115

    申请日：2018-04-18

    Applicant: Oracle International Corporation

    Inventor： Damien Hilloulin ,  Davide Bartolini ,  Oskar Van Rest ,  Alexander Weld ,  Sungpack Hong ,  Hassan Chafi

    IPC: G06F16/901 ,  G06F16/28 ,  G06F16/22

    Abstract: Techniques are provided herein for efficient representation of heterogeneous graphs in memory. In an embodiment, vertices and edges of the graph are segregated by type. Each property of a type of vertex or edge has values stored in a respective vector. Directed or undirected edges of a same type are stored in compressed sparse row (CSR) format. The CSR format is more or less repeated for edge traversal in either forward or reverse direction. An edge map translates edge offsets obtained from traversal in the reverse direction for use with data structures that expect edge offsets in the forward direction. Subsequent filtration and/or traversal by type or property of vertex or edge entails minimal data access and maximal data locality, thereby increasing efficient use of the graph.

    FAST DETECTION OF VERTEX-CONNECTIVITY WITH DISTANCE CONSTRAINT
    15.
    发明申请
    FAST DETECTION OF VERTEX-CONNECTIVITY WITH DISTANCE CONSTRAINT 审中-公开

    公开(公告)号：US20200151216A1

    公开(公告)日：2020-05-14

    申请号：US16185236

    申请日：2018-11-09

    Applicant: Oracle International Corporation

    Inventor： Martin Sevenich ,  Sungpack Hong ,  Alexander Weld ,  Hassan Chafi

    IPC: G06F16/901 ,  G06F16/22 ,  G06F16/9532

    Abstract: Embodiments perform real-time vertex connectivity checks in graph data representations via a multi-phase search process. This process includes an efficient first search phase using landmark connectivity data that is generated during a preprocessing phase. Landmark connectivity data maps the connectivity of a set of identified landmarks in a graph to other vertices in the graph. Upon determining that the subject vertices are not closely related via landmarks, embodiments implement a second search phase that performs a brute-force search for connectivity, between the subject vertices, among the graph's non-landmark vertices. This brute-force search prevents exploration of cyclical paths by recording the vertices on a currently-explored path in a stack data structure. The second search phase is automatically aborted upon detecting that the non-landmark vertices in the graph are over a threshold density. In this case, embodiments perform a third search phase involving either a modified breadth-first search or modified bidirectional search.

    Defining subgraphs declaratively with vertex and edge filters
    16.
    发明授权
    Defining subgraphs declaratively with vertex and edge filters 有权

    公开(公告)号：US10445319B2

    公开(公告)日：2019-10-15

    申请号：US15592050

    申请日：2017-05-10

    Applicant: Oracle International Corporation

    Inventor： Alexander Weld ,  Korbinian Schmid ,  Sungpack Hong ,  Hassan Chafi ,  Hyungyu Shin

    IPC: G06F17/30 ,  G06F16/2453 ,  G06F16/248 ,  G06F16/25

    Abstract: Techniques herein optimally distribute graph query processing across heterogeneous tiers. In an embodiment, a computer receives a graph query to extract a query result (QR) from a graph in a database operated by a database management system (DBMS). The graph has vertices interconnected by edges. Each vertex has vertex properties, and each edge has edge properties. The computer decomposes the graph query into filter expressions (FE's). Each FE is processed as follows. A filtration tier to execute the FE is selected from: the DBMS which sends at least the QR to a stream, a stream evaluator that processes the stream as it arrives without waiting for the entire QR to arrive and that stores at least the QR into memory, and an in-memory evaluator that identifies the QR in memory. A translation of the FE executes on the filtration tier to obtain vertices and/or edges that satisfy the FE.

    Defining subgraphs declaratively with vertex and edge filters
    18.
    发明授权
    Defining subgraphs declaratively with vertex and edge filters 有权

    公开(公告)号：US11294899B2

    公开(公告)日：2022-04-05

    申请号：US16548687

    申请日：2019-08-22

    Applicant: Oracle International Corporation

    Inventor： Alexander Weld ,  Korbinian Schmid ,  Sungpack Hong ,  Hassan Chafi ,  Hyungyu Shin

    IPC: G06F17/30 ,  G06F16/2453 ,  G06F16/248 ,  G06F16/25 ,  G06F16/901 ,  G06F16/27

    Abstract: Techniques herein optimally distribute graph query processing across heterogeneous tiers. In an embodiment, a computer receives a graph query to extract a query result (QR) from a graph in a database operated by a database management system (DBMS). The graph has vertices interconnected by edges. Each vertex has vertex properties, and each edge has edge properties. The computer decomposes the graph query into filter expressions (FE's). Each FE is processed as follows. A filtration tier to execute the FE is selected from: the DBMS which sends at least the QR to a stream, a stream evaluator that processes the stream as it arrives without waiting for the entire QR to arrive and that stores at least the QR into memory, and an in-memory evaluator that identifies the QR in memory. A translation of the FE executes on the filtration tier to obtain vertices and/or edges that satisfy the FE.

    Multi-source breadth-first search (Ms-Bfs) technique and graph processing system that applies it
    20.
    发明授权
    Multi-source breadth-first search (Ms-Bfs) technique and graph processing system that applies it 有权

    公开(公告)号：US10949466B2

    公开(公告)日：2021-03-16

    申请号：US16712453

    申请日：2019-12-12

    Applicant: Oracle International Corporation

    Inventor： Martin Sevenich ,  Sungpack Hong ,  Alexander Weld ,  Hassan Chafi ,  Daniel Lehmann

    IPC: G06F16/00 ,  G06F16/901 ,  G06F16/23 ,  G06F16/903

    Abstract: Techniques herein minimize memory needed to store distances between vertices of a graph for use during a multi-source breadth-first search (MS-BFS). In an embodiment, during each iteration of a first sequence of iterations of a MS-BFS, a computer updates a first matrix that contains elements that use a first primitive integer type having a first width to record a distance from a source vertex of a graph to another vertex. The computer detects that a count of iterations of the first sequence of iterations exceeds a threshold. Responsively, the computer creates a second matrix that contains elements that use a second primitive integer type having a second width that is larger than the first width to record a distance from a source vertex of the graph to another vertex. During each iteration of a second sequence of iterations of the MS-BFS, the computer updates the second matrix.

Patent Agency Ranking