Lune

ICDE2020Top-tier venue

Kaleido: An Efficient Out-of-core Graph Mining System on A Single Machine

Cheng Zhao, Zhibin Zhang, Peng Xu, Tianqi Zheng, Jiafeng Guo

Abstract

Graph mining is one of the most important categories of graph algorithms. However, exploring the subgraphs of an input graph produces a huge amount of intermediate data.

The "think like a vertex" programming paradigm, pioneered by Pregel, cannot readily formulate mining problems, which is designed to produce graph computation problems like PageRank. Existing mining systems like Arabesque and RStream need large amounts of computing and memory resources.

In this paper, we present Kaleido, an efficient single machine, out-of-core graph mining system which treats disks as an extension of memory. Kaleido treats intermediate data in graph mining tasks as a tensor and adopts a succinct data structure for the intermediate data. Kaleido utilizes the eigenvalue of the adjacency matrix of a subgraph to efficiently solve the subgraph isomorphism problems with an acceptable constraint that the vertex number of a subgraph is less than 9. Kaleido implements half-memory-half-disk storage for storing large intermediate data, which treats the disk as an extension of the memory. Comparing with two state-of-the-art mining systems, Arabesque and RStream, Kaleido outperforms them by a GeoMean 12.3× and 40.0× respectively.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

12 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • FlexMiner: A Pattern-Aware Accelerator for Graph Pattern Mining cites Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU
  • DIMMining: pruning-efficient and parallel graph mining on near-memory-computing cites FlexMiner: A Pattern-Aware Accelerator for Graph Pattern Mining
  • DIMMining: pruning-efficient and parallel graph mining on near-memory-computing cites SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processing-in-Memory Systems
  • DIMMining: pruning-efficient and parallel graph mining on near-memory-computing cites Efficient and Scalable Graph Pattern Mining on GPUs
  • DIMMining: pruning-efficient and parallel graph mining on near-memory-computing cites Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU
  • SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processing-in-Memory Systems cites Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU
  • Efficient and Scalable Graph Pattern Mining on GPUs cites FlexMiner: A Pattern-Aware Accelerator for Graph Pattern Mining
  • Efficient and Scalable Graph Pattern Mining on GPUs cites Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers12

  1. Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPUXuhao Chen, Roshan Dathathri, Gurbinder Gill, Keshav PingaliVLDB 2020 · 81 citations
  2. SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processing-in-Memory SystemsMaciej Besta, Raghavendra Kanakagiri, Grzegorz Kwasniewski, Rachata Ausavarungnirun et al.MICRO 2021 · 78 citations
  3. DIMMining: pruning-efficient and parallel graph mining on near-memory-computingGuohao Dai, Zhenhua Zhu, Tianyu Fu, Chiyue Wei et al.ISCA 2022 · 56 citations
  4. Efficient and Scalable Graph Pattern Mining on GPUsXuhao Chen, ArvindOSDI 2022 · 53 citations
  5. FlexMiner: A Pattern-Aware Accelerator for Graph Pattern MiningXuhao Chen, Tianhao Huang, Shuotao Xu, Thomas Bourgeat et al.ISCA 2021 · 41 citations

Related papers

  1. A Locality-Aware Energy-Efficient Accelerator for Graph Mining ApplicationsPengcheng Yao, Long Zheng, Zhen Zeng, Yu Huang et al.MICRO 2020 · 43 citations
  2. MiniGraph: Querying Big Graphs with a Single MachineXiaoke Zhu, Yang Liu, Shuhao Liu, Wenfei FanVLDB 2023 · 12 citations
  3. Peregrine: a pattern-aware graph mining systemKasra Jamshidi, Rakesh Mahadasa, Keval VoraEuroSys 2020 · 107 citations
  4. G-thinker: A Distributed Framework for Mining Subgraphs in a Big GraphDa Yan, Guimu Guo, Md Mashiur Rahman Chowdhury, M. Tamer Özsu et al.ICDE 2020 · 48 citations
  5. Hybrid Subgraph Matching Framework Powered by Sketch Tree for Distributed SystemsYuejia Zhang, Weiguo Zheng, Zhijie Zhang, Peng Peng et al.ICDE 2022 · 12 citations
Dusk over the sea between two cliffs drawn in fine vertical lines