IEICE TRANSACTIONS on Information
Scalable and Adaptive Graph Querying with MapReduce
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
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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://global.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 -
English
