Efficient Subgraph Indexing for Biochemical Graphs

Chimi Wangmo, Lena Wiese

2022

Abstract

The dynamic nature of graph-structured data demands fast subgraph query processing to solve real-world problems such as identifying spammers in social networks, fraud detection in the financial system, and finding motifs in biological networks. The need for an efficient subgraph search has motivated the study for filtering the candidate graphs using the filter-then-verify framework with minimal indexing size. This paper presents an efficient in-memory index structure for indexing the paths in the transaction graph database. Our radix tree-based index structure addresses the issue of high memory consumption related to trie for representing biochemical datasets. Furthermore, we also contrast various containers used in the radix nodes. We demonstrate empirically the benefits of compressing the common prefixes in the path by achieving 20% reduction in the indexing size than a trie-based implementation.

Paper Citation

in Harvard Style

Wangmo C. and Wiese L. (2022). Efficient Subgraph Indexing for Biochemical Graphs. In Proceedings of the 11th International Conference on Data Science, Technology and Applications - Volume 1: DATA, ISBN 978-989-758-583-8, pages 533-540. DOI: 10.5220/0011350100003269

in Bibtex Style

@conference{data22,
author={Chimi Wangmo and Lena Wiese},
title={Efficient Subgraph Indexing for Biochemical Graphs},
booktitle={Proceedings of the 11th International Conference on Data Science, Technology and Applications - Volume 1: DATA,},
year={2022},
pages={533-540},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0011350100003269},
isbn={978-989-758-583-8},
}

in EndNote Style

TY - CONF

JO - Proceedings of the 11th International Conference on Data Science, Technology and Applications - Volume 1: DATA,
TI - Efficient Subgraph Indexing for Biochemical Graphs
SN - 978-989-758-583-8
AU - Wangmo C.
AU - Wiese L.
PY - 2022
SP - 533
EP - 540
DO - 10.5220/0011350100003269