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

Kim JHong SJeong SPark SYu K(2024)SGIR-Tree: Integrating R-Tree Spatial Indexing as Subgraphs in Graph Database Management SystemsISPRS International Journal of Geo-Information10.3390/ijgi1310034613:10(346)Online publication date: 27-Sep-2024
https://doi.org/10.3390/ijgi13100346
Wei BGuo XLi XWu ZZhao JZou Q(2024)Construct and Query A Fine-Grained Geospatial Knowledge GraphData Science and Engineering10.1007/s41019-023-00237-49:2(152-176)Online publication date: 22-Jan-2024
https://doi.org/10.1007/s41019-023-00237-4
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
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

22
Total Citations
View Citations
115
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kim JHong SJeong SPark SYu K(2024)SGIR-Tree: Integrating R-Tree Spatial Indexing as Subgraphs in Graph Database Management SystemsISPRS International Journal of Geo-Information10.3390/ijgi1310034613:10(346)Online publication date: 27-Sep-2024
https://doi.org/10.3390/ijgi13100346
Wei BGuo XLi XWu ZZhao JZou Q(2024)Construct and Query A Fine-Grained Geospatial Knowledge GraphData Science and Engineering10.1007/s41019-023-00237-49:2(152-176)Online publication date: 22-Jan-2024
https://doi.org/10.1007/s41019-023-00237-4
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
Bai LZhu L(2023)Path-Based Approximate Matching of Spatiotemporal RDF DataUncertain Spatiotemporal Data Management for the Semantic Web10.4018/978-1-6684-9108-9.ch005(81-101)Online publication date: 15-Dec-2023
https://doi.org/10.4018/978-1-6684-9108-9.ch005
Tian MHu XHuang JMa KLi HZheng STao LQiu Q(2023)Spatio-Temporal Relevance Classification from Geographic Texts Using Deep LearningISPRS International Journal of Geo-Information10.3390/ijgi1209035912:9(359)Online publication date: 1-Sep-2023
https://doi.org/10.3390/ijgi12090359
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
Zhang FLu QDu ZChen XCao C(2021)A comprehensive overview of RDF for spatial and spatiotemporal data managementThe Knowledge Engineering Review10.1017/S026988892100008436Online publication date: 22-Jun-2021
https://doi.org/10.1017/S0269888921000084
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.

Figures

Tables

Media

View Issue’s Table of Contents