Information Technology Reference
In-Depth Information
A
X
B
'cites' relation
edge sequence
publication
Fig. 10.1.
An example of a connection between vertices A and B. Two paths originated
in A and B connected in a common vertex X.
The knowledge about complex relationships among publications can be used
for example for ranking the result of the search for publications using the com-
plex relationship discovery among entities present in the result and then sorting
them according to that information. Another use case can be an automated
recommendation of publications based on the preferred set of publications by
searching for close connections between the publications from the preferred set.
Intuitively, the complex relationship discovery has sense in any other field of
interest that incorporates graph structured data. For that reason, this chapter
introduces an indexing technique called the
ρ
-index that enables ecient dis-
covery of all complex relationships between any two inspected entities in large
collections of arbitrary graph structured data.
This chapter is then structured as follows, Section 10.2 presents related work
in the field of indexing graph structured data, Section 10.3 is a brief insight into
the design of the proposed indexing structure. Section 10.4 introduces a search
algorithm that is used to discover all paths between any two vertices in the
indexed graph using
ρ
-index. Consequently, the experimental evaluation of the
designed indexing structure and the search algorithm is in Section 10.5. Finally,
this chapter is concluded and some directions of the future work are proposed
in Section 10.6.
10.2
Related Work
The problem of answering various graph queries has two possible solutions. One
is through an algorithmic on the fly query answering and the other one is prepro-
cessing some indexing structure that would ease the computational complexity
of the query processing.
Firstly we discuss one of the on the fly algorithmic approaches which is Tar-
jan's algorithmic solution to a
single source path expression problem
from [18, 19]
