Jieming Shi
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.
- Alternative fueling station locator. http://www.afdc.energy.gov/locator/stations/.Google Scholar
- Bbc lab post. http://www.bbc.co.uk/blogs/internet/entries/63841314-c3c6--33d2-a7b8-f58ca040a65b.Google Scholar
- Crime in chicagoland. http://crime.chicagotribune.com/.Google Scholar
- Data.gov. http://www.data.gov.Google Scholar
- Dbpedia. http://wiki.dbpedia.org.Google Scholar
- Hospital compare. http://health.data.gov/def/cqld.Google Scholar
- Owlim-se. http://owlim.ontotext.com/display/OWLIMv43/OWLIM-SE.Google Scholar
- Parliament. http://parliament.semwebcentral.org.Google Scholar
- Patients like me. www.patientslikeme.com.Google Scholar
- Spot crime. http://www.spotcrime.com/.Google Scholar
- Virtuoso. http://virtuoso.openlinksw.com.Google Scholar
- Yago. http://www.mpi-inf.mpg.de/departments/databases-and-information-systems/research/yago-naga/yago/.Google Scholar
- S. Agrawal, S. Chaudhuri, and G. Das. Dbxplorer: A system for keyword-based search over relational databases. In ICDE, pages 5--16, 2002. Google ScholarDigital Library
- R. Battle and D. Kolas. Enabling the geospatial semantic web with parliament and geosparql. Semantic Web, 3(4):355--370, 2012. Google ScholarCross Ref
- 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.Google ScholarCross Ref
- A. Brodt, D. Nicklas, and B. Mitschang. Deep integration of spatial query processing into native RDF triple stores. In SIGSPATIAL, pages 33--42, 2010. Google ScholarDigital Library
- X. Cao, G. Cong, and C. S. Jensen. Retrieving top-k prestige-based relevant spatial web objects. PVLDB, 3(1):373--384, 2010. Google ScholarDigital Library
- X. Cao, G. Cong, C. S. Jensen, and M. L. Yiu. Retrieving regions of interest for user exploration. PVLDB, 7(9):733--744, 2014. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- S. Cohen, J. Mamou, Y. Kanza, and Y. Sagiv. Xsearch: A semantic search engine for XML. In VLDB, pages 45--56, 2003. Google ScholarDigital Library
- B. B. Dalvi, M. Kshirsagar, and S. Sudarshan. Keyword search on external memory data graphs. PVLDB, 1(1):1189--1204, 2008. Google ScholarDigital Library
- S. Elbassuoni and R. Blanco. Keyword search over RDF graphs. In CIKM, pages 237--242, 2011. Google ScholarDigital Library
- 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.Google Scholar
- R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. In PODS, 2001. Google ScholarDigital Library
- H. Fu and K. Anyanwu. Effectively interpreting keyword queries on RDF databases with a rear view. In ISWC, pages 193--208, 2011. Google ScholarDigital Library
- G. Giannopoulos, E. Biliri, and T. Sellis. Personalizing keyword search on RDF data. In TPDL, pages 272--278, 2013.Google ScholarCross Ref
- L. Guo, F. Shao, C. Botev, and J. Shanmugasundaram. XRANK: ranked keyword search over XML documents. In SIGMOD, pages 16--27, 2003. Google ScholarDigital Library
- A. Guttman. R-trees: A dynamic index structure for spatial searching. In SIGMOD, pages 47--57, 1984. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- H. He, H. Wang, J. Yang, and P. S. Yu. BLINKS: ranked keyword searches on graphs. In SIGMOD, pages 305--316, 2007. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- G. R. Hjaltason and H. Samet. Distance browsing in spatial databases. ACM Trans. Database Syst., 24(2):265--318, 1999. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- V. Hristidis, L. Gravano, and Y. Papakonstantinou. Efficient ir-style keyword search over relational databases. In VLDB, pages 850--861, 2003. Google ScholarDigital Library
- V. Hristidis and Y. Papakonstantinou. DISCOVER: keyword search in relational databases. In VLDB, pages 670--681, 2002. Google ScholarDigital Library
- J. Inglis. Inverted indexes and multi-list structures. Comput. J., 17(1):59--63, 1974.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- R. Jin, N. Ruan, S. Dey, and J. X. Yu. SCARAB: scaling reachability computation on large graphs. In SIGMOD, pages 169--180, 2012. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- K. Kyzirakos, M. Karpathiotakis, and M. Koubarakis. Strabon: A semantic geospatial DBMS. In ISWC, pages 295--311, 2012. Google ScholarDigital Library
- W. Le, F. Li, A. Kementsietsidis, and S. Duan. Scalable keyword search on large RDF data. TKDE, 26(11):2774--2788, 2014.Google ScholarCross Ref
- J. Leskovec and C. Faloutsos. Sampling from large graphs. In KDD, pages 631--636, 2006. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- J. Liagouris, N. Mamoulis, P. Bouros, and M. Terrovitis. An effective encoding scheme for spatial RDF data. PVLDB, 7(12):1271--1282, 2014. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- T. Neumann and G. Weikum. RDF-3X: a risc-style engine for RDF. PVLDB, 1(1):647--659, 2008. Google ScholarDigital Library
- J. M. Ponte and W. B. Croft. A language modeling approach to information retrieval. In SIGIR, pages 275--281, 1998. Google ScholarDigital Library
- E. Prud'Hommeaux, A. Seaborne, et al. Sparql query language for rdf. W3C recommendation, 15, 2008.Google Scholar
- D. Shasha, J. T. L. Wang, and R. Giugno. Algorithmics and applications of tree and graph searching. In PODS, pages 39--52, 2002. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- S. J. van Schaik and O. de Moor. A memory efficient reachability data structure through bit vector compression. In SIGMOD, pages 913--924, 2011. Google ScholarDigital Library
- C. Wang, W. Ku, and H. Chen. Geo-store: a spatially-augmented SPARQL query evaluation system. In SIGSPATIAL, pages 562--565, 2012. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- X. Yan, P. S. Yu, and J. Han. Substructure similarity search in graph databases. In SIGMOD, pages 766--777, 2005. Google ScholarDigital Library
- H. Yildirim, V. Chaoji, and M. J. Zaki. GRAIL: scalable reachability index for large graphs. PVLDB, 3(1):276--284, 2010. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
Index Terms
- Top-k Relevant Semantic Place Retrieval on Spatial RDF Data
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 librariesThis 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 ApplicationsAbstractThe 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