{'fraction_non_alphanumeric': 0.024536205864751647, 'fraction_numerical': 0.0023937761819269898, 'mean_word_length': 5.057971014492754, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
KVGraph : A Cypher-- Query Processor On Top of Redis Dmitriy Kunitskiy

There is an emerging interest in graph databases due to their potential in storing and querying ubiquitous and evergrowing connected data. Cypher, the most widely deployed graph query language, is simple to learn and allows for compact expression of graph queries. However, given the intrinsic complexity of many graph algorithms and the expansive horizon of possible optimizations, the subject of query processing over large graphs, including how to efficiently represent and store a graph’s structure and data to support querying, can appear daunting. In this paper, we propose a graph representation based on adjacency lists that keeps the graph structure and node properties entirely in Redis, a popular in-memory key-value store. Next, we outline a smaller and less expressive graph query language, Cypher--, that “dumbs down” the original by removing advanced features, such as the Kleene star and GREP-like path expressions, while remaining a proper subset of the language. Armed with the above, as well as several assumptions about the graph at hand, we propose a simple query evaluation algorithm that relies on associating variables to the set of their possible bindings and leverages Redis’s O(1) look up time. The correctness of this algorithm is assessed by comparing the output of our prototype against Neo4j, which is treated as the reference implementation. Finally, we compare the performance our implementation with Neo4j’s and describe a class of queries where our approach produces the same results and outperforms Neo4j by up to an order of magnitude, even with indices enabled.