A hybrid approach combining R*-tree and k-d trees to improve linked open data query performance

Yuxiang Sun, Tianyi Zhao, Seulgi Yoon, Yongju Lee

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

Semantic Web has recently gained traction with the use of Linked Open Data (LOD) on the Web. Although numerous state-of-the-art methodologies, standards, and technologies are applicable to the LOD cloud, many issues persist. Because the LOD cloud is based on graph-based resource description framework (RDF) triples and the SPARQL query language, we cannot directly adopt traditional techniques employed for database management systems or distributed computing systems. This paper addresses how the LOD cloud can be efficiently organized, retrieved, and evaluated. We propose a novel hybrid approach that combines the index and live exploration approaches for improved LOD join query performance. Using a two-step index structure combining a disk-based 3D R*-tree with the extended multidimensional histogram and flash memory-based k-d trees, we can efficiently discover interlinked data distributed across multiple resources. Because this method rapidly prunes numerous false hits, the performance of join query processing is remarkably improved. We also propose a hot-cold segment identification algorithm to identify regions of high interest. The proposed method is compared with existing popular methods on real RDF datasets. Results indicate that our method outperforms the existing methods because it can quickly obtain target results by reducing unnecessary data scanning and reduce the amount of main memory required to load filtering results.

Original languageEnglish
Article number2405
JournalApplied Sciences (Switzerland)
Volume11
Issue number5
DOIs
StatePublished - 1 Mar 2021

Keywords

  • Big Data
  • Index structure
  • Join query
  • LOD cloud
  • Multidimensional histogram
  • RDF

Fingerprint

Dive into the research topics of 'A hybrid approach combining R*-tree and k-d trees to improve linked open data query performance'. Together they form a unique fingerprint.

Cite this