System |Π: A Native RDF Repository Based on the Hypergraph Representation for RDF Data Model

RDF is the data interchange layer for the Semantic Web. In order to manage the increasing amount of RDF data, an RDF repository should provide not only the necessary scalability and efficiency, but also sufficient inference capabilities. Though existing RDF repositories have made progress towards these goals, there is still ample space for improving the overall performance. In this paper, we propose a native RDF repository, System Π, to pursue a better tradeoff among system scalability, query efficiency, and inference capabilities. System Π takes a hypergraph representation for RDF as the data model for its persistent storage, which effectively avoids the costs of data model transformation when accessing RDF data. Based on this native storage scheme, a set of efficient semantic query processing techniques are designed. First, several indices are built to accelerate RDF data access including a value index, a labeling scheme for transitive closure computation, and three triple indices. Second, we propose a hybrid inference strategy under the pD ^* semantics to support inference for OWL-Lite with a relatively low computational complexity. Finally, we extend the SPARQL algebra to explicitly express inference semantics in logical query plan by defining some new algebra operators. In addition, MD5 hash value of URI and schema level cache are introduced as practical implementation techniques. The results of performance evaluation on the LUBM benchmark and a real data set show that System Π has a better combined metric value than other comparable systems.     

基于Neo4j的领域本体存储方法研究*

在分析民航突发事件应急管理领域本体及其存储特点的基础上,提出了一种基于Neo4j的领域本体RDF图数据存储方法,研究了领域本体RDF有向标记图结构与Neo4j图数据库存储模型的关系,结合民航突发事件应急管理领域本体的实例查询,给出了RDF图与Neo4j之间的映射关系及其实现过程。实验验证了Neo4j图数据库在满足领域本体RDF图数据查询的同时,进一步提高了查询的效率,为大数据平台下的RDF图数据语义检索与推理提供了方法支撑。     

RGB-D based place representation in topological maps

With the recent developments in sensor technology including Microsoft Kinect, it has now become much easier to augment visual data with three-dimensional depth information. In this paper, we propose a new approach to RGB-D based topological place representation—building on bubble space. While bubble space representation is in principle transparent to the type and number of sensory inputs employed, practically, this has been only verified with visual data that are acquired either via a two degrees of freedom camera head or an omnidirectional camera. The primary contribution of this paper is of practical nature in this perspective. We show that bubble space representation can easily be used to combine RGB and depth data while affording acceptable recognition performance even with limited field of view sensing and simple features.     

SESLDS: An Extension Scheme for Linked Data Sources Based on Semantically Enhanced Annotation and Reasoning

In the era of Big Data, users prefer to get knowledge rather than pages from Web. Linked Data, a rather new form of knowledge representation and publishing described by RDF, can provide a more precise and comprehensible semantic structure to satisfy the aforementioned requirement. Besides, as the standard query language for RDF data, SPARQL has become the foundation protocol of Linked Data querying. The core idea of RDF Schema (RDFS) is to extend upon RDF vocabulary and allow attachment of semantics to user defined classes and properties. However, RDFS cannot fully utilize the potential of RDF since it cannot express the implicit semantics between linked entities in Linked Data sources. To fill this gap, in this paper, we design a new semantic annotating and reasoning approach that can extend more implicit semantics from different properties. We firstly establish a well‐defined semantically enhanced annotation strategy for Linked Data sources. In particular, we present some new semantic properties for predicates in RDF triples and design a Semantic Matrix for Predicates (SM_P). We then propose a novel general Semantically Extended Scheme for Linked Data Sources (SES_LDS) to realize the semantic extension over the target Linked Data source through semantically enhanced reasoning. Lastly, based on the experimental analyses, we verify that our proposal has advantages over the initial Linked Data source and can return more valid results.     

The Semantic Web: the roles of XML and RDF

XML and RDF are the current standards for establishing semantic interoperability on the Web, but XML addresses only document structure. RDF better facilitates interoperation because it provides a data model that can be extended to address sophisticated ontology representation techniques. We explain the role of ontologies in the architecture of the Semantic Web. We then briefly summarize key elements of XML and RDF, showing why using XML as a tool for semantic interoperability will be ineffective in the long run. We argue that a further representation and inference layer is needed on top of the Web's current layers, and to establish such a layer, we propose a general method for encoding ontology representation languages into RDF/RDF schema. We illustrate the extension method by applying it to Ontology Interchange Language, an ontology representation and inference language     

Fractional alpha stable network traffic model and its application in QoS routing

It is not a simple and trivial work to set up an appropriate network traffic model. A fractional Alpha model is proposed in this paper and two proofs based on flow and session level, respectively, are given. Based on this model, the lower bound for the residual of the queueing distribution is deduced. Comparing the residual distribution function (RDF) based on our model with it based on other models, we find our formula matches the real RDF better. Based on this formula, we can predict the need for forwarding performance. Then a novel QoS routing algorithm based on this prediction is proposed. Last we demonstrate a simple example to denote how our algorithm can effectively improve the utility of bandwidth and amount of traffic and guarantee QoS.     

An Efficient Multivalued Hopfield Network for the Traveling Salesman Problem

In this Letter we show that discrete multivalued Hopfield-type neural networks enable a relatively easy formulation of the Traveling Salesman Problem compared to the traditional Hopfield model. Thus, with the multivalued representation the network can be easily confined to feasible solutions, avoiding the need to tune any parameter. An investigation into the performance of the network has led us to define updating rules based on simple effective heuristic algorithms, a technique that can not be usually incorporated into standard Hopfield models. Simulation results for Euclidean Traveling Salesman Problems taken from the data library TSPLIB [11] indicate that this multivalued neural approach is superior to the best neural network currently reported for this problem.     

On the Turing Completeness of the Semantic Web

The evidenced fact that “Linking is as powerful as computing” in a dynamic web context has lead to evaluating Turing completeness for hypertext systems based on their linking model. The same evaluation can be applied to the Semantic Web domain too. RDF is the default data model of the Semantic Web links, so the evaluation comes back to whether or not RDF can support the required computational power at the linking level. RDF represents semantic relationships with explicitly naming the participating triples, however the enumeration is only one method amongst many for representing relations, and not always the most efficient or viable. In this paper we firstly consider that Turing completeness of binary-linked hypertext is realized if and only if the links are dynamic (functional). Ashman’s Binary Relation Model (BRM) showed that binary relations can most usefully be represented with Mili’s pE (predicate-expression) representation, and Moreau and Hall concluded that hypertext systems which use the pE representation as the basis for their linking (relation) activities are Turing-complete. Secondly we consider that RDF –as it is- is a static version of a general ternary relations model, called TRM. We then conclude that the current computing power of the Semantic Web depends on the dynamicity supported by its underlying TRM. The value of this is firstly that RDF’s triples can be considered within a framework and compared to alternatives, such as the TRM version of pE, designated pfE (predicate-function-expression). Secondly, that a system whose relations are represented with pfE is likewise going to be Turing-complete. Thus moving from RDF to a pfE representation of relations would give far greater power and flexibility within the Semantic Web applications.     

Dynamic and fast processing of queries on large-scale RDF data

As RDF data continue to gain popularity, we witness the fast growing trend of RDF datasets in both the number of RDF repositories and the size of RDF datasets. Many known RDF datasets contain billions of RDF triples (subject, predicate and object). One of the grant challenges for managing these huge RDF data is how to execute RDF queries efficiently. In this paper, we address the query processing problems against the billion triple challenges. We first identify some causes for the problems of existing query optimization schemes, such as large intermediate results, initial query cost estimation errors. Then, we present our block-oriented dynamic query plan generation approach powered with pipelining execution. Our approach consists of two phases. In the first phase, a near-optimal execution plan for queries is chosen by identifying the processing blocks of queries. We group the join patterns sharing a join variable into building blocks of the query plan since executing them first provides opportunities to reduce the size of intermediate results generated. In the second phase, we further optimize the initial pipelining for a given query plan. We employ optimization techniques, such as sideways information passing and semi-join, to further reduce the size of intermediate results, improve the query processing cost estimation and speed up the performance of query execution. Experimental results on several RDF datasets of over a billion triples demonstrate that our approach outperforms existing RDF query engines that rely on dynamic programming based static query processing strategies.     

Exploring Correlated Subspaces for Efficient Query Processing in Sparse Databases

Sparse data are becoming increasingly common and available in many real-life applications. However, relatively little attention has been paid to effectively model the sparse data and existing approaches such as the conventional "horizontal” and "vertical” representations fail to provide satisfactory performance for both storage and query processing, as such approaches are too rigid and generally do not consider the dimension correlations. In this paper, we propose a new approach, named HoVer, to store and conduct query for sparse data sets in an unmodified RDBMS, where HoVer stands for Horizontal representation over Vertically partitioned subspaces. According to the dimension correlations of sparse data sets, a novel mechanism has been developed to vertically partition a high-dimensional sparse data set into multiple lower-dimensional subspaces, and all the dimensions are highly correlated intrasubspace and highly unrelated intersubspace, respectively. Therefore, original data objects can be represented by the horizontal format in respective subspaces. With the novel HoVer representation, users can write SQL queries over the original horizontal view, which can be easily rewritten into queries over the subspace tables. Experiments over synthetic and real-life data sets show that our approach is effective in finding correlated subspaces and yields superior performance for the storage and query of sparse data.     

Multiresolution volume visualization with a texture-based octree

Although 3D texture-based volume rendering guarantees image quality almost interactively, it is difficult to maintain an interactive rate when the technique has to be exploited on large datasets. In this paper, we propose a new texture memory representation and a management policy that substitute the classical one-texel per voxel approach for a hierarchical approach. The hierarchical approach benefits nearly homogeneous regions and regions of lower interest. The proposed algorithm is based on a simple traversal of the octree representation of the volume data. Driven by a user-defined image quality, defined as a combination of data homogeneity and importance, a set of octree nodes (the cut) is selected to be rendered. The degree of accuracy applied for the representation of each one of the nodes of the cut in the texture memory is set independently according to the user-defined parameters. The variable resolution texture model obtained reduces the texture memory size and thus texture swapping, improving rendering speed.     

Efficient rule mining and compression for RDF style KB based on Horn rules

The volume of published linked open datasets in RDF format is growing exponentially in the last decades. With this continuous proliferation of this growth, demands for managing, accessing, and compressing the RDF dataset have become increasingly important. Most approaches are focused on the structured compression technique while a very few researches have been done for compact representation of the RDF dataset. In this paper, we have proposed an efficient rule mining and compression approach for RDF datasets through various meaningful semantic association rules determined from the RDF graph. We have introduced grammar-based pattern system, clustering of rules, rules pruning, and Top-k scheme to improve the expressiveness of rule patterns, identify the similarity within the random pair of rules, extract the most delicate rules, find the accurate mining threshold, and efficiently learn the rules during the rule mining process from RDF Knowledge Base. Our proposed system uses Horn rules to achieve better compression through storing the triples matched with the precedent part while deleting the triples matched with the head part of the rules. For decreasing the mining time, we have introduced the ranking of the rules. The experimental result on the benchmark dataset asserts that our proposed rule mining and compression scheme has achieved approximately 22.10%, 40.5%, and 44% better compression than the exiting AMIE+, Rule-based compression, and TripleBit approaches, respectively. Our system also has achieved better performance both in terms of compression time and rule mining cost.

     

Extending SPARQL with regular expression patterns (for querying RDF)

RDF is a knowledge representation language dedicated to the annotation of resources within the framework of the semantic web. Among the query languages for RDF, SPARQL allows querying RDF through graph patterns, i.e., RDF graphs involving variables. Other languages, inspired by the work in databases, use regular expressions for searching paths in RDF graphs. Each approach can express queries that are out of reach of the other one. Hence, we aim at combining these two approaches. For that purpose, we define a language, called PRDF (for “Path RDF”) which extends RDF such that the arcs of a graph can be labeled by regular expression patterns. We provide PRDF with a semantics extending that of RDF, and propose a correct and complete algorithm which, by computing a particular graph homomorphism, decides the consequence between an RDF graph and a PRDF graph. We then define the PSPARQL query language, extending SPARQL with PRDF graph patterns and complying with RDF model theoretic semantics. PRDF thus offers both graph patterns and path expressions. We show that this extension does not increase the computational complexity of SPARQL and, based on the proposed algorithm, we have implemented a correct and complete PSPARQL query engine.