Skip to main content

Translating anti-vertex in cypher for graph databases and graph mining systems

Resource type
Thesis type
(Project) M.Sc.
Date created
Author: Ahmad, Saad
An Anti-vertex is a declarative construct that indicates absence of a vertex, i.e., the resulting subgraph should not have a vertex in its specified neighborhood that matches the anti-vertex. Anti-vertices are natively supported in Peregrine, a state-of-the-art graph mining system, and has been proposed as a prototype extension to Cypher graph query language. The semantics of Anti-vertices have been well-established in accordance with semantics of subgraph matching, which includes isomorphism, homomorphism, and no-repeated-edge matching. This project focuses on enabling two cypher-based backends, Neo4j and Graphflow, to support anti-vertices. The two backends support anti-vertex queries by executing WHERE NOT EXISTS queries to match patterns based on the absence of a particular vertex. The query engine in Graphflow has been modified to support nested subqueries using the WHERE NOT EXISTS queries. The Cypher grammar in Graphflow is updated to accept anti-vertex query syntax as user input. The anti-vertex queries are translated to an appropriate WHERE NOT EXISTS queries by the backend. We have benchmarked the translated anti-vertex queries in Neo4j and Graphflow against the natively supported anti-vertex queries in Peregrine. The native anti-vertex query support in Peregrine performs significantly faster than the translated WHERE NOT EXISTS query in Graphflow and Neo4j. The performance gap highlights opportunities to improve graph database systems by natively support anti-vertex constructs.
43 pages.
Copyright statement
Copyright is held by the author(s).
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: Vora, Keval
Member of collection
Download file Size
etd22868.pdf 1.21 MB

Views & downloads - as of June 2023

Views: 0
Downloads: 1