Index based graphs

[danwwilson]

Hi all,

I am trying to get my head around index based graphs. I am needing to know how they are created and the like.

Below is an ascii version of what one of these graphs might look like. I know this is a bit vague but any help that can be thrown my way would be much appreciated.

Value 1 | ----|
Value 2 | -|
Value 3 | |----
Value 4 | |---------
Value 5 | --|
-----------------------
50 100 50
Dan

[Epsilon=One]

I am trying to get my head around index based graphs. I am needing to know how they are created and the like.No small task if you are referring to graph indexing for SQL queries, etc. You're asking for a book length answer or an advanced university course.

You might start with the following:

http://www.CQthus.com/GraphIndexing (http://www-faculty.cs.uiuc.edu/~hanj/pdf/sigmod04_gindex.pdf)

[lovingnet5]

Graph has become increasingly important in modelling complicated structures and schemaless data such as proteins, chemical compounds, and XML documents. Given a graph query, it is desirable to retrieve graphs quickly from a large database via graph-based indices. In this paper, we investigate the issues of indexing graphs and propose a novel solution by applying a graph mining technique. Different from the existing path-based methods, our approach, called gIndex, makes use of frequent substructure as the basic indexing feature. Frequent substructures are ideal candidates since they explore the intrinsic characteristics of the data and are relatively stable to database updates. To reduce the size of index structure, two techniques, size-increasing support constraint and discriminative fragments, are introduced. Our performance study shows that gIndex has 10 times smaller index size, but achieves 3--10 times better performance in comparison with a typical path-based method, GraphGrep. The gIndex approach not only provides and elegant solution to the graph indexing problem, but also demonstrates how database indexing and query processing can benefit form data mining, especially frequent pattern mining. Furthermore, the concepts developed here can be applied to indexing sequences, trees, and other complicated structures as well.