ABSTRACT
The World Wide Web Consortium's RDF standard primarily consists of (subject, property, object) triples that specify the value that a given subject has for a given property. However, it is frequently the case that even for a fixed subject and property, the value varies with time. As a consequence, efforts have been made to annotate RDF triples with "valid time" intervals. However, to date, no proposals exist for efficient indexing of such temporal RDF databases. It is clearly beneficial to store RDF data in a relational DB - however, standard relational indexes are inadequately equipped to handle RDF's graph structure. In this paper, we propose the tGRIN index structure that builds a specialized index for temporal RDF that is physically stored in an RDBMS. Past efforts to store RDF in relational stores include Jena2 from HP, Sesame from OpenRDF.org, and 3store from the University of Southampton. We show that even when these efforts are augmented with well known temporal indexes like R+ trees, SR-trees, ST-index, and MAP21, the tGRIN index exhibits superior performance. In terms of index build time, tGRIN takes two thirds or less of the time used by any other system, and it uses a comparable amount of memory and less disk space than Jena, Sesame and 3store. More importantly, tGRIN can answer queries three to six times faster for average query graph patterns and five to ten times faster for complex queries than these systems.
- D. J. Abadi, A. Marcus, S. Madden, and K. J. Hollenbach. Scalable semantic web data management using vertical partitioning. In VLDB, pages 411--422, 2007. Google ScholarDigital Library
- J. Abello and Y. Kotidis. Hierarchical graph indexing. In CIKM, pages 453--460, 2003. Google ScholarDigital Library
- S. C. Buraga and G. Ciobanu. A rdf-based model for expressing spatio-temporal relations between web sites. In WISE, pages 355--361, 2002. Google ScholarDigital Library
- L. P. Cordella, P. Foggia, C. Sansone, and M. Vento. A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs. IEEE Trans. PAMI, 26(10):1367--1372, 2004. Google ScholarDigital Library
- C. Gutiérrez, C. A. Hurtado, and A. A. Vaisman. Temporal rdf. In ESWC, pages 93--107, 2005. Google ScholarDigital Library
- C. Gutierrez, C. A. Hurtado, and A. A. Vaisman. Introducing time into rdf. IEEE Trans. Knowl. Data Eng., 19(2):207--218, 2007. Google ScholarDigital Library
- S. Harris and N. Gibbins. 3store: Efficient bulk rdf storage. In PSSS, pages 1--15, 2003.Google Scholar
- J. Heggland. Ontolog: Temporal annotation using ad hoc ontologies and application profiles. In ECDL, pages 118--128, London, UK, 2002. Springer-Verlag. Google ScholarDigital Library
- A. K. Jain, M. N. Murty, and P. J. Flynn. Data clustering: a review. ACM Comput. Surv., 31(3):264--323, 1999. Google ScholarDigital Library
- B. Liu and B. Hu. Path queries based rdf index. SKG, 0:91, 2005. Google ScholarDigital Library
- A. Martelli and U. Montanari. An efficient unification algorithm. ACM Trans. Program. Lang. Syst., 4(2):258--282, 1982. Google ScholarDigital Library
- A. Matono, T. Amagasa, M. Yoshikawa, and S. Uemura. An efficient pathway search using an indexing scheme for RDF. Genome Informatics, 14:374--375, 2003.Google Scholar
- B. Salzberg and V. J. Tsotras. Comparison of access methods for time-evolving data. ACM Comput. Surv., 31(2):158--221, 1999. Google ScholarDigital Library
- S. Trißl and U. Leser. Fast and practical indexing and querying of very large graphs. In SIGMOD, pages 845--856, 2007. Google ScholarDigital Library
- O. Udrea, A. Pugliese, and V. S. Subrahmanian. Grin: A graph based rdf index. In AAAI, pages 1465--1470, 2007. Google ScholarDigital Library
- X. Yan, P. S. Yu, and J. Han. Graph indexing: a frequent structure-based approach. In SIGMOD, pages 335--346, 2004. Google ScholarDigital Library
Index Terms
- Scaling RDF with Time
Recommendations
RDF, Jena, SparQL and the 'Semantic Web'
SIGUCCS '09: Proceedings of the 37th annual ACM SIGUCCS fall conference: communication and collaborationThe Resource Description Format (RDF) is used to represent information modeled as a "graph": a set of individual objects, along with a set of connections among those objects. In that role, RDF is one of the pillars of the so-called Semantic Web. This ...
Efficient RDF Query Processing using Multidimensional Indexing
PCI '17: Proceedings of the 21st Pan-Hellenic Conference on InformaticsEfficient management of RDF data is important due to the increasing number of data sources available in RDF, which fosters interoperability and enables data integration and interlinking. An RDF store maintains data in the form of triples, subject (S), ...
Faceted operations on composed RDF ontologies
Public and private organisations increasingly release their data. The use of these open data can be supported and stimulated by providing considerable metadata, including discovery, contextual and other detailed metadata. This paper argues that faceted ...
Comments