Abstract Graph stream is the model used to represent evolving graph data over time, which can be represented as a sequence of edge streams containing temporal information. To effectively manage an ultra large scale graph stream, existing designs usually use summarization structures based on compressed matrices to support approximate storage and querying of graph streams. However, the state-of-the-art structures are based on limited-sized compressed matrix. When dealing with dynamical graph stream data, they either use an extra adjacency list outside the compressed matrix to store left-over edges whose expected buckets in the matrix have been occupied by other previously inserted edges, or allocate new building blocks of compressed matrices to provide more space capacity. Such designs suffer from linear lookup time caused by the adjacency list or long system blocking time caused by data movement during structure scaling. Moreover, in graph stream applications with dynamically growing data sizes, recent data commonly carries greater significance and value. Existing designs fail to store the time information of items of graph streams in a space efficient way and leave recent data management over graph streams an unsolved problem. To address the dynamically expanding graph stream with the ability to accentuate the importance of recent data, in this work, we propose Sliding-ITeM, a novel adaptive-size graph stream summarization structure with a sliding window model. Two factors contribute to the efficiency of Sliding-ITeM. First, Sliding-ITeM proposes a novel fingerprint suffix index tree (FSIT) structure to efficiently manage the items assigned to a same bucket of a compressed matrix in a fine-grained and scalable way. It thus achieves time and space efficiency for graph stream management as well as avoiding costly blocking time for structure extending. Second, Sliding-ITeM divides continuous time into discrete time slices and stores items belong to different time slices in separate ITeM compressed matrices. Sliding-ITeM organizes the compressed matrices into a chain style chronologically and achieves efficient obtaining of value from recent data as well as removal of expired data following a sliding-window model. We conduct comprehensive experiments over large-scale graph stream data collected from real world systems to evaluate the performance of Sliding-ITeM. Experimental results show that it significantly reduces the operation latency by more than 67% in sliding window queries compared to state-of-the-art designs, while greatly reducing the system blocking duration by three orders of magnitude.

Sequence alignment, a crucial task in genome analysis for downstream applications such as mutation detection, faces challenges due to longer sequences and increased errors in the era of third-generation sequencing. This paper focuses on the optimization of Minimap2, a widely used alignment algorithm for mapping variable-length reads to extensive reference sequences. To enhance the algorithm’s performance, we introduce a novel approach leveraging FPGA technology to expedite the time-consuming extension step.

A graph stream refers to a continuous stream of edges, forming a huge and fast-evolving graph. The vast volume and high update speed of a graph stream bring stringent requirements for the data management structure, including sublinear space cost, computation-efficient operation support, and scalability of the structure. Existing designs summarize a graph stream by leveraging a hash-based compressed matrix and representing an edge using its fingerprint to achieve practical storage for a graph stream with a known upper bound of data volume. However, they fail to support the dynamically extending of graph streams. In this paper, we propose Auxo, a scalable structure to support space/time efficient summarization of dynamic graph streams. Auxo is built on a proposed novel prefix embedded tree (PET) which leverages binary logarithmic search and common binary prefixes embedding to provide an efficient and scalable tree structure. PET reduces the item insert/query time from O (| E |) to O ( log | E |) as well as reducing the total storage cost by a log | E | scale, where | E | is the size of the edge set in a graph stream. To further improve the memory utilization of PET during scaling, we propose a proportional PET structure that extends a higher level in a proportionally incremental style. We conduct comprehensive experiments on large-scale real-world datasets to evaluate the performance of this design. Results show that Auxo significantly reduces the insert and query time by one to two orders of magnitude compared to the state of the arts. Meanwhile, Auxo achieves efficiently and economically structure scaling with an average memory utilization of over 80%.

Graph stream, which represents an evolving graph updating as an infinite edge stream, is a special emerging graph data model widely adopted in big data analysis applications. Entirely storing the continuously produced and tremendously large-scale datasets is impractical. Therefore, graph stream summarization structures which support approximate graph stream storage and management attract much recent attention. Existing designs commonly leverage a compressive matrix and use hash-based schemes to map each edge to a bucket of the matrix. Accordingly, they store the edges associated with the same node in the same row or column of the matrix. We show that existing designs suffer from unacceptable query latency and precision in the presence of node degree skewness in graph streams.We argue that the key to efficient graph stream summarization is to identify the high-degree nodes and leverage a differentiated strategy for the associated edges. However, it is not trivial to estimate the degree of a node in real-time graph streams due to the rigorous requirements of space and time efficiency. Moreover, the existence of duplicate edges makes high-degree nodes identification difficult. To solve the problem, we propose Scube, an efficient summarization structure for skewed graph streams. Two factors contribute to the efficiency of Scube. First, Scube proposes a space and computation efficient probabilistic counting scheme to identify high-degree nodes in a graph stream. Second, Scube differentiates the storage strategy for the edges associated with high-degree nodes by dynamically allocating multiple rows or columns. We conduct comprehensive experiments to evaluate the performance of Scube on large-scale real-world datasets. The results show that Scube significantly reduces the query latency over a graph stream by 48%-99%, as well as achieving acceptable query accuracy compared to the state-of-the-art designs.

Graph stream, referred to as an evolving graph with a timing sequence of updated edges through a continuous stream, is an emerging data format widely used in big data applications. Coping with a graph stream is challenging because: 1) fully storing the continuously produced and extremely large-scale datasets is difficult if not impossible; 2) supporting queries relevant to both graph topology and temporal information is nontrivial. Recently, graph stream summarization techniques have attracted much attention in providing approximate storage and query processing for a graph stream. Existing designs largely utilize hash functions to reduce the graph scale and leverage a compressive matrix to represent the graph stream. However, such designs are unable to store the time dimension information of graph streams, and thus fail to support temporal queries. In this paper, we propose Horae, a novel graph stream summarization structure for efficient temporal range query, which presents a time prefix embedded multi-layer summarization structure. Our design is based on the insight that an arbitrary temporal range of length$L$can be decomposed to at most$2\log L$sub-ranges, where all the time points in each sub-range have the same binary code prefix. We further design an efficient Binary Range Decomposition (BRD) algorithm, which achieves a logarithmic scale query processing time. Experimental results show that Horae significantly reduces the latency of various temporal range queries by two to three orders of magnitude compared to the state-of-the-art designs.

Summary The scale of real‐world graphs is constantly growing. To deal with large‐scale graphs, distributed graph processing has attracted much research efforts. Existing distributed graph processing systems are commonly built on traditional TCP/IP communication stack, which leads to network bottleneck because of low bandwidth and heavy kernel stack operations. Meanwhile, in real power‐law graphs, the average number of mirror vertices after graph partitioning is very large, resulting in significant communication overhead among nodes. The emerging high‐performance Remote Direct Memory Access (RDMA) network has the features of low latency, high bandwidth, and low CPU overhead, which brings new opportunities for distributed graph processing systems. Existing RDMA‐assisted graph processing systems focus on synchronous execution, which imposes barriers between consecutive iterations. Synchronous execution transfers bulk data among nodes and thus only needs a small number of network transfers. However, synchronous execution is usually less efficient than asynchronous execution because of bulk synchronization. Asynchronous execution accelerates graph processing by eliminating barriers, which in turn requires to transfer a large amount of small size data. In this paper, we propose RGraph, an RDMA‐assisted asynchronous distributed graph processing system. RGraph distributes edges into two parts to isolate master and mirror vertices. RGraph exploits the asymmetry of RDMA to accelerate the one‐to‐many communication between master and mirror vertices. We implement RGraph on top of PowerGraph and conduct comprehensive experiments with large‐scale real graphs to evaluate its performance. Results show that compared to existing designs, RGraph reduces the execution time by up to 81%.

How to reduce the costly cross-rack data transferring is challenging in improving the performance of MapReduce platforms. Previous schemes mainly exploit the data locality in the Map phase to reduce the cross-rack communications. However, the Map locality based schemes may lead to highly skewed distribution of Map tasks across racks in the platform, resulting in serious load imbalance among different cross-rack links during Shuffling. Recent research results show that the slow Shuffling is the root cause of the MapReduce performance degradation. Very limited work has been done for speeding up the Shuffle phase. A notable scheme leverages the principle of the power of choice to balance the network loads on different cross-rack links during Shuffling for a specific type of sampling applications, where processing a random subset of the large-scale data collection is sufficient to derive the final result. The scheme launches a few additional tasks to offer more choices for task selection during Shuffling. However, such a scheme is designed for sampling applications and not applicable to general applications, where all the input data instead of a random subset is processed. In this work, we observe that with high Map locality, the network is mainly saturated in Shuffling but relatively free in the Map phase. A little sacrifice in Map locality may greatly accelerate Shuffling. Based on this, we propose a novel scheme called Shadow for Shuffle-constrained general applications, which strikes a trade-off between Map locality and Shuffling load balance. Specifically, Shadow iteratively chooses an original Map task from the most heavily loaded rack and creates a duplicated task for it on the most lightly loaded rack. During processing, Shadow makes a choice between an original task and its replica by efficiently pre-estimating the job execution time. We conduct extensive experiments to evaluate the Shadow design. Results show that Shadow greatly reduces the cross-rack skewness by 36.6 percent and the job execution time by 26 percent compared to existing schemes.

The emergence of big data applications makes efficient representation for large-scale dynamic data sets a challenge. The state-of-the-art design, i.e., the dynamic cuckoo filter (DCF), provides extensible approximate set representation by employing a novel chain based data structure which allows appending new building cuckoo filter blocks. However, such a design needs linearly increasing computation costs and memory space when a set scales. This makes it inefficient for big data sets. In this paper, we propose a novel data structure for dynamic big data sets, called logarithmic dynamic cuckoo filter (LDCF). LDCF uses a novel multi-level tree structure and reduces the worst insertion and membership testing times from O(N) to O(1), where N is the size of the set. At the same time, LDCF reduces the memory cost of DCF as the cardinality of the set increases. Comprehensive experiment results show that LDCF significantly reduces the membership checking time and the memory space cost for large-scale datasets compared to state-of-the-art designs.

Complete Event Trend (CET) detection over large-scale event streams is important and challenging in various applications such as financial services, real-time business analysis, and supply chain management. A potential large number of partial intermediate results during complex event matching can raise prohibitively high memory cost for the processing system. The state-of-the-art scheme leverages compact graph encoding, which represents the common sub-sequences of different complex events using a common sub-graph to achieve space efficiency for storing the intermediate results. However, we show that such a design raises unacceptable computation cost for the graph traversal needed whenever a new event comes. To address this problem, in this paper, we propose a novel attribute-based indexing (ABI) graph model to represent the relationship between events. By classifying the predicates and constructing the graph based on both the comparators in the predicates and the attribute values of the events, we achieve parallel event stream processing and efficient graph construction. Our design significantly reduces the total computation cost of graph construction from O(n2) to O(nlog(m)), where n is the number of events and m is the number of the attribute vertices. We further design several efficient traversal-based algorithms to extract CETs from the graph. We implement our design and conduct comprehensive experiments to evaluate the performance of this design. The results show that our design wins a couple of orders of magnitude back from state-of-the-art schemes.

Efficient job scheduling is an important and challenging issue in big data processing systems. Traditional designs commonly give priority to data locality during scheduling and follow a network-optimized principle to avoid costly data moving across the network. The emergence of the high-performance Remote Direct Memory Access (RDMA) network brings new opportunities for big data processing systems. However, the existing RDMA-assisted designs ignore the dependency among stages during scheduling and this can result in unsatisfied system efficiency. In this work, we propose Argus, a novel RDMA-assisted job scheduler which achieves high resource utilization by fully exploiting the structure feature of stage dependency. Argus prioritizes the stages whose completion can enable more schedulable stages. We implement Argus on top of RDMA-Spark, and conduct comprehensive experiments to evaluate the performance using large-scale traces collected from real-world systems. Results show that compared to state-of-the-art designs, Argus reduces the job completion time and makespan by 38% and 31%, respectively.

With the emergence of big data applications, stream join systems are widely used in extracting valuable information among multi-source streams. However, providing completeness of processing results in a large-scale distributed stream join system is challenging because it is hard to guarantee the consistency among all instances. We show through experiments that the abnormal result can make the quality of achieved data unacceptable in practice.In this paper, we propose Eunomia, a novel distributed stream join system which leverages an ordered propagation model for efficiently eliminating abnormal results. We design a light-weighted self-adaptive strategy to adjust the structure in the model according to the dynamic stream input rates and workloads. It can improve the scalability and performance significantly. We implement Eunomia and conduct comprehensive experiments to evaluate its performance. The results show that Eunomia eliminates abnormal results to guarantee the completeness, improves the system throughput by 25% and reduces the processing latency by 74% compared to state-of-the-art designs.

Summary Distributed Stream Processing Systems (DSPS) are very popular to process unbounded data streams in real‐time. Low processing latency is a fundamental requirement for DSPS applications to maintain the real‐time response. This requirement of low processing latency for DSPS is badly affected due to inevitable failures in computing systems. Generally, DSPS grapple with these inevitable failures by triggering periodic checkpoints. The periodic checkpoints pessimistically persist the application state so that the execution may be resumed after the failure. These periodic checkpoints incur high overheads due to the high frequency of checkpoints triggering, which increases the overall execution time. On the other hand, failure occurrences in real‐world systems are not periodic. This sharp contrast between the periodic checkpoints and failure distributions in the real‐world systems makes the periodic checkpoints inefficient. We propose a failure‐aware adaptive fault tolerance model called FATM which triggers the checkpoints inline with the underlying failure rate. Further, we design a model for utility factor and checkpoint overheads to evaluate the performance of fault tolerance models for DSPS. We implement the FATM atop Apache Flink and perform a series of experiments. To validate the effectiveness of FATM, experiment results are compared with the existing checkpoint‐based models of DSPS. The results show that the FATM significantly reduces the checkpoint frequency, increases the utility factor, and reduces the checkpoint overheads by 28%.

Summary Load balancing among the processing elements (PEs) of distributed stream processing system (DSPS) is a key issue in the presence of data skewness. Existing data partitioning schemes for DSPS suffer from the scalability problem and system in‐efficiency. Non‐key based partitioning strategies raise prohibitively high memory overhead for the stateful operations with a large number of keys and high data parallelism, while the key‐based schemes introduce load imbalance for highly skewed data. Predicting the nature of stream data in advance can help to reduce the load imbalance among the PEs of DSPS. For this purpose, the heavy hitter algorithms approximate the hot items of streaming data. However, existing designs suffer from unsatisfied prediction accuracy. In this work, we propose an efficient algorithm to filter hot items in a stream of incoming data. The proposed scheme dynamically monitors the items of a stream and greatly improves the accuracy of estimation by keeping the actual key‐value pair for the frequent items. On one hand, to ensure better load balancing for the skewed data streams, the detected hot keys are directed to more than two PEs randomly from the limited workers. On the other hand, for less frequent keys, the proposed scheme explores the principle of the power of two choices to distribute load. We conduct extensive experiments on both real‐world and synthetic data sets. The results show that the proposed pre‐filtering approach significantly outperforms existing designs in terms of prediction accuracy. The results also show that our design achieves a more balanced load as compared to the existing designs.

Real-world stream data with skewed distributions raises unique challenges to distributed stream processing systems. Existing stream workload partitioning schemes usually use a “one size fits all” design, which leverages either a shuffle grouping or a key grouping strategy for partitioning the stream workloads among multiple processing units, leading to notable problems of unsatisfied system throughput and processing latency. In this article, we show that the key grouping based schemes result in serious load imbalance and low computation efficiency in the presence of data skewness while the shuffle grouping schemes are not scalable in terms of memory space. We argue that the key to efficient stream scheduling is the popularity of the stream data. We propose PStream, a popularity-aware differentiated distributed stream processing system which assigns the hot keys using shuffle grouping while assigns rare ones using key grouping. PStream leverages a novel light-weighted probabilistic counting scheme for identifying the currently hot keys in dynamic real-time streams. The scheme is extremely efficient in computation and memory consumption, so that the predictor based on it can be well integrated into processing instances in the system. We further design an adaptive threshold configuration scheme, which can quickly adapt to the dynamical popularity changes in highly dynamical real-time streams. We implement PStream on top of Apache Storm and conduct comprehensive experiments using large-scale traces from real-world systems to evaluate the performance of this design. Results show that PStream achieves a 2.3× improvement in terms of processing throughput and reduces the processing latency by 64 percent compared to state-of-the-art designs.

Multi-version graph processing has recently attracted much research efforts. Existing multi-version graph storage designs use either copy-based schemes or delta-based schemes. A copy-based scheme stores every version separately and may lead to expensive space cost due to high storage redundancy. On the contrary, a delta based scheme only stores incremental deltas between different versions and relies on delta computation for version switching. In this work, we observe: 1) high degree vertices incur much more significant storage overheads during graph version evolving compared to low degree vertices; 2) the skewed access frequency among graph versions greatly influences the system performance for version reproducing. Based on the observations, we propose Pensieve, a skewness-aware multi-version graph processing system. Two factors contribute to the efficiency of Pensieve. First, Pensieve leverages a differentiated graph storage strategy that stores low degree vertices using copy-based scheme while stores high degree ones using delta-based scheme. Such a design achieves a good trade-off between storage cost and version switching time for multi-version graph processing. Second, the Pensieve graph storage exploits the time locality of graph version access and designs a novel last-root version switching scheme, which significantly improves the access efficiency for recent versions. We implement Pensieve on top of Ligra, and conduct comprehensive experiments to evaluate the performance of this design using large-scale datasets collected from real world systems. The results show that Pensieve substantially outperforms state-of-the-art designs in terms of memory consumption and version switching time.

Efficient event stream dissemination is a challenging problem in large-scale Online Social Network (OSN) systems due to the costly inter-server communications caused by the per-user view data storage. To solve the problem, previous schemes mainly explore the structures of social graphs to reduce the inter-server traffic. Based on the observation of high cluster coefficients in OSNs, a state-of-the-art social piggyback scheme can save redundant messages by exploiting an intrinsic hub-structure in an OSN graph for message piggybacking. Essentially, finding the best hub-structure for piggybacking is equivalent to finding a variation of the densest sub-graph. The existing scheme computes the best hub-structure by iteratively removing the node with the minimum weighted degree. Such a scheme incurs a worst computation cost of O(n2), making it not scalable to large-scale OSN graphs. Using alternative hubstructure instead of the best hub-structure can speed up the piggyback assignment. However, they greatly sacrifice the communication efficiency of the assignment schedule. Different from the existing designs, in this work, we propose a QuickPoint algorithm, which removes a fraction of nodes in each iteration in finding the best hub-structure. We mathematically prove that QuickPoint converges in O(logαn)(α > 1) iterations in finding the best hub-structure for efficient piggyback. We implement QuickPoint in parallel atop Pregel, a vertex-centric distributed graph processing platform. Comprehensive experiments using large-scale data from Twitter and Flickr show that our scheme is 38.8× more efficient compared to existing schemes.

Blockchain technology offers an intelligent amalgamation of distributed ledger, Peer-to-Peer (P2P), cryptography, and smart contracts to enable trustworthy applications without any third parties. Existing blockchain systems have successfully either resolved the scalability issue by advancing the distributed consensus protocols from the control plane, or complemented the security issue by updating the block structure and encryption algorithms from the data plane. Yet, we argue that the underlying P2P network plane remains as an important but unaddressed barrier for accelerating the overall blockchain system performance, which can be discussed from how fast and reliable the network is. In order to improve the blockchain network performance about enabling fast and reliable broadcast, we establish a trust-enhanced blockchain P2P topology which takes transmission rate and transmission reliability into consideration. Transmission rate reflects blockchain network speed to disseminate transactions and blocks, and transmission reliability reveals whether transmission rate changes drastically on unreliable network connection. This paper presents BlockP2P-EP, a novel trust-enhanced blockchain topology to accelerate transmission rate and meanwhile retain transmission reliability. BlockP2P-EP first operates the geographical proximity sensing clustering, which leverages K-Means algorithm for gathering proximity peer nodes into clusters. It follows by the hierarchical topological structure that ensures strong connectivity and small diameter based on node attribute classification. Then we propose establishing trust-enhanced network topology. On top of the trust-enhanced blockchain topology, BlockP2P-EP conducts the parallel spanning tree broadcast algorithm to enable fast data broadcast among nodes both intra- and inter- clusters. Finally, we adopt an effective node inactivation detection method to reduce network load. To verify the validity of BlockP2P-EP protocol, we carefully design and implement a blockchain network simulator. Evaluation results show that BlockP2P-EP can exhibit promising network performance in terms of transmission rate and transmission reliability compared to Bitcoin and Ethereum.

This article studies the core maintenance problem for dynamic graphs which requires to update each vertex's core number with the insertion/deletion of vertices/edges. Previous algorithms can either process one edge associated with a vertex in each iteration or can only process one superior edge associated with the vertex (an edge 〈u; v〉 is a superior edge of vertex u if v' core number is no less than u's core number) in each iteration. Thus for high superior-degree vertices (the vertices associated with many superior edges) insertions/deletions, previous algorithms become very inefficient. In this article, we discovered a new structure called joint edge set whose insertions/deletions make each vertex's core number change at most one. The joint edge set mainly contains all the superior edges associated with the high superior-degree vertices as long as these vertices are 3+-hop independent. Based on this discovery, faster parallel algorithms are devised to solve the core maintenance problems. In our algorithms, we can process all edges in the joint edge set in one iteration and thus can greatly increase the parallelism and reduce the processing time. The results of extensive experiments conducted on various types of real-world, temporal, and synthetic graphs illustrate that the proposed algorithms achieve good efficiency, stability and scalability. Specifically, the new algorithms can outperform the single-edge processing algorithms by up to four orders of magnitude. Compared with the matching based algorithm and the superior edge based algorithm, our algorithms show a significant speedup up to 60× in the processing time.

Cloud computing provides utility-based and scalable services to end-users. In the past decade, the demands for resource management in cloud computing have increased substantially which lead to certain challenges such as optimal resource utilization, power consumption, and service level agreement violations. Workload performance prediction serves as an assistance to address these issues. In this paper, we propose a prediction model based on clustered Case-Based Reasoning (CBR). The proposed model determines the performance metrics for workload prior to the co-operation of autonomic computing characteristics. Thus, CBR provides optimal scheduling of resources and workload monitoring for cloud data centers. In order to validate the proposed CBR-based prediction model, we perform a series of experiments and evaluate the effectiveness in terms of precision, recall, f-measure, and mean square error rate. We generate the cases for CBR using traces from the Google cluster data center. Moreover, we also validate our proposed prediction model against Support Vector Machine (SVM) prediction scheme. Experimental results show that the proposed CBR outperforms the SVM-based approach and yields 10% improvement in terms of precision.

Big data applications play a significant role in diverse fields. Distributed Stream Processing Engines (DSPEs) are widely used to support real time applications efficiently. Partitioning algorithms are used to partition data streams into multiple nodes to process in parallel to gain efficient performance. Aggregation cost is an important factor when process stateful streaming applications using such partitioning algorithms because it plays an important role on performance when final result is being produced in stateful streaming applications. However, impact of aggregation cost in stream processing is not discussed comprehensively in existing literature. We use performance modeling to identify the importance of aggregation cost when workload is high. We implement performance model on a multi-node cluster to predict the same behavior as on single resource performance model. We demonstrate that stateful streaming applications need more resources as compare to stateless applications when workload is high and both stateful and stateless applications are running in the same DSPE. Experiments results show that a stateful streaming application needs more resources compared to a stateless streaming application when both applications are running on the same DSPE when the workload is high. Further experiment results show that the performance modeling may be helpful to predict maximum workload that can be process on a DSPE and increase in parallelism level is not guaranteed to increase the performance of streaming applications.

Efficient set representation and membership testing are important in various big data applications. The state-of-the-art Cuckoo filter design shows great advantages in both query efficiency and the support of item deletion, compared to previous Bloom filter and its variants. However, in this work, we show mathematically and experimentally that Cuckoo filter may suffer serious performance degradation during element insertion because of its random choice strategy for inserting an element into the candidate buckets. Such a random choice strategy incurs load imbalance among different buckets in Cuckoo filter and can lead to frequent relocations and the consequent long time for inserting an item. To solve this problem, we propose a novel design which leverages the principle of the power of two choices to select the better candidate bucket during inserting an element. Our design balances the load distribution among buckets in Cuckoo filter and avoids a large amount of relocations during insertion. We implement our design and apply it in real-world applications. We conduct comprehensive experiments using large-scale data sets collected from real world systems to evaluate the performance of this design. The results show that our design significantly reduces the average number of relocations of Cuckoo filter by 35%, as well as reducing item inserting latency by 25%.

Many BigData applications require to perform quick join operations on different large-scale real-time data streams. The key challenge to design an efficient stream join system is how to reasonably partition the streaming data among distributed processing nodes to avoid high density of join computation. However, the skewed distribution of real world streams raises great challenges for streaming data partitioning in distributed stream join systems. Existing hash based partitioning schemes incur significant load imbalance which leads to low system throughput and long processing latency, while shuffling based strategies incur redundant join computation and much more communication. To address this issue, in this paper, we propose and implement a scalable distributed stream join system, Simois, which shuffles the potential top heavy-load keys while hashing the others. However, how to identify the keys which lead to the heavy workload imbalance is challenging, because the heavy workload is determined by the current joint status of two streams, and the distribution of the two streams may change with time. To solve this problem, we design a novel efficient exponential counting scheme for identifying the keys with the heaviest workload in the two dynamic streams. The proposed exponential counting scheme needs extremely low computation and space cost, so that it can be well implemented in a stream processing system. Moreover, we design a popularity decline algorithm to make our design adaptive to the highly dynamic changes of streams. We implement Simois on top of Apache Storm and conduct comprehensive experiments using large-scale real world traces. Experiment results show that Simois improves the system throughput significantly by 52% and reduces the average latency by 37%, compared to existing state-of-the-art designs.

In the bigdata era, many applications are required to perform quick and accurate join operations on large-scale realtime data streams, such as stock trading and online advertisement analysis. To achieve high throughput and low latency, distributed stream join systems explore efficient stream partitioning strategies to execute the complex stream join procedure in parallel. Existing systems mainly deploy two kinds of partitioning strategies, i.e., random partitioning and hash partitioning. Random partitioning strategy partitions one data stream uniformly while broadcasting all the tuples of the other data stream. This simple strategy may incur lots of unnecessary computations for low-selectivity stream join. Hash partitioning strategy maps all the tuples of the two data streams according to their attributes for joining. However, hash partitioning strategy suffers from a serious load imbalance problem caused by the skew distribution of the attributes, which is common in real-world data. The skewed load may seriously affect the system performance. In this paper, we carefully model the load skewness problem in distributed join systems. We explore the key tuples which lead to the heavy load skewness, and propose an efficient key selection algorithm, GreedyFit to find out these key tuples. We design a lightweight tuple migration strategy to solve the load imbalance problem in real-time and implement a new distributed stream join system, FastJoin. Experimental results using real-world data show that FastJoin can significantly improve the system performance in terms of throughput and latency compared to the state-of-the-art stream join systems.

Event stream dissemination dominates the workloads in large-scale Online Social Network (OSN) systems. Based on the de facto per-user view data storage, event stream dissemination raises a large amount of inter-server traffic due to the complex interconnection among OSN users. The state-of-the-art schemes mainly explore the structure features of social graphs to reduce the inter-server communications for event stream dissemination. Different sub-graph structures are exploited for achieving approximated optimal solutions. However, such schemes incur prohibitively high cost of either computation or communication. In this work, we follow a different design philosophy by using a game theoretic approach, which decomposes the highly complex graph computation problem into rational decision making of every individual social link. Specifically, we propose a novel social piggyback game to achieve a more efficient solution. We mathematically prove the existence of the Nash Equilibrium of the social piggyback game. Moreover, we propose an efficient best response dynamic algorithm to achieve the Nash Equilibrium, which quickly converges in a small number of iterations for large-scale OSNs. We further show that the communication cost of this design achieves a 1.5-approximation of the theoretical social optimum. We conduct comprehensive experiments using large-scale real-world traces from popular OSN systems as well as implement a prototype system to evaluate the performance of this design. Results show that the social piggyback game achieves a significant 302× improvement in system efficiency compared to existing schemes.

In large-scale Online Social Network (OSN) systems, event stream dissemination incurs costly inter-server communication due to the per-user view data storage. To solve the problem, existing schemes commonly leverage the social graph structures to save redundant inter- server traffics across social links. The state-of-the- art social piggyback scheme reduces the inter-server traffics by fully exploiting the proposed hub- structure, based on the observation of high cluster coefficient in OSNs. In order to find the best hub- structure, however, such a scheme needs to identify the global densest sub-graph by iteratively removing the node with the minimum weighted degree. Such a process causes a worst computation cost of O(n2), making the social piggyback scheme unscalable for real-world large-scale OSN graphs. In this work, we propose a novel scheme by exploiting the social community for event stream dissemination. We first detect the social communities in a social graph by using an efficient community detection algorithm based on distance dynamics. For each community, we then design a heuristics algorithm to fully leverage the hub- structure. The heuristics algorithm explores the hub- structure center on the node with maximum degree in each iteration. We collect large-scale datasets from DBLP and Facebook and conduct comprehensive experiments to evaluate our design. The results show that our design significantly reduces the communication overhead and computing time by 40.71% and 81.21% compared to existing schemes, respectively.

Distributed Stream Processing Systems (DSPSs) have been widely deployed to process infinite data streams. Short processing latency and short recovery time are both vital for many DSPS applications. Existing DSPS designs commonly leverage elaborated task allocation strategies to achieve short processing latency. Such designs, however, ignore the requirement of system fault tolerance. Indeed, providing fault tolerant capability in a DSPS can cause significant degradation of system performance. Especially, the intrinsic dependency between upstream and down-stream tasks can incur cascaded waiting during recovery, leading to prohibitively long recovery time. In this paper, we propose Ares, a high performance and fault tolerant DSPS. Ares considers both system performance and fault tolerant capability during task allocation. In the design of Ares, we formalize the problem of Fault Tolerant Scheduler (FTS) for finding an optimal task allocation which maximizes the system utility. We use a game-theoretic approach to solve the FTS problem and propose a novel Nirvana algorithm based on best-response dynamics. We mathematically prove the existence of Nash equilibrium in the FTS game. We implement Ares atop Apache Storm and conduct comprehensive experiments to evaluate this design. The results show that, compared to existing designs Ares achieves a 3.6× improvement of throughput, as well as reducing the processing latency and the recovery time by 50.2% and 52.5%, respectively.

Different from traditional web searching, the relevant information for a social network system (SNS) is commonly the content from his/her friends. Such a difference makes content indexing extremely difficult for an online social network (OSN) search system because every user has an individual view during searching. Building such a per-user view index over existing SNS Key-Value stores raises a large amount of communication cost due to the complex interconnections among OSN users, making the search system unscalable. To address the problem, we propose a novel protocol called summary index to support keyword searching. In the protocol, each user keeps a directory of the succinct summaries of his/her neighbors, and checks these summaries for potential hits before sending any queries. Two factors contribute to the low overhead of our design: the summary index representations are memory efficient, and the summary dissemination for index updating is communication efficient. First, we design an incremental scalable Bloom filter for summarizing the content constantly generated by a neighbor of a user. For an issued query by a user, the search system first checks against the summary index for a user's neighbor to predict the neighbors likely having desired content. Thus, the search system saves a significant inter-server communication cost by avoiding exhaustively transmitting the query to all the neighbors. Second, to further reduce the overhead for maintaining the social index, we leverage the piggyback strategy which exploits the links with high social strengths to avoid redundant messages during updating the per-user view summary index. We conduct comprehensive simulations using traces from real world systems to evaluate this design. Results show that our scheme significantly outperforms existing schemes for OSN searching in terms of inter-sever traffic by 98 percent.

The emergence of large-scale dynamic sets in real applications creates stringent requirements for approximate set representation structures: 1) the capacity of the set representation structures should support flexibly extending or reducing to cope with dynamically changing of set size; 2) the set representation structures should support reliable delete operation. Existing techniques for approximate set representation, e.g., the cuckoo filter, the Bloom filter and its variants cannot meet both the requirements of a dynamic set. To solve the problem, in this paper we propose the dynamic cuckoo filter (DCF) to support reliable delete operation and elastic capacity for dynamic set representation and membership testing. Two factors contribute to the efficiency of the DCF design. First, the data structure of a DCF is extendable, making the representation of a dynamic set space efficient. Second, a DCF utilizes a monopolistic fingerprint for representing an item and guarantees reliable delete operation. Experiment results show that compared to the existing state-of-the-art designs, DCF achieves 75% reduction in memory cost, 50% improvement in construction speed, and 80% improvement in speed of membership query. We implement a prototype file backup system and use DCF for data deduplication. Comprehensive experiment results demonstrate the efficiency of our DCF design compared to existing schemes.

Real-world stream data with skewed distribution raises unique challenges to distributed stream processing systems. Existing stream workload partitioning schemes usually use a “one size fits all” design, which leverage either a shuffle grouping or a key grouping strategy for partitioning the stream workloads among multiple processing units, leading to notable problems of unsatisfied system throughput and processing latency. In this paper, we show that the key grouping based schemes result in serious load imbalance and low computation efficiency in the presence of data skewness while the shuffle grouping schemes are not scalable in terms of memory space. We argue that the key to efficient stream scheduling is the popularity of the stream data. We propose and implement a differentiated distributed stream processing system, call DStream, which assigns the popular keys using shuffle grouping while assigns unpopular ones using key grouping. We design a novel efficient and light-weighted probabilistic counting scheme for identifying the current hot keys in dynamic real-time streams. Two factors contribute to the power of this design: 1) the probabilistic counting scheme is extremely computation and memory efficient, so that it can be well integrated in processing instances in the system; 2) the scheme can adapt to the popularity changes in the dynamic stream processing environment. We implement the DStream system on top of Apache Storm. Experiment results using large-scale traces from real-world systems show that DStream achieves a 2.3× improvement in terms of processing throughput and reduces the processing latency by 64% compared to state-of-the-art designs.

Being a core-enabling technology for next generation communication infrastructure, Wireless Sensor Networks (WSNs) are under heavy research curiosity since last couple of decades. Data collection and transmission are one of the fundamental operations in WSNs. Performance of data collection directly affects the efficiency and lifetime of WSNs. The comprehensive background knowledge of data collection schemes is essential for identification of possible future directions in the domain. In this paper, we provide a review of modern data collection schemes, organize them into appropriate classes and setup their taxonomy. We explore the performance of various data collection schemes and conduct comprehensive comparative analysis. Subsequently, we identify corresponding issues and challenges for further optimization of operating environments for WSNs.

How to reduce the costly cross-rack data transferring is challenging in improving the performance of MapReduce platforms. Previous schemes mainly exploit the data locality in the Map phase to reduce the cross-rack communications. However, the Map locality based schemes may lead to highly skewed distribution of Map tasks across racks in the platform, resulting in serious load imbalance among different cross-rack links during Shuffling. Recent research results show that the slow Shuffling is the root cause of the MapReduce performance degradation. Very limited work has been done for speeding up the Shuffle phase. A notable scheme leverages the principle of the power of choice to balance the network loads on different cross-rack links during Shuffling for a specific type of sampling applications, where processing a random subset of the large-scale data collection is sufficient to derive the final result. The scheme launches a few additional tasks to offer more choices for task selection during Shuffling. However, such a scheme is designed for sampling applications and not applicable to general applications, where all the input data instead of a random subset is processed. In this work, we observe that with high Map locality, the network is mainly saturated in Shuffling but relatively free in the Map phase. A little sacrifice in Map locality may greatly accelerate Shuffling. Based on this, we propose a novel scheme called Shadow for Shuffle-constrained general applications, which strikes a trade-off between Map locality and Shuffling load balance. Specifically, Shadow iteratively chooses an original Map task from the most heavily loaded rack and creates a duplicated task for it on the most lightly loaded rack. During processing, Shadow makes a choice between an original task and its replica by efficiently pre-estimating the job execution time. We conduct extensive experiments to evaluate our Shadow design. Results show that Shadow greatly reduces the cross-rack skewness by 30.7% and the job execution time by 27.9% compared to existing schemes.

Retrieving relevant data for users in online social network (OSN) systems is a challenging problem. Cassandra, a storage system used by popular OSN systems, such as Facebook and Twitter, relies on a DHT-based scheme to randomly partition the personal data of users among servers across multiple data centers. Although DHT is highly scalable for hosting a large number of users (personal data), it leads to costly inter-server communications across data centers due to the complex interconnection and interaction among OSN users. In this paper, we explore how to retrieve the OSN content in a cost-effective way by retaining the simple and robust nature of OSNs. Our approach exploits a simple, yet powerful principle called Community-Based Locality (CBL), which posits that if a user has a one-hop neighbor within a particular community, it is very likely that the user has other one-hop neighbors inside the same community. We demonstrate the existence of community-based locality in diverse traces of popular OSN systems such as Facebook, Orkut, Flickr, Youtube, and Livejournal. Based on the observation, we design a CBL-based algorithm to build the content index in OSN systems. By partitioning and indexing the relevant data of users within a community on the same server in the data center, the CBL-based index avoids a significant amount of inter-server communications during searching, making retrieving relevant data for a user in large-scale OSNs efficient. In addition, by using CBL-based scheme we can provide much faster search response and balanced loads. We conduct comprehensive trace-driven simulations to evaluate the performance of the proposed scheme. Results show that ourscheme significantly reduces the network traffic by 73 percent while reduces the query latency by 35 percent compared with existing schemes.

Event stream dissemination dominates the workloads in large-scale Online Social Network (OSN) systems. Based on the de facto per-user view data storage, event stream dissemination raises a large amount of inter-server traffics due to the complex interconnection among OSN users. The state-of-the-art schemes mainly explore the structure features of social graphs to reduce the inter-server messages for event stream dissemination. Different sub-graph structures are exploited for achieving the approximated optimal assignment. However, such schemes incur high costs of computation or communication. In this work, we follow a different design philosophy by using a game theoretic approach, which decomposes the high complex graph computation problem into individuals' rational strategy selection of each node. Specifically, we propose a novel social piggyback game to achieve a more efficient solution. We mathematically prove the existing of the Nash Equilibrium of the social piggyback game. Moreover, we propose an efficient best response dynamic algorithm to achieve the Nash Equilibrium, which quickly converges in a small number of iterations for large-scale OSNs. We further show that the communication cost of this design achieves a 1.5-approximation of the theoretical social optimal. We conduct comprehensive experiments to evaluate the performance of this design using large-scale real-world traces from popular OSN systems. Results show that the social piggyback game achieves a significant 302× improvement in system efficiency compared to existing schemes.

Efficient event stream dissemination is a challenging problem in large-scale Online Social Network (OSN) systems due to the costly inter-server communications caused by the per-user view data storage. To solve the problem, previous schemes mainly explore the structure of the social graphs to reduce the inter-server traffics. Based on the observation of high cluster coefficient in OSNs, a state-of-the-art social piggyback scheme proves to be effective in saving redundant messages by exploiting an intrinsic hub structure in an OSN graph. Essentially, finding the best hub structure for piggybacking is equivalent to finding a variation of the densest sub-graph. The existing scheme computes the densest sub-graph by iteratively removing the node with the minimum weighted degree. Such a scheme incurs a worst computation cost of O(n2), making it not scalable to large-scale OSN graphs. Using alternative hub structures instead of the densest sub-graph can speed up the piggybacking assignment. They however greatly sacrifice the communication efficiency of the assignment schedule. Different from the existing designs, in this work, we propose the QuickPoint algorithm, which achieves the removal of a fraction of nodes in each iteration in finding the densest sub-graph. We mathematically prove that QuickPoint converges in O(logan)(a > 1) iterations in finding the densest sub-graph for efficient piggyback. We implement QuickPoint in parallel using Pregel, a vertex-centric distributed graph processing platform. Comprehensive experiments using large-scale data from Twitter and Flickr show that our scheme achieves a 38.8× improvement in efficiency compared to the existing schemes.

Audio represents one of the most appealing yet least exploited modalities in wireless sensor networks, due to the potentially extremely large data volumes and limited wireless capacity. Therefore, how to effectively collect audio sensing information remains a challenging problem. In this paper, we propose a new paradigm of audio information collection based on the concept of audio-on-demand. We consider a sink-free environment targeting for disaster management, where audio chunks are stored inside the network for retrieval. The difficulty is to guarantee a high search success rate without infrastructure support. To solve the problem, we design a novel replication algorithm that deploys an optimal number of$O(\sqrt{n})$replicas across the sensor network. We prove the optimality of the energy consumption of the algorithm. We implement a sink-free audio-on-demand (SAoD) WSN system, and conduct extensive simulations to evaluate the performance and efficiency of our design. The experimental results show that our design can provide satisfactory quality of audio-on-demand service with short startup latency and slight playback jitter. Extensive simulation results show that this design achieves a search success rate of 98 percent while reducing the search energy consumption by an order of magnitude compared with existing schemes.

Efficiently operating on relevant data for users in large-scale online social network (OSN) systems is a challenging problem. Storage systems used by popular OSNs often rely on key-value stores, where randomly partitioning the data of users among servers across the data centers is the defacto standard. Although by using DHTs, the random partition scheme is highly scalable for hosting a large number of users, it leads to costly inter-server communications across data centers due to the complexity of interconnection and interaction between OSN users. In this paper, we explore how to reduce the inter-server communications by retaining the simple and robust nature of OSNs. We propose a data placement solution atop OSN systems to divide users among servers according to the interaction-locality-based structure. Our approach exploits a simple, yet powerful principle of OSN interactions, self-similarity, which reveals that the inter-server communication cost is minimized under such intrinsic structure. Our algorithm avoids a significant amount of inter-server traffic as well as achieves load balance among servers across the data centers. We demonstrate the existence of self-similarity in large-scale Facebook traces including 10 million Facebook users and 24 million interaction events. We conduct comprehensive trace-driven simulations to evaluate this design. Results show that our scheme significantly reduces the traffic and latency of OSN systems comparing to existing schemes.

With the increasing popularity of location-based social networks, a large number of users have been involved in the check-ins. The venues where the user frequently repeats check-ins tend to play a very important role in his daily life, as they not only dominate the user's mobility behavior but also imply the user's personal preferences. Therefore, fast discerning of such check-in venues could enable us to improve a wide range of location-based services. In this paper, we propose a new location classification problem for users of location-based social networks, in which we aim to discern, given the observation that a user makes a "new" check-in at a venue, whether he will frequently repeat check-ins at this venue. To solve the problem, we first extract 16 features attached to the user's "new" check-ins. With the publicly available check-in dataset, we then train a location classifier based on Support Vector Machine and compare it with two baselines based on majority voting. The comparison results demonstrate the practicability of the trained location classifier.

Retrieving relevant data for users in online social network (OSN) systems is a challenging problem. Cassandra, a storage system used by popular OSN systems, such as Facebook and Twitter, relies on a DHT-based scheme to randomly partition the personal data of users among servers across multiple data centers. Although DHT is highly scalable for hosting a large number of users (personal data), it leads to costly inter-server communications across data centers due to the complex interconnection and interaction among OSN users. In this paper, we explore how to retrieve the OSN content in a cost-effective way by retaining the simple and robust nature of OSNs. Our approach exploits a simple, yet powerful principle called Community-Based Locality (CBL), which posits that if a user has an one-hop neighbor within a particular community, it is very likely that the user has other one-hop neighbors inside the same community. We demonstrate the existence of community-based locality in diverse traces of popular OSN systems such as Facebook, Orkut, Flickr, Youtube, and Livejournal.

With the recent findings of excellent emission and absorption characteristics in carbon nanotubes (CNTs), new CMP prototypes with on-chip antennas are now available.Wireless NoC becomes a promising technique among all the CMP interconnection alternatives. By using a recursively defined structure, the two-tier hybrid wireless/wired WCube [1] on-chip interconnecting network scales exponentially with the logical connection degree of a wireless router. WCube uses dimension-ordered strategy to avoid deadlock in wormhole routing. It however suffers unreachable problem in a partial structure, i.e., if the original recursive topology is not strictly maintained, the dimension-ordered routing algorithm does not work due to the missing paths. To address the problem in a partial WCube, we design an algorithm (called APW) which prohibits turns adaptively according to the structure of an irregular WCube.We proved that the proposed turns policy of APW guarantees the reachability of any partial WCube structures as well as keeping the wormhole routing deadlock-free. We further adapt the APW algorithm to achieve the DAPW algorithm to alleviate the uneven traffic in some cases, which prohibited turns in the different positions of each abstract cycle. We conduct comprehensive simulations using GEM5 to evaluate this design. The results show that our APW and DAPW successfully solve the unreachable problem in a partial WCube and significantly outperforms the partial WCube in terms of latency, throughout and power consumption.

Efficiently operating on relevant data for users in large-scale online social network (OSN) systems is a challenging problem. Storage systems used by popular OSN systems often rely on key-value stores, where randomly partitioning the data of users among servers across the data centers is the defacto standard. Although by using DHTs, the random partition scheme is highly scalable for hosting a large number of users, it leads to costly inter-server communications across data centers due to the complexity of interconnection and interaction between OSN users. In this paper, we explore how to reduce the inter-server communications by retaining the simple and robust nature of OSNs. We propose a data placement solution atop OSN systems to divide users among servers according to the interaction-locality-based structure. Our approach exploits a simple, yet powerful principle of OSN interactions, self-similarity, which reveals that the inter-server communication cost is minimized under such intrinsic structure. Our algorithm avoids a significant amount of inter-server traffic as well as achieves load balance among servers across the data centers. We demonstrate the existence of self-similarity in large-scale Facebook traces including 10 million Facebook users and 24 million interaction events. We conduct comprehensive trace-driven simulations to evaluate this design exploiting the unique feature of self-similarity. Results show that our scheme significantly reduces the traffic and latency of the existing schemes.

Audio represents one of the most appealing yet least exploited modalities in wireless sensor networks, due to the potentially extremely large data volumes and limited wireless capacity. Therefore, how to effectively collect audio sensing information remains a challenging problem. In this paper, we propose a new paradigm of audio information collection based on the concept of audio-on-demand. We consider a sink-free environment targeting for disaster management, where audio chunks are stored inside the network for retrieval. The difficulty is to guarantee a high search success rate without infrastructure support. To solve the problem, we design a novel replication algorithm that deploys an optimal number of O(√n) replicas across the sensor network. We prove the optimality of the energy consumption of the algorithm, and use real testbed experiments and extensive simulations to evaluate the performance and efficiency of our design. The experimental results show that our design can provide satisfactory quality of audio-on-demand service with short startup latency and slight playback jitter. Extensive simulation results show that this design achieves a search success rate of 98% while reducing the search energy consumption by an order of magnitude compared with existing schemes.

Peer-to-Peer multikeyword searching requires distributed intersection/union operations across wide area networks, raising a large amount of traffic cost. Existing schemes commonly utilize Bloom Filters (BFs) encoding to effectively reduce the traffic cost during the intersection/union operations. In this paper, we address the problem of optimizing the settings of a BF. We show, through mathematical proof, that the optimal setting of BF in terms of traffic cost is determined by the statistical information of the involved inverted lists, not the minimized false positive rate as claimed by previous studies. Through numerical analysis, we demonstrate how to obtain optimal settings. To better evaluate the performance of this design, we conduct comprehensive simulations on TREC WT10G test collection and query logs of a major commercial web search engine. Results show that our design significantly reduces the search traffic and latency of the existing approaches.

Efficient and effective full-text retrieval in unstructured peer-to-peer networks remains a challenge in the research community. First, it is difficult, if not impossible, for unstructured P2P systems to effectively locate items with guaranteed recall. Second, existing schemes to improve search success rate often rely on replicating a large number of item replicas across the wide area network, incurring a large amount of communication and storage costs. In this paper, we propose BloomCast, an efficient and effective full-text retrieval scheme, in unstructured P2P networks. By leveraging a hybrid P2P protocol, BloomCast replicates the items uniformly at random across the P2P networks, achieving a guaranteed recall at a communication cost of O(√N), where N is the size of the network. Furthermore, by casting Bloom Filters instead of the raw documents across the network, BloomCast significantly reduces the communication and storage costs for replication. We demonstrate the power of BloomCast design through both mathematical proof and comprehensive simulations based on the query logs from a major commercial search engine and NIST TREC WT10G data collection. Results show that BloomCast achieves an average query recall of 91 percent, which outperforms the existing WP algorithm by 18 percent, while BloomCast greatly reduces the search latency for query processing by 57 percent.

The advances of wireless networking and sensor technology open up an interesting opportunity to infer human activities in a smart home environment. Existing work in this paradigm focuses mainly on recognizing activities of single user. In this work, we focus on the fundamental problem of recognizing activities of multiple users using a wireless body sensor network, and propose a scalable pattern mining approach to recognize both single- and multiuser activities in a unified framework. We exploit Emerging Pattern-a discriminative knowledge pattern which describes significant changes among activity classes of data-for building activity models and design a scalable, noise-resistant, Emerging Pattern-based Multiuser Activity Recognizer (epMAR) to recognize both single- and multiuser activities. We develop a multimodal, wireless body sensor network for collecting real-world traces in a smart home environment, and conduct comprehensive empirical studies to evaluate our system. Results show that epMAR outperforms existing schemes in terms of accuracy, scalability, and robustness.

We consider deterministic feasibility and time complexity of two fundamental tasks in distributed computing: consensus and mutual exclusion. Processes have different labels and communicate through a multiple access channel. The adversary wakes up some processes in possibly different rounds. In any round, every awake process either listens or transmits. The message of a process i is heard by all other awake processes, if i is the only process to transmit in a given round. If more than one process transmits simultaneously, there is a collision and no message is heard. We consider three characteristics that may or may not exist in the channel: collision detection (listening processes can distinguish collision from silence), the availability of a global clock showing the round number, and the knowledge of the number n of all processes. If none of the above three characteristics is available in the channel, we prove that consensus and mutual exclusion are infeasible; if at least one of them is available, both tasks are feasible, and we study their time complexity. Collision detection is shown to cause an exponential gap in complexity: if it is available, both tasks can be performed in time logarithmic in n, which is optimal, and without collision detection both tasks require linear time. We then investigate both consensus and mutual exclusion in the absence of collision detection, but under alternative presence of the two other features. With global clock, we give an algorithm whose time complexity linearly depends on n and on the wake-up time, and an algorithm whose complexity does not depend on the wake-up time and differs from the linear lower bound only by a factor O(\log^2 n). If n is known, we also show an algorithm whose complexity differs from the linear lower bound only by a factor O(\log^2 n).

Real-time activity recognition using body sensor networks is an important and challenging task and it has many potential applications. In this paper, we propose a real time, hierarchical model to recognize both simple gestures and complex activities using a wireless body sensor network. In this model, we first use a fast, lightweight template matching algorithm to detect gestures at the sensor node level, and then use a discriminative pattern based real-time algorithm to recognize high-level activities at the portable device level. We evaluate our algorithms over a real-world dataset. The results show that the proposed system not only achieves good performance (an average precision of 94.9%, an average recall of 82.5%, and an average real-time delay of 5.7 seconds), but also significantly reduces the network communication cost by 60.2%.

Previous multikeyword search in DHT-based P2P systems often relies on multiple single keyword search operations, suffering from unacceptable traffic cost and poor accuracy. Precomputing term-set-based index can significantly reduce the cost but needs exponentially growing index size. Based on our observations that 1) queries are typically short and 2) users usually have limited interests, we propose a novel index pruning method, called TSS. By solely publishing the most relevant term sets from documents on the peers, TSS provides comparable search performance with a centralized solution, while the index size is reduced from exponential to the scale of O(nlog(n)). We evaluate this design through comprehensive trace-driven simulations using the TREC WT10G data collection and the query log of a major commercial search engine.

Efficient and effective full-text retrieval in unstructured peer-to-peer networks remains a challenge in the research community. First, it is difficult, if not impossible, for unstructured P2P search protocols to effectively locate items with guaranteed recall rate. Second, existing schemes to improve search successful rate often rely on replicating a large number of item replicas across the wide area network, incurring a large amount of communication and storage cost. In this paper we propose BloomCast, an efficient and effective full-text retrieval scheme, in unstructured P2P networks. BloomCast is effective because it guarantees perfect recall rate with high probability. It is efficient because the overall communication cost of full-text search is reduced below a formal bound. Furthermore, by casting Bloom Filters instead of the raw documents across the network, BloomCast significantly reduces the communication cost and storage cost for replication. We demonstrate the power of BloomCast design through both mathematical proof and comprehensive simulations. Results show that BloomCast outperforms existing schemes in terms of both recall rate and communication cost.

Nowadays contents in Internet like weblogs, wikipedia and news sites become "live". How to notify and provide users with the relevant contents becomes a challenge. Unlike conventional Web search technology or the RSS feed, this paper envisions a personalized full-text content filtering and dissemination system in a highly distributed environment such as a Distributed Hash Table (DHT). Users can subscribe to their interested contents by specifying some terms and threshold values for filtering. Then, published contents will be disseminated to the associated subscribers. We propose a novel and simple framework of filter registration and content publication, STAIRS. By the new framework, we propose three algorithms (default forwarding, dynamic forwarding and adaptive forwarding) to reduce the forwarding cost and false dismissal rate; meanwhile, the subscriber can receive the desired contents with no duplicates. In particular, the adaptive forwarding utilizes the filter information to significantly reduce the forwarding cost. Experiments based on two real query logs and two real datasets show the effectiveness of our proposed framework.

The efficiency of matching structures is the key issue for content publish/subscribe systems. In this paper, we propose an efficient matching tree structure, named CobasTree, for a distributed environment. Particularly, we model a predicate in each subscription filter as an interval and published content value as a data point. The CobasTree is designed to index all subscription intervals and a matching algorithm is proposed to match the data points to these indexed intervals. Through a set of techniques including selective multicast by bounding intervals, cost model-based interval division, and CobasTree merging, CobasTree can match the published contents against subscription filters with a high efficiency. We call the whole framework including CobasTree and the associated techniques as COBAS. The performance evaluation in simulation environment and PlanetLab environment shows COBAS significantly outperforms two counterparts with low cost and fast forwarding.

By combining an unstructured protocol with a DHT-based index, hybrid Peer-to-Peer (P2P) improves search efficiency in terms of query recall and response time. The key challenge in hybrid search is to estimate the number of peers that can answer a given query. Existing approaches assume that such a number can be directly obtained by computing item popularity. In this work, we show that such an assumption is not always valid, and previous designs cannot distinguish whether items related to a query are distributed in many peers or are in a few peers. To address this issue, we propose QRank, a difficulty-aware hybrid search, which ranks queries by weighting keywords based on term frequency. Using rank values, QRank selects proper search strategies for queries. We conduct comprehensive trace-driven simulations to evaluate this design. Results show that QRank significantly improves the search quality as well as reducing system traffic cost compared with existing approaches.

Existing replication strategies in unstructured P2P networks, such as square-root principle based replication, can effectively improve search efficiency. How to get optimal replication strategy, however, is not trivial. In this paper we show, through mathematical proof, that random replication strategy achieves the optimal results. By randomly distributing rather small numbers of item and query replicas in the unstructured P2P network, we can guarantee perfect search success rate comparable to exhaustive search with high probability. Our analysis also shows that the cost for such replication strategy is determined by the network size of a P2P system. We propose a hybrid P2P architecture which combines a lightweight DHT with an unstructured P2P overlay to address the problems of network size estimating and random peer sampling. We conduct comprehensive simulation to evaluate this design. Results show that our scheme achieves perfect search success rate with quite small overhead.

Geographical hash table (GHT) has been widely used to provide energy efficiency for data-centric storage in wireless sensor networks. Such a mechanism, however, suffers from high communication cost when we apply multi-dimensional event search in the network. In this work, we present MDS, a flexible, complete, and efficient multi-dimensional search mechanism atop traditional GHT based data-centric storage architecture. MDS utilizes bloom filters to reduce the communication cost of in-network intersection and union operations for multi-dimensional queries in wireless sensor networks. This scheme can be easily extended to support multi-dimensional range queries. Our mathematical analysis indicates the optimal settings for the bloom filters that maximize the traffic savings according to the information popularities. We conduct comprehensive simulations to evaluate our design. Results show that MDS achieves significant performance improvement in terms of energy consumptions and thus improves the applicability of the multi-dimensional search over the GHT based data-centric storage in sensor networks.

Current search mechanisms of DHT-based P2P systems can well handle a single keyword search problem. Other than single keyword search, multi-keyword search is quite popular and useful in many real applications. Simply using the solution for single keyword search will require distributed intersection/union operations in wide area networks, leading to unacceptable traffic cost. As it is well known that Bloom Filter (BF) is effective in reducing traffic, we would like to use BF encoding to handle multi-keyword search. Applying BF is not difficult, but how to get optimal results is not trivial. In this study we show, through mathematical proof, that the optimal setting of BF in terms of traffic cost is determined by the global statistical information of keywords, not the minimized false positive rate as claimed by previous methods. Through extensive experiments, we demonstrate how to obtain optimal settings. We further argue that the intersection order between sets is important for multi-keyword search. Thus, we design optimal order strategies based on BF for both "and" and "or" queries. To better evaluate the performance of this design, we conduct extensive simulations on TREC WT10G test collection and the query log of a commercial search engine. Results show that our design significantly reduces the search traffic of existing approach by 73%.

By combining an unstructured protocol with a DHT-based global index, hybrid peer-to-peer (P2P) improves search efficiency in terms of query recall and response time. The key challenge in hybrid search is to estimate the number of peers that can answer a given query. Existing approaches assume that such a number can be directly obtained by computing item popularity. In this work, we show that such an assumption is not always valid, and previous designs cannot distinguish whether items related to a query are distributed in many peers or are in a few peers. To address this issue, we propose QRank, a difficulty-aware hybrid search, which ranks queries by weighting keywords based on term frequency. Using rank values, QRank selects proper search strategies for queries. We conduct comprehensive trace-driven simulations to evaluate this design. Results show that QRank significantly improves the search quality as well as reducing system traffic cost compared with existing approaches.

Efficient service discovery in dynamic, crossorganizational is one of the challenge aspects in ChinaGrid. Network overlay and search algorithms are two important considerations to the problem. Tree topology of organizations is easily managed but the root is a single point of failure; P2P structure tends to be conversed. To merge the advantages of both, we present a hybrid system with two layers: Tree Layer and Peer Layer. This structure is practical because organizations targeting at sub objects of a subject are inclined to be organized hierarchically as a Superpeer; and all these Superpeers construct an unstructured P2P network that adapts to peer’s interest by Learn Neighbor Algorithm. Experimental evaluation shows that our mechanism exhibits better search performance than fully hierarchical or fully distributed system.

This paper proposes a semantic overlay based on the small world phenomenon that facilitates efficient search for information retrieval in unstructured P2P systems. In the semantic overlay, each node maintains a number of short-range links which are semantically similar to each other, together with a small collection of long-range links that help increasing recall rate of information retrieval and reduce network traffic as well. Experimental results show that our model can improve performance by 150% compared to Gnutella and by up to 60% compared to the Interest-based model - a similar shortcut-based search technique.

The emerging service grids bring together various distributed services to a 'market' for clients to request and enable the integration of services across distributed, heterogeneous, and dynamic virtual organizations. In the experience of constructing and using the ChinaGrid, we meet two challenges, optimizing the QoS of the grid resources and minimizing complexity for application users and developers. In this paper, we present Q-SAC, a QoS optimized service automatic composition model to address these problems. Two main features of Q-SAC are (1) automatic grid service composition, and (2) global level multidimensional QoS optimization for the composition plan. We design the algorithms for generating and optimizing the composite services. The simulation results show that our model and solution are practical and efficient.

The emerging service grids bring together various distributed application-level services to a 'market' for clients to request and enable the integration of services across distributed, heterogeneous, dynamic virtual organizations. However, there are a number of applications with the requirement of time constraints. We propose a real-time strategy in service grid architecture. We also extend the OGSI grid service semantics for fault-tolerance. The real-time and fault-tolerant strategies seem efficient through experiments.