GRIN: A graph based RDF index

TitleGRIN: A graph based RDF index
Publication TypeConference Papers
Year of Publication2007
AuthorsUdrea O, Pugliese A, V.S. Subrahmanian
Conference NameProceedings of the National Conference on Artificial Intelligence
Date Published2007///

RDF (“Resource Description Framework”) is now a widelyused World Wide Web Consortium standard. However,
methods to index large volumes of RDF data are still in
their infancy. In this paper, we focus on providing a very
lightweight indexing mechanism for certain kinds of RDF
queries, namely graph-based queries where there is a need to
traverse edges in the graph determined by an RDF database.
Our approach uses the idea of drawing circles around selected
“center” vertices in the graph where the circle would encom-
pass those vertices in the graph that are within a given dis-
tance of the “center” vertex. We come up with methods of
finding such “center” vertices and identifying the radius of the
circles and then leverage this to build an index called GRIN.
We compare GRIN with three existing RDF indexex: Jena,
Sesame, and RDFBroker. We compared (i) the time to an-
swer graph based queries, (ii) memory needed to store the
index, and (iii) the time to build the index. GRIN outper-
forms Jena, Sesame and RDFBroker on all three measures
for graph based queries (for other types of queries, it may be
worth building one of these other indexes and using it), at the
expense of using a larger amount of memory when answering