Search

This paper studies batch processing of core maintenance in hypergraph streams. We focus on updating the coreness of each vertex after the hypergraph evolves. Unlike existing works that mainly focus on exact coreness updates for the single hyperedge dynamic or approximate update, we propose the first known batch processing algorithms for exact core maintenance with insertions or deletions of multiple hyperedges. By proposing a hyperedge structure Joint Hyperedge Set, we tackle the challenges of quantifying the range of coreness change and finding potential vertices whose coreness may update. In addition, we accelerate coreness updates even further by finding structures that enable parallel execution. Extensive experiments illustrate the efficiency, scalability, and effectiveness of our batch core maintenance algorithms on real-world hypergraphs. It shows that our algorithms can be faster than the single hyperedge processing approaches by a factor of nearly half the number of hyperedges processed, and our parallel algorithms achieve linear acceleration with the increasing number of threads. [ABSTRACT FROM AUTHOR]

With the prosperity of vehicular networks and intelligent transport systems, vast amount of data can be easily collected by vehicular devices from their users and widely spread in the vehicular networks for the purpose of solving large-scale machine learning problems. Hence how to preserve the data privacy of users during the learning process has become a public concern. To address this concern, under the celebrated framework of differential privacy (DP), we present in this paper a decentralized parallel stochastic gradient descent (D-PSGD) algorithm, called DP2-SGD, which can offer protection for privacy of users in vehicular networks. With thorough analysis we show that DP2-SGD satisfies (ε, δ)-DP while the learning efficiency is the same as D-PSGD without privacy preservation. We also propose a refined algorithm called EC-SGD by introducing an error-compensate strategy. Extensive experiments show that EC-SGD can further improve the convergence efficiency over DP2-SGD in reality. [ABSTRACT FROM AUTHOR]

Blockchain technologies can enable secure computing environments among mistrusting parties. Permissioned blockchains are particularly enlightened by companies, enterprises, and government agencies due to their efficiency, customizability, and governance-friendly features. Obviously, seamlessly fusing blockchain and cloud computing can significantly benefit permissioned blockchains; nevertheless, most blockchains implemented on clouds are originally designed for loosely-coupled networks where nodes communicate asynchronously, failing to take advantages of the closely-coupled nature of cloud servers. In this paper, we propose an innovative cloud-oriented blockchain – CloudChain, which is a modularized three-layer system composed of the network layer, consensus layer, and blockchain layer. CloudChain is based on a shared-memory model where nodes communicate synchronously by direct memory accesses. We realize the shared-memory model with the Remote Direct Memory Access technology, based on which we propose a shared-memory consensus algorithm to ensure presistence and liveness, the two crucial blockchain security properties countering Byzantine nodes. We also implement a CloudChain prototype based on a RoCEv2-based testbed to experimentally validate our design, and the results verify the feasibility and efficiency of CloudChain. [ABSTRACT FROM AUTHOR]

Abstract: Given a universe containing elements and a collection of multisets or sets over , the multiset multicover (MSMC) problem or the set multicover (SMC) problem is to cover all elements at least a number of times as specified in their coverage requirements with the minimum number of multisets or sets. In this paper, we give various exact algorithms for these two problems with or without constraints on the number of times a multiset or set may be chosen. First, we show that the MSMC without multiplicity constraints problem can be solved in time and polynomial space, where is the maximum coverage requirement and denotes the total number of given multisets over . (The notation suppresses a factor polynomial in .) To our knowledge, this is the first known exact algorithm for the MSMC without multiplicity constraints problem. Second, by combining dynamic programming and the inclusion–exclusion principle, we can exactly solve the SMC without multiplicity constraints problem in time. Compared with two recent results, in [Q.-S. Hua, Y. Wang, D. Yu, F.C.M. Lau, Set multi-covering via inclusion–exclusion, Theoretical Computer Science, 410 (38–40) (2009) 3882–3892] and [J. Nederlof, Inclusion exclusion for hard problems, Master Thesis, Utrecht University, The Netherlands, 2008], respectively, ours is the fastest exact algorithm for the SMC without multiplicity constraints problem. Finally, by directly using dynamic programming, we give the first known exact algorithm for the MSMC or the SMC with multiplicity constraints problem in time and space. This algorithm can also be easily adapted as a constructive algorithm for the MSMC without multiplicity constraints problem. [Copyright &y& Elsevier]

Coreness is an important index to reflect the cohesiveness of a graph. The problems of core computation in static graphs and core update in dynamic graphs, known as the core decomposition and core maintenance problems respectively, have been extensively studied in previous work. However, most of these work focus on unweighted graphs. Considering that graphs are weighted in a lot of realistic applications, it is indispensable to extend the coreness to weighted graphs and devise efficient algorithms for weighted core decomposition and weighted core maintenance. In this work, we present a new definition of weighted coreness for vertices in a weighted graph, by taking into account the weights of vertices, which makes the coreness in unweighted graph be a special case. We propose efficient algorithms for both weighted core decomposition and weighted core maintenance problems. The coreness of vertices can be computed in linear time by the proposed decomposition algorithm, while the proposed core maintenance algorithm can process multiple-edge insertions/deletions simultaneously, which greatly reduces the core update time. Comprehensive experiments on both realistic networks and temporal graphs exhibit our algorithms are efficient and scalable. [ABSTRACT FROM AUTHOR]

Coverage is one of the key issues to achieve energy efficiency of a wireless sensor network. Sensor scheduling is one of the most important methods to solve coverage problems. It can ensure the coverage degree of a region and prolong the network lifetime. In this paper, we focus on the k -coverage scheduling problem to guarantee k -coverage sensing and network connectivity. We consider both deterministic and stochastic sensing models of the sensors and adapt the results of deterministic sensing model to solve the sensor scheduling problem under the stochastic sensing model. We use regular pentagons to divide the sensing disks to solve the k -coverage problem. Each sensor node runs a stochastic k -coverage-preserving scheduling algorithm to determine its work modes, and redundant nodes can enter into sleep mode, while active nodes ensure the coverage of the network. Theoretical analysis and simulation results show that our algorithm can reduce the number of active nodes and extend the network lifetime significantly while maintaining a given coverage degree. [ABSTRACT FROM AUTHOR]