An Efficient and Scalable RDF Indexing Strategy based on B-Hashed-Bitmap Algorithm using CUDA
|
10.5120/18216-9221 |
Sharmi Sankar, Munesh Singh, Awny Sayed and Jihad Alkhalaf Bani-younis. Article: An Efficient and Scalable RDF Indexing Strategy based on B-Hashed-Bitmap Algorithm using CUDA. International Journal of Computer Applications 104(7):31-38, October 2014. Full text available. BibTeX
@article{key:article,
author = {Sharmi Sankar and Munesh Singh and Awny Sayed and Jihad Alkhalaf Bani-younis},
title = {Article: An Efficient and Scalable RDF Indexing Strategy based on B-Hashed-Bitmap Algorithm using CUDA},
journal = {International Journal of Computer Applications},
year = {2014},
volume = {104},
number = {7},
pages = {31-38},
month = {October},
note = {Full text available}
}
Abstract
Indexing enormous databases such as RDF has been a focus of intense research. As is well understood, indexing plays a pivotal role in speeding up data retrieval operations and query performance. Besides expediting search, an index can motivate new data-store schemes and technologies that can possibly revolutionize large data-analytics engine design, more often relevant to semantic web. Due to the proliferation of internet and the ease of creating and generating data on the fly - handling, storing and the subsequent semantic processing has proven to be a major bottleneck for the RDF data community. Handling data of such scale and magnitude requires a parallel approach as provided by the GPUs (Graphical processing units). In this paper, a new efficient and scalable index is proposed that uses a combination of B+ trees, hashing and sparse matrices. These data structures have an edge over others in terms of their implementation as a parallel algorithm using the CUDA (Compute Unified Device Architecture) framework meant to program massively parallel GPU multicores. So far, RDF data has been mostly implemented either as a RDBMS or as a non-native data-store, in both cases the sequential indexing strategy fails miserably with the scaling of the data-store. Parallel implementation of indices provides a suitable option for dealing with scalable and dynamically generated data over distributed networks. The crucial sparse matrix part of the proposed index is benchmarked against different CUDA memory implementations to derive optimal matrix processing options. The sparse matrix search is profiled using cudamemchk and visual profiler for identifying bottlenecks and inconsistencies in thread execution called thread divergence. Benchmarking the data provides promising results for a B+ tree based index coupled with hashing and sparse matrix implementations.
References
- T. Berners-Lee, J. Hendler, and O. Lassila. The semantic web, Scientific American, 284(5), May 2001.
- Wolfgang Nejdl, Hadhami Dhraief, Martin Wolpers, O-Telos-RDF: A Resource Description Format with Enhanced Meta-Modeling Functionalities based on O-Telos
- Svihla,M. Transforming Relational Data into Ontology Based RDF Data( a doctoral thesis). June 2007.
- Antoniou, G. and van Harmelen, F. (2004). A Semantic Web Primer. Cambridge: The MIT Press.
- Speeding up on-disk RDF index lookups using B+Hash trees, Minh Khoa Nguyen, Cosmin Basca, Abraham Bernstein, IOS Press, 2012
- T. Neumann and G. Weikum, RDF-3X: A RISC-style engine for RDF, Proc. VLDB, 1(1), 2008
- Mohammed Hussain, Pankil Doshi, Latifur Khan, James McGlothlin, Murat Kantarcioglu, Bhavani Thuraisingham, Efficient Query Processing for Large RDF Graphs Using Hadoop and MapReduce, Technical Report UTDCS-41-09, Department of Computer Science, The University of Texas at Dallas, November, 2009.
- Hexastore: Sextuple Indexing for Semantic Web Data Management, Cathrin Weiss, Panagiotis Karras, Abraham Bernstein
- Large RDF Representation Framework for GPUs Case Study Key-Value Storage and Binary Triple Pattern, Chidchanok Choksuchat, Chantana Chantrapornchai, International Computer Science and Engineering Conference (ICSEC), 2013
- Binary RDF representation for publication and exchange (HDT), Javier D. Fernandez, Miguel A. Martinez-Prieto, Claudio Gutierrez, Axel Polleres, Mario Arias, Journal of Web Semantics: Science, Services, and Agents on the World Wide Web, Elsevier
- Optimizing RDF stores by coupling General-purpose Graphics Processing Units and Central Processing Units, Bassem Makni
- Erling and Mikhailov, RDF Support in the Virtuoso DBMS
- Javier D. Fernándeza, Miguel A. Martínez-Prietoa, Claudio Gutiérrezb, Axel Polleresc, Mario Ariasa, Binary RDF representation for publication and exchange (HDT), Web Semantics: Science, Services and Agents on the World Wide Web, Vol. 19, March 2013
- Efficient Hash Tables on the GPU, Dan Anthony Feliciano Alcantara, PhD Thesis, University of California, Davis
- ceres-solver - Google Code: https://code. google. com/p/ceres-solver/
- NVIDIA Cusparse Library, DU-06709-001_v5. 5, July 2013, Nvidia Corporation.
- D. J. Abadi, A. Marcus, S. R. Madden, and K. Hollenbach. Scalable semantic web data management using vertical partitioning. In VLDB, pages 411–422, 2007.
- Hexastore: Sextuple Indexing for Semantic Web Data Management, Cathrin Weiss, Panagiotis Karras, Abraham Bernstein, 2008.
- Semantic Search over the Web Data-Centric Systems and Applications 2012, pp 31-60.
- Beckett, D. , The design and implementation of the Redland RDF application framework. Computer Networks, 39(5):577-588, 2002.
- Lee Feigenbaum, Sean Martin, Matthew N. Roy, Benjamin Szekely and Wing C. Yung: Boca: an open-source RDF store for building Semantic Web applications, Brief Bioinform (2007) 8 (3): 195-200.
- Guha, R. , rdfDB: An RDF Database, http://www. guha. com/rdfdb, 2007.
- Broekstra, J. , Kampman, A. , van Harmelen. Sesame: A Generic Architecture for Storing and Querying RDF and RDF Schema. ISWC, Springer, Sardinia, 2002.
- Towards distributed processing of RDF path queries, pages 207-230, Richard Vdovjak, Jeen Broekstra, Geert-Jan Houben
- Perfect Spatial Hashing, Sylvian Lefebvre, Hugues Hoppe, Microsoft Research.