Cross-chain transaction plays a pivotal role in enhancing decentralized applications by enabling interactions and executing local transactions across multiple blockchain systems. However, existing methods on its execution often suffer from high latency, primarily due to the sequential order-validate-execute paradigm, where each local transaction is processed only after the preceding ones are committed. This sequential approach slows down the process as it requires sequential commitment steps on involved blockchains. To address these challenges, we propose Turbo, a novel framework that enhances cross-chain transaction execution by adopting an optimistic execution paradigm. Turbo optimizes latency by concurrently ordering transactions without strict dependency sequences and employing advanced validation techniques to ensure sequence consistency. We implemented Turbo on top of the Cosmos network and conducted extensive experimentation. The results demonstrate its practicality in handling cross-chain transaction execution with low latency, marking a substantial improvement over the state-of-the-art.

Cross-chain transaction processing is pivotal to blockchain interoperability, enabling coordinated state transitions across multiple blockchains to support increasingly complexdecentralized applications(dApps). However, existing atomicity-preserving mechanisms, predominantly based ontwo-phase commit(2PC) protocols, are hindered by sequential coordination, prolonged state locking, and high susceptibility to cascading aborts. These limitations severely degrade throughput and latency under contention, undermining practical deployability. This paper proposes Furion, a novel cross-chain transaction processing mechanism that achieves both atomicity and efficiency. Furion introduces the multi-future exploration, a new execution paradigm that explicitly materializes multiple possible futures of cross-chain states via multi-versioning. By speculatively executing transactions across feasible state evolutions, Furion eliminates blocking on unresolved dependencies and fundamentally avoids cascading aborts. To further unlock concurrency in the finalization phase, Furion employs preemptive voting, which allows local transactions to cast commit or abort votes early when their outcomes are invariant across all state versions. Experimental evaluations demonstrate that Furion significantly outperforms state-of-the-art systems, achieving substantially higher throughput, lower latency, and markedly reduced abort rates under skewed and highly contended workloads.

Asynchronous Byzantine Fault Tolerant (BFT) consensus protocols have garnered significant attention with the rise of blockchain technology. A typical asynchronous protocol is designed by executing sequential instances of the Asynchronous Common Sub-seQuence (ACSQ). The ACSQ protocol consists of two primary components: the Asynchronous Common Subset (ACS) protocol and a block sorting mechanism, with the ACS protocol comprising two stages: broadcast and agreement. However, current protocols encounter three critical issues: high latency arising from the execution of the agreement stage, latency instability due to the integral-sorting mechanism, and reduced throughput caused by block discarding. To address these issues, we propose Falcon, an asynchronous BFT protocol that achieves low latency and enhanced throughput. Falcon introduces a novel broadcast protocol, Graded Broadcast (GBC), which enables a block to be included in the ACS set directly, bypassing the agreement stage and thereby reducing latency. To ensure safety, Falcon incorporates a new binary agreement protocol called Asymmetrical Asynchronous Binary Agreement (AABA), designed to complement GBC. Additionally, Falcon employs a partial-sorting mechanism, allowing continuous rather than simultaneous block committing, enhancing latency stability. Finally, we incorporate an agreement trigger that, before its activation, enables nodes to wait for more blocks to be delivered and committed, thereby boosting throughput. We conduct a series of experiments to evaluate Falcon, demonstrating its superior performance.

AsynchronousByzantine Fault Tolerance(BFT) consensus protocols are gaining attention for their resilience against network attacks. Among them,Multi-valued Byzantine Agreement(MVBA) protocols play a critical role, which accepts input values from each replica and returns a consistent output. The state-of-the-art MVBA protocol, sMVBA, has a good-case latency of$6\delta$and an expected bad-case latency of$12\delta$, with$\delta$representing the network delay. Additionally, sMVBA exhibits a communication of$O(n^{2})$in both good and bad cases. Although it outperforms other MVBA protocols, sMVBA still lags behind partially-synchronous counterparts. For instance, PBFT achieves a good-case latency of$3\delta$, and HotStuff boasts a good-case communication of$O(n)$. This paper introduces a novel MVBA protocol, Pako, aiming for performance comparable to partially-synchronous protocols. Pako leverages an existing MVBA protocol as a black box and introduces an additional view with an optimistic path to commit values efficiently. Two Pako variants, Pako1 and Pako2, provide a trade-off between latency and communication. To be more specific, Pako1 achieves a good-case latency of$3\delta$with$O(n^{2})$communication, while Pako2 reduces the communication to$O(n)$with a slightly higher good-case latency of$5\delta$. A series of experiments demonstrate Pako's significant outperformance of counterparts.

Standing as a foundational element within blockchain systems, theByzantine Fault Tolerant(BFT) consensus has garnered significant attention over the past decade. The introduction of aDirected Acyclic Directed(DAG) structure into BFT consensus design, termed DAG-based BFT, has emerged to bolster throughput. However, prevalent DAG-based protocols grapple with substantial latency issues, suffering from a latency gap compared to non-DAG protocols. For instance, leading-edge DAG-based protocols named GradedDAG and BullShark exhibit a good-case latency of$4$and$6$communication rounds, respectively. In contrast, the non-DAG protocol, exemplified by PBFT, attains a latency of$3$rounds in favorable conditions. To bridge this latency gap, we propose Remora, a novel DAG-based BFT protocol. Remora achieves a reduced latency of$3$rounds by incorporating optimistic paths. At its core, Remora endeavors to commit blocks through the optimistic path initially, facilitating low latency in favorable situations. Conversely, in unfavorable scenarios, Remora seamlessly transitions to a pessimistic path to ensure liveness. Various experiments validate Remora's feasibility and efficiency, highlighting its potential as a robust solution in the realm of BFT consensus protocols.

Sandwich arbitrage is a popular strategy for blockchain-based decentralized exchange (DEX) users to facilitate decentralized token exchanges and make profits. However, conventional Sandwich arbitrage only focuses on one big-deal transaction and executes arbitrary actions within an intrablock, leading to a huge loss of profit opportunities. In this article, we present Lasagne, a novel high-profit arbitrage strategy that allows the exploration of profit opportunities from multiple small-deal transactions across interblocks. Specifically, Lasagne involves a suite of novel strategies: fishing, bundle, and grid, each of which is tailored to a liquidity pool with diverse transaction frequencies and skewness. The experimental results demonstrate the superiority of Lasagne over a state-of-the-art sandwich in terms of feasibility and effectiveness.

Dynamic searchable symmetric encryption (DSSE) schemes empower data owners to outsource their encrypted data to clouds while retaining the ability to update or search on it. Despite a lot of efforts devoted in recent years, there are still several challenges that have not been well addressed. First, the confidentiality of data might be compromised if forward privacy and backward privacy cannot be ensured. Second, only the traditional single keyword-file search has attracted tremendous attention, while other popular queries like Boolean queries and range queries are not fully investigated. Lastly, how to solve these problems on untrusted servers that may deviate from pre-defined protocols is also challenging. In this article, aiming to tackle the above problems, we propose a novel DSSE scheme named${\sf HeX}$based on Trusted Execution Environment (TEE) that supports rich queries on untrusted servers while guaranteeing forward and backward privacy. We achieve strong forward and backward security by designing a deferred obfuscating read-write technique atop the bitmap index. We further extend the basic scheme to realize Boolean queries and range queries by reducing them to basic keyword queries. Strict theoretical analysis is conducted to prove the security of${\sf HeX}$, and extensive evaluations illustrate its efficiency and practicality.

Broadcast primitives likeReliable Broadcast(RBC) are integral toDirected Acyclic Graph(DAG)-based asynchronousByzantine Fault Tolerant(BFT) protocols. Despite recent advancements, these protocols often suffer from high latency due to the inherent three communication rounds in RBC. To mitigate this latency, we propose employingBest-Effort Broadcast(BBC) for message dissemination, which requires only one communication round. However, leveraging BBC poses challenges in constructing a DAG-based ledger and ensuring consistent commitment in the face of contradictory blocks. In this paper, we introduce PlainDAG, a low-latency and secure asynchronous DAG-based BFT protocol that eschews complex broadcast primitives. Instead, it achieves lower latency by simplifying broadcast and committing with a larger quorum of votes. Our approach addresses the integrity, agreement, and totality properties lacking in BBC compared to RBC, thus ensuring correctness. Key to the design of PlainDAG is the introduction of anIntegral Referencefield in blocks, which references previously committed blocks and facilitates voting among contradictory blocks. Additionally, we devise a block query scheme to retrieve missing blocks. Theoretical analysis demonstrates the generalized design applicability of PlainDAG for asynchronous DAG-based BFTs, with the best-case latency of 2 communication rounds and practical resilience. Experimental results underscore the superiority of PlainDAG over state-of-the-art asynchronous DAG-based protocols in latency, while achieving comparable throughput performance.

Blockchain-based query with its traceability and data provenance has become increasingly popular and widely adopted in numerous applications. Yet existing index-based query approaches are only efficient under static blockchain query workloads where the query attribute or type must be fixed. It turns out to be particularly challenging to construct an efficient index for dynamic workloads due to prohibitively long construction time and excessive storage consumption. In this paper, we present FlexIM, the first efficient and verifiable index management system for blockchain dynamic queries. The key innovation in FlexIM is to uncover the inherent characteristics of blockchain, i.e., data distribution and block access frequency, and then to optimally choose the index by utilizing reinforcement learning technique under varying workloads. In addition, we enhance and facilitate verifiability with low storage overhead by leveraging Root Merkle Tree (RMT) and Bloom Filter Merkle Tree (BMT). Our comprehensive evaluations demonstrate that FlexIM outperforms the state-of-the-art blockchain query mechanism, vChain+, by achieving a 26.5% speedup while consuming 94.2% less storage, on average, over real-world Bitcoin datasets.

Directed Acyclic Graph (DAG)-based blockchain (a.k.a distributed ledger) has become prevalent for supporting highly concurrent applications. Its inherent parallel data structure accelerates block generation significantly, shifting the bottleneck from performance to storage scalability. An intuitive solution is to apply state sharding that divides the entire ledger (i.e., transactions and states) into multiple shards. While each node only stores proportional transactions, it suffers from the challenges of storing and ensuring the processing consistency of cross-shard transactions. In this paper, we propose SharDAG, a new mechanism that leverages adaptive sharding for DAG-based blockchains to achieve high performance and strong consistency. The key idea of SharDAG is to exploit unique characteristics - silent assets - and design a lightweight processing mechanism based on avatar account caching. Furthermore, we design a Byzantine resilient cross-shard verification mechanism with a theoretically optimal number of participating nodes, which guarantees the consistency and security of avatar account aggregation. Our comprehensive evaluations on real-world workloads demonstrate that SharDAG presents up to 3.8 x throughput improvement compared to the state-of-the-art and reduces the storage overhead of cross-shard transactions.

The widespread availability of Internet access and online services has led to the generation of numerous large-scale graphs in various real-world applications, such as online social networks and knowledge graphs. Keyword search stands out as a crucial task in the analysis and mining of these graphs. However, graph data owners tend to outsource storage and computation tasks to the cloud due to limited computing and storage resources. In this case, it is critical to ensure the integrity of the query results, as the cloud may have an incentive to return tampered results to serve its own interests. Currently, blockchain systems can store data efficiently and securely, creating a decentralized, tamper-proof digital platform. This functionality positions blockchain as a crucial complement and enhancement to traditional cloud storage solutions. Mainstream blockchains use a hybrid storage system to improve scalability, storing small meta-data on-chain and outsourcing raw data off-chain. While cryptographic proofs protect data integrity for queries, current schemes only support key-value data. This paper pioneers the study of authenticated keyword searches on graphs in hybrid-storage blockchains. The key challenge is to design an authenticated data structure (ADS) based on the graph data that can efficiently deal with keyword search queries. We propose Merkle Path DAG (MP-DAG), a novel ADS that aggregates the unqualified paths that will not appear in the result trees to efficiently handle authenticated keyword search queries on graphs. Furthermore, to reduce the ADS storage cost, we design an optimization scheme MP-DAG* by combining the similar subgraphs of MP-DAG. Experimental results demonstrate the performance of the proposed ADS and optimization measure.

With the development of permissioned blockchains, transaction processing plays an increasingly crucial role in improving performance. The execution and consensus phases in existing transaction processing methods are based on total order. The consensus phase constructs a total order representing the execution order and submission order of different transactions. Then, in the execution phase, transactions are executed or validated sequentially based on this total order. However, while the total order guarantees consistency across nodes, it also restricts the execution order of any two transactions, even if there is no conflict between them. Additionally, existing methods process transactions based on block snapshots before the consensus phase, but these snapshots are only updated after reaching consensus. The stale data between these phases results in high transaction abort rates due to delays in updated visibility. Therefore, we propose a novel blockchain called Partial Order-Based Ledger (POBL). POBL constructs a partial order of transaction executions in the execution phase and then, in the consensus phase, builds a consistent submission order based on this execution partial order. Notably, POBL allows the visibility of transaction processing results in the execution phase even before committing its block. To ensure the correct execution, the consensus and execution phases need to consider the consistency of data and the dependencies between transactions. Therefore, we use a graph, PGraph, to capture the concurrent partial order in the execution phase. In the consensus phase, we propose a consensus algorithm to conduct the maximal common subgraph, CPGraph, based on the PGraphs of different nodes. We propose to validate blocks and transactions in parallel based on CPGraph, without being restricted by the order between blocks. We perform extensive experiments compared to state-of-the-art architectural systems, and our method significantly outperforms existing work.

To improve the throughput of Byzantine Fault Tolerance (BFT) consensus protocols, the Directed Acyclic Graph (DAG) topology has been introduced to parallel data processing, leading to the development of DAG-based BFT consensus. However, existing DAG-based works heavily rely on Reliable Broadcast (RBC) protocols for block broadcasting, which introduces significant latency due to the three communication steps involved in each RBC. For instance, DAGRider, a representative DAG-based protocol, exhibits the best latency of 12 steps, considerably higher than non-DAG protocols like PBFT, which only requires 3 steps. To tackle this issue, we propose LightDAG, which replaces RBC with lightweight broadcasting protocols such as Consistent Broadcast (CBC) and Plain Broadcast (PBC). Since CBC and PBC can be implemented in two and one communication steps, respectively, LightDAG achieves low latency.In our proposal, we present two variants of LightDAG, namely LightDAG1 and LightDAG2, each providing a trade-off between the best latency and the expected worst latency. In LightDAG1, every block is broadcast using CBC, which exhibits a best latency of 5 steps and an expected worst latency of 14 steps. Since CBC cannot guarantee the totality property, we design a block retrieval mechanism in LightDAG1 to assist replicas in retrieving missing blocks. LightDAG2 utilizes a combination of PBC and CBC for block broadcasting, resulting in the best latency of 4 steps and an expected worst latency of 12(t+1) steps, where t represents the number of actual Byzantine replicas. Since a Byzantine replica may equivocate through PBC, LightDAG2 prohibits blocks from directly referencing contradictory blocks. To ensure liveness, we propose a mechanism to identify and exclude Byzantine replicas if they engage in equivocation attacks. Extensive experiments have been conducted to evaluate LightDAG, and the results demonstrate its feasibility and efficiency.

Cross-chain Decentralized Applications (dApps) are increasingly popular for their ability to handle complex tasks across various blockchains, extending beyond simple asset transfers or swaps. However, ensuring all dependent transactions execute correctly together, known as complete atomicity, remains a challenge. Existing works provide financial atomicity, protecting against monetary loss, but lack the ability to ensure correctness for complex tasks. In this paper, we introduce Avalon, a transaction execution framework for cross-chain dApps that guarantees complete atomicity for the first time. Avalon achieves this by introducing multiple state layers above the native one to cache state transitions, allowing for efficient management of these state transitions. Most notably, for concurrent cross-chain transactions, Avalon resolves not only intra-chain conflicts but also addresses potential inconsistencies between blockchains via a novel state synchronization protocol, enabling serializable cross-chain execution. We implement Avalon using smart contracts in Cosmos ecosystem and evaluate its commitment performance, demonstrating acceptable latency and gas consumption even under conflict cases.

Mainstream blockchain systems such as Bitcoin and Ethereum are revolutionizing the financial industry by adopting the Nakamoto consensus protocol, i.e., Proof-of-Work (PoW). Only nodes with sufficient computing resources can work out the PoW difficulties, thereby increasing the mining cost of malicious attackers and ensuring the security of blockchain systems. Such an assumption of having abundant resources leads to drawbacks of low throughput and risk of centralization. In this article, we present Dispatcher, a novel distributed consensus protocol that takes resource heterogeneity into account to ensure resource-aware PoW with high efficiency. Dispatcher introduces a hierarchical topology to offer flexible PoW difficulties tailored for different nodes’ resources. In particular, it utilizes the limited resource of each node to jointly maximize the performance by concurrent mining. Moreover, we design an adaptive incentive mechanism to fit the available resource of blockchain nodes to rewards. Our experiments show that Dispatcher enjoys a substantial performance margin over the state-of-the-art. We can achieve a 50% throughput improvement compared with OHIE.

Increasingly popular decentralized applications (dApps) with complex application logic incur significant overhead for executing smart contract transactions, which greatly limits public blockchain performance. Pre-executing transactions off the critical path can mitigate substantial I/O and computation costs during execution. However, pre-execution does not yield any state transitions, rendering the system state inconsistent with actual execution. This inconsistency can lead to deviations in pre-execution paths when processing smart contracts with multiple state-related branches, thus diminishing pre-execution effectiveness. In this paper, we develop Seer, a novel public blockchain execution engine that incorporates fine-grained branch prediction to fully exploit pre-execution effectiveness. Seer predicts state-related branches using a two-level prediction approach, reducing inconsistent execution paths more efficiently than executing all possible branches. To enable effective reuse of pre-execution results, Seer employs checkpoint-based fast-path execution, enhancing transaction execution for both successful and unsuccessful predictions. Evaluations with realistic blockchain workloads demonstrate that Seer delivers an average of 27.7× transaction-level speedup and an overall 20.6× speedup in the execution phase over vanilla Ethereum, outperforming existing blockchain execution acceleration solutions.

To parallelize data processing within BFT consensus protocols,Directed Acyclic Graph(DAG) structures have been integrated into consensus design, shaping the realm of DAG-based BFT protocols. Existing DAG-based protocols rely on theReliable Broadcast(RBC) protocol or its variants for block dissemination, which ensures consistency and totality properties of the data delivery. However, the inherent communication overhead ofO(n2) in RBC (wherenis the total replica count) results in an unwieldyO(n3) overhead in current DAG-based solutions, as each replica disseminates blocks through RBC in parallel. In response to this issue, we propose two new broadcast protocols:Provable Broadcast(PBC) andEnhanced ProvableBroadcast (EPBC). Both PBC and EPBC maintain the consistency property of data delivery, similar to RBC, while offering linear communication overhead without totality. Leveraging these broadcast protocols, we devise Wahoo, a novel DAG-based BFT protocol that significantly reduces communication overhead toO(n2). To address the absence of the totality property, we introduce a block retrieval mechanism to assist replicas in acquiring missing blocks. Additionally, under favorable conditions, Wahoo achieves a low latency of 4δ (where δ symbolizes the actual network delay), rivaling the best performance of existing DAG-based protocols. Various experiments showcase Wahoo’s high performance, owing to its substantially reduced communication overhead.

Directed Acyclic Graph(DAG)-based blockchain represents a paradigm shift from conventional blockchains, which has the potential to drastically improve throughput performance through concurrent storage and executions. In practice, however, existing DAG-based blockchains fail to deliver such promises, often with limited throughput, high conflicts, and security vulnerabilities under dynamic workloads. The root causes are their unawareness of the workload characteristics of different workload sizes and skewed access patterns. In this paper, we propose MorphDAG, the first workload-aware DAG-based blockchain that can significantly enhance throughput without compromising security and achieve elastic scaling under realistic workloads. We derive the theoretically optimal degree of storage concurrency to achieve high throughput while retaining system security as the workload size changes, while enabling fine-grained concurrency adjustment that accommodates aProof-of-Stake(PoS)-based consensus protocol. We develop a dual-mode transaction processing mechanism that effectively resolves the conflicts brought by skewed access. We implement a prototype of MorphDAG and evaluate under real-world workloads. Extensive evaluations demonstrate that MorphDAG improves end-to-end throughput by up to 2.3× and 2.4× over state-of-the-art DAG-based blockchain systems AdaptChain and OHIE, respectively.

The privacy-preserving query is critical for modern blockchain systems, especially when supporting many crucial applications such as finance and healthcare. Recent advances in blockchain query schemes mainly focus on enhancing the traceability efficiency of integrity authentication. Despite these efforts, we argue that the exposure of retrieval information may result in privacy leakage, which inevitably poses an important yet unresolved challenge. In this paper, we introduce Cloak, a novel privacy-preserving blockchain query scheme with two notable features. First, it utilizes a two-phase distributed query requests technique, i.e., division and aggregation, to hide retrieval information based on the natural independent characteristic of blockchain. Second, we add noise to the sub-request set to avoid malicious attacks during transmission and adopt smart contract-based asymmetric encryption to guarantee the correctness of query results. Experimental results demonstrate that Cloak improves the query performance by up to 4× and reduces the storage overhead by 50% compared with the state-of-the-art Spiral.

To overcome the scaling and performance limitations, the Directed Acyclic Graph (DAG) is utilized as the underlying storage model of blockchain systems, which enables concurrent transaction processing and confirmation. However, accompanied by high performance, DAG-based blockchains still suffer from the severe challenge of constrained storage scalability, i.e., expensive storage overhead. Based on an in-depth analysis of the data, we discover that the root cause of storage overhead stems from the considerable data redundancy in the DAG-based blockchains. In this paper, we propose GeckoDAG, a lightweight DAG-based blockchain, whose design consists of two steps. First, we abstract a storage model named Basic from the existing DAG-based blockchain systems, which offers both high performance and security. On top of Basic, we then devise GeckoDAG, which merges previous transactions into Transaction Union (TU) and reduces the data redundancy in TU, thus lowering the storage overhead. To evaluate our design, we implement a prototype of GeckoDAG and conduct various experiments on it. The experimental results demonstrate that GeckoDAG can offer storage scalability while maintaining the security and efficiency of DAG-based blockchains.

To enable parallel processing, the Directed Acyclic Graph (DAG) structure is introduced to the design of asyn-chronous Byzantine Fault Tolerant (BFT) consensus protocols, known as DAG-based BFT. Existing DAG-based BFT protocols operate in successive waves, with each wave containing three or four Reliable Broadcast (RBC) rounds to broadcast data, resulting in high latency due to the three communication steps required in each RBC. For instance, Tusk, a state-of-the-art DAG-based BFT protocol, has a good-case latency of 7 communication steps and an expected worst latency of 21 communication steps. To reduce latency, we propose GradedDAG, a new DAG-based BFT consensus protocol based on our adapted RBC called Graded RBC (GRBC) and the Consistent Broadcast (CBC), with each wave consisting of only one GRBC round and one CBC round. Through GRBC, a replica can deliver data with a grade of 1 or 2, and a non-faulty replica delivering the data with grade 2 can ensure that more than 2/3 of replicas have delivered the same data. Meanwhile, through CBC, data delivered by different non-faulty replicas must be identical. In each wave, a block in the GRBC round will be elected as the leader. If a leader block has been delivered with grade 2, it and all its ancestor blocks can be committed. GradedDAG offers a good-case latency of 4 communication steps and an expected worst latency of 7.5 communication steps, significantly lower than the state-of-the-art. Experimental results demonstrate GradedDAG's feasibility and efficiency.

In most blockchain-based application scenarios, a complete application logic consists of multiple continuous transactions, in which the initiation of one transaction depends on the confirmation result of the previous one. This mandates that continuous transactions must be processed in the correct order. Unfortunately, existing chain-based blockchains fail to effectively support continuous transaction processing due to considerable latency in confirming continuous transactions. Recent studies shifted from chain-based blockchains toDirected Acyclic Graph(DAG) based blockchains, which reduced transaction confirmation latencies. However, DAG-based blockchains store transactions in an out-of-order manner that leads to unordered transaction processing. To address this challenge, we propose FLUID, a new DAG-based blockchain that supports continuous transaction processing while delivering high performance. The fundamental idea of FLUID is to design a transaction dependency tracking structure to ensure that continuous transactions can be processed in the correct order. FLUID utilizes a conflict resolution mechanism to provide instant confirmation and to support concurrent transaction processing with lower latencies. In addition, FLUID builds a checkpoint-based verification mechanism to achieve deterministic consensus on transaction processing results in the DAG. Extensive experiments demonstrate that our proposed FLUID can improve the throughput over state-of-the-art OHIE by 66% with two orders of magnitude lower latencies.

Wi-Fi technology is becoming a promising enabler of device-free fitness tracking to provide reviews and recommendations for effective homely exercise. State-of-the-art Wi-Fi fitness assistants succeed in recognizing the simple meta-movements (e.g., Push-Up and Squat) with discrete and repeatable patterns. Unfortunately, these prior attempts can hardly scale to the combination movements of ever-growing interests in intensive fitness programs. Combination movements are composed of meta-movements that are mutually concatenated or inserted. They have a compound characteristic that inherits from the diversity of combination orders and continuity of meta-movements. The compound characteristic causes substantial training data collection costs and a challenge of combination decomposition that is a prerequisite for providing fine-grained fitness assessment. To this end, we proposeInFit, a Wi-Fi-based device-free fitness assistant system for combination movements. First, we design a novel data augmentation method, namelyStitching-based Virtual Sample Generation(SVSG), to reduce the training data collection costs by generating virtual combination movements. Second, a 2-stage combination movement recognition model is designed to learn temporal dependencies between movements and decompose combination movements. From its outputs, we can tell whether a combination movement is standard. Extensive experimental results show that InFit can achieve an average recognition accuracy of$94\%$. With zero training samples of combination movements, the average accuracy is$40\%$higher than the baselines. In addition, SVSG can provide a general enhancement on multiple competing schemes with similar sensing tasks.

Gesture recognition by using Inertial Measurement Unit (IMU) sensors plays an important role in various Internet of Things (IOT) applications, e.g., smart home, intelligent medical system and so on. Traditional technologies usually utilize machine learning algorithms to train different gestures during the offline phase, then recognize the gesture during the online phase. However, such technologies cannot recognize these gestures without prior training. Even for the same gesture, with different gesture amplitude may result in unsuccessful recognition. Also if we change the person to perform the same gesture, the algorithms fails. In order to overcome these drawbacks, we propose an approach, which will be able to track the human body motion in real-time and also recognize complicated gestures. It utilizes the accelerometer information and proposes comprehensive localization algorithms for each deployed sensor attached on the human body. Then, it takes the correlation and limitation among body parts into account to recognize the gesture. Our experiments results show that, the successful recognition rate of our algorithm is 100%. Furthermore, any part of the human body can be well tracked, the tracking accuracy can reach$0.06m$.

The popularity of blockchain technology has revived interest in Byzantine Fault Tolerance (BFT) consensus protocols. However, existing protocols suffer from high latency, especially when the system is deployed in a worldwide manner. Taking Practical Byzantine Fault Tolerance (PBFT), the best-known and de-facto standard of BFT consensus protocol, as an example, it requires at least three phases to commit a request. Although some works attempt to shorten the number of phases by proposing a fast-path commitment rule, they either sacrifice resilience or subvert security.

A Directed Acyclic Graph (DAG)-based blockchain with its inherent parallel structure can potentially significantly improve the throughput performance over conventional blockchains. Such a performance improvement can be further enhanced through concurrent transaction processing. This, however, brings new challenges in concurrency control design in that there is an increased number of concurrent reads and writes to the same address in a DAG-based blockchain, which leads to a considerable rise of potential conflicts. Therefore, one critical problem is how to effectively and efficiently detect and order conflicting transactions. In this work, for the first time, we aim to improve system throughput and processing latency by exploring the address dependencies among different transactions. We propose NEZHA, an efficient concurrency control scheme for DAG-based blockchains. Specifically, NEZHA intelligently constructs an address-based conflict graph (ACG) while incorporating address dependencies as edges to capture all conflicting transactions. To generate a total order between transactions, we propose a hierarchical sorting (HS) algorithm to derive sorting ranks of addresses based on the ACG and sort transactions on each address. Extensive experiments demonstrate that, even under high data contention, NEZHA can increase the throughput over the conventional conflict graph scheme by up to 8 ×, while decreasing the transaction processing latency up to 10 ×.

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.

It has been recognized that one of the bottlenecks in the UTXO-based blockchain systems is the slow block validation - the process of validating a newly-received block by a node before locally storing it and further broadcasting it. As a block contains multiple inputs, the block validation mainly involves checking the inputs against the status data, which is also known as the Unspent Transaction Outputs (UTXO) set. As time goes by, the UTXO set becomes more and more expansive, most of which can only be stored on disks. This considerably slows down the input checking and thus block validation, which can potentially compromise system security. To deal with the above problem, we disassemble the function of input checking into three parts: existence validation (EV), unspent validation (UV), and script validation (SV). Based on the disassembly, we propose EBV, an efficient block validation mechanism to speed up EV, UV, and SV individually. First, EBV changes the representation of status data, from UTXO set to a bit-vector set, which drastically reduces its size. The smaller status data can be entirely maintained in memory, thereby accelerating UV and also block validation. Second, EBV requires each transaction to carry the proof data, which enables EV and SV without accessing the disks. Furthermore, we also cope with two challenges in the design of EBV, namely transaction inflation and fake positions. To evaluate the EBV mechanism, we implement a prototype on top of Bitcoin, the most widely known UTXO-based blockchain, and conduct extensive experiments to compare EBV and Bitcoin. The experimental results demonstrate that EBV successfully reduces the memory requirement by 93.1 % and the block validation time by up to 93.5%.

With customization of demands and functionalities, diverse blockchain systems are integrated with IoT in different application scenarios, forming a multichain environment. Multichain interoperability has become a crucial emerging issue, i.e., different blockchain systems are difficult to interact with each other credibly and efficiently. It further leads to isolated data islands across multichain. Therefore, it is of significant importance to facilitate data sharing among multichain systems. Toward achieving this, there are two main challenges. First, data across multiple blockchains must be shared reliably to meet the tamper-proof merits of blockchain technology. Second, we must control the data access process in a fine-grained way to protect sensitive data and user privacy. This article proposes SynergyChain, a multichain framework to enable reliable data sharing with controllable data access. By aggregating the data from multiple blockchains and reorganizing it in SynergyChain, we can achieve data reliability with the verification. Meanwhile, SynergyChain provides hierarchical access control based on smart contracts, making access control automated and credible. Experiments show that SynergyChain can support data sharing reliably and efficiently and reduce data query latency compared with multichain data requesting sequentially.

Due to the lack of supervision in the decentralized exchanges (DEXs), arbitrageurs can utilize information and take advantage of price gap to make profits over such platforms such as Ethereum blockchain. DEX arbitrage poses possibilities and opportunities for defrauding and can seriously impair the operation of the Ethereum ecosystem. It motivates this work to explore and characterize the unique features of arbitrage which differ from other frauds such as money laundering and Ponzi games for better detection. This work makes the first attempt for detecting arbitrage on Ethereum through feature fusion and positive-unlabeled learning (PU learning). We first conduct an in-depth analysis and exploit two-fold arbitrage features by fusion including: 1) statistical features that explicitly represent the node activity levels according to expert knowledge; and 2) structural features that implicitly encode the transactions information by graph machine learning. We then apply PU learning to generate negative instances for compensating the imbalanced arbitrage datasets. We evaluate our proposed method through extensive experiments over a real-world dataset and demonstrate that it can achieve 90% accuracy in detecting arbitrage activities on Ethereum.

Sharing data across various Internet of Things (IoT) devices has been a common challenge due to efficiency, security, and stability issues. Blockchain, with security features, is considered to be a potential solution for data sharing in IoT settings. However, traditional blockchain-based solutions cannot satisfy the efficiency requirement of high-frequency data sharing among IoT devices. In this paper, we propose an efficient IoT data sharing approach by adopting the Payment Channel Network (PCN)-extended blockchain. Besides, we develop a homomorphic hashing-based transaction segmentation scheme to solve the issue of low transaction success ratio caused by channel deposit restrictions in PCN. In addition, a Multi-point Relay (MPR)-based multi-path routing scheme has been developed to ensure high-frequency transaction forwarding. The communication overhead of maintaining the routing table is reduced by our proposed Multi-point Relay Selection algorithm, and multiple alternate paths generated by Multiple Routing Path algorithm can improve the transaction success rate. Experiment evaluations have demonstrated that that our proposed approach outperforms the baseline approaches in terms of the transaction efficiency and success ratio.

Multi-FPGA architectures have gained great interests in accelerating large-scale graph processing with great potential on high throughput and energy efficiency. As a beneficial complement, work stealing functions effectively to balance the computational workload on different FPGAs dynamically. Unfortunately, existing graph partitioning schemes originally designed in distributed settings potentially mismatch the work stealing-enabled multi-FPGA situations, where the computation is balanced while the communication overhead is unprecedentedly significant. In this paper, we present a 2-dimension balanced graph partitioning for work stealing assisted graph systems on multi-FPGAs, which can reduce communication overhead while preserving the optimal performance of work stealing. Our approach is novel by 1) exploring the tradeoff between load balance dimension and communication dimension in work-stealing-enabled graph processing system for the optimal performance, and 2) optimizing the memory access sequences to improve the granularity of graph partitioning for high-throughput graph analytics. Our experimental results show that our approach achieves 1.63x$\sim$2.56x speedups compared with state-of-the-art FPGA-based graph processing systems.

Recent successful pilot studies on blockchains showed significant benefits of data provenance towards improved visibility and authenticity, as well as a reduction of administrative costs. Traditionally, all the parties reside in a single blockchain system, which leads to various single-chain provenance query schemes. However, for the sake of convenience, it has been a trend for different parties to deploy their own blockchain systems separately, which requires cross-chain provenance queries. Unfortunately, state-of-the-art blockchain query schemes suffered from inauthentic transactions and low efficiencies when expanding to adversarial cross-chain commercial deals. To be more specific, query results may be inconsistent and incomplete over multiple blockchains due to the lack of global knowledge on cross-chain dependencies. Moreover, these schemes perform cross-chain provenance queries in sequence, leading to high query latencies. In this paper, we present Vassago, the first multi-chain system that empowers efficient and authenticated provenance queries. Vassago incorporates three innovative designs: 1) it explores the dependencies of cross-chain transactions, 2) it validates the authenticity of cross-chain provenance by recording and querying the dependencies on a shared blockchain, and 3) it improves efficiency by parallelizing query processes. Our experimental results show that Vassago can shorten the query latency by 85.9% and reduce the storage consumption by up to 85.7%, with negligible overhead.

Federated learning (FL) has been gaining popularity as a way to provide privacy-preserving data sharing for the Internet of Medical Things (IoMT). As a complementary, blockchain technology is used in recent literature to make FL secure. However, existing blockchain-based FL (BFL) solutions do not perform well when data in a BFL cluster are sparse. A direct solution is to collect as many devices as possible to establish a large BFL cluster. However, these devices may locate in geographically distant areas and be separated by great distance, which further results in high communication latency. The high latency will lead to BFL’s low system efficiency due to frequent communications in the blockchain consensus. In this article, we propose that the large cluster should be divided into multiple smaller clusters, each in its own geographical area and organized with a BFL. In this context, we propose CFL, a cross-cluster FL system facilitated by the cross-chain technique. CFL connects multiple BFL clusters, where only a few aggregated updates are transmitted over long distances across clusters, thus improving the system efficiency. The design of CFL focuses on a cross-chain consensus protocol, which guarantees the model updates to be exchanged securely across clusters. We carry out extensive experiments to evaluate CFL in comparison with BFL, and show both CFL’s feasibility and efficiency.

Cloud platforms can provide flexible and cost-effective environments for parallel applications. However, the resource over-commitment issues, i.e., cloud providers often provide much more executable virtual CPUs than available physical CPUs, still impede the synchronization operations of parallel applications, causing severe performance degradation. Existing methods optimize parallel applications by promoting the priorities of involved VMs. They cannot fully explore the performance of parallel applications, because they ignore the time-slice requirements of different phases of parallel applications. Furthermore, non-parallel applications experience unsatisfied performance because of low scheduling priorities. Given empirical analysis on time-slices of virtual machines (VMs), we find that shortening time-slices can mitigate synchronization overhead which incurs during communication phases, while over-short time-slices cause frequent cache misses in computation phases. Accordingly, we propose an Adaptive Time-slice Control (ATC) mechanism. ATC first detects the phases of parallel applications based on lock latency or cache misses. Then, ATC shortens time-slices during communication phases and prolongs time-slices during computation phases for parallel applications, and sets a uniform time-slice for non-parallel applications. We evaluate ATC using seven well-known benchmarks with 25+ applications. Experiments show that ATC obtains 1.5-75× performance gain for running parallel applications than state-of-the-art solutions, with nearly unaffected impact on non-parallel applications.

Modern large-scale cloud platforms require live migration technique on Docker containers with stateful workload to support load balancing, host maintenance, and Quality of Service (QoS) improvement. Efficient and scalable Docker live migration is expected to guarantee the component-integrity (image, runtime, and management context) with negligible downtime. In this paper, we present a highly efficient live migration system called Sledge, which ensures the component-integrity by integrating both images and management context during runtime migration. The key insight is that the layered image can be leveraged to reduce the migration overhead, and appropriately selective migration of management context will effectively improve QoS with negligible downtime. To achieve good scalability, a lightweight container registry mechanism for end-to-end image migration is designed to avoid the redundant layers transmission. In addition, a dynamic context loading scheme is proposed to precisely load the management context into the running daemon, which can significantly reduce downtime. Experiments show that, compared with the state-of-the-art, Sledge reduces 57% of total migration time, 55% of image migration time, and 70% downtime.

In the Bitcoin system, transaction history of an address can be useful in many scenarios, such as the balance calculation and behavior analysis. However, it is non-trivial for a common user who runs a light node to fetch historical transactions, since it only stores headers without any transaction details. It usually has to request a full node who stores the complete data. Validation of these query results is critical and mainly involves two aspects: correctness and completeness. The former can be implemented via Merkle branch easily, while the latter is quite difficult in the Bitcoin protocol. To enable the completeness validation, a strawman design is proposed, which simply includes the BF (Bloom filter) in the headers. However, since the size of BF is about KB, light nodes in the strawman will suffer from the incremental storage burden. What's worse, an integrated block must be transmitted when BF cannot work, resulting in large network overhead. In this paper, we propose LVQ, the first lightweight verifiable query approach that reduces the storage requirement and network overhead at the same time. To be specific, by only storing the hash of BF in headers, LVQ keeps data stored by light nodes being little. Besides, LVQ introduces a novel BMT (BF integrated Merkle Tree) structure for lightweight query, which can eliminate the communication costs of query results by merging the multiple successive BFs. Furthermore, when BF cannot work, a lightweight proof by SMT (Sorted Merkle Tree) is exploited to further reduce the network overhead. The security analysis confirms LVQ's ability to enable both correctness and completeness validation. In addition, the experimental results demonstrate its lightweight.

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.

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.

Effective finger writing underpins semantic text input task for virtual reality applications. We demonstrate WiWrite, a novel finger writing system that leverages the ubiquitous wireless signals to enable character recognition and word estimation. WiWrite decomposes characters into basic strokes and distinguishes them by exploring the unique signal reflection pattern caused by finger movements. Apart from the prior arts relying on specialized sensors or wearable devices, WiWrite is device-free without any accessories in deed. Our real-world experiments in two different scenarios show that WiWrite succeeds in classifying 26 upper-case alphabets with 90.8% average accuracy and recognizing simple words with an average accuracy of 96.7%.

Today, stream data applications represent the killer applications for Edge computing: placing computation close to the data source facilitates real-time analysis. Previous efforts have focused on introducing light-weight distributed stream processing (DSP) systems and dividing the computation between Edge servers and the clouds. Unfortunately, given the limited computation power of Edge servers, current efforts may fail in practice to achieve the desired latency of stream data applications. In this vision paper, we argue that by introducing FPGAs in Edge servers and integrating them into DSP systems, we might be able to realize stream data processing in Edge infrastructures. We demonstrate that through the design, implementation, and evaluation of F-Storm, an FPGA-accelerated and general-purpose distributed stream processing system on Edge servers. F-Storm integrates PCIe-based FPGAs into Edge-based stream processing systems and provides accelerators as a service for stream data applications. We evaluate F-Storm using different representative stream data applications. Our experiments show that compared to Storm, F-Storm reduces the latency by 36% and 75% for matrix multiplication and grep application. It also obtains 1.4x and 2.1x improvement for these two applications, respectively. We expect this work to accelerate progress in this domain.

The pioneer blockchain platform Bitcoin has drawn massive attention from various sectors in society, with its promising decentralized, irreversible, and trust-free natures. Increasing volume of Bitcoin transactions makes it impractical for each user to store a full copy of whole ledger, especially for a normal user who makes few transactions and owns constrained storage space. There are already some works conducted to reduce the storage overhead by redesigning the system protocol, based on different trust assumptions. An example is running light nodes, which trust the full nodes to store its relevant data and reply to its data request timely. However, it introduces the risks of permanent data loss, as the data relevant to a light node may be tailored by all the full nodes later. Another attempt is conducted by organizing the nodes into several cooperative units based on a trust assumption, which is hard to satisfy in practice. In this paper, we propose a novel Jigsaw-like Data Reduction (Jidar) approach. Each node in Jidar only stores transactions of interest and relevant Merkle branches from the complete blocks, just like selecting several pieces from the jigsaw puzzles. A node can maintain and verify all its relevant data locally and safely without any trust assumptions. To verify the validity of a newly proposed transaction, Merkle branches relevant to the inputs are provided along with the transaction by the proposer. In view of the requirement that a user wants to cohere all the fragments stored in different nodes into a complete block, just like stitching all the pieces into a complete jigsaw-puzzle picture, a mechanism to query full data is added to Jidar. Experimental results demonstrate that Jidar can reduce a normal node's storage cost to about 1.03% of the original Bitcoin system at a low communication cost

While current fairness-driven I/O schedulers are successful in allocating equal time/resource share to concurrent workloads, they ignore the I/O request queueing or reordering in storage device layer, such as Native Command Queueing (NCQ). As a result, requests of different workloads cannot have an equal chance to enter NCQ (NCQ conflict) and fairness is violated. We address this issue by providing the first systematic empirical analysis on how NCQ affects I/O fairness and SSD utilization and accordingly proposing a NCQ-aware I/O scheduling scheme, NASS. The basic idea of NASS is to elaborately control the request dispatch of workloads to relieve NCQ conflict and improve NCQ utilization. NASS builds on two core components: an evaluation model to quantify important features of the workload, and a dispatch control algorithm to set the appropriate request dispatch of running workloads. We integrate NASS into four state-of-the-art I/O schedulers and evaluate its effectiveness using widely used benchmarks and real world applications. Results show that with NASS, I/O schedulers can achieve 11-23% better fairness and at the same time improve device utilization by 9-29%.

Fingerprinting-based indoor localization via WiFi has achieved a great breakthrough in the past decade. However, it suffers from an inherent problem that the localization accuracy declines sharply over time due to the dynamic environment and unstable WiFi devices. Researchers have designed many methods to update the localization model, e.g., crowdsourcing-based model updating, in order to maintain the localization accuracy. Unfortunately, they have not taken the privacy into consideration during the updating process. This will lead to a threat that the eavesdroppers could guess the location providers' private information according to the updating model. For the goal of maintaining the localization accuracy without the risk of privacy breaching, we proposed FLoc, a fingerprinting-based indoor localization system which updates the localization model via a federated learning framework. In FLoc, every provider maintains a local localization model in their own device. They will regularly encrypt the updating parameters and share them to a common model server. At the model server, it aggregates the encrypted information of the local models to maintain a general model, which will be sent back to the local devices for next updating iteration. We evaluate FLoc in an APs unknown laboratory corridor. The experiment results show that FLoc has a comparable localization performance. Moreover, it can successfully protect the providers' privacy, since the information transferred is all encrypted.

Modern bookcrossing leverages the mobile networks to help readers share books via convenient connection, and thus expedites the dissemination of information. However, the lack of traceability has significantly hindered the wide adoption of mobile bookcrossing, leading to loss of books. Meanwhile, the managerial inefficiency of current mobile bookcrossing systems becomes another obstacle for advancing the book circulation. To overcome these problems, we propose to leverage the promising blockchain technology with the merits of its immutability and cryptographic smart contract. In this paper, we present BookChain, a traceable and efficient blockchain-based innercampus book sharing system. BookChain stores the complete sharing data of an interested book permanently on blockchain, such that every reader can trace the borrowing history, which reduces the potential for loss of book. BookChain also introduces the use of smart contract to automate the circulation of books with minimal human intervention, resulting in the improvement of efficiency. The experimental results show the effectiveness and low-cost of the proposed system under high concurrent users.

Next-generation blockchain ecosystem will be fuelled by a large variety of blockchain systems. These systems increasingly demand proper cross-chain cooperation to provide richer functionalities and enhanced capabilities in the future landscape. How to enable such `interoperability' - effective communication and efficient data transfer across multiple blockchain systems is thus critical and facing many unprecedented theoretical and practical challenges. In this paper, we first clarify the definition of interoperability based on the cross disciplinary nature. Second, a roadmap of challenges needed to be addressed for interoperability has been laid out. Third, we articulate novel architectural approaches to fill in the gap by enforcing the interoperability from different blockchain layers.

The Big Data era and intelligent educational systems have empowered personalized learning. As one of the most effective personalized learning tools, Recommender Systems (RS) are applied for student performance prediction, and personalized content replenishment for learning remediation. A wide variety of context-aware RS for personalized learning have been devised and implemented, adherent with student's learning contexts such as location, time, and activity. Due to the physical constraints, today's education is still carried out at schools, making classes the indispensable and easily achievable context. Leveraging such information can be beneficial for performance improvement and effective learning recommendation in common classroom settings. In this work, we propose a novel approach, `Class Contextual Factor' (CCF)-based RS that synthesizes students' personal and class-level factors for better performances. More specifically, we first derive the CCF from a weighted Q-matrix to estimate students' mastery levels over KCs using an attribute-based recommendation technique. Then, we ensemble an item-based collaborative filtering algorithm for remedial exercise recommendation. By using a real world dataset from an online intelligent tutoring system, evaluations show that our CCF -based method outperforms the popular counterparts (i.e., IRT, RS with collaborative filtering), and is able to provide interpretable results for traceable learning remediation.

Disk failure has become a major concern with the rapid expansion of storage systems in data centers. Based on SMART (Self-Monitoring, Analysis and Reporting Technology) attributes, many researchers derive disk failure prediction models using machine learning techniques. Despite the significant developments, the majority of works rely on offline training and thereby hinder their adaption to the continuous update of forthcoming data, suffering from the 'model aging' problem. We are therefore motivated to uncover the root cause -- the dynamic SMART distribution for 'model aging', aiming to resolve the performance degradation as to pave a comprehensive study in practice.

In modern big data warehouse systems, we observe a common phenomenon that a column of data values can be derived from one or several other columns by transforming and concatenating these columns. We call this relationship between columns a Soft Concatenation Mapping (SCM). SCMs imply significant redundancy in the schema or data, and therefore can be exploited for data integration or data compression. In this paper, we formalize the problem of SCM detection and prove it is NP-hard. We then propose efficient approximate algorithms to detect all SCMs or an optimal set of SCMs in a table. Our experiments on both real-world and synthetic datasets show promising results.

In this paper, we present TICC, an automatic data compression component that can transparently eliminate data redundancies across columns in column-oriented database systems. We further propose two approaches to integrate inter-column compression into existing database systems. One approach is to use User Defined Functions (UDFs), and the other is native. We implement these two approaches on top of Hive based on the ORC file, a common data format in column stores, and evaluate the performance of TICC using real-world datasets. The experimental results demonstrate that TICC can significantly reduce the storage overhead and process a variety of queries over large-scale data with up to 20% performance improvement over the original Hive.

Hash Ripple join is an online aggregation algorithm that can rapidly give good approximate join results increases with the progress of the join operation and converges to the real result when the join finishes. Luo et al. proposed a parallel hash ripple join (PHRJ) that runs in a distributed setting. However, the PHRJ has two drawbacks when handling large-scale data: 1) PHRJ updates approximate results in fine grain which induces extra communication cost in a distributed environment 2) When data is out of memory, PHRJ cannot provide unbiased approximate result. In this thesis, a scalable hash ripple join is proposed that 1) runs on a distributed framework that can process distributed data in coarse-grain to speed up the join performance; 2) continuously gives unbiased and consistent approximate join results even in the presence of memory overflow; and 3) has good scalability handling growing amount of data. We have implemented a prototype of the scalable hash ripple join (SHRJ) algorithm on Spark. Experiment results show that SHRJ can give good approximate join result while taking less than 10% of the time of Spark's own join operator.

Gesture recognition has emerged recently as a promising application in our daily lives. Owing to low cost, prevalent availability, and structural simplicity, RFID shall become a popular technology for gesture recognition. However, the performance of existing RFID-based gesture recognition systems is constrained by unfavorable intrusiveness to users, requiring users to attach tags on their bodies. To overcome this, we propose GRfid, a novel device-free gesture recognition system based on phase information output by COTS RFID devices. Our work stems from the key insight that the RFID phase information is capable of capturing the spatial features of various gestures with low-cost commodity hardware. In GRfid, after data are collected by hardware, we process the data by a sequence of functional blocks, namely data preprocessing, gesture detection, profiles training, and gesture recognition, all of which are well-designed to achieve high performance in gesture recognition. We have implemented GRfid with a commercial RFID reader and multiple tags, and conducted extensive experiments in different scenarios to evaluate its performance. The results demonstrate that GRfid can achieve an average recognition accuracy of 96.5 and 92.8 percent in the identical-position and diverse-positions scenario, respectively. Moreover, experiment results show that GRfid is robust against environmental interference and tag orientations.

Rate adaptation is an essential component in today's wireless standards, which help approach the channel capacity and maximize the throughput. However, how to estimate the optimal data rate in a fluctuated channel remains of great concern. Previous wisdoms leverage PHY layer information for rate estimation, including confidence information like SoftPHY hints, and channel state information (CSI) measurements. However, when experiencing rapid time varying and frequency selective fading channel, the above metrics can be inaccurate. The reason roots from the fact that there are not enough cost-efficient pilots, which are pre-known symbols inserted in a packet for channel estimation. In this paper, we observe that by digging into both PHY layer decoder and upper layer protocol headers, more reliable data bits with high confidence level can be exploited. These data bits, termed smart pilot, can be used to calibrate the channel estimation measurements cost-efficiently. Based on the calibrated estimation, we further propose a novel greedy rate selection algorithm to track the optimal data rate, which successfully avoids the impact of deep fading subcarriers in both legacy 802.11a/g and 802.11n MIMO systems. Our experiments on GNU radio testbed show that SmartPilot quickly tracks the link variance, and improve the channel estimation accuracy by 87%. Furthermore, the trace driven simulation reveals that greedy rate selection algorithm predicts the data rate as good as the optimal rate adaptation algorithms for 802.11 standards.

Partially overlapped channels are barely used for concurrent transmission in WiFi networks, since they lead to collisions where the collided packets cannot be decoded successfully. In this paper, we observe that the actual corrupted symbols by partial-channel interference in OFDM-based WiFi networks are not as severe as we expected. There remains extra coding redundancy that can be exploited from the corrupted symbols, and utilized for packet recovery. Accordingly, we present a novel paradigm termed Piros, in order to Push the lImits of partially concurrent transmission in WiFi networks. Piros strategically leverages the coding redundancy according to the overlap portion in a distributed manner, and extracts useful decoding information from the corrupted symbols to decode the packet with partial-channel interference.

Reliable people counting is crucial to many urban applications. However, most existing people counting systems are sensor-based and can only work in some fixed gateways or checkpoints where sensors have been installed. This high dependence on the exact locations of sensors leads to low accuracy. To overcome these limitations, in this paper, we propose a smartphone-based people counting system, Wi-Counter, by leveraging the pervasive Wi-Fi infrastructure. To collect comprehensive Wi-Fi signals and people count information based on crowdsource, Wi-Counter first adopts a preprocessor to overcome the noisy, discrepant, and fragile data based on the Wiener filter and Newton interpolation. It then makes use of the designated five-layer neural network to learn the relation model between the Wi-Fi signals and the number of people. By analyzing the received Wi-Fi signals, Wi-Counter can estimate the number of people based on the resulting model. We have conducted experiments by implementing a prototype of Wi-counter based on smartphones and evaluated the system in terms of accuracy and power consumption in an indoor testbed covering an area of 96 m $^2$. Wi-Counter achieved a counting accuracy of up to 93% and exhibited reliable and robust performance resisting temporal environmental changes with negligible power usage.

Recently, there is a massive growth in the amount of wireless video traffics. To increase the network efficiency and cater to the needs of Quality of Experience (QoE), researchers propose hybrid MAC schemes, with multiple MAC protocols anchored in a single MAC layer. Different MAC protocols are selected for diverse users' requirements. However, the existing hybrid MAC mainly combines various MAC protocols in time domain. Only one type of traffic can be satisfied at a time, and others have to endure poor QoE. Meanwhile, the channel resources are not fully utilized due to coarse usage in time domain. Motivated by this, we propose FC-MAC, a Fine-grained Cognitive MAC for video streaming in wireless networks. Instead of dividing channel time into slots, FC-MAC splits the channel frequency into fine-grained subchannels, and hybrid different MAC protocols in frequency domain. By dynamically adjusting the bandwidth and the MAC protocols according to the users' needs and channel condition, FC-MAC ensures the QoE at low cost and achieves high multiplexing gain. We conduct extensive simulations to verify the effectiveness of FC-MAC. Numerous results show that compared with time domain hybrid MAC, FC-MAC achieves 190% performance gain.

Newly popular indoor location-based services (ILBS), when integrated with commerce and public safety, offer a promising land for wireless indoor localization technologies. WLAN is suggested to be one of the most potential candidates owing to its prevalent infrastructure (i.e., access points (APs)) and low cost. However, the overall performance can be greatly degraded by the spatial localizability variance problem, i.e., the localization accuracy across various locations may have significant differences given any fixed AP deployment. As a result, it brings in user experience inconsistency which is unfavorable for ILBS. In this paper, we propose NomLoc - an indoor localization system using nomadic APs to address the performance variance problem. The key insight of NomLoc is to leverage the mobility of nomadic APs to dynamically adjust the WLAN network topology. A space partition (SP)-based localization algorithm is tailored for NomLoc to perform calibration-free positioning. Moreover, fine-grained channel state information (CSI) is employed to mitigate the performance degradation of the SP-based method due to multipath and none-line-of-sight (NLOS) effects. We have implemented the NomLoc system with off-the-shelf devices and evaluated the performance in two typical indoor environments. The results show that NomLoc can greatly mitigate spatial localizability variance and improve localization accuracy with the assistance of nomadic APs as compared with the corresponding static AP deployment. Moreover, it is robust to the position error of nomadic APs.

Rate adaptation is an essential component in today's wireless standards, for its ability to adaptively approach the channel capacity, and maximize the system throughput. The difficulty in rate adaptation stems from estimating the optimal data rate in a fluctuated channel. Previous wisdoms leverage PHY layer information for rate estimation, such as Soft PHY hints or Channel State Information. These information solely comes from one same layer, which are insufficient to track the optimal data rate. We observe that by investigating the information in both PHY layer decoder and upper layer protocol headers, more pilots can be exploited to estimate the optimal data rate across both time and frequency domain. These smart pilots help remove the residual channel effect and calibrate the CSI with minimum overhead. Based on the calibrated CSI, we propose a novel greedy rate selection algorithm to harness frequency diversity, which obtains the optimal data rate over all the subcarriers. Our experiments on GNU radio test bed show that Smart Pilot quickly tracks the link variance, and reduces the residual channel effect by 87%. Further, the trace driven simulation reveals that greedy rate selection algorithm predicts the data rate as good as the optimal rate adaptation algorithms for 802.11 standards.

Ocean covers nearly 71% of our planet's surface, yet 95% of the ocean remains unexplored by human being, and wireless sensor networks are envisioned to perform monitoring tasks over the large portion of our world. However, deploying wireless sensor networks on the sea poses many challenges and for maritime surveillance security applications we may need to deploy sensors both on the sea surface and underwater for three-dimensional detection. In this paper, we propose a hybrid ocean sensor networks called Double-head maritime Sensor Networks (DSNs), which combine the advantages of wireless sensor networks and underwater acoustic sensor networks. By leveraging the unique characteristics of DSNs, we design a localization scheme LDSN which is consisted of two algorithms SML and FLA. We first use SML to localize moored anchor nodes as seed nodes. After the underwater sensor networks have been localized, the floating double-head nodes can figure out its instant position via FLA algorithm. We evaluate the scheme by simulations and the results show that the scheme can achieve a high localization accuracy.

It is known that current fixed spectrum assignment policy has made the spectrum resource significantly underutilized. As a promising solution, cognitive radio emerges and shows its advantages. It allows the unlicensed users to opportunistically access the spectrum not used by the licensed users. To ensure that the unlicensed users can identify the vacate spectrum fast and accurately without interfering the licensed users, cooperative sensing is explored to improve the sensing performance by leveraging spatial diversity. However, cooperation gain can be compromised dramatically with cooperation overhead. Furthermore, when sensing decisions are made, contention on spectrum access also contributes a lot to the control overhead, especially in the distributed networks. Motivated by this, we propose a novel MAC design, termed Frequency domain Cooperative sensing and Multi-channel contention (FCM) for Cognitive Radio Ad Hoc Networks (CRAHNs). FCM is proposed for OFDM (Orthogonal Frequency Division Multiplexing) modulation based communication systems, which moves cooperative sensing and multi-channel contention from time domain into frequency domain. Therefore, control overhead caused by cooperation and contention can be significantly reduced. Meanwhile, the sensing and access performance can be both guaranteed. Extensive simulation results show that FCM can effectively reduce the control overhead, and improve the average throughput by 220% over Traditional Cooperative MAC for CRAHNs.

Many emerging applications such as intruder detection and border protection drive the fast increasing development of device-free passive (DfP) localization techniques. In this paper, we present Pilot, a Channel State Information (CSI)-based DfP indoor localization system in WLAN. Pilot design is motivated by the observations that PHY layer CSI is capable of capturing the environment variance due to frequency diversity of wideband channel, such that the position where the entity located can be uniquely identified by monitoring the CSI feature pattern shift. Therefore, a ``passive'' radio map is constructed as prerequisite which include fingerprints for entity located in some crucial reference positions, as well as clear environment. Unlike device-based approaches that directly percepts the current state of entities, the first challenge for DfP localization is to detect their appearance in the area of interest. To this end, we design an essential anomaly detection block as the localization trigger relying on the CSI feature shift when entity emerges. Afterwards, a probabilistic algorithm is proposed to match the abnormal CSI to the fingerprint database to estimate the positions of potential existing entities. Finally, a data fusion block is developed to address the multiple entities localization challenge. We have implemented Pilot system with commercial IEEE 802.11n NICs and evaluated the performance in two typical indoor scenarios. It is shown that our Pilot system can greatly outperform the corresponding best RSS-based scheme in terms of anomaly detection and localization accuracy.

Indoor positioning systems have received increasing attention for supporting location-based services in indoor environments. WiFi-based indoor localization has been attractive due to its open access and low cost properties. However, the distance estimation based on received signal strength indicator (RSSI) is easily affected by the temporal and spatial variance due to the multipath effect, which contributes to most of the estimation errors in current systems. In this work, we analyze this effect across the physical layer and account for the undesirable RSSI readings being reported. We explore the frequency diversity of the subcarriers in orthogonal frequency division multiplexing systems and propose a novel approach called FILA, which leverages the channel state information (CSI) to build a propagation model and a fingerprinting system at the receiver. We implement the FILA system on commercial 802.11 NICs, and then evaluate its performance in different typical indoor scenarios. The experimental results show that the accuracy and latency of distance calculation can be significantly enhanced by using CSI. Moreover, FILA can significantly improve the localization accuracy compared with the corresponding RSSI approach.

Radio spectrum resource is shown to be significantly underutilized with fixed spectrum assignment policy. As a promising solution, cognitive radio allows unlicensed users to opportunistically access the spectrum not used by the licensed users. Cooperative sensing is further exploited to improve the sensing performance of unlicensed users by leveraging spatial diversity. However, cooperation gain can be compromised dramatically with cooperation overhead. Furthermore, when sensing decisions are made, contention on spectrum access also becomes an overhead, especially in the distributed networks. Motivated by this, we propose a novel MAC design, termed Frequency domain Cooperative sensing and Multi-channel contention (FCM). FCM moves cooperative sensing and multi-channel contention from time domain into frequency domain. Thus, the control overhead caused by cooperation and contention can be significantly reduced, without reducing the sensing and access performance. Extensive simulation results show that FCM can effectively reduce the control overhead, and improve the average throughput by 220% over Traditional Cooperative MAC for CRAHNs.

WLAN-based indoor location fingerprinting has been attractive owing to the advantages of open access and high accuracy. Most fingerprinting-based systems so far rely on the received signal strength (RSS), which can be easily measured at the receiver with commercial WLAN equipment. However, RSS is a coarse value which simply measures the received power for a whole channel. Thus, it fluctuates over time in typical indoor environments with rich multipath effects and not unique for a specific location. In this paper, we present the design, implementation, and evaluation of a Fine-grained Indoor Fingerprinting System (FIFS). FIFS explores a PHYlayer Channel State Information (CSI) that specifies the channel status over all the subcarriers for location fingerprinting in WLAN. The system leverages the CSI values including different amplitudes and phases at multiple propagation paths, known as the frequency diversity, to uniquely manifest a location. Moreover, the multiple antennas provides the spatial diversity that can be further augmented in fingerprinting. We also present a coherence bandwidth-enhanced probability algorithm with a correlation filter to map object to the fingerprints. We conducted experiments in two typical indoor scenarios with commercial IEEE 802.11 NICs. The experimental results demonstrate that the overall positioning accuracy can be improved compared with the RSS-based Horus system.

Device-free passive (Dfp) motion detection seeks to monitor the position change of entities without actively carrying any physical devices. Recently, WLAN with a rich set of installed wireless infrastructures enables motion detection in the area of interest. WLAN-enabled DfP motion detection rely on received signal strength (RSS) is verified to be able to provide acceptable high accuracy. Although RSS can be easily measured with commercial equipments, it is suspectable to measurement itself due to multipath effect in indoor environment. In this paper, we present an Indoor device-free Motion Detection system (FIMD) to overcome the preceding RSS-based limitation. FIMD explores properties of Channel State Information (CSI) from PHY layer in OFDM system. FIMD is designed based on the insight that CSI maintains temporal stability in static environment, while exhibits burst patterns when motion takes place. Motivated by this observation, FIMD uses a novel feature extracted from CSI to leverage its temporal stability and frequency diversity. The motion detection is conducted with outliers identification from normal features in continuous monitoring using density-based DBSCAN algorithm. Moreover, we leverage two schemes including false alert filter and data fusion to enhance the detection accuracy. We implement FIMD system with commercial IEEE 802.11n NICs and evaluate its performance in two typical indoor scenarios. Experiment results show that FIMD can achieve high detection rate. Moreover, comparing with RSSI, the feature extracted from CSI enables better detection performance in accuracy and robustness to narrowband interference.

Indoor positioning systems have received increasing attention for supporting location-based services in indoor environments. WiFi-based indoor localization has been attractive due to its open access and low cost properties. However, the distance estimation based on received signal strength indicator (RSSI) is easily affected by the temporal and spatial variance due to the multipath effect, which contributes to most of the estimation errors in current systems. How to eliminate such effect so as to enhance the indoor localization performance is a big challenge. In this work, we analyze this effect across the physical layer and account for the undesirable RSSI readings being reported. We explore the frequency diversity of the subcarriers in OFDM systems and propose a novel approach called FILA, which leverages the channel state information (CSI) to alleviate multipath effect at the receiver. We implement the FILA system on commercial 802.11 NICs, and then evaluate its performance in different typical indoor scenarios. The experimental results show that the accuracy and latency of distance calculation can be significantly enhanced by using CSI. Moreover, FILA can significantly improve the localization accuracy compared with the corresponding RSSI approach.