Projects          People          Publications          Presentations          Videos          Contact
Semantics and Integration
   Probabilistic ontologies

   Annotated RDF



Ontology systems

   RDF views



Related projects and labs


RDF (“Resource Description Framework”) is now a widely used 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 encompass those vertices in the graph that are within a given distance 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 answer graph based queries, (ii) memory needed to store the index, and (iii) the time to build the index. GRIN outperforms 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 queries.


Octavian Udrea, Andrea Pugliese, V.S. Subrahmanian


  • Octavian Udrea, Andrea Pugliese, and V. S. Subrahmanian. GRIN: A Graph Based RDF Index. In AAAI, pages 1465–1470, 2007 [PDF].
  • Andrea Pugliese, Octavian Udrea, and V. S. Subrahmanian. Scaling RDF with Time. To appear in the proceedings of WWW'08 [PDF].


  • A Graph-Based RDF Index presented at the 2007 AAAI [PPT].
Last updated: March 26 2008
Contact us with questions or comments