More Web Proxy on the site http://driver.im/

research-article

Top-k Relevant Semantic Place Retrieval on Spatial RDF Data

Authors:

Nikos MamoulisAuthors Info & Claims

SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

Pages 1977 - 1990

https://doi.org/10.1145/2882903.2882941

Published: 26 June 2016 Publication History

Abstract

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 user only inputs a set of keywords and the goal is to find small RDF subgraphs which contain all keywords. At the same time, popular RDF knowledge bases also include spatial semantics, which opens the road to location-based search operations. In this work, we propose and study a novel location-based keyword search query on RDF data. The objective of top-k relevant semantic places (kSP) retrieval is to find RDF subgraphs which contain the query keywords and are rooted at spatial entities close to the query location. The novelty of kSP queries is that they are location-aware and that they do not rely on the use of structured query languages. We design a basic method for the processing of kSP queries. To further accelerate kSP retrieval, two pruning approaches and a data preprocessing technique are proposed. Extensive empirical studies on two real datasets demonstrate the superior and robust performance of our proposals compared to the basic method.

References

[1]

Alternative fueling station locator. http://www.afdc.energy.gov/locator/stations/.

[2]

Bbc lab post. http://www.bbc.co.uk/blogs/internet/entries/63841314-c3c6--33d2-a7b8-f58ca040a65b.

[3]

Crime in chicagoland. http://crime.chicagotribune.com/.

[4]

Data.gov. http://www.data.gov.

[5]

Dbpedia. http://wiki.dbpedia.org.

[6]

Hospital compare. http://health.data.gov/def/cqld.

[7]

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

[8]

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

[9]

Patients like me. www.patientslikeme.com.

[10]

Spot crime. http://www.spotcrime.com/.

[11]

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

[12]

Yago. http://www.mpi-inf.mpg.de/departments/databases-and-information-systems/research/yago-naga/yago/.

[13]

S. Agrawal, S. Chaudhuri, and G. Das. Dbxplorer: A system for keyword-based search over relational databases. In ICDE, pages 5--16, 2002.

Digital Library

[14]

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

[15]

N. Bikakis, G. Giannopoulos, J. Liagouris, D. Skoutas, T. Dalamagas, and T. Sellis. Rdivf: Diversifying keyword search on RDF graphs. In TPDL, pages 413--416, 2013.

[16]

A. Brodt, D. Nicklas, and B. Mitschang. Deep integration of spatial query processing into native RDF triple stores. In SIGSPATIAL, pages 33--42, 2010.

Digital Library

[17]

X. Cao, G. Cong, and C. S. Jensen. Retrieving top-k prestige-based relevant spatial web objects. PVLDB, 3(1):373--384, 2010.

Digital Library

[18]

X. Cao, G. Cong, C. S. Jensen, and M. L. Yiu. Retrieving regions of interest for user exploration. PVLDB, 7(9):733--744, 2014.

Digital Library

[19]

P. Cappellari, R. D. Virgilio, A. Maccioni, and M. Roantree. A path-oriented RDF index for keyword search query processing. In DEXA, pages 366--380, 2011.

Digital Library

[20]

J. Cheng, S. Huang, H. Wu, and A. W. Fu. Tf-label: a topological-folding labeling scheme for reachability querying in a large graph. In SIGMOD, pages 193--204, 2013.

Digital Library

[21]

S. Cohen, J. Mamou, Y. Kanza, and Y. Sagiv. Xsearch: A semantic search engine for XML. In VLDB, pages 45--56, 2003.

Digital Library

[22]

B. B. Dalvi, M. Kshirsagar, and S. Sudarshan. Keyword search on external memory data graphs. PVLDB, 1(1):1189--1204, 2008.

Digital Library

[23]

S. Elbassuoni and R. Blanco. Keyword search over RDF graphs. In CIKM, pages 237--242, 2011.

Digital Library

[24]

S. Elbassuoni, M. Ramanath, R. Schenkel, and G. Weikum. Searching RDF graphs with SPARQL and keywords. IEEE Data Eng. Bull., 33(1):16--24, 2010.

[25]

R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. In PODS, 2001.

Digital Library

[26]

H. Fu and K. Anyanwu. Effectively interpreting keyword queries on RDF databases with a rear view. In ISWC, pages 193--208, 2011.

Digital Library

[27]

G. Giannopoulos, E. Biliri, and T. Sellis. Personalizing keyword search on RDF data. In TPDL, pages 272--278, 2013.

[28]

L. Guo, F. Shao, C. Botev, and J. Shanmugasundaram. XRANK: ranked keyword search over XML documents. In SIGMOD, pages 16--27, 2003.

Digital Library

[29]

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

Digital Library

[30]

C. Halaschek-Wiener, B. Aleman-Meza, I. B. Arpinar, and A. P. Sheth. Discovering and ranking semantic associations over a large RDF metabase. In VLDB, pages 1317--1320, 2004.

Digital Library

[31]

H. He, H. Wang, J. Yang, and P. S. Yu. BLINKS: ranked keyword searches on graphs. In SIGMOD, pages 305--316, 2007.

Digital Library

[32]

J. A. Hendler, J. Holm, C. Musialek, and G. Thomas. US government linked open data: Semantic.data.gov. IEEE Intelligent Systems, 27(3):25--31, 2012.

Digital Library

[33]

G. R. Hjaltason and H. Samet. Distance browsing in spatial databases. ACM Trans. Database Syst., 24(2):265--318, 1999.

Digital Library

[34]

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

Digital Library

[35]

V. Hristidis, L. Gravano, and Y. Papakonstantinou. Efficient ir-style keyword search over relational databases. In VLDB, pages 850--861, 2003.

Digital Library

[36]

V. Hristidis and Y. Papakonstantinou. DISCOVER: keyword search in relational databases. In VLDB, pages 670--681, 2002.

Digital Library

[37]

J. Inglis. Inverted indexes and multi-list structures. Comput. J., 17(1):59--63, 1974.

[38]

H. Jiang, H. Wang, P. S. Yu, and S. Zhou. Gstring: A novel approach for efficient search in graph databases. In ICDE, pages 566--575, 2007.

[39]

R. Jin, N. Ruan, S. Dey, and J. X. Yu. SCARAB: scaling reachability computation on large graphs. In SIGMOD, pages 169--180, 2012.

Digital Library

[40]

R. Jin, N. Ruan, Y. Xiang, and H. Wang. Path-tree: An efficient reachability indexing scheme for large directed graphs. ACM Trans. Database Syst., 36(1):7, 2011.

Digital Library

[41]

V. Kacholia, S. Pandit, S. Chakrabarti, S. Sudarshan, R. Desai, and H. Karambelkar. Bidirectional expansion for keyword search on graph databases. In VLDB, pages 505--516, 2005.

Digital Library

[42]

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

Digital Library

[43]

W. Le, F. Li, A. Kementsietsidis, and S. Duan. Scalable keyword search on large RDF data. TKDE, 26(11):2774--2788, 2014.

[44]

J. Leskovec and C. Faloutsos. Sampling from large graphs. In KDD, pages 631--636, 2006.

Digital Library

[45]

S. T. Leutenegger, J. M. Edgington, and M. A. Lopez. STR: A simple and efficient algorithm for R-tree packing. In ICDE97, pages 497--506, 1997.

Digital Library

[46]

J. Liagouris, N. Mamoulis, P. Bouros, and M. Terrovitis. An effective encoding scheme for spatial RDF data. PVLDB, 7(12):1271--1282, 2014.

Digital Library

[47]

X. Lian, E. D. Hoyos, A. Chebotko, B. Fu, and C. Reilly. k-nearest keyword search in RDF graphs. J. Web Sem., 22:40--56, 2013.

Digital Library

[48]

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

Digital Library

[49]

J. M. Ponte and W. B. Croft. A language modeling approach to information retrieval. In SIGIR, pages 275--281, 1998.

Digital Library

[50]

E. Prud'Hommeaux, A. Seaborne, et al. Sparql query language for rdf. W3C recommendation, 15, 2008.

[51]

D. Shasha, J. T. L. Wang, and R. Giugno. Algorithmics and applications of tree and graph searching. In PODS, pages 39--52, 2002.

Digital Library

[52]

T. Tran, H. Wang, S. Rudolph, and P. Cimiano. Top-k exploration of query candidates for efficient keyword search on graph-shaped (RDF) data. In ICDE, pages 405--416, 2009.

Digital Library

[53]

S. J. van Schaik and O. de Moor. A memory efficient reachability data structure through bit vector compression. In SIGMOD, pages 913--924, 2011.

Digital Library

[54]

C. Wang, W. Ku, and H. Chen. Geo-store: a spatially-augmented SPARQL query evaluation system. In SIGSPATIAL, pages 562--565, 2012.

Digital Library

[55]

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, pages 31--47, 2013.

[56]

H. Wang and C. C. Aggarwal. A survey of algorithms for keyword search on graph data. In Managing and Mining Graph Data, pages 249--273. 2010.

[57]

X. Yan, P. S. Yu, and J. Han. Substructure similarity search in graph databases. In SIGMOD, pages 766--777, 2005.

Digital Library

[58]

H. Yildirim, V. Chaoji, and M. J. Zaki. GRAIL: scalable reachability index for large graphs. PVLDB, 3(1):276--284, 2010.

Digital Library

[59]

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

[60]

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
Jiang JChoi BHuang XXu JBhowmick S(2024)DKWS: A Distributed System for Keyword Search on Massive GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3313726(1-16)Online publication date: 2024
https://doi.org/10.1109/TKDE.2023.3313726
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

Index Terms

Top-k Relevant Semantic Place Retrieval on Spatial RDF Data
1. Information systems

Recommendations

Research and Implementation of Mine Risk Area Semantic Retrieval System based on Ontology

In this paper, the authors first analyze the research and development of semantic retrieval technology based on ontology, and introduce the key theoretical knowledge of ontology and semantic web, including the definition, description language, ...
Ontology acquisition and semantic retrieval from semantic annotated chinese poetry
JCDL '04: Proceedings of the 4th ACM/IEEE-CS joint conference on Digital libraries

This research aims to utilize semantic web[1]. technology to the semantic annotation of classical Chinese poetry. We investigate the feasibilities and advantages of semantic retrieval and automated ontology acquisition from semantically annotated poems ...
Semantic Region Retrieval from Spatial RDF Data
Database Systems for Advanced Applications
Abstract
The top-k most relevant Semantic Place retrieval (kSP) query on spatial RDF data combines keyword-based and location-based retrieval. The query returns semantic places that are subgraphs rooted at a place entity with an associated location. The ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

June 2016

2300 pages

ISBN:9781450335317

DOI:10.1145/2882903

General Chairs:
Fatma Özcan
IBM Research, USA
,
Georgia Koutrika
HP Labs, USA
,
Program Chair:
Sam Madden
Massachusetts Institute of Technology, USA

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Hong Kong RGC
EU
National Nat- ural Science Foundation of China

Conference

SIGMOD/PODS'16

Sponsor:

SIGMOD

SIGMOD/PODS'16: International Conference on Management of Data

June 26 - July 1, 2016

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
558
Total Downloads

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

Reflects downloads up to 31 Dec 2024

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
Jiang JChoi BHuang XXu JBhowmick S(2024)DKWS: A Distributed System for Keyword Search on Massive GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3313726(1-16)Online publication date: 2024
https://doi.org/10.1109/TKDE.2023.3313726
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
Fakas GKalamatianos G(2023)Proportionality on Spatial Data with ContextACM Transactions on Database Systems10.1145/358843448:2(1-37)Online publication date: 13-May-2023
https://dl.acm.org/doi/10.1145/3588434
Cinar EAltingovde IChen HDuh WHuang HKato MMothe JPoblete B(2023)Exploiting Cluster-Skipping Inverted Index for Semantic Place RetrievalProceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3539618.3591983(1981-1985)Online publication date: 19-Jul-2023
https://dl.acm.org/doi/10.1145/3539618.3591983
Lu JZhou ZLiu JFeng J(2023)SSPR: A Skyline-Based Semantic Place Retrieval MethodNeural Information Processing10.1007/978-3-031-30105-6_28(331-342)Online publication date: 13-Apr-2023
https://doi.org/10.1007/978-3-031-30105-6_28
Mahboubi SAkbarinia RValduriez P(2022)Privacy-Preserving Top-k Query Processing in Distributed SystemsTransactions on Large-Scale Data- and Knowledge-Centered Systems XLII10.1007/978-3-662-60531-8_1(1-24)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-662-60531-8_1
Chen ZYao BWang ZGao XShang SMa SGuo M(2021)Flexible Aggregate Nearest Neighbor Queries and its Keyword-Aware Variant on Road NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.297599833:12(3701-3715)Online publication date: 1-Dec-2021
https://doi.org/10.1109/TKDE.2020.2975998
Jiang JChoi BXu JBhowmick S(2021)A Generic Ontology Framework for Indexing Keyword Search on Massive GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2019.295653533:6(2322-2336)Online publication date: 1-Jun-2021
https://doi.org/10.1109/TKDE.2019.2956535
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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents