Graph Pattern Mining (GPM) is a class of algorithms that identifies given shapes within a graph, e.g., cliques of a certain size. Any area of a graph can contain a shape of interest, but in real-world graphs, these shapes tend to be concentrated in areas deemed skewed. Because mining skewed areas can dominate GPM computations, the overwhelming majority of state-of-the-art GPM techniques break such areas into many small parts and load balance them across servers. This paper takes a diametrically opposite approach: we suggest a framework that concentrates rather than divides the skewed areas. Our framework, called GraphINC, relies on two key innovations. First, it introduces a new graph partitioning scheme capable of separating the skewed area from the rest of the graph. Second, it offloads the skewed part onto a new class of hardware accelerator, a programmable network switch. We implemented our framework to leverage a commercial 100 Gbps switch and obtained results 6.5 to 52.4× faster thanks to our novel offloading technique.

Transaction logging and log shipping are standard techniques to provide recoverability and high availability in data management systems. They entail an update to a local log file at every transaction and sending such an update to a remote site in a coordinated fashion. Modern databases have leveraged technologies such as Persistent Memory (PM) and RDMA-enabled networking to perform these updates as fast as possible. This mix of technologies, however, presents several drawbacks: some technologies are not portable, restricting deployments to a single class of machines; they make the data path more contrived; and they force very low-level APIs to interoperate, posing severe correctness issues.