Search

The deployment of increasingly diverse services on edge devices is becoming increasingly prevalent. Efficiently deploying functionally heterogeneous services to resource heterogeneous edge nodes while achieving superior user experience is a challenge that every edge system must address. In this paper, we propose a container-node graph (CN-Graph)-based container optimal matching deployment algorithm, edge Kuhn-Munkres algorithm (EKM) based on container-node graph, designed for heterogeneous environment to optimize system performance. Initially, containers are categorized by functional labels, followed by construction of a CN-Graph model based on the relationship between containers and nodes. Finally, the container deployment problem is transformed into a weighted bipartite graph optimal matching problem. In comparison with the mainstream container deployment algorithms, Swarm, Kubernetes, and the recently emerged ECSched-dp algorithm, the EKM algorithm demonstrates the ability to effectively enhance the average runtime performance of containers to 3.74 times, 4.10 times, and 2.39 times, respectively. [ABSTRACT FROM AUTHOR]

Graph pattern matching is widely used in real-world applications, such as social network analysis. Since the traditional subgraph isomorphism is NP-complete and often too restrictive to catch sensible matches, relaxed graph pattern matching models are used. However, existing algorithms suffer from limited linear scalability and restricted degrees of parallelism. In this paper, we propose fast parallel algorithms, GPGS and GPDS, for graph simulation and dual simulation, respectively. They make most use of the GPU performance by adopting the edge-centric processing model. We perform parallel computations on the data graph edges to evaluate the matching constraints for each vertex allowing for fast and scalable algorithms. To the best of our knowledge, we present the first GPU-based algorithms for graph simulation and dual simulation. Extensive experiments on synthetic and real-world data graphs demonstrate that our algorithms significantly outperform existing methods, achieving up to 74.8 × acceleration for GPGS and up to 114.2 × acceleration for GPDS. [ABSTRACT FROM AUTHOR]

The existing signed graph neural networks mainly focus on the design process of neighbor aggregation function, but ignore the correlation between nodes, which leads to the decline of the representation ability of neural networks. In order to solve the above problems, a SDEGNN (Signed Distance Encoding based on Graph Neural Network) model based on enhanced signed distance encoding is proposed in this paper. Firstly, the problem of limited representation ability in signed graph neural networks is discussed. Secondly, in order to capture the correlation between nodes, signed distance encoding is proposed as the node feature representation to enhance the representation ability of the model. Thirdly, the signed distance encoding is injected into the information aggregation process of the signed graph convolutional network, and the objective function is proposed to optimize the SDEGNN model. The SDEGNN model is verified performance by three real signed network datasets Bitcoin-OTC, Bitcoin-Alpha, and Wiki-RfA. The experimental results show that the SDEGNN model can effectively improve the accuracy of link sign prediction tasks. [ABSTRACT FROM AUTHOR]

Accurate news representation is of crucial importance in personalized news recommendation. Most of existing news recommendation model lack comprehensiveness because they do not consider the higher-order structure between user–news interactions, relevance between user clicks on news. In this paper, we propose graph neural news recommendation based on multi-view representation learning which encodes high-order connections into the representation of news through information propagation along the graph. For news representations, we learn click news and candidate news content information embedding from various news attributes. And then combine obtained structure-based representations with representations from news content. Besides, we adopt a candidate-aware attention network to weight clicked news based on their relevance with candidate news to learn candidate-aware user interest representation for better matching with candidate news. The performance of the model has been improved in common evaluation metric. Extensive experiments on benchmark datasets show that our approach can effectively improve performance in news recommendation. [ABSTRACT FROM AUTHOR]

Fake news detection has attracted significant attention since the spread of fake news on social media has affected the media's credibility. Some existing fake news detection models only applied news content features as input. They treated the extracted news and user features as text but ignored the interaction between the various components of the news. Furthermore, the news dissemination information was not captured effectively. To address these problems, we propose a dual-channel graph convolutional attention network with dynamic feature fusion named DGCAN. News on social media does not exist in isolation, but is connected and interactive with each other. Therefore, first, we construct a heterogeneous graph to model the semantic information between source tweets and words and the spread structure information between source tweets and users, respectively. Second, we capture the semantic information and dissemination structure information of news at the same time with a designed dual-channel graph convolutional network. Third, we integrate the graph attention mechanism to learn the importance of tweet, user, and word nodes in heterogeneous graphs. Finally, we apply the attention mechanism between sub-channels to learn the semantic and spread features. Experiments on two real-world datasets demonstrate that the model proposed in this paper achieves state-of-the-art performance. [ABSTRACT FROM AUTHOR]

This article delves into the analysis and identification of influential individuals within social networks, a fundamental issue in the realm of social network science and complex network analysis. Within social networks, the impact of individuals on information propagation, shaping beliefs, and influencing the behavior of others is of paramount importance. Most of the current methods are based on the assumption that the entire graph is visible. However, this assumption does not hold for many real-world graphs. This study is conducted to extend current maximization methods, with link prediction techniques to pseudo-visibility graphs. The proposed method in this paper leverages graph models and influence algorithms to identify and select influential individuals within a social network. It begins by employing graph models to predict connections within the network and subsequently employs influence algorithms to opt for the most suitable individuals for exerting influence within the network. The primary advantage of this approach lies in its capability to enhance communication and influence within social networks with minimal observation. This method aids in a better understanding of the network's structure and the behaviors of its members, ultimately facilitating more effective information dissemination. In this study, we implemented five concepts for influence maximization in the context of the proposed method. Our results indicate that the algorithms perform best when considering lower diffusion coefficients. This suggests that focusing on lower diffusion coefficients allows the algorithm to demonstrate its superiority. Additionally, our findings reveal a notable consistency in results across various graph removal scenarios, highlighting a key advantage of our proposed approach on real-world graphs. [ABSTRACT FROM AUTHOR]

Modeling the interactions between users and items to accurately predict a user preference on items is very crucial for improving the performance of recommendation. Although existing graph-based methods have achieved great progress in predicting a user preference for recommendation, they usually need additional side information which is difficultly obtained, and ignore the temporal-order associations between items (users) when constructing graphs. In this paper, we propose a temporal-order association-based dynamic graph evolution model for recommendation, which can not only capture temporal-order item associations and user relationships by recurrently constructing a temporal-order item association graph and a user similarity graph but also update and promote the embeddings and graphs by performing a novel dynamic evolution mechanism based on two graph convolutional networks (GCNs). Specifically, the proposed model consists of two main components: recurrent graph construction component and message propagation and aggregation component. The former recurrently constructs the temporal-order item association graph and the user similarity graph only from the history interactions and embeddings to capture the item-item and user-user relationships. The latter performs a novel dynamic evolution mechanism based on two GCNs on these two auxiliary graphs and interaction graph to refine user and item representations, which further helps the process of constructing two auxiliary graphs. Finally, the final embeddings of users and items are used to predict a user preference on all items the user has not interacted with. The experimental results illustrate that our method outperforms the state-of-the-art methods on five real-world datasets. [ABSTRACT FROM AUTHOR]

Although there are numerous data modeling tools for relational databases, data modeling for NoSQL databases has seen another perspective. These databases (a) do not define any explicit schema, (b) store data in a denormalized manner, and (c) give many structure alternatives. The decision to structure the data always relies on rules of thumb, which do not guarantee an optimal structural solution. Based on this motivation, this paper offers a workload-driven model for the logical schema design of a NoSQL document database. It consists of Model input, Intermediate transformation, and Final schema generation. The proposed model takes the conceptual schema (EER model) and application workload (queries and anticipated data volume) as input and describes a procedure to convert it into a logical model for NoSQL document stores. The conversion process initially converts the application queries into query graphs. The query graphs, along with the anticipated data volume, are used to generate the query labels. The resulting query labels are assigned on the schema graph designed from the EER model. The schema graph and labels are used to transform the EER model into the appropriate logical schema model based on the actions defined for each label. We evaluate the model using a case study in the eCommerce application domain. The experimental evaluation shows the proposed model outperforms the existing conventional, optimized, and query path graphs models in multiple aspects, including query performance, storage space efficiency, aggregate pipeline efficiency, read–write latency, collection-wise performance, scalability, throughput and latency. By effectively addressing the challenges associated with managing the variety and volume of big data through a well-designed schema, our proposed model significantly reduces the time, cost, and effort required for schema development and repair. [ABSTRACT FROM AUTHOR]

As the size of graph data grows exponentially, it is usually processed by parallel and distributed computing environment. During parallel processing, the first step is to divide the graph data into many subgraphs and then place them on different computational nodes. However, the existing graph clustering methods cannot adapt to parallel processing or improve computing performance. The main reason is that these methods only focus on the graph data but do not care about the graph's application algorithm. Therefore, this paper addresses a graph clustering method that supports parallel processing by perceiving the application algorithm semantics. We specifically focus on the characteristic of "tight inside and loose outside". Based on this characteristic, we give a new formula for calculating the modularity of the subgraph. In a graph application, graph data and its associated application algorithm are not separated from each other. Thus, we also focus on the execution patterns of the application algorithm. Combining the modularity of a subgraph and execution patterns of an application algorithm, we present the critical concept of semantic serial degree as a new criterion for big graph clustering. Consequently, we propose a graph clustering method that effectively balances the importance between the graph data and its associated application algorithm. By achieving this balance, our approach ensures that the final clustering results are more suitable for parallel and distributed processing. Extended experiments show that our proposed graph clustering method is more general and compatible with traditional clustering methods. Compared with FastUnfolding, a state-of-the-art graph clustering method, the completion times of an application algorithm are significantly reduced due to the help of the proposed graph clustering method. [ABSTRACT FROM AUTHOR]

Extracting information from growing networks like social networks has a wide domain of applications. Therefore, many large-scale distributed graph processing systems have been developed. Such systems use some kinds of partitioning to distribute a big graph over machines. Minimizing the number of cutting edges and balancing the load are two general factors that most of the partitioning algorithms try to optimize regardless of the properties of the underlying systems. Although these general factors are necessary, we believe that they are not enough for all systems. In this paper, we investigate common features of block-centric graph processing systems and extract some system-specific core factors that influence on the quality of partitions: minimizing the diameter of the integrated-graph, maximizing the size of integrated vertices, and preventing the skew problem in the size of integrated vertices. The proposed partitioning method, tries to optimize system-specific factors as well as general ones. Evaluating iPartition over real-world graphs showed that it can significantly improve the performance of block-centric graph processing systems in terms of network traffic and synchronization barriers. More specifically, the amount of superstep reduction over frequently-used distributed graph partitioning methods varies from 20 to 75%, based on the type of the graph. The reduction in transmitted messages over the network varies from 10 to 80%. [ABSTRACT FROM AUTHOR]

The existing deep learning compilers are unable to perform efficient hardware performance-related graph fusion when both time and power consumption are considered. In addition, the compilers optimize the computational graph of deep neural networks (DNNs) by performing static graph transformation based on the greedy algorithm, only considering the runtime performance, and ignoring the cost of the tuning process. To solve these problems, this paper proposes a DNN computational graph optimization compiler (PCGC). Through the performance feedback at runtime, PCGC designs a computational graph fusion and splitting optimization strategy based on multilevel operator layer fusion-splitting rules. First, PCGC uses a rule-guided graph segmentation algorithm to recursively segment the computational graph into smaller subgraph to achieve an efficient and detailed search. Then, PCGC uses the cost model to receive feedback from hardware performance information, proposes cost model and operator fusion rules to synthetically guide the partial fusion and partitioning of nodes and edges of the computational graph, and generates optimal subgraphs flexibly according to different hardware to optimize the search space for partial fusion. Finally, we make the cost model converge quickly to the loss value we set by manually adjusting the parameters. Compared with other advanced compilers, PCGC optimizes the overall power consumption on an embedded GPU by an average of 130.5% when the time consumption on each hardware is not lower than the average time consumption. On domain-specific architecture, PCGC optimizes power consumption by an average of 66.5%. On FPGA, PCGC optimizes power consumption by 66.1%. In a sense, PCGC can achieve high-speed inference in specific power supply scenarios, reducing the carbon emissions of edge computing. [ABSTRACT FROM AUTHOR]

As a popular platform-independent language, Java is widely used in enterprise applications. In the past few years, language vulnerabilities exploited by Java malware have become increasingly prevalent, which cause threats for multi-platform. Security researchers continuously propose various approaches for fighting against Java malware programs. The low code path coverage and poor execution efficiency of dynamic analysis limit the large-scale application of dynamic Java malware detection methods. Therefore, researchers turn to extracting abundant static features to implement efficient malware detection. In this paper, we explore the direction of capturing malware semantic information by using graph learning algorithms and present BejaGNN (Behavior-based Java malware detection via Graph Neural Network), a novel behavior-based Java malware detection method using static analysis, word embedding technique, and graph neural network. Specifically, BejaGNN leverages static analysis techniques to extract ICFGs (Inter-procedural Control Flow Graph) from Java program files and then prunes these ICFGs to remove noisy instructions. Then, word embedding techniques are adopted to learn semantic representations for Java bytecode instructions. Finally, BejaGNN builds a graph neural network classifier to determine the maliciousness of Java programs. Experimental results on a public Java bytecode benchmark demonstrate that BejaGNN achieves high F1 98.8% and is superior to existing Java malware detection approaches, which verifies the promise of graph neural network in Java malware detection. [ABSTRACT FROM AUTHOR]

The distributed computing or parallel computing system uses an interconnection network as a topology structure to connect a large number of processors. The disjoint paths of interconnection networks are related to parallel computing and the fault tolerance. l-path cover of graph G = (V (G) , E (G)) consists of (internally) disjoint paths P k s ( 1 ≤ k ≤ l ), where ∪ k = 1 l V (P k) = V (G) . The bubble-sort star graph is bipartite and has favorable reliability and fault tolerance which are critical for multiprocessor systems. We focus on the one-to-one 1-path cover, one-to-one (2 n - 3) -path cover, and many-to-many 2-path cover of the bubble-sort star graph B S n . More specifically, let V (B S n) = V e ∪ V o with V e ∩ V o = ∅ , for { u , x } ⊂ V e and { v , y } ⊂ V o , we prove that (1) B S n contains a 1-path cover, i.e., Hamiltonian path P uv , (2) B S n contains one-to-one (2 n - 3) -path cover P k s ( 1 ≤ k ≤ 2 n - 3 ) between u and v, and (3) B S n contains many-to-many 2-path cover P uv and P xy , where n ≥ 3 . Since B S n is (2 n - 3) -regular graph, the one-to-one (2 n - 3) -path cover is the maximal one-to-one path cover. [ABSTRACT FROM AUTHOR]

Subgraph matching, as a challenging problem in the graph area, has a wide range of applications from social networks to computational biology. It refers to finding the occurrences of a query graph in a given large graph. Subgraph matching is considered an NP-complete problem in the literature. In order to reduce the computational complexity of subgraph matching, pruning the search space with heuristics, e.g., topological features, have been studied broadly. In this paper, we propose a novel pruning strategy in subgraph matching to reduce the size of search space, named Eigen Decomposition Pruning. EDP uses local spectral features to prune the search space instead of directly using topological features. Firstly, it generates a Local Laplacian Matrix (LLM) for each candidate solution. Then, it prunes the false positive candidates from the search space using the spectral features of these LLMs. An LLM is defined to capture the features in the localities of a graph and imposes a low computation overhead. Additionally, EDP recognizes more false positive candidates than previous methods due to more informative spectral features of LLM, which results in a noticeable decrease in the overall time of subgraph matching. To assess the performance of our algorithm, it is applied to both real and synthetic datasets and is compared against four well-known methods in this field. The theoretical analysis and experimental results confirm the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Fault diagnosis of interconnection networks is vital to ensuring the reliability and maintenance of multiprocessor systems. Based on graph theory, diagnostic algorithms for solving the problem of fault diagnosis in interconnection networks have been widely studied. As the number of processors in multiprocessor systems has increased in recent years, fault diagnosis algorithms based on graph theory cannot meet the current diagnosis requirements of some interconnection networks, such as t-diagnosable systems. In this paper, we use the evolution diagnosis approach to study fault diagnosis in t-diagnosable systems under the PMC model. First, for a t-diagnosable system G with a syndrome σ , we use a simple centralized algorithm to generate its simplified diagnosis graph G f , which contains all the faulty nodes in G. Based on the graph, we prove that the faulty node set in G is the minimum cover set of G f . Next, we prove that the problem of computing the minimum cover set for G f is equivalent to the problem of computing the optimal solution of a zero-one integer program. Using this result, we propose a novel genetic algorithm to solve the problem of the zero-one integer program. The simulation results show that the diagnostic accuracy of our proposed algorithm is equal to or greater than 96% and that the proposed algorithm outperforms its competitors in terms of diagnostic accuracy, number of iterations and running time. [ABSTRACT FROM AUTHOR]

In Network Function virtualization (NFV), network functions are virtualized as Virtual Network functions (VNFs). A network service consists of a set of VNFs. One of the major challenges in implementing this paradigm is allocating optimal resources to VNFs. Most existing work assumes that services are represented as service functional chains (SFC), which are chains. However, for more complex and diversified network services, a more appropriate representation is Virtual Network Function Forwarding Graph (VNF-FG), namely directed acyclic Graph (DAGs). Previous works failed to take advantage of this special graph structure, which makes them unsuitable for complex and diverse network service scenarios. Aiming at the problem of virtual network function Forwarding Graph mapping (VNF-FGE) represented by DAG, this paper proposes a virtual network function (VNF) deployment algorithm based on graph convolution network (GCN) and deep reinforcement learning (DRL), called GDRL-VNFP. First, we describe the VNF-FGE problem as an integer linear programming (ILP) problem and the virtual network service request (NSR) as a DAG. Secondly, in order to overcome the challenges brought about by the different sizes and dynamic arrival of the DAG representation of NSR, an efficient algorithm based on GCN and DRL is proposed, which can generate deployment solutions in real time under the premise of meeting the quality of service and minimize the total cost of deployment. We use GCN to extract features from the physical network topology and VNF-FG represented by DAG, and in addition, and construct a sequence-to-sequence model based on the attention mechanism for the output mapping scheme. Finally, we trained the model using a policy-based gradient-based reinforcement learning algorithm that could quickly find a near-optimal solution for the problem instance. Simulation results show that our GDRL-VNFP outperforms state-of-the-art solutions in terms of deployment cost, service request reception rate and runtime. [ABSTRACT FROM AUTHOR]

Graph coloring is widely used to parallelize scientific applications by identifying subsets of independent tasks that can be executed simultaneously. Graph coloring assigns colors the vertices of a graph, such that no adjacent vertices have the same color. The number of colors used corresponds to the number of parallel steps in a real-world end-application. Therefore, the total runtime of the graph coloring kernel adds to the overall parallel overhead of the real-world end-application, whereas the number of the vertices of each color class determines the number of the independent concurrent tasks of each parallel step, thus affecting the amount of parallelism and hardware resource utilization in the execution of the real-world end-application. In this work, we propose a high-performance graph coloring algorithm, named ColorTM, that leverages Hardware Transactional Memory (HTM) to detect coloring inconsistencies between adjacent vertices. ColorTM detects and resolves coloring inconsistencies between adjacent vertices with an eager approach to minimize data access costs, and implements a speculative synchronization scheme to minimize synchronization costs and increase parallelism. We extend our proposed algorithmic design to propose a balanced graph coloring algorithm, named BalColorTM, with which all color classes include almost the same number of vertices to achieve high parallelism and resource utilization in the execution of the real-world end-applications. We evaluate ColorTM and BalColorTM using a wide variety of large real-world graphs with diverse characteristics. ColorTM and BalColorTM improve performance by 12.98 × and 1.78 × on average using 56 parallel threads compared to prior state-of-the-art approaches. Moreover, we study the impact of our proposed graph coloring algorithmic designs on a popular end-application, i.e., Community Detection, and demonstrate the ColorTM and BalColorTM can provide high-performance improvements in real-world end-applications across various input data given. [ABSTRACT FROM AUTHOR]

Circuits in a graph are interesting structures and identifying them is of an important relevance for many applications. However, enumerating circuits is known to be a difficult problem, since their number can grow exponentially. In this paper, we propose fast parallel approaches for enumerating elementary circuits of directed graphs based on graphics processing unit (GPU). Our algorithms are based on a massive exploration of the graph in a breadth-first search strategy. Algorithm V-FEC explores the graph starting from different vertices simultaneously. To further reduce the search space, we present T-FEC, another algorithm that uses triplets as an initial set to start exploring. To the best of our knowledge, those are the first parallel GPU-based algorithms for finding all circuits of a given graph. In addition, they find circuits of a given length and circuits with a specific vertex or edge. The evaluation results show that the proposed approaches achieve up to 190x speed-up over Johnson's algorithm, one of the most efficient sequential algorithms for finding circuits. [ABSTRACT FROM AUTHOR]

Multiprocessor systems with parallel computing play an important role in data processing. Considering the optimal use of existing computing systems, scheduling on parallel systems has gained great significance. Usually, a sequential program to run on parallel systems is modeled by a task graph. Because scheduling of task graphs onto processors is considered the most crucial NP-complete problem, many attempts have been made to find the most approximate optimal scheduling using genetic algorithms. Its chromosomal representation largely influences the performance of the genetic algorithm. The chromosomal structure used in the existing genetic algorithms does not entirely scan the solution space. As a result, these algorithms fail to produce an appropriate schedule frequently. To overcome this constraint, the present study proposed a new method for constructing chromosomal representation. The proposed approach was divided into three phases: ranking, clustering, and cluster scheduling, where a genetic algorithm schedules clusters. To optimize the proposed genetic algorithm's performance, it was equipped with four heuristic principles: load balancing, reuse of idle time, task duplication, and critical path. Finally, by comparing the obtained results for 6 task graphs in 3 types, the amount of optimization was equal to the results of previous best algorithm, but in the other 3 types, the amount of optimization was a value between 4.25 and 6.88%. [ABSTRACT FROM AUTHOR]

In the process of software system evolution, software users constantly put forward a large number of expectations. For these expectations, software developers usually use the existing third-party libraries and other software resources to accelerate their development processes. At present, tons of third-party libraries are available. Therefore, appropriate recommendation methods are very important for developers to find suitable libraries for their development projects. In this paper, we present KG2Lib, a recommendation method to assist software developers in selecting suitable software libraries for their current projects. KG2Lib exploits a knowledge-graph-based convolutional network to recommend software libraries by relying on a set of libraries which were already called by current projects. The interaction matrix, weight matrix and knowledge graph are the inputs of KG2Lib. What's more, KG2Lib recommends libraries to developers from project level and library level, which can better capture the fine-grained information to achieve better recommend performance. The performance of KG2Lib was evaluated on three datasets with four existing baseline models. The experimental results show that KG2Lib achieves better performance and helps software developers accurately select the appropriate third-party libraries. [ABSTRACT FROM AUTHOR]

GPGPU architectures have become the dominant platform for massively parallel workloads, delivering high performance and energy efficiency for popular applications such as machine learning, computer vision or self-driving cars. However, irregular applications, such as graph processing, fail to fully exploit GPGPU resources due to their divergent memory accesses that saturate the memory hierarchy. To reduce the pressure on the memory subsystem for divergent memory-intensive applications, programmers must take into account SIMT execution model and memory coalescing in GPGPUs, devoting significant efforts in complex optimization techniques. Despite these efforts, we show that irregular graph processing still suffers from low GPGPU performance. We observe that in many irregular applications the mapping of data to threads can be safely changed. In other words, it is possible to relax the strict relationship between thread and data processed to reduce memory divergence. Based on this observation, we propose the Irregular accesses Reorder Unit (IRU), a novel hardware extension tightly integrated in the GPGPU pipeline. The IRU reorders data processed by the threads on irregular accesses to improve memory coalescing, i.e., it tries to assign data elements to threads as to produce coalesced accesses in SIMT groups. Furthermore, the IRU is capable of filtering and merging duplicated accesses, significantly reducing the workload. Programmers can easily utilize the IRU with a simple API, or let the compiler issue instructions from our extended ISA. We evaluate our proposal for state-of-the-art graph-based algorithms and a wide selection of applications. Results show that the IRU achieves a memory coalescing improvement of 1.32x and a 46% reduction in the overall traffic in the memory hierarchy, which results in 1.33x speedup and 13% energy savings on average, while incurring in a small 5.6% area overhead. [ABSTRACT FROM AUTHOR]

As an important part of distributed graph computing, graph partitioning has been widely studied. However, the majority of the existing approaches to distributed graph partitioning barely take into consideration the relationship between the partition strategy and the graph algorithm's characteristics. The current graph partitioning strategies are on the basis of the graph structure, and the performance is diverse as running different graph algorithms. In this paper, considering the characteristics of a graph algorithm, we propose a distributed graph partitioning framework that can decide which partitioning strategy is better based on the program analysis. We also design a triangle-based partitioning strategy which benefits several graph algorithms such as the triangle counting. In addition, to reduce the number of shuffling operations in PageRank algorithm, we redesign the PageRank algorithm which considers the corresponding hash partitioning. The experimental results show that our adaptive graph partitioning framework implemented on Graphx surpasses the original one, especially for the triangle counting and PageRank, no matter on real-world graphs or synthetic graphs. [ABSTRACT FROM AUTHOR]

Given a large data graph, trimming techniques can reduce the search space by removing vertices without outgoing edges. One application is to speed up the parallel decomposition of graphs into strongly connected components (SCC decomposition), which is a fundamental step for analyzing graphs. We observe that graph trimming is essentially a kind of arc-consistency problem, and AC-3, AC-4, and AC-6 are the most relevant arc-consistency algorithms for application to graph trimming. The existing parallel graph trimming methods require worst-case O (n m) time and worst-case O (n) space for graphs with n vertices and m edges. We call these parallel AC-3-based as they are much like the AC-3 algorithm. In this work, we propose AC-4-based and AC-6-based trimming methods. That is, AC-4-based trimming has an improved worst-case time of O (n + m) but requires worst-case space of O (n + m) ; compared with AC-4-based trimming, AC-6-based has the same worst-case time of O (n + m) but an improved worst-case space of O (n) . We parallelize the AC-4-based and AC-6-based algorithms to be suitable for shared-memory multi-core machines. The algorithms are designed to minimize synchronization overhead. For these algorithms, we also prove the correctness and analyze time complexities with the work-depth model. In experiments, we compare these three parallel trimming algorithms over a variety of real and synthetic graphs on a multi-core machine, where each core corresponds to a worker. Specifically, for the maximum number of traversed edges per worker by using 16 workers, AC-3-based traverses up to 58.3 and 36.5 times more edges than AC-6-based trimming and AC-4-based trimming, respectively. That is, AC-6-based trimming traverses much fewer edges than other methods, which is meaningful especially for implicit graphs. In particular, for the practical running time, AC-6-based trimming achieves high speedups over graphs with a large portion of trimmable vertices. [ABSTRACT FROM AUTHOR]

A deterministic method for synthesizing the interconnect topologies optimized for the required properties is proposed. The method is based on the original description of graphs by projections, establishing the bijective correspondence of the required properties and the projection properties of the initial graph, postulating the corresponding restrictions of modified projections and on iteratively applying these restrictions to them either until the projections system is solved and the projections of the desired graph are obtained, or until its incompatibility with the given initial conditions is revealed. [ABSTRACT FROM AUTHOR]

Existing Web services recommendation models suffer from matrix sparsity and cold-start problems due to the limited number of user-service interactions and too little contextual information, so this paper introduces knowledge graph as auxiliary information to Web service recommendation to alleviate matrix sparsity and cold-start problems. And we propose the Web services recommendation based on Metapath-guided Graph Attention Network Model (WSR-MGAT) to fully exploit the structural information of the knowledge graph to improve the recommendation accuracy. Specifically, WSR-MGAT uses graph embedding method to obtain the initial embedding of entities and relationships. In order to obtain more closely related neighbors, we propose to use a distance-aware path sampling method to extract meta-path instances with closer relationships. Previous knowledge graph-based Web service recommendations do not make full use of the rich interaction information, which may lead to limited performance. To address this problem, this paper uses meta-paths to guide nodes to recursively aggregate higher-order neighbor information and use an attention mechanism to distinguish the importance of neighbors. Meanwhile, the semantic information of nodes under different meta-paths is fused to obtain a more comprehensive embedding of nodes. To verify the performance of the model, we use the real data crawled from the ProgrammableWeb platform to conduct multiple groups of experiments. The experimental results show that the WSR-MGAT improves over the strongest baselines w.r.t. Prec@10 by 4.6%; Recall@10 by 3.8%; NDCG@10 by 4.2% and F1@10 by 4.9%. [ABSTRACT FROM AUTHOR]

In location-based social network platforms, the point-of-interest(POI) recommendation is an essential function to serve users. The existing POI recommendation algorithms are rarely able to fully integrate various factors affecting the POI recommendation and cannot make dynamic recommendations to users over time. To address this issue, POI recommendation based on a multiple bipartite graph network model (MBR) is proposed. To reduce the overall complexity of the recommendation algorithm, we propose a clustering algorithm based on graph model, which determines the center of user clustering in the established user graph. An algorithm for finding the sparsest subgraph is built to cluster users who have social friendships or check in at similar POI, which significantly excludes more dissimilar users and makes the final recommendation more effective, as well as reducing the algorithm's complexity. To make more accurate recommendations to users, a large heterogeneous network of six weighted bipartite graphs is built based on the user clustering to describe the relations between users' social relationships, geographical locations of POI, and temporal information. The original Large-scale Information Network Embedding (LINE) model is too complex to be adopted for the learning of vertex embedding, thus it is optimized by negative sampling and Alias sampling methods and are fused with bipartite graphs, which accelerates the training speed. Finally, simulation experiments are conducted with the Gowalla dataset to verify the MBR algorithm, and the results show that the algorithm outperforms another three recommendation algorithms in terms of time awareness. [ABSTRACT FROM AUTHOR]

Various methods have been proposed to evaluate the reliability of a graph, one of the most well known of which is the reliability polynomial, R(G, p). It is assumed that G(V, E) is a simple and unweighted connected graph whose nodes are perfect and edges are operational with an independent probability p. Thus, the edge reliability polynomial is a function of p of the number of network edges. There are various methods for calculating the coefficients of reliability polynomial, all of which are related to their recursive nature, which has led to an increase in their computational complexity. Therefore, if the difference between the number of links and nodes in the network exceeds a certain amount, the exact calculation of the coefficients R(G, p) is practically in the NP-hard complexity class. In this paper, while examining the problems in the previous methods, four new approaches for estimating the coefficients of reliability polynomial are presented. In the first approach, using an iterative method, the coefficients are estimated. This method, on average, has the same accuracy as common methods in the related studies. In addition, the second method as an intelligent scheme for integrating the values of coefficients has been proposed. The values of coefficients for smaller, larger, and finally intermediate indices have been determined with the help of this intelligent approach. Further, as a third proposed method, Benford's law is utilized to combine the coefficients. Finally, in the fourth approach, using the Legendre interpolation method, the coefficients are effectively estimated with an appropriate accuracy. To compare these approaches fairly and accurately with each other, they have been carried out on synthetic and real-world underlying graphs. Then, their efficiency and accuracy have been evaluated, compared, and analyzed according to the experimental results. [ABSTRACT FROM AUTHOR]

With the advent of cloud computing, more businesses are turning to the cloud for deploying their applications and for infrastructure solutions. Quality of Service parameters has a direct impact on businesses. Enterprises have to select the best cloud service provider with optimum cost. In this paper, we present a graph-based method for ranking cloud service providers. First, we compute a partial correlation between cloud service providers in terms of their response time. Second, we construct a graphical lasso regularization network with a penalty, which controls spurious connections. Third, the service providers are ranked based on degree centrality. Finally, we applied a normalized discounted cumulative gain method to measure the rank quality of cloud service providers. The comparative experimental results show that lasso regularization performs better than the traditional Bonferroni correction method. [ABSTRACT FROM AUTHOR]

Graph analytics plays an important role in many areas such as big data and artificial intelligence. The vertex-centric programming model provides friendly interfaces to programmers and is extensively used in graph processing frameworks. However, it is prone to generate many irregular memory accesses and scheduling overhead due to vertex-based execution and scheduling of programs in the backend. Instead, the matrix-based model provides a different approach by using high-performance matrix operations in the backend to improve the efficiency of graph processing. Unfortunately, current matrix-based frameworks only support the synchronous parallel model, which constrains its application to various graph algorithms. To address these problems, this paper proposes a graph processing framework, which combines matrix operations with the asynchronous model while providing friendly programming interfaces similar to vertex-centric programming model. Firstly, we propose an approach to map the vertex-based graph processing to matrix operations in the asynchronous model. Then, we propose two asynchronous scheduling policies, Gauss–Seidel policy and relaxed Gauss–Seidel policy, for different graph algorithms. After that, our framework applies the batch scheduling and optimized in-memory data structure to reduce the scheduling overhead introduced by the asynchronous model. Experimental results show that our framework performs better than the popular vertex programming frameworks such as GraphLab and GRACE in both performance and speedup and achieves similar performance compared to the BSP-based matrix framework such as GraphMat. [ABSTRACT FROM AUTHOR]

Prior algorithms on graph simulation for distributed graphs are not scalable enough as they exhibit heavy message passing. Moreover, they are dependent on the graph partitioning quality that can be a bottleneck due to the natural skew present in real-world data. As a result, their degree of parallelism becomes limited. In this paper, we propose an efficient parallel edge-centric approach for distributed graph pattern matching. We design a novel distributed data structure called ST that allows a fine-grain parallelism, and hence guarantees linear scalability. Based on ST, we develop a parallel graph simulation algorithm called PGSim. Furthermore, we propose PDSim, an edge-centric algorithm that efficiently evaluates dual simulation in parallel. PDSim combines ST and PGSim in a Split-and-Combine approach to accelerate the computation stages. We prove the effectiveness and efficiency of these propositions through theoretical guarantees and extensive experiments on massive graphs. The achieved results confirm that our approach outperforms existing algorithms by more than an order of magnitude. [ABSTRACT FROM AUTHOR]

Graphs are suitable data structures for expressing the relationship between different types of data. With a continuous increase in the graph size, using suitable methods to divide graphs and parallelize the processing load becomes crucial. Balanced graph partitioning has been extensively studied for static and streaming graphs. However, for a time-evolving graph (TEG), whose size and structure are periodically updated, related partitioning methods are lacking. A straightforward approach is to capture snapshots of a TEG and adopt the partitioning methods designed for static or streaming graphs. Although feasible partitioning quality can be expected, the time overhead is high due to frequent repartitioning. This paper proposes two TEG partitioning methods, namely seed and similarity, to decrease the partitioning time. According to the experimental results, on average, seed and similarity require 29–39% of the partitioning time required by snapshot. Moreover, the proposed methods maintain reasonable partitioning quality. [ABSTRACT FROM AUTHOR]

Travelling salesman problem (TSP) is a graph problem that has been widely used in many applications, especially for transportation and logistics. Because TSP is a NP hard problem, minimizing the complexity of TSP algorithms is an important problem. Many heuristic algorithms have been proposed to compute the TSP tours of a given static graph. But limited studies have been done on time-evolving graph (TEG) where the graph can change over time due to update events, such as weight changes on edges or vertices. It is a more challenging problem because the speed of TSP computations must be high enough to catch up the graph update frequency. In this paper, we make the very first attempt to minimize the computation time of solving TSP on time-evolving graphs. By exploring parallel computing power and reusing previous computing results, we proposed a distributed and incremental TSP algorithm which can be implemented on vertex-centric parallel graph computing frameworks to efficiently find TSP tours on large changing graphs. Our incremental algorithm can maintain shortest TSP tour with minimum amount of recomputation. Through our experimental evaluation, we have shown incremental TSP algorithm is 98% faster than distributed algorithm. [ABSTRACT FROM AUTHOR]

Complex expressions are the basis of data analytics. To process complex expressions on big data efficiently, we developed a novel optimization strategy for parallel computation platforms such as Hadoop and Spark. We attempted to minimize the rounds of data repartition to achieve high performance. Aiming at this goal, we modeled the expression as a graph and developed a simplification algorithm for this graph. Based on the graph, we converted the round minimization problem into a graph decomposition problem and developed a linear algorithm for it. We also designed appropriated implementation for the optimization strategy. Extensive experimental results demonstrate that the proposed approach could optimize the computation of complex expressions effectively with small cost. [ABSTRACT FROM AUTHOR]

Recently more and more information sources are connected together and become a sort of complex graphs that can be exploited not only as a structured and semi-structured data such as rdb or xml, RDF or NoSQL, but also as many kinds of unstructured data such as web, bioinformatics, genometrics, patents, social media, knowlege graphs, IoT, hidden graph from deep learning results. State of the art studies have suggested methods of presenting data as hyper-graphs in search queries and finding search results in subgraphs or graph embeddings rather than a list of individual node results. We study the problem of retrieving top-k graph results with the query relevances; that is, given a set of query keywords Q on a graph G, we aim to find a subgraph g of G such that g is highly related to Q and closely linked under g. In order to consider the relevant graph results and the connectivity simultaneously, we present an effective algorithm graph threshold algorithm (GTA) based on a threshold algorithm (TA) which works efficiently in non-graph structure. We show that GTA does not need unnecessary searches under given objective functions, and prove the existence of an upper bound of the size of subgraph for top-k results, called hop max , which makes it efficient to find the combined results. Finally, we conduct the performance studies on real and synthetic graphs, which demonstrate that our algorithm significantly outperforms conventional approaches with respect to time complexity and cost consumption. [ABSTRACT FROM AUTHOR]

Developing efficient graph algorithms implementations is an extremely important problem of modern computer science, since graphs are frequently used in various real-world applications. Graph algorithms typically belong to the data-intensive class, and thus using architectures with high-bandwidth memory potentially allows to solve many graph problems significantly faster compared to modern multicore CPUs. Among other supercomputer architectures, vector systems, such as the SX family of NEC vector supercomputers, are equipped with high-bandwidth memory. However, the highly irregular structure of many real-world graphs makes it extremely challenging to implement graph algorithms on vector systems, since these implementations are usually bulky and complicated, and a deep understanding of vector architectures hardware features is required. This paper presents the world first attempt to develop an efficient and simultaneously simple graph processing framework for modern vector systems. Our vector graph library (VGL) framework targets NEC SX-Aurora TSUBASA as a primary vector architecture and provides relatively simple computational and data abstractions. These abstractions incorporate many vector-oriented optimization strategies into a high-level programming model, allowing quick implementation of new graph algorithms with a small amount of code and minimal knowledge about features of vector systems. In this paper, we evaluate the VGL performance on four widely used graph processing problems: breadth-first search, single source shortest paths, connected components, and page rank. The provided comparative performance analysis demonstrates that the VGL-based implementations achieve significant acceleration over the existing high-performance frameworks and libraries: up to 14 times speedup over multicore CPUs (Ligra, Galois, GAPBS) and up to 3 times speedup compared to NVIDIA GPU (Gunrock, NVGRAPH) implementations. [ABSTRACT FROM AUTHOR]

Network on chip (NoC) has been of great interest in recent years. However, according to the recent studies, high communication cost has been raised as the one most important challenges in mapping process in NoC. In order to address these issues, this research takes the advantages of the improved shuffled frog leaping based on two-dimensional torus networks in figure of an enhanced algorithm. In other words, using the proposed mapping category features, increase in the number of nodes has very little effect on the provided performance by the proposed algorithm, because it first improves the write cost of each cluster with less instead of high communication cost. Moreover, nodes having greater relevance in the graph of application are often adjacent to each other. Therefore, while the communication cost is reduced, the search space mapping gets larger which leads to easier and less costly access to the optimal mapping. In fact, between two nodes with higher weight, it is less distance to write in the network substrate. This reduction reduces the distance between the two nodes in the end, reducing the cost of communication. Simulation results show that the communication cost is improved by 3.62, 0.90, 0.72 and 1.35% compared to PSMAP algorithm for the 263dec mp3dec graph, Lmap algorithm for the 263enc mp3dec graph, Lmap algorithm for the MWD graph and PSMAP algorithm for MPEG-4 graph, respectively. [ABSTRACT FROM AUTHOR]

Force-directed algorithm is one of the most commonly used methods for visualization of 2D graphs. These algorithms can be applied to a plethora of applications such as data visualization, social network analysis, crypto-currency transactions, and wireless sensor networks. Due to their effectiveness in visualization of topological data, various force-directed algorithms for 2D graphs were proposed in recent years. Although force-directed algorithms for 2D graphs were extensively investigated in research community, the algorithms for 3D graph visualization were rarely reported in the literature. In this paper, we propose four novel clustering-based force-directed (CFD) algorithms for visualization of 3D graphs. By using clustering algorithms, we divide a large graph into many smaller graphs so that they can be effectively processed by force-directed algorithms. In addition, weights are also introduced to further enhance the calculation for clusters. The proposed CFD algorithms are tested on 3 datasets with varying numbers of nodes. The experimental results show that proposed algorithms can significantly reduce edge crossings in visualization of large 3D graphs. The results also reveal that CFD algorithms can also reduce Kamada and Kawai energy and standardized variance of edge lengths in 3D graph visualization. [ABSTRACT FROM AUTHOR]

The wide use of recommendation systems includes more users and items in system operations, leading to a significant increase in the size of related datasets. However, recommendation algorithms on existing single-machine-based graph engines have been developed without considering the important characteristics of recommendation datasets, i.e., huge size and power-law degree distribution. In this paper, we address how to realize efficient graph- and matrix-factorization-based recommendation algorithms, handling recommendation datasets on RealGraph, a state-of-the-art single-machine-based graph engine. Through extensive experiments, we demonstrate that our recommendation algorithms on RealGraph universally and consistently outperform the algorithms on other graph engines over all datasets up to 34 times. [ABSTRACT FROM AUTHOR]

The vertex-centric (VC) computation model has emerged as a promising approach for easy parallel programming and massive parallel execution for big graph processing. A simple graph computation can easily be implemented in the VC model, but some algorithms cannot easily be implemented in the VC model. Examples of the latter algorithms are those that use vertex subsets or subgraphs as a manipulation unit. Such a "global view style" is natural for programmers to design graph algorithms, but the VC model requires us to redesign algorithms in the "local view style" focusing on a vertex. The gap between these styles prevents us from writing parallel programs for useful graph computations. In this paper, we propose a novel DSL for graph processing that can be used to write parallel programs for big graph processing in the "global view style". It is compiled into the VC model so that it can enjoy massive parallelism in various parallel computing environments including commercial cloud services like Amazon EC2. We show non-trivial examples in our DSL, and our experimental results show that the compiled program achieves good scalability. [ABSTRACT FROM AUTHOR]

Foreign exchange (FOREX) market is a decentralized global marketplace in which different participants, such as international banks, companies or investors, can buy, sell, exchange and speculate on currencies. This market is considered to be the largest financial market in the world in terms of trading volume. Indeed, the just-in-time price prediction for a currency pair exchange rate (e.g., EUR/USD) provides valuable information for companies and investors as they can take different actions to improve their business. The trading volume in the FOREX market is huge, disperses, in continuous operations (24 h except weekends), and the context significantly affects the exchange rates. This paper introduces a context-aware algorithm to model the behavior of the FOREX Market, called parallel elastic network model (PENM). This algorithm is inspired by natural procedures like the behavior of macromolecules in dissolution. The main results of this work include the possibility to represent the market evolution of up to 21 currency pair, being all connected, thus emulating the real-world FOREX market behavior. Moreover, because the computational needs required are highly costly as the number of currency pairs increases, a hybrid parallelization using several shared memory and message passing algorithms studied on distributed cluster is evaluated to achieve a high-throughput algorithm that answers the real-time constraints of the FOREX market. The PENM is also compared with a vector autoregressive (VAR) model using both a classical statistical measure and a profitability measure. Specifically, the results indicate that PENM outperforms VAR models in terms of quality, achieving up to 930 × speed-up factor compared to traditional R codes using in this field. [ABSTRACT FROM AUTHOR]

The fast development of big data computing contributes to the fact that large-scale graph processing has become a basic computing model in both academic and industrial communities, and it has been applied in many actual big data computing works, such as social network analysis, Web search, and product promotion. These computing works include large-scale graphs of billions of vertices and trillions of edges. Such scale has brought many challenges to large-scale graph processing. This paper mainly introduces the essential features and challenges of large-scale graph processing and how we can handle billions of edges on a multi-core machine, for which we represent out-of-core processing system and semi-external memory processing systems. This paper also summarizes the key technologies in graph processing systems and forecasts the future development of large-scale graph processing systems. [ABSTRACT FROM AUTHOR]

The demand to deliver fast responses in processing time-evolving graphs is higher than ever before in a large number of big data applications. This problem promotes extensive uses of an incremental computing model, which executes the underlying graph algorithm on the newly updated graph structure by taking the results of the computation on the outdated graph structure as initial values, in distributed time-evolving graph computing systems. In this paper, we experimentally study how the initial values of the computation on a newly updated graph structure influence the convergence of the iterative graph analysis, and we develop an optimization framework on the basis of the incremental computing model to accelerate the convergence of processing time-evolving graphs thus achieving high performance for time-evolving graph analysis. In contrast to the traditional incremental computing model, which uses the results of the computation on the outdated graph structure directly, the proposed framework predicts the optimal initial values of the computation on the new graph structure and thereby reduces the number of iterations. Two different prediction approaches are designed to optimize the initial values based on a combination of the results of the computation on the previous graph data and the newly incoming graph data. We have evaluated our optimization framework using the graph algorithms PageRank and KMeans on Amazon EC2 clusters. The experiments demonstrate that the incremental computing implementation with the initial value prediction have reduced the number of iterations by 30% for the PageRank algorithm and 13.7% for the KMeans algorithm, and reduced the response time by 12.7% and 10.6% accordingly compared to the traditional incremental computing model. [ABSTRACT FROM AUTHOR]

Well-known techniques for tiled code generation are based on the polyhedral model and affine transformations. An alternative approach to generation of tiled code is to correct original rectangular tiles defined for a loop nest by means of the transitive closure of a dependence graph instead of deriving and applying affine transformations. In this paper, we present results of an analysis of basic features of tiles generated due to correction of original rectangular tiles. We introduce procedures which allow us to recognize such features as target tile type (fixed, varied, parametric), dimensionality, size (the number of statement instances within a tile), and loop nest tileability (the percentage of statement instances that can be tiled with rectangular tiles). We consider differences between those features of tiles generated by means of affine transformations and transitive closure. We also discuss results of experiments with PolyBench benchmarks and show how differences in tiles generated with the examined approach and affine transformations affect serial tiled code performance. [ABSTRACT FROM AUTHOR]

We study the problem of computing Euclidean minimum weight matching which investigates the minimum weight perfect matching in a complete geometric graph on a set of 2n points in the plane. We propose a simple randomized approximation algorithm based on the geometrical aspect of the problem with O(n) expected time. The proposed algorithm computes a matching within at most 3 factors of the optimal solution. We also do some experimental tests to evaluate the performance of the proposed algorithm which indicate the efficiency of the proposed algorithm in finding the approximate matching in the practice. [ABSTRACT FROM AUTHOR]

Efficient message forwarding in mobile ad hoc network in disaster scenarios is challenging because location information on the boundary and interior nodes is often unavailable. Information related to boundary nodes can be used to design efficient routing protocols as well as to prolong the battery power of devices along the boundary of an ad hoc network. In this article, we developed an algorithm, CWBound, which discovers boundary nodes in a complex non-convex mobile ad hoc (CNCAH) networks. Experiments show that the CWBound algorithm is at least three times faster than other state-of-the-art algorithms, and up to 400 times faster than classical force-directed algorithms. The experiments also confirmed that the CWBound algorithm achieved the highest accuracy (above 97% for 3 out of the 4 types of CNCAH networks) and sensitivity (90%) among the algorithms evaluated. [ABSTRACT FROM AUTHOR]

Graphics processing units (GPUs) have become popular high-performance computing platforms for a wide range of applications. The trend of processing graph structures on modern GPUs has also attracted an increasing interest in recent years. This article aims to review research works on adapting the massively parallel architecture of GPUs to accelerate the performance of fundamental graph operations. Despite their merits, some factors such as the unique architecture of GPUs, limited programming models, and irregular structures of graphs prevent GPU implementations from achieving high performance. Thus, this survey also discusses challenges and optimization techniques used by recent studies to fully utilize the GPU capability. A categorization of the existing research works is also presented based on the specific issues these attempted to solve. [ABSTRACT FROM AUTHOR]

In this paper, we address the matrix chain multiplication problem, i.e., the multiplication of several matrices. Although several studies have investigated the problem, our approach has some different points. First, we propose MapReduce algorithms that allow us to provide scalable computation for large matrices. Second, we transform the matrix chain multiplication problem from sequential multiplications of two matrices into a single multiplication of several matrices. Since matrix multiplication is associative, this approach helps to improve the performance of the algorithms. To implement the idea, we adopt multi-way join algorithms in MapReduce that have been studied in recent years. In our experiments, we show that the proposed algorithms are fast and scalable, compared to several baseline algorithms. [ABSTRACT FROM AUTHOR]

Flash memory is widely used in the storage system. The direct use of multi-dimensional index structure over flash memory would introduce a large number of redundant writes since such index structure requires fine-grained updates intensively. K-D-B-tree is a classic multi-dimensional index structure. In this paper, the implementation of K-D-B-tree over flash memory, namely F-KDB, is proposed to handle fine-grained updates. In F-KDB, a K-D-B-tree node is represented as a collection of logs (termed as logging entries) to efficiently process the updates of the node. Since the collecting and parsing of all the relevant logging entries to construct a node could degrade the query performance, a Workload Adaptive ( WA) online algorithm is proposed to improve the query performance. A series of experiments are conducted to demonstrate the efficiency of F-KDB over flash memory. The response times of insertion/deletion are significantly reduced and the overall performance of F-KDB is improved. [ABSTRACT FROM AUTHOR]

In this paper, we use the regular distribution method to design a perfect load balancing algorithm for an n-star with a maximum error of 1 and a time complexity of 3 n( n+1). This algorithm is based on the novel notion of leader trees. A second algorithm proposed in this paper as an enhancement to our first algorithm and uses an arbitrary spanning tree as the leader tree and has a worst time complexity of 2.25 n 2−3 n+0.75. We also discuss the issue of dynamically selecting the leader tree and hybrid load balancing algorithms in general. Furthermore, we present a hybrid algorithm for load balancing on the star interconnection network which benefits from a diffusion load balancing preprocessing phase and shows a smaller mean time complexity than our two first algorithms. [ABSTRACT FROM AUTHOR]

This paper presents BSR-parallel algorithms for some problems in fundamental graph theory : transitive closure, connected components, spanning tree, bridges and articulation points of a graph and bipartite graph recognition. There already exist constant time algorithms to solve these problems on a mesh with reconfigurable bus system using O( N 4) processors. Here we show that these problems can be solved in constant time using only O( N 2) processors on the BSR model ( N is the number of vertices of the graph G). Therefore, our algorithms are more work-efficient. These new results suggest that many other problems in graph theory can be solved in constant time using the BSR model. [ABSTRACT FROM AUTHOR]