Bipartite graphs are widely used to model relationships between entities of different types, where nodes are divided into two disjoint sets. Similarity search, a fundamental operation that retrieves nodes similar to a given query node, plays a crucial role in various real-world applications, including machine learning and graph clustering. However, existing state of-the-art methods often struggle to accurately capture the unique structural properties of bipartite graphs or fail to incorporate the informative node attributes, leading to suboptimal performance. Besides, their high computational complexity limits scalability, making them impractical for large graphs with millions of nodes and tens of thousands of attributes. To overcome these challenges, we first introduce Attribute-augmented Hidden Personalized PageRank (AHPP), a novel random walk model designed to blend seamlessly both the higher-order bipartite structure proximity and attribute similarity. We then formulate the similarity search over attributed bipartite graphs as an approximate AHPP problem and propose two efficient push-style local algorithms with provable approximation guarantees. Finally, extensive experiments on real-world and synthetic datasets validate the effectiveness of AHPP and the efficiency of our proposed algorithms when compared with fifteen competitors.

Abstract Symmetry, a phenomenon of self-similarity, is common in many networks, which often incurs a lot of redundant accesses and computations, even duplicate results when executing graph matching tasks. Many approaches (e.g. symmetry-breaking methods) try to disrupt symmetry by translating symmetry into restrictions and then imposing restrictions on the exploration order. However, the restrictions are finer-grained. If the pattern graph is complex, more restrictions are generated from symmetry breaking methods, thus complicating the exploration process and degrading the performance. Here, we present novel SymmPi, which exploits symmetry removal for fast graph matching. SymmPi first identifies the coarse-grained axisymmetric subgraphs of the given pattern graphs instead of finer relationships. If a pattern graph is not axisymmetric, SymmPi will remove some of its edges until axisymmetric subgraphs are found. Thus, the original pattern graph is transformed to a set of axisymmetric subgraphs plus some edges. Then, SymmPi finds the matches of the axisymmetric subgraph and extends these matches to the original pattern graphs by permuting the matches with additional checks. Our experiments on both directed and undirected graphs, demonstrate that SymmPi achieves a significant performance improvement over the state-of-the-art undirected and directed graph matching methods and systems.

Community search is a widely studied semi-supervised graph clustering problem, retrieving a high-quality connected subgraph containing the user-specified query vertex. However, existing methods primarily focus on cohesiveness within the community but ignore the sparsity outside the community, obtaining sub-par results. Inspired by this, we adopt the well-knownconductancemetric to measure the quality of a community and introduce a novel problem ofconductance-based community search (CCS).CCSaims at finding a subgraph with the smallestconductanceamong all connected subgraphs that contain the query vertex. We prove that theCCSproblem is NP-hard. To efficiently queryCCS, a four-stagesubgraph-conductance-based community search algorithm,SCCS, is proposed. Specifically, we first greatly reduce the entire graph using local sampling techniques. Then, a three-stage local optimization strategy is employed to continuously refine the community quality. Namely, we first utilize a seeding strategy to obtain an initial community to enhance its internal cohesiveness. Then, we iteratively add qualified vertices in the expansion stage to guarantee the internal cohesiveness and external sparsity of the community. Finally, we gradually remove unqualified vertices during the verification stage. Extensive experiments on real-world datasets containing one billion-scale graph and synthetic datasets show the effectiveness, efficiency, and scalability of our solutions.

Speech recognition is becoming prevalent in daily life. However, due to the similar semantic context of the entities and the overlap of Chinese pronunciation, the pronoun homophone, especially “他/她/它 (he/she/it)”, (their pronunciation is “Tā”) is usually recognized incorrectly. It poses a challenge to automatically correct them during the post-processing of Chinese speech recognition. In this paper, we propose three models to address the common confusion issues in this domain, tailored to various application scenarios. We implement the language model, the LSTM model with semantic features, and the rule-based assisted Ngram model, enabling our models to adapt to a wide range of requirements, from high-precision to low-resource offline devices. The extensive experiments show that our models achieve the highest recognition rate for “Tā” correction with improvements from 70% in the popular voice input methods up to 90%. Further ablation analysis underscores the effectiveness of our models in enhancing recognition accuracy. Therefore, our models improve the overall experience of Chinese speech recognition of “Tā” and reduce the burden of manual transcription corrections.

Temporal community search is an important task in graph analysis, which has been widely used in many practical applications. However, existing methods suffer from two major defects: (i) they only require that the target result contains the query vertexq, leading to the temporal proximity betweenqand other vertices being ignored. Thus, they may find many temporal irrelevant vertices (these vertices are called query-drifted vertices) concerningqfor satisfying their objective functions; (ii) their methods are NP-hard, incurring high costs for exact solutions or compromised qualities for approximate/heuristic algorithms. In this paper, we propose a new problem named query-centered temporal community search to overcome these limitations. Specifically, we first present a novel concept of Time-Constrained Personalized PageRank to characterize the temporal proximity betweenqand other vertices. Then, we introduce a model calledβ-temporal proximity core, which can seamlessly combine temporal proximity and structural cohesiveness. Subsequently, our problem is formulated as an optimization task that finds aβ-temporal proximity core with the largestβ.We theoretically prove that our problem can circumvent these query-drifted vertices. To solve our problem, we first devise an exact and near-linear time greedy removing algorithm that iteratively removes unpromising vertices. To improve efficiency, we then design an approximate two-stage local search algorithm with bound-based pruning techniques. Finally, extensive experiments on eight real-life datasets and nine competitors show the superiority of the proposed solutions.

Learning Chinese word embeddings is important in many tasks of Chinese language information processing, such as entity linking, entity extraction, and knowledge graph. A Chinese word consists of Chinese characters, which can be decomposed into sub-characters (radical, component, stroke, etc). Similar to roots in English words, sub-characters also indicate the origins and basic semantics of Chinese characters. So, many researches follow the approaches designed for learning embeddings of English words to improve Chinese word embeddings. However, some Chinese characters sharing the same sub-characters have different meanings. Furthermore, with more cultural interaction and the popularization of the Internet and web, many neologisms, such as transliterated loanwords and network terms, are emerging, which are only close to the pronunciation of their characters, but far from their semantics. Here, a tripartite weighted graph is proposed to model the semantic relationship among words, characters, and sub-characters, in which the semantic relationship is evaluated according to the Chinese linguistic information. So, the semantic relevance hidden in lower components (sub-characters, characters) can be used to further distinguish the semantics of corresponding higher components (characters, words). Then, the tripartite weighted graph is fed into our Chinese word embedding modelinsideCC to reveal the semantic relationship among different language components, and learn the embeddings of words. Extensive experimental results on multiple corpora and datasets verify that our proposed methods outperform the state-of-the-art counterparts by a significant margin.

Intuitively, word representation for logographic languages like Chinese can be enhanced by its internal characteristics. Several research endeavors tried to learn Chinese word embeddings with characters, radicals, or subcharacters containing rich semantic information. In this paper, motivated by Four-Corner Method for Character Indexation, we extract features from four corners of characters with important morphological charactertics. Based on the features from four corners, we propose a model to utilize characters and four corner features of words to capture both semantic and morphological information. Moreover, we apply an attention scheme to integrate internal information dynamically, which includes two strategies to assign different weights for elements according to the word frequency. Experimental results on social news corpus and Chinese Wikipedia Dump show exploiting the four corner morphological features is crucial for capturing the meanings of Chinese words. Meanwhile, the results on word analogy, word similarity, and text classification tasks demonstrate that our approach obtains better results than state-of-the-art approaches.

Temporal subgraph mining is recently ubiquitous. Identifying diversified and lasting ingredients is a fundamental problem in analyzing temporal networks. In this paper, we investigate the problem of finding diversified lasting cohesive subgraphs from temporal networks. Specifically, we first introduce a new model, called maximal lasting$(k,\sigma)$-core, for characterizing lasting cohesive subgraphs on temporal networks so as to the nodes in the subgraph are connected densely and also the subgraph's structure remains unchanged for a period of time. To enhance the diversity of results, we then formulate a diversified lasting cohesive subgraphs problem, which finds$r$maximal lasting$(k,\sigma)$-cores with maximum coverage regarding the number of vertices and timestamps. Unfortunately, we show that the optimization problem is NP-hard. To tackle this issue, we first devise a greedy algorithm namedGreLCwith (1-1/e) approximation ratio. However,GreLChas prohibitively high time and space complexity, resulting in poor scalability. Then, an improved DFS-based search algorithm calledTopLCwith 1/4 approximation ratio is proposed to lower the computational cost. Finally, empirical studies on six real-world temporal networks demonstrate that the proposed solutions perform efficiently and accurately, and our model is better than temporal cohesive subgraphs detected by existing approaches.

Reachability queries ask whether a vertex can reach another vertex on large directed graphs. It is one of the most fundamental graph operators and has attracted researchers in both academics and industry to study it. The main technical challenge is to support fast reachability queries by efficient managing the three main costs: the index construction time, the index size and the query processing time on large/small and sparse/dense graphs. As real world graphs grow bigger in size, these problems remain open challenges that demand high performance solutions. In this article, we propose aMulti-Dimensional Graph Labelingapproach (calledMGTag) to supporting fast reachability queries.MGTagis novel in three aspects. First, it recursively partitions a graph into multiple subgraphs with disjoint vertex sets, called non-shared graphs, and several inter-partition edges, called cross-edges. Second, we build a four-dimensional label – one dimension of layer, one dimension of non-shared graph and two dimensions of interval for each vertex in non-shared graphs. Finally, with the four-dimensional labeling scheme, we design algorithms to answer reachability queries efficiently. The extensive experiments on 28 large/small and dense/sparse graphs show that building the high dimensional index is quickly and the index size is also competitive compared with most of the state-of-the-art approaches. The results also show that our approach is more scalable and efficient than the state-of-the-art approaches in answering reachability queries on large/small and sparse/dense graphs.

Real-world networks, such as phone-call networks and social networks, are often not static but temporal. Mining cohesive subgraphs from static graphs is a fundamental task in network analysis and has been widely investigated in the past decades. However, the concepts of cohesive subgraphs shift from static to temporal graphs raise many important problems. For instance, how to detect stable cohesive subgraphs on temporal networks such that the nodes in the subgraph are densely and stably connected over time. To address this problem, we resort to the conventional quasi-clique and propose a new model, called maximal$\rho $-stable ($\delta, \gamma $)-quasi-clique, to capture both the cohesiveness and the stability of a subgraph. We show that the problem of enumerating all maximal$\rho $-stable ($\delta, \gamma $)-quasi-cliques is NP-hard. To efficiently tackle our problem, we first devise a novel temporal graph reduction algorithm to significantly reduce the temporal graph without losing any maximal$\rho $-stable ($\delta, \gamma $)-quasi-clique. Then, on the reduced temporal graph, we propose an effective branch and bound enumeration algorithm, namedBB&SCM, with four carefully designed pruning techniques to accomplish the enumeration process. Finally, we conduct extensive experiments on seven real-world temporal graphs, and the results demonstrate that the temporal graph reduction algorithm can safely reduce 98% nodes of the temporal graph (with millions of nodes and edges) andBB&SCMis at least two orders of magnitude faster than the baseline algorithms. Moreover, we also evaluate the effectiveness of our model against other baseline models.

As a markup language for describing web resources, RDF is often used to represent graph data. SPARQL is a standard query language for RDF data, which is convenient in querying RDF. As RDF data grows rapidly, how to deal with complex queries over large-scale data in a reasonable time still remains many challenges. The existing RDF query systems often fail to respond within a reasonable time when dealing with complex SPARQL queries. Therefore, we propose an efficient parallel SPARQL query system and novel in three aspects. First, the proposed design provides a dynamic selectivity estimation strategy and generates an optimal query plan for parallel query processing. Second, the new design proposes a parallel processing model to maximize the parallelism of the system. Finally, chunk-based task distribution strategy is implemented to assist the parallel processing model. Based on the proposed design, we implement an efficient parallel query system (Grace). Extensive experiments on LUBM and BTC benchmarks show that Grace outperforms RDF-3X, Virtuoso, TripleBit and achieves a good performance of scalability on the number of threads.

Abstract Now, with the prevalence of social media, such as Facebook, Weibo, how to maximize influence of individuals, products, actions in new media is of practical significance. Generally, maximizing influence first needs to identify the most influential individuals since they can spread their influence to most of others in the social media. Many studies on influence maximization aimed to select a subset of nodes in static graphs once. Actually, real graphs are evolving. So, influential individuals are also changing. In these scenarios, people tend to select influential individuals multiple times instead of once. Namely, selections are raised sequentially, forming a sequence (query sequence). It raises several new challenges due to changing influential individuals. In this paper, we explore the problem of Influence Maximization over Streaming Graph (SGIM). Then, we design a compact solution for storing and indexing streaming graphs and influential nodes that eliminates the redundant computation. The solution includes Influence-Increment-Index along with two sketch-centralized indices called Influence-Index and Reverse-Influence-Index. Computing influence set of nodes will incur a large number of redundant computations. So, these indices are designed to keep track of the nodes’ influence in sketches. Finally, with the indexing scheme, we present the algorithm to answer SGIM queries. Extensive experiments on several real-world datasets demonstrate that our method is competitive in terms of both efficiency and effectiveness owing to the design of index.

RDF data is big and continues to grow rapidly. RDF data sets are typically viewed as heterogeneous graph data sets with complex correlations and multifaceted heterogeneity. Although there have been flurry of research on processing and analyzing RDF data, efficient storage, computation, analysis of big and growing RDF data continue to challenge multiple computer science disciplines, ranging from systems, network computing, data management to data analytics. In this paper, we make use of strawman arguments on big RDF data challenges with respect to storage, computation, analysis, focusing on identifying the grand challenges in developing high performance RDF storage, parallel computation, efficient distribution, and smart RDF analytics. We attempt to answer a number of important and frequently asked questions: (1) Do we really need RDF-specific storage techniques and algorithms for building efficient and high performance RDF stores? (2) How hard can it be to effectively parallelize big RDF data for high performance storage, computation, and mining? (3) What type of distribution models can we employ to scale RDF processing models and algorithms for real-time querying (subgraph pattern matching) and mining of big RDF data? (4) Can machine learning algorithms be leveraged to effectively mine and dive into RDF data? We attempt to answer these questions by sharing some of our results, our unique experiences, and our lessons learned from a collection of research projects in RDF systems research and development. We will also discuss our ongoing research endeavors, potential applications and avenues for future work.

Theta join is commonly employed in real practices. Although SPARQL is a popular RDF query language, SPARQL does not define the specification of theta join until 2013. After that, few RDF stores except the stores based on RDBMS or key-value stores can process theta join. However, processing theta join on RDBMS or key-value stores is costly due to lack of RDF-native optimization. Efficient solutions to process theta join queries on RDF graph directly have not been fully explored. Here, we present ThetaStore to parallel process SPARQL theta join queries on large RDF graphs. First, a uniform SPARQL query graph model for theta join queries and equi-join queries is defined. Second, each subject, predicate, and object of RDF triples are mapped into order-preserving IDs instead of an random integer as most of RDF stores do. By this way, the engine does not need to translate theta join into a set of equi-joins. Finally, the engine employs decomposition and segment-oriented parallelization to execute SPARQL queries. The engine decomposes query into several star sub-queries and the intermediate results matching each pattern are divided into segments. Extensive experiments are conducted on large RDF data sets and experimental results show that ThetaStore outperforms state-of-the-art systems in both theta joins and equi-joins.

Reachability query asks whether a vertex can reach another vertex on large directed graphs. It is one of the most fundamental graph operators and has attracted many researchers to study it. Although there are many approaches solving this problem, it still remains a challenging problem when it comes to leverage the three main costs: the index construction time, the index size, and the query time on large and dense graphs. In this paper, we propose a High Dimension Graph Labeling approach to answer reachability queries. First, we recursively partition a graph into disjoint non-shared graphs, among which there are no common vertices, and cross edges. Second, we build a four dimensional label - one dimension of layer, one dimension of sub-graph and two dimensions of interval for each vertex. With the layer label and the sub-graph label, we can determine the positions (non-shared graphs) of any two vertices. Two dimensional interval label is used to assist to answer the reachability queries for vertex pair in those non-shared graphs. Finally, we design algorithms to answer researchability queries efficiently. In order to speed up query answering, we also build two directional labels: up and down labels to filter vertices quickly. The extensive experiments on 28 large/small and dense/sparse graphs show that building the high dimensional index is quickly and the index size is also competitive compared with most of the state of the art approaches. The results also show that our approach is more scalable and efficient than the state-of-the-art approaches in answering reachability queries.

Nowadays, more and more large scale knowledge bases are available for public access.Although these knowledge bases have their inherent access interfaces, such as SPARQL, they are generally unfriendly to end users.An intuitive way to bridge the gap between users and knowledge bases is to enable users to ask questions with natural language interface and return desired answers directly.Here the challenge is how to discover the query intention of users.Another challenge is how to obtain accurate answers from knowledge bases.In this paper, we model the query intention with a graph based on an entity-driven method.Consequently, the core problem of natural language question answering can be treated as subgraph matching over knowledge bases.For a query graph, there is a huge number of candidate mappings in a knowledge base, including ambiguities.Thus, a semantic vector is proposed to address disambiguation by evaluating the semantic similarity between edges in a query graph and paths in a knowledge base.By this way, our system can extract accurate answers directly without any offline work.Extensive experiments over the series of QALD challenges show the effectiveness of our system Svega in terms of recall and precision against other state-of-the-art systems.

Large scale iterative graph computation presents an interesting systems challenge due to two well known problems: (1) the lack of access locality and (2) the lack of storage efficiency. This paper presents PathGraph, a system for improving iterative graph computation on graphs with billions of edges. First, we improve the memory and disk access locality for iterative computation algorithms on large graphs by modeling a large graph using a collection of tree-based partitions. This enables us to use path-centric computation rather than vertex-centric or edge-centric computation. For each tree partition, we re-label vertices using DFS in order to preserve consistency between the order of vertex ids and vertex order in the paths. Second, a compact storage that is optimized for iterative graph parallel computation is developed in the PathGraph system. Concretely, we employ delta-compression and store tree-based partitions in a DFS order. By clustering highly correlated paths together as tree based partitions, we maximize sequential access and minimize random access on storage media. Third but not the least, our path-centric computation model is implemented using a scatter/gather programming model. We parallel the iterative computation at partition tree level and perform sequential local updates for vertices in each tree partition to improve the convergence speed. To provide well balanced workloads among parallel threads at tree partition level, we introduce the concept of multiple stealing points based task queue to allow work stealings from multiple points in the task queue. We evaluate the effectiveness of PathGraph by comparing with recent representative graph processing systems such as GraphChi and X-Stream etc. Our experimental results show that our approach outperforms the two systems on a number of graph algorithms for both in-memory and out-of-core graphs. While our approach achieves better data balance and load balance, it also shows better speedup than the two systems with the growth of threads.

The emerging need for conducting complex analysis over big RDF datasets calls for scale-out solutions that can harness a computing cluster to process big RDF datasets. Queries over RDF data often involve complex self-joins, which would be very expensive to run if the data are not carefully partitioned across the cluster and hence distributed joins over massive amount of data are necessary. Existing RDF data partitioning methods can nicely localize simple queries but still need to resort to expensive distributed joins for more complex queries. In this paper, we propose a new data partitioning approach that takes use of the rich structural information in RDF datasets and minimizes the amount of data that have to be joined across different computing nodes. We conduct an extensive experimental study using two popular RDF benchmark data and one real RDF dataset that contain up to billions of RDF triples. The results indicate that our approach can produce a balanced and low redundant data partitioning scheme that can avoid or largely reduce the cost of distributed joins even for very complicated queries. In terms of query execution time, our approach can outperform the state-of-the-art methods by orders of magnitude.

Now more and more large graphs are available. One interesting problem is how to effectively find reachability between any vertex pairs in a very large graph. Multiple approaches have been proposed to answer reachability queries. However, most approaches only perform well on small graphs. Processing reachability queries on large graphs requires much storage and computation and still remains challenges. In this paper, we propose a scalable and fast indexing approach called Interval-Index, based on traversal tree-based partitioning and relabeling scheme. Our approach has several unique features: first, the traversal tree-based partitioning ensures access locality and parallelism in computation; second, continuous relabeling ensures fast querying and saves search space; third, we convert the entire graph database into a traversal tree graph on a smaller scale, to reach a compact storage structure. Finally, we run extensive experiments on synthetic graphs and real graphs with different sizes, and show that Interval-Index approach outperforms the state-of-the-art Feline in both storage size and the performance of query execution.

In recent years, systems researchers have devoted considerable effort to the study of large-scale graph processing. Existing distributed graph processing systems such as Pregel, based solely on distributed memory for their computations, fail to provide seamless scalability when the graph data and their intermediate computational results no longer fit into the memory; and most distributed approaches for iterative graph computations do not consider utilizing secondary storage a viable solution. This paper presents GraphMap, a distributed iterative graph computation framework that maximizes access locality and speeds up distributed iterative graph computations by effectively utilizing secondary storage. GraphMap has three salient features: (1) It distinguishes data states that are mutable during iterative computations from those that are read-only in all iterations to maximize sequential access and minimize random access. (2) It entails a two-level graph partitioning algorithm that enables balanced workloads and locality-optimized data placement. (3) It contains a proposed suite of locality-based optimizations that improve computational efficiency. Extensive experiments on several real-world graphs show that GraphMap outperforms existing distributed memory-based systems for various iterative graph algorithms.

The flexibility of the RDF data model has attracted an increasing number of organizations to store their data in an RDF format. With the rapid growth of RDF datasets, we envision that it is inevitable to deploy a cluster of computing nodes to process large-scale RDF data in order to deliver desirable query performance. In this paper, we address the challenging problems of data partitioning and query optimization in a scale-out RDF engine. We identify that existing approaches only focus on using fine-grained structural information for data partitioning, and hence fail to localize many types of complex queries. We then propose a radically different approach, where a coarse-grained structure, namely Rooted Sub-Graph (RSG), is used as the partition unit. By doing so, we can capture structural information at a much greater scale and hence are able to localize many complex queries. We also propose a k-means partitioning algorithm for allocating the RSGs onto the computing nodes as well as a query optimization strategy to minimize the inter-node communication during query processing. An extensive experimental study using benchmark datasets and real dataset shows that our engine, SemStore, outperforms existing systems by orders of magnitudes in terms of query response time.

Large scale graph processing represents an interesting challenge due to the lack of locality. This paper presents Path Graph for improving iterative graph computation on graphs with billions of edges. Our system design has three unique features: First, we model a large graph using a collection of tree-based partitions and use an path-centric computation rather than vertex-centric or edge-centric computation. Our parallel computation model significantly improves the memory and disk locality for performing iterative computation algorithms. Second, we design a compact storage that further maximize sequential access and minimize random access on storage media. Third, we implement the path-centric computation model by using a scatter/gather programming model, which parallels the iterative computation at partition tree level and performs sequential updates for vertices in each partition tree. The experimental results show that the path-centric approach outperforms vertex centric and edge-centric systems on a number of graph algorithms for both in-memory and out-of-core graphs.

With the rapid development of information technology, the needs of unstructured data storage and processing is growing rapidly, which develops a new requirement for the database storage. Traditional row-oriented relational databases appear to be inadequate for the data query and analysis. In this paper, we propose a novel approach to store the unstructured data in a relational database. By splitting the VALUE property of the unstructured KEY/VALUE data and recreating the two-dimensional data, the original data can be stored in relational databases. The system introduced in this paper is designed to handle this task. In addition, this system rebuilds the SQL as its query language, which makes it compatible with relational databases. In experiments of the query for unstructured data, the outcomes show that the system is good at decomposing the SQL statement submitted by users, and generating the corrected sub-query statements. The results of the experiments show that the performance of this system is good.

The volume of RDF data continues to grow over the past decade and many known RDF datasets have billions of triples. A grant challenge of managing this huge RDF data is how to access this big RDF data efficiently. A popular approach to addressing the problem is to build a full set of permutations of (S, P, O) indexes. Although this approach has shown to accelerate joins by orders of magnitude, the large space overhead limits the scalability of this approach and makes it heavyweight. In this paper, we present TripleBit, a fast and compact system for storing and accessing RDF data. The design of TripleBit has three salient features. First, the compact design of TripleBit reduces both the size of stored RDF data and the size of its indexes. Second, TripleBit introduces two auxiliary index structures, ID-Chunk bit matrix and ID-Predicate bit matrix, to minimize the cost of index selection during query evaluation. Third, its query processor dynamically generates an optimal execution ordering for join queries, leading to fast query execution and effective reduction on the size of intermediate results. Our experiments show that TripleBit outperforms RDF-3X, MonetDB, BitMat on LUBM, UniProt and BTC 2012 benchmark queries and it offers orders of mangnitude performance improvement for some complex join queries.

The scale of RDF graph grows very rapidly. Managing huge scale RDF graph distributively is becoming increasingly important. Partitioning RDF graph is a vital pre-processing step for the goal. When applying graph partitioning algorithms developed over past decades to RDF graph represented using well known RDF model such as Directed Labeled Graphs, Bipartite Graph, the vertices which a triple depends on may be in different partitions. Such partitioning on the RDF models induces huge communication overhead during processing queries. We argue in this paper that there is need for a representation of RDF to enable the parallel and distributed computing application on RDF data. We propose statement hyper graph model which avoid this crucial deficiency of the graph model of RDF data. The proposed models reduce the decomposition problem to the well-known hyper graph partitioning problem. In the light of this model, we explore the cases like horizontal partitioning, vertical partitioning, grid partitioning, etc and evaluate their performance.

Virtualization as a powerful and convenient technique has been widely used recently. Inserting the VMM between the hardware and operation system enables multiple virtual machines simultaneously running on hardware. However, these changes in system architecture, while improving the whole physical computing resources' utilization, also pay a certain price for virtualization. How to measure this part of CPU overhead, and how about the relationship between this part of CPU overhead and virtual machine number and the type of workload executing in virtual machine are two important questions to the further research of virtualization performance. In this paper we provide a system to measure the overhead of virtualization. With this system we could dynamically obtain the utilization of computing resource. Based on the analysis to the results of several experiments, we compare and study the relationship between the different factors and the overhead of virtualization. Finally, we predict the probably trend of the overhead under the impact of some factors.

With the development of virtualization technology, it can run more and more guest domains on one single physical machine. So the network I/O demand is also rapidly increasing, for these guest domains can supply more and more services or run more and more applications. This will lead to serious contention on network I/O of physical machine. Although we can use high performance NICs (network interface cards) to improve network I/O performance, one single NIC cannot get further performance improvement which depends on hardware technology. Linux bonding can achieve high bandwidth network by using multiple NICs, but it does not guarantee QoS among guest domains. Also it would terminate one guest domain's communication because of its response mechanism of ARP. Therefore, we present an approach named Virtual Bonding to achieve high bandwidth network by using multi-NICs. It aggregates multi-NICs to provide high bandwidth and high-quality network services. It also introduces load balancing mechanism between multi-NICs. So it can make full use of every NIC. Furthermore, it makes perfect support to virtualization environment.

As the degree of virtualization is growing considerably, improving performance of virtual machine environments motivates deeper investigation of the internal processes and performance implications of virtualization. Several tools are currently available to help analyze performance in virtual machine environments. However, all of these cannot support users to add their own trace information. In this paper, we present Xenrelay, a unified, efficient, and simple mechanism for transferring large amounts of data from guest domain kernel to privileged domain user-space. Xenrelay allows users (who trace subsystems of guest domain to analyze performance) to record and fast relay data between domains. We provide a case of Xenrelay's value in revealing behavior of virtualization. We build a block trace toolkit (using Xenrelay as an engine). This toolkit is used to track the block I/O virtualization procedures and evaluates overheads in the Xen environment. Our trace results identify that the main delay is the time of request transmission and block device operation. Besides, the results reveal impact of the I/O schedules on the disk performance.

Resurgence of virtualization calls for suitable benchmark to validate the design of virtualization system. Among the virtual machines' performance, I/O especially disk I/O is the most critical one. Since I/O is a key factor that impacts virtual machine performance, this paper introduces a benchmark- vBench for disk I/O micro-performance evaluation of virtual machine. vBench is mainly consisted of serial disk I/O evaluation and parallel disk I/O evaluation. Since error during test is inevitable, for the purpose of error correction, we design an efficient approach which we runs the same workloads in two loops, then the execution times of two loops minus each other. The approach can correctly deal with loop overhead. To prevent compiler from optimizing the code and lead to the wrong execution time of workloads, vBench is embedded inline assembly code. vBench provides the performance evaluation for system call of disk I/O, application level disk I/O and parallel disk I/O. Disk I/O performance evaluation of vBench can measure disk I/O micro-performance of virtual machine in certain extreme conditions. Experiments show that the results of vBench are accurate and vBench can reflect the disk I/O performance of the virtual machines correctly. Therefore, vBench is more accurate, more reliable than the traditional benchmarks and more suitable for evaluating virtual machine disk I/O performance.

The Business Process Execution Language for Web services (BPEL) has emerged as the de-facto standard for implementing processes. While being a powerful language, BPEL is difficult to use. As a result only experienced users are able to select the right construct. However, XPDL, which was proposed by Workflow Management Coalition, are widely accepted by enterprises. Therefore, this paper presents a tool, named as workflow transformation system between XPDL and BPEL (WFTXB) to automatically translate workflow expressed in terms of XPDL onto BPEL, and vice versa. For transformation between XPDL and BPEL, the tool adopts the graph structure as intermediate language. During the transformation, the tool first analyses the structures of process, and gets the result of map-like structure, which is expressed with adjacency matrix. Then the tool scans the adjacency matrix and identifies the structure of block. Finally, the tool generates BPEL or XPDL code.

Grid computing extends the application domain to include interaction and collaboration, termed as interactive grid. Interactive grid enables various collaborative applications, in which activities involve geographically distributed and heterogeneous resources, SO work together to achieve a common goal. Thus, software support to facilitate coordination among entities is needed. This paper introduces a session management framework for collaborative applications in interactive grid, and describes the mechanisms of session management in detail. Then, a scalable and flexible software architecture based on OGSA is presented, which can adapt to the dynamism of grid resources. Finally, the performance evaluation is given.