research-article

An effective encoding scheme for spatial RDF data

Authors:

John Liagouris,

Nikos Mamoulis,

Panagiotis Bouros,

Manolis TerrovitisAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 7, Issue 12

Pages 1271 - 1282

https://doi.org/10.14778/2732977.2733000

Published: 01 August 2014 Publication History

Abstract

The RDF data model has recently been extended to support representation and querying of spatial information (i.e., locations and geometries), which is associated with RDF entities. Still, there are limited efforts towards extending RDF stores to efficiently support spatial queries, such as range selections (e.g., find entities within a given range) and spatial joins (e.g., find pairs of entities whose locations are close to each other). In this paper, we propose an extension for RDF stores that supports efficient spatial data management. Our contributions include an effective encoding scheme for entities having spatial locations, the introduction of on-the-fly spatial filters and spatial join algorithms, and several optimizations that minimize the overhead of geometry and dictionary accesses. We implemented the proposed techniques as an extension to the opensource RDF-3X engine and we experimentally evaluated them using real RDF knowledge bases. The results show that our system offers robust performance for spatial queries, while introducing little overhead to the original query engine.

References

[1]

Linkedgeodata. http://linkedgeodata.org/About.

[2]

Owlim-se. http://owlim.ontotext.com/display/OWLIMv43/OWLIM-SE.

[3]

Parliament. http://parliament.semwebcentral.org.

[4]

Virtuoso. http://virtuoso.openlinksw.com.

[5]

D. J. Abadi, A. Marcus, S. Madden, and K. J. Hollenbach. Scalable semantic web data management using vertical partitioning. In VLDB, 2007.

Digital Library

[6]

M. Atre, V. Chaoji, M. J. Zaki, and J. A. Hendler. Matrix "bit" loaded: a scalable lightweight join query processor for rdf data. In WWW, 2010.

Digital Library

[7]

R. Battle and D. Kolas. Enabling the geospatial semantic web with parliament and geosparql. Semantic Web, 3(4): 355--370, 2012.

[8]

M. A. Bornea, J. Dolby, A. Kementsietsidis, K. Srinivas, P. Dantressangle, O. Udrea, and B. Bhattacharjee. Building an efficient rdf store over a relational database. In SIGMOD, 2013.

Digital Library

[9]

T. Brinkhoff, H.-P. Kriegel, and B. Seeger. Efficient processing of spatial joins using r-trees. In SIGMOD, 1993.

Digital Library

[10]

A. Brodt, D. Nicklas, and B. Mitschang. Deep integration of spatial query processing into native rdf triple stores. In GIS, 2010.

Digital Library

[11]

J. Broekstra, A. Kampman, and F. van Harmelen. Sesame: An architecture for storin gand querying rdf data and schema information. In Spinning the Semantic Web, pages 197--222, 2003.

[12]

E. I. Chong, S. Das, G. Eadon, and J. Srinivasan. An efficient sql-based rdf querying scheme. In VLDB, 2005.

Digital Library

[13]

A. Guttman. R-trees: A dynamic index structure for spatial searching. In SIGMOD, 1984.

Digital Library

[14]

M. Hadjieleftheriou, E. G. Hoel, and V. J. Tsotras. Sail: A spatial index library for efficient application integration. GeoInformatica, 9(4): 367--389, 2005.

Digital Library

[15]

J. Hoffart, F. M. Suchanek, K. Berberich, and G. Weikum. Yago2: A spatially and temporally enhanced knowledge base from wikipedia. Artificial Intelligence, 194: 28--61, 2013.

Digital Library

[16]

M. Koubarakis and K. Kyzirakos. Modeling and querying metadata in the semantic sensor web: The model strdf and the query language stsparql. In ESWC (1), pages 425--439, 2010.

Digital Library

[17]

K. Kyzirakos, M. Karpathiotakis, and M. Koubarakis. Strabon: A semantic geospatial dbms. In ISWC (1), pages 295--311, 2012.

Digital Library

[18]

M.-L. Lo and C. V. Ravishankar. Spatial hash-joins. In SIGMOD, 1996.

Digital Library

[19]

N. Mamoulis and D. Papadias. Slot index spatial join. TKDE., 15(1): 211--231, 2003.

Digital Library

[20]

T. Neumann and G. Moerkotte. Characteristic sets: Accurate cardinality estimation for rdf queries with multiple joins. In ICDE, 2011.

Digital Library

[21]

T. Neumann and G. Weikum. Rdf-3x: a risc-style engine for rdf. PVLDB, 1(1): 647--659, 2008.

Digital Library

[22]

T. Neumann and G. Weikum. Scalable join processing on very large rdf graphs. In SIGMOD, 2009.

Digital Library

[23]

C.-J. Wang, W.-S. Ku, and H. Chen. Geo-store: a spatially-augmented sparql query evaluation system. In GIS, 2012.

Digital Library

[24]

D. Wang, L. Zou, Y. Feng, X. Shen, J. Tian, and D. Zhao. S-store: An engine for large rdf graph integrating spatial information. In DASFAA (2), pages 31--47, 2013.

[25]

C. Weiss, P. Karras, and A. Bernstein. Hexastore: sextuple indexing for semantic web data management. PVLDB, 1(1): 1008--1019, 2008.

Digital Library

[26]

K. Wilkinson, C. Sayers, H. A. Kuno, and D. Reynolds. Efficient rdf storage and retrieval in jena2. In SWDB, 2003.

[27]

Y. Yan, C. Wang, A. Zhou, W. Qian, L. Ma, and Y. Pan. Efficient indices using graph partitioning in rdf triple stores. In ICDE, 2009.

Digital Library

[28]

P. Yuan, P. Liu, B. Wu, H. Jin, W. Zhang, and L. Liu. Triplebit: a fast and compact system for large scale rdf data. PVLDB, 6(7): 517--528, 2013.

Digital Library

[29]

K. Zeng, J. Yang, H. Wang, B. Shao, and Z. Wang. A distributed graph engine for web scale rdf data. PVLDB, 6(4): 265--276, 2013.

Digital Library

[30]

L. Zou, J. Mo, L. Chen, M. T. Özsu, and D. Zhao. gstore: Answering sparql queries via subgraph matching. PVLDB, 4(8): 482--493, 2011.

Digital Library

Cited By

Zhu LLu JBai L(2024)Path-based approximate matching of fuzzy spatiotemporal RDF dataWorld Wide Web10.1007/s11280-024-01247-627:2Online publication date: 3-Feb-2024
https://dl.acm.org/doi/10.1007/s11280-024-01247-6
Wei BGuo XWu ZZhao JZou Q(2023)Construct Fine-Grained Geospatial Knowledge GraphDatabase Systems for Advanced Applications. DASFAA 2023 International Workshops10.1007/978-3-031-35415-1_19(267-282)Online publication date: 17-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-35415-1_19
Theocharidis KLiagouris JMamoulis NBouros PTerrovitis M(2022)SRX: efficient management of spatial RDF dataThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-019-00554-z28:5(703-733)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/s00778-019-00554-z
Show More Cited By

An effective encoding scheme for spatial RDF data
1. Information systems
  1. Data management systems
    1. Database management system engines
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory

Recommendations

Top-k Relevant Semantic Place Retrieval on Spatial RDF Data
SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

RDF data are traditionally accessed using structured query languages, such as SPARQL. However, this requires users to understand the language as well as the RDF schema. Keyword search on RDF data aims at relieving the user from these requirements; the ...
Deep integration of spatial query processing into native RDF triple stores
GIS '10: Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems

Semantic Web technologies, most notably RDF, are well-suited to cope with typical challenges in spatial data management including analyzing complex relations between entities, integrating heterogeneous data sources and exploiting poorly structured data, ...
SRX: efficient management of spatial RDF data
Abstract
We present a general encoding scheme for the efficient management of spatial RDF data. The scheme approximates the geometries of the RDF entities inside their (integer) IDs and can be used, along with several operators and optimizations we ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 7, Issue 12

August 2014

296 pages

ISSN:2150-8097

Editors:
H. V. Jagadish
University of Michigan
,
Aoying Zhou
East Normal University, China

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 August 2014

Published in PVLDB Volume 7, Issue 12

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
115
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhu LLu JBai L(2024)Path-based approximate matching of fuzzy spatiotemporal RDF dataWorld Wide Web10.1007/s11280-024-01247-627:2Online publication date: 3-Feb-2024
https://dl.acm.org/doi/10.1007/s11280-024-01247-6
Wei BGuo XWu ZZhao JZou Q(2023)Construct Fine-Grained Geospatial Knowledge GraphDatabase Systems for Advanced Applications. DASFAA 2023 International Workshops10.1007/978-3-031-35415-1_19(267-282)Online publication date: 17-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-35415-1_19
Theocharidis KLiagouris JMamoulis NBouros PTerrovitis M(2022)SRX: efficient management of spatial RDF dataThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-019-00554-z28:5(703-733)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/s00778-019-00554-z
Glake DRitter NOcker FAhmady-Moghaddam NOsterholz DLenfers UClemen TDemartini GZuccon GCulpepper JHuang ZTong H(2021)Hierarchical Semantics Matching For Heterogeneous Spatio-temporal SourcesProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3482350(565-575)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3459637.3482350
Sun YSarwat M(2021)Riso-Tree: An Efficient and Scalable Index for Spatial Entities in Graph Database Management SystemsACM Transactions on Spatial Algorithms and Systems10.1145/34509457:3(1-39)Online publication date: 16-Jun-2021
https://dl.acm.org/doi/10.1145/3450945
Bouros PMamoulis N(2019)Spatial joinsSIGSPATIAL Special10.1145/3355491.335549411:1(13-21)Online publication date: 5-Aug-2019
https://dl.acm.org/doi/10.1145/3355491.3355494
Vlachou ADoulkeridis CGlenis ASantipantakis GVouros GHung CPapadopoulos G(2019)Efficient spatio-temporal RDF query processing in large dynamic knowledge basesProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3299732(439-447)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3299732
Nikitopoulos PVlachou ADoulkeridis CVouros G(2019)Parallel and scalable processing of spatio-temporal RDF queries using SparkGeoinformatica10.1007/s10707-019-00371-025:4(623-653)Online publication date: 3-Jul-2019
https://dl.acm.org/doi/10.1007/s10707-019-00371-0
Sun YSarwat M(2019)A spatially-pruned vertex expansion operator in the Neo4j graph database systemGeoinformatica10.1007/s10707-019-00361-223:3(397-423)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s10707-019-00361-2
Sun YSarwat MBanaei-Kashani FHoel EGüting RTamassia RXiong L(2018)A generic database indexing framework for large-scale geographic knowledge graphsProceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3274895.3274966(289-298)Online publication date: 6-Nov-2018
https://dl.acm.org/doi/10.1145/3274895.3274966
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents