AG-Index: Adjacent Edge Hash Index for Graph Databases

Hui Hui Wang; Yun Peng; He Jiao Huang

doi:10.4028/www.scientific.net/AMM.631-632.1045

Paper Titles

Research and Build a Test Platform for EPON OLT Software
p.1023

Research on the Key Technologies of Highly Reliable Embedded IDE Based on R80515
p.1027

Structured Big Data Management System Supported Cross-Domain Query
p.1033

The Key Technology Research of Mechanical Parts Dynamic Management Database System
p.1039

AG-Index: Adjacent Edge Hash Index for Graph Databases
p.1045

Research and Design of a Massive Offline Data Analysis System Based on Hadoop
p.1049

Research on Data Mining Optimization and Security Based on MapReduce
p.1053

A Novel over Writable and Restoring Solution of Filesystem for NAND Flash
p.1057

Data Provenance Tracing for Transformation Diagram Based on Wivern
p.1061

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 631-632AG-Index: Adjacent Edge Hash Index for Graph...

AG-Index: Adjacent Edge Hash Index for Graph Databases

Abstract:

Many queries have been proposed to retrieve graphs. Among others, subgraph query is a fundamental one: given a graph database and a query graph, find the graphs in the database containing the query graph. Most existing works follow the filtering-and-verification framework, where a core task is to reduce the number of candidate graphs. This paper follows the framework and we propose a novel index, namely AG-Index. It indexes adjacent edge pairs of data graphs and can significantly reduce the number of candidate graphs. Our experiments show that our AG-Index outperforms several existing techniques on real-life datasets and synthetic datasets.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 631-632)

Pages:

1045-1048

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.631-632.1045

Citation:

Cite this paper

Online since:

September 2014

Authors:

Hui Hui Wang, Yun Peng, He Jiao Huang

Keywords:

Adjacent Edge Pairs, Filtering-and-Verification, Subgraph Query

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] J. M. Barnard, Substructure searching methods: Old and new, Journal of Chemical Information and Computer Sciences, vol. 33, no. 4, pp.532-538, (1993).

DOI: 10.1021/ci00014a001

Google Scholar

[2] M. Koyuturk, A. Grama, W. Szpankowski. An Efficient Algorithm for Detecting Frequent Subgraphs in Biological Networks. Bioinformatics, 20: I200-207, (2004).

DOI: 10.1093/bioinformatics/bth919

Google Scholar

[3] R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, E. Upfal. The Web as a Graph. ACM PODS Conference, (2000).

DOI: 10.1145/335168.335170

Google Scholar

[4] S. Raghavan, H. Garcia-Molina. Representing web graphs. ICDE Conference, pages 405-416, (2003).

Google Scholar

[5] Yan, X., Yu, P.S., Han, J.: Graph indexing: A frequent structure-based approach. In SIGMOD, PAGES 335-346, (2004).

Google Scholar

[6] X. Yan, P. S. Yu, and J. Han. Graph indexing based on discriminative frequent structure analysis. ACM Trans. Database Syst., 30(4): 960-993, (2005).

DOI: 10.1145/1114244.1114248

Google Scholar

[7] H. Shang, Y. Zhang, X. Lin, and J. X. Yu. Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. PVLDB, 1(1): 364-375, (2008).

DOI: 10.14778/1453856.1453899

Google Scholar