Scalable and Adaptive Graph Querying with MapReduce

Song-Hyon KIM; Kyong-Ha LEE; Inchul SONG; Hyebong CHOI; Yoon-Joon LEE

doi:10.1587/transinf.E96.D.2126

Scalable and Adaptive Graph Querying with MapReduce

Song-Hyon KIM, Kyong-Ha LEE, Inchul SONG, Hyebong CHOI, Yoon-Joon LEE

Full Text Views

0

Share
Cite this

Summary :

We address the problem of processing graph pattern matching queries over a massive set of data graphs in this letter. As the number of data graphs is growing rapidly, it is often hard to process such queries with serial algorithms in a timely manner. We propose a distributed graph querying algorithm, which employs feature-based comparison and a filter-and-verify scheme working on the MapReduce framework. Moreover, we devise an efficient scheme that adaptively tunes a proper feature size at runtime by sampling data graphs. With various experiments, we show that the proposed method outperforms conventional algorithms in terms of scalability and efficiency.

Publication: IEICE TRANSACTIONS on Information Vol.E96-D No.9 pp.2126-2130

Publication Date: 2013/09/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.E96.D.2126

Type of Manuscript: LETTER

Category: Fundamentals of Information Systems

Authors

Song-Hyon KIM
  Korea Air Force Academy
Kyong-Ha LEE
  ETRI
Inchul SONG
  Samsung Electronics
Hyebong CHOI
  KAIST
Yoon-Joon LEE
  KAIST

Keyword

graph query, parallel processing, MapReduce, adaptive tuning

Cite this

Copy

Song-Hyon KIM, Kyong-Ha LEE, Inchul SONG, Hyebong CHOI, Yoon-Joon LEE, "Scalable and Adaptive Graph Querying with MapReduce" in IEICE TRANSACTIONS on Information, vol. E96-D, no. 9, pp. 2126-2130, September 2013, doi: 10.1587/transinf.E96.D.2126.
Abstract: We address the problem of processing graph pattern matching queries over a massive set of data graphs in this letter. As the number of data graphs is growing rapidly, it is often hard to process such queries with serial algorithms in a timely manner. We propose a distributed graph querying algorithm, which employs feature-based comparison and a filter-and-verify scheme working on the MapReduce framework. Moreover, we devise an efficient scheme that adaptively tunes a proper feature size at runtime by sampling data graphs. With various experiments, we show that the proposed method outperforms conventional algorithms in terms of scalability and efficiency.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.E96.D.2126/_p

Copy

@ARTICLE{e96-d_9_2126,
author={Song-Hyon KIM, Kyong-Ha LEE, Inchul SONG, Hyebong CHOI, Yoon-Joon LEE, },
journal={IEICE TRANSACTIONS on Information},
title={Scalable and Adaptive Graph Querying with MapReduce},
year={2013},
volume={E96-D},
number={9},
pages={2126-2130},
abstract={We address the problem of processing graph pattern matching queries over a massive set of data graphs in this letter. As the number of data graphs is growing rapidly, it is often hard to process such queries with serial algorithms in a timely manner. We propose a distributed graph querying algorithm, which employs feature-based comparison and a filter-and-verify scheme working on the MapReduce framework. Moreover, we devise an efficient scheme that adaptively tunes a proper feature size at runtime by sampling data graphs. With various experiments, we show that the proposed method outperforms conventional algorithms in terms of scalability and efficiency.},
keywords={},
doi={10.1587/transinf.E96.D.2126},
ISSN={1745-1361},
month={September},}

Copy

TY - JOUR
TI - Scalable and Adaptive Graph Querying with MapReduce
T2 - IEICE TRANSACTIONS on Information
SP - 2126
EP - 2130
AU - Song-Hyon KIM
AU - Kyong-Ha LEE
AU - Inchul SONG
AU - Hyebong CHOI
AU - Yoon-Joon LEE
PY - 2013
DO - 10.1587/transinf.E96.D.2126
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2013
AB - We address the problem of processing graph pattern matching queries over a massive set of data graphs in this letter. As the number of data graphs is growing rapidly, it is often hard to process such queries with serial algorithms in a timely manner. We propose a distributed graph querying algorithm, which employs feature-based comparison and a filter-and-verify scheme working on the MapReduce framework. Moreover, we devise an efficient scheme that adaptively tunes a proper feature size at runtime by sampling data graphs. With various experiments, we show that the proposed method outperforms conventional algorithms in terms of scalability and efficiency.
ER -