Contribution evaluation is essential for incentivizing high-quality data sharing in federated learning (FL), yet existing Shapley-value-based methods are prohibitively expensive and overlook temporal influence propagation. In this paper, we propose Ripple Shapley, a novel attribution framework that enables accurate, real-time data valuation within a single federated training run. Our method decomposes each sample’s impact into an instantaneous drop term and a recursive ripple term, the latter capturing downstream influence via a Jacobian chain over global updates. To scale computation, we introduce a low-rank approximation of the Jacobian product and construct a shared subspace for efficient ripple accumulation. Extensive experiments on CIFAR-10 and MNIST show that Ripple Shapley achieves up to 62× speedup over existing Shapley-based FL methods while maintaining high attribution fidelity, significantly improving efficiency, robustness, and fairness in federated environments. We further demonstrate its effectiveness in dynamic federated learning scenarios and its potential for real-time data pricing.

With the rapid growth of data, redundancy among different users in cloud environments has become increasingly prominent. Detecting and removing these redundant parts can effectively improve storage efficiency. But these processes may dramatically degrade the system performance, especially when dealing with similar data. Although deduplication and delta compression are common data reduction techniques, their high overhead can outweigh the benefits. As a result, users often cannot determine in advance whether compression is worthwhile for their datasets. Some approaches have attempted to solve this, but each has important limitations. Danny Harnik et al. proposed a sampling-based deduplication estimation method using linear programming, which efficiently estimates redundancy from exact duplicates. However, it fails to capture redundancy arising from similar data, thus underestimating the full compression potential. To address this limitation, we propose Smart-to-Compress, a predictive compression decision framework. We introduce the Super Feature Frequency Histogram (SFH) to capture redundancy among similar data. Combined with the Duplication Frequency Histogram (DFH), our method estimates the overall Data Reduction Ratio (DRR) without scanning the entire dataset. Furthermore, we design a game-theoretic decision model to weigh compression benefits against predicted costs, providing users with guidance on whether compression should be applied. Experiments on real-world datasets show that our method accurately predicts compression value, reduces unnecessary overhead, and offers reliable decision-making support for users.

Post-deduplication in traditional cloud environments primarily focuses on single-node, where delta compression is performed on the same deduplication node located on server side. However, with data explosion, the multi-node post-deduplication, also called global deduplication, has become a hot issue in research communities, which aims to simultaneously execute delta compression on data distributed across all nodes. Simply setting up single-node deduplication systems on multi-node environments would significantly affect storage utilization and incur secondary overhead from file migration. Nevertheless, existing global deduplication solutions suffer from lower data compression ratios and high computational overhead due to their resemblance detection's inherent limitations and overly coarse granularities. Similar blocks typically have high correlations between sub-blocks; inspired by this observation, we propose IBNR (Intra-Block Neighborhood Relationship-Based Resemblance Detection for High-Performance Multi-Node Post-Deduplication), which introduces a novel resemblance detection based on relationships between sub-blocks and determines the ownership of blocks in entry stage to achieve efficient global deduplication. Furthermore, the by-products of IBNR have shown powerful scalability by replacing internal resemblance detection scheme with existing solutions on practical workloads. Experimental results indicate that IBNR outperforms state-of-the-art solutions, achieving an average 1.99× data reduction ratio and varying degrees of improvement across other key metrics.

Detecting similar data is crucial for optimizing file storage and transmission in HTTP protocols and Content Delivery Networks. Traditional MinHash methods encounter significant efficiency challenges due to their reliance on K-shingle structures, resulting in high computational costs and storage requirements. Additionally, these methods expose privacy risks in cloud environments, where sensitive information can be inferred from MinHash signatures. To address both efficiency and security concerns, we propose Horse-MinHash, which integrates a fast, content-defined feature extraction scheme with a non-interactive zero-knowledge proof-based similarity estimation method. Our approach significantly enhances computational efficiency while ensuring robust privacy protection by preventing plaintext exposure. Experimental results demonstrate that Horse-MinHash achieves lower mean squared error in Jaccard similarity estimation and reduces time overhead for average block sizes of 16 KB or more, outperforming state-of-the-art methods.

Cloud storage is widely used for flexible and efficient data management, yet redundant data across users requires storage optimization. Deduplication helps by storing only unique data, making data sharing and ownership verification essential post-deduplication. Current Proof of Ownership (PoW) methods rely on interactive communication, leading to delays and performance issues during intensive data operations, and often assume a level of trust that may not hold in practical scenarios. To overcome these issues, we propose ES-PoW, a non-interactive secure proof of ownership scheme for cloud storage. ES-PoW performs ownership verification in a single round, avoiding delays in block verification. Using modular exponentiation and the discrete logarithm problem, ES-PoW generates and verifies ownership proofs efficiently. Unlike previous schemes, ES-PoW is resilient against brute-force, replay, and Man-in-the-Middle attacks, without relying on trusted nodes, making it better suited to real-world applications. Experimental results show that ES-PoW reduces I/O operation time and accelerates computation, achieving up to 53.6× and 54.5× speed improvements over current methods.

With the widespread adoption of cloud storage, effectively identifying and eliminating redundant data among users while ensuring data security has become a significant challenge. However, traditional similarity detection methods has limitations in privacy protection. Although conventional encryption techniques can safeguard privacy, they have difficulty detecting redundancy between similar blocks. Thus, we propose a secure reduction of redundant and similar data for cloud storage to address these challenges based on zero-knowledge proof (Sec-Reduce), called Sec-Reduce. It first employs a novel zero-knowledge proof technique for file-level redundancy detection, where redundant files are identified and excluded from storage. To further determine the similarity of non-redundant files, the scheme performs content-based chunking and feature extraction using a similarity feature extraction method. These extracted features are then encrypted using the approximate homomorphic encryption scheme Cheon-Kim-Kim-Song (CKKS) to enable similarity detection in the ciphertext environment. Finally, secure delta encoding is applied to store unique ciphertext blocks and deltas. Evaluations of real-world datasets demonstrate that Sec-Reduce achieves higher storage savings than existing encrypted storage methods, with storage overhead comparable to plaintext storage and only moderate performance overhead.

Recently, Oblivious Storage has been proposed to prevent privacy leakage from user access patterns, which obfuscates and makes it computationally indistinguishable from the random sequences by fake accesses and probabilistic encryption. The same data exhibits distinct ciphertexts. Thus, it seriously impedes cloud providers’ efforts to improve storage utilization to remove user redundancy, which has been widely used in the existing cloud storage scenario. Inspired by the successful adoption of removing duplicate data in cloud storage, we attempt to integrate obliviousness, remove redundancy, and propose a practical oblivious storage, PEO-Store. Instead of fake accesses, introducing delegates breaks the mapping link between a valid access pattern and a specific client. The cloud interacts only with randomly authorized delegates. This design leverages non-interactive zero-knowledge-based redundancy detection, discrete logarithm problem-based key sharing, and secure time-based delivery proof. These components collectively protect access pattern privacy, accurately eliminate redundancy, and prove the data delivery among delegates and the cloud. Theoretical proof demonstrates that, in our design, the probability of identifying the valid access pattern with a specific client is negligible. Experimental results show that PEO-Store outperforms state-of-the-art methods, achieving an average throughput of up to 3 times faster and saving 74% of storage space.

With the increasing number of big data applications, large amounts of valuable data are distributed in different organizations or regions. Federated Learning (FL) enables collaborative model training without sharing sensitive data and is widely used in AI medical diagnosis, economy, and autonomous driving scenarios. However, it still leaks the privacy from the gradient exchange in federated learning. What’s worse, state-of-the-art work, such as Batchcrypt, still suffers from computational overhead due to a considerable amount of computation and communication costs caused by homomorphic encryption. Therefore, we propose a novel symmetric key-based homomorphic encryption scheme, Sym-Fed. To unleash the power of symmetric encryption in federated learning, we combine random masking with symmetric encryption and keep the homomorphic property during the gradient exchange in the federated learning process. Finally, the security analysis and experimental results on real workloads show that our design achieves performance improvement 6× to 668× and reduces the communication overhead 1.2× to 107× compared with the state-of-the-art work, BatchCrypt and FATE, without model accuracy degradation and security compromise.

With intelligent devices’ prevalence, mobile edge computing (MEC) technology can effectively process the massive data in the Internet of Things (IoT). The metadata produced in MEC plays a role in colossal data management. However, it also includes lots of user privacy information. Traditional privacy protection solutions sacrifice the metadata’s availability or are incompatible with the distributed environment. To overcome this dilemma, we propose a blockchain-based secure searching strategy for metadata (BSSMeta) in MEC. By leveraging a lightweight proxy re-encryption scheme and a decentralized key generation method on the blockchain, BSSMeta keeps the security of the metadata searching tasks. Meanwhile, a main/secondary smart contract method and a buffer uploading strategy are proposed for the efficiency of the searching and uploading processes. As a byproduct, BSSMeta also supports searching metadata in a multiuser environment and gives users access control to metadata. Finally, we provide a security analysis of BSSMeta and implement a prototype on the Hyperledger Fabric platform. The results of experiments on various workloads show that BSSMeta is feasible and flexible in security and efficiency.

With the prevalence of cloud storage, people prefer to outsource their data to the cloud for flexibility and reliability. Undoubtedly, there are lots of redundancy among these data. However, high-end storage with deduplication costs heavy computation and increases the data management complexity. Potential customers need the redundancy proportion information of their outsourced data to decide whether high-end storage with deduplication is worthwhile. Thus, many researchers have previously attempted to predict the redundant ratio. However, existing mechanisms ignore the redundancy proportion among similar chunks containing many duplicate data. Although resemblance detection, detecting the duplicate parts among similar data, has become a hot issue, it is hardly applied to the conventional deduplication ratio estimation because of unacceptable calculation cost. Therefore, we analyze the limitations and challenges of deduplication ratio prediction in prediction scope and response time and further propose a novel prediction scheme. By leveraging the context-aware resemblance detection, and confidence interval theory, our method can achieve faster estimation speed with higher accuracy in deduplication ratio compared with the state-of-the-art work. Finally, the results show that our method can efficiently and effectively estimate the proportion of duplicate chunks and redundant data among similar chunks by conducting experiments on real workloads.

In this paper, we propose a novel chunk-context-aware resemblance detection al-gorithm called CARD. By introducing machine learning into deduplication, the chunk feature will embed the chunk-context information after the N-sub-chunk shingles based initial feature extraction and BP-Neural network training. In the predicting process, each chunk's initial feature corresponds to a chunk-context feature. Finally, the cloud calculates the different part among resemblance chunks based on these feature by delta encoding. Only the different part is stored. The basic workflow corresponds to Figure 1. For more detailed illustrations, please see our full paper here

Recently, cloud storage has been widely used in our daily life. And there are lots of redundancy among these outsourced data. Conventional deduplication technology efficiently splits these data at the chunk level and removes the duplicate chunks to save the network bandwidth and improve the cloud storage utility. But it ignores the redundancy among similar chunks. Resemblance detection has recently become a hot issue with detecting these redundant parts among similar data. CARD, the state-of-the-art work, can efficiently and effectively remove these redundancies by introducing the neural network with resemblance detection. However, the source domain of the CARD model may have an explicitly different input distribution. The cloud cannot deal with the possible future domain data based on CARD design. This cross-domain setting may serials degrades the performance of CARD. To overcome this problem, we propose a cross-domain resemblance detection scheme called MetaContext. Integrating the chunk-context aware model and the learn-to-learn idea can produce a more robust chunk feature than CARD. As a byproduct, it also outperforms the CARD in speed. Finally, we implement the MetaContext and conduct serial experiments on real workloads. The results show that our method can efficiently and effectively detect and remove the redundancy among similar data.

Abstract Chunking is one of the most important processes in a secure deduplication system. It determines the deduplication ratio, metadata size, and the encryption key number. Existing chunking algorithms can be categorized as client‐side chunking algorithm and the server‐aid chunking algorithm. Although the former one can directly be applied into the secure deduplication, it ignores the management overhead caused by the metadata size and encryption key number. Thus, the conventional server‐aid chunking algorithm is proposed. However, it is not secure because the interaction between the client and the server is based on the plaintext. Thus, we propose a two‐party secure server‐aid chunking algorithm, TSS. It supports the secure server‐aid interaction and reduces the metadata size and the encryption key number in the secure deduplication with a comparable deduplication ratio. The theoretical proof and experimental results show that our method outperforms the state‐of‐the‐art chunking algorithm, elastic chunking algorithm.

With the growing popularity of cloud storage, how to prevent information leakage from cloud access patterns attracts great attention. Oblivious RAM is proposed for this purpose. It is designed for the memory system, and most existing work focused on improving performance in the main memory. Recently, ORAM has been extended to the cloud environment, and it is called Oblivious Data Storage. TaoStore, the state-of-the-art oblivious data storage system, integrates the ORAM technology with synchronous I/O technology to reduce the mean response time. As we observed, there is a strong locality existing in user accesses. However, existing Oblivious Storage research did not consider this. In this article, we propose Loco-Store, an oblivious data storage. In Loco-Store, we design a novel stash controller scheme that can dynamically group relevant blocks during the oblivious I/O processes. We also propose a locality-based eviction algorithm to keep the security guarantee. The theoretical proof proves that our scheme keeps the security definition of ORAM. Finally, we implement a prototype and conduct extensive experiments on real-world datasets. The results show that Loco-Store can save the network bandwidth consumption up to 39.19 percent, and reduce the overall access time by 26.17 percent

With the prevalence of cloud storage, data deduplication has been a widely used technology by removing cross users’ duplicate data and saving network bandwidth. Nevertheless, traditional data deduplication hardly detects duplicate data among resemblance chunks. Currently, a resemblance data deduplication, called Finesse, has been proposed to detect and remove the duplicate data among similar chunks efficiently. However, we observe that the chunks following the similar chunk have a high chance of resembling data locality property, and vice versa. Processing these adjacent similar chunks in small average chunk size level increases the metadata, which deteriorates the deduplication system performance. Moreover, existing resemblance data deduplication schemes ignore the performance impact from metadata. Therefore, we propose a fast variable-grained resemblance data deduplication for cloud storage. It dynamically combines the adjacent resemblance chunks or unique chunks or breaks those chunks, located at the transition region between resemblance chunks and unique chunks. Finally, we implement a prototype and conduct a serial of experiments on real-world datasets. The results show that our method dramatically reduces the metadata size while achieving the high deduplication ratio.

Summary The amount of outsourced data grows rapidly. In recent years, cloud service providers integrate data deduplication systems with convergent encryption (CE) methods, in which a file encryption key is determined by its own content instead of the secret of a specific user, to save the storage cost and ensure the security of outsourced data. However, present secure deduplication systems failed to deal with data modifications efficiently. We observe that when a client makes small changes on an existing file, the current chunking algorithms cannot effectively detect the similarities and always create chunks with largely overlapped contents. It reduces data deduplication ratios and results in unnecessary overhead. In this paper, we propose Sed‐Dedup, an efficient secure delta encoding deduplication system to address this problem. In Sed‐Dedup, we introduce a novel delta encoding approach to store modified contents in delta files and leave the original files intact. Two schemes with different encoding policies are designed. Both of them can solve the issue and improve the secure deduplication performance. To evaluate the performance, we implement a prototype and conduct extensive experiments based on synthetic and real‐world datasets. Our experimental results show that Sed‐Dedup is superior to the state‐of‐the‐art secure deduplication systems.

Android usually employs the Secure Socket Layer (SSL) protocol to protect the user’s privacy in network transmission. However, developers may misuse SSL-related APIs, which would lead attackers to steal user’s privacy through man-in-the-middle attacks. Existing methods based on static decompiling technology to detect SSL security vulnerabilities of Android applications cannot cope with the increasingly common packed applications. Meanwhile, dynamic analysis approaches have the disadvantages of excessive resource consumption and time-consuming. In this paper, we propose a dynamic method to solve this issue based on our novel automatic traversal model. At first, we propose several new traversal strategies to optimize the widget tree according to the user interface (UI) types and the interface state similarity. Furthermore, we develop a more granular traversal model by refining the traversal level from the Activity component to the Widget and implement a heuristic depth-first traversal algorithm in combination with our customized traversal strategy. In addition, the man-in-the-middle agent plug-in is extended to implement real-time attack test and return the attack results. Based on the above ideas, we have implemented SSLDetecter, an efficient automated detection system of Android application SSL security vulnerability. We apply it on multiple devices in parallel to detect 2456 popular applications in several mainstream application markets and find that 424 applications are suffering from SSL security vulnerabilities. Compared with the existing system SMV-HUNTER, the time efficiency of our system increases by 38% and the average detection rate increases by 6.39 percentage points, with many types of SSL vulnerabilities detected.

With the popularity of cloud computing, mobile devices can store/retrieve personal data from anywhere at any time. Consequently, the data security problem in mobile cloud becomes more and more severe and prevents further development of mobile cloud. There are substantial studies that have been conducted to improve the cloud security. However, most of them are not applicable for mobile cloud since mobile devices only have limited computing resources and power. Solutions with low computational overhead are in great need for mobile cloud applications. In this paper, we propose a lightweight data sharing scheme (LDSS) for mobile cloud computing. It adopts CP-ABE, an access control technology used in normal cloud environment, but changes the structure of access control tree to make it suitable for mobile cloud environments. LDSS moves a large portion of the computational intensive access control tree transformation in CP-ABE from mobile devices to external proxy servers. Furthermore, to reduce the user revocation cost, it introduces attribute description fields to implement lazy-revocation, which is a thorny issue in program based CP-ABE systems. The experimental results show that LDSS can effectively reduce the overhead on the mobile device side when users are sharing data in mobile cloud environments.

Data chunking is one of the most important issues in a deduplication system, which not only determines the effectiveness of deduplication such as deduplication ratio, but also impacts the modification overhead. It breaks the file into chunks to find out the redundancy by fingerprint comparisons. The content-defined chunking algorithms such as TTTD, BSW CDC, and RC, can resist the boundary shift problem caused by small modifications. However, we observe that there exist a lot of consecutive maximum chunk sequences in various benchmarks. These consecutive maximum chunk sequences will lead to local boundary shift problem when facing small modifications. Based on this observation, we propose a new chunking algorithm, Elastic Chunking. By leveraging dynamic adjustment policy, elastic chunk can quickly find the boundary to remove the consecutive maximum chunk sequences. To evaluate the performance, we implement a prototype and conduct extensive experiments based on synthetic and realistic datasets. Compared with TTTD, BSW CDC and RC algorithms, proposed chunking algorithm can achieve the higher deduplication ratio and throughput.

Sorting is a basic computational task in Computer Science. As a variant of the sorting problem, top-k selecting have been widely used. To our knowledge, on average, the state-of-the-art top-k selecting algorithm Partial Quicksort takes C(n, k) = 2(n+1)Hn+2n-6k+6-2(n+3-k)Hn+1-k comparisons and about C(n, k)/6 exchanges to select the largest k terms from n terms, where Hn denotes the n-th harmonic number. In this paper, a novel top-k algorithm called DC-Top-k is proposed by employing a divide-and-conquer strategy. By a theoretical analysis, the algorithm is proved to be competitive with the state-of-the-art top-k algorithm on the compare time, with a significant improvement on the exchange time. On average, DC-Top-k takes at most (2-1/k)n+O(klog2k) comparisons and O(klog2k) exchanges to select the largest k terms from n terms. The effectiveness of the proposed algorithm is verified by a number of experiments which show that DC-Top-k is 1-3 times faster than Partial Quicksort and, moreover, is notably stabler than the latter. With an increase of k, it is also significantly more efficient than Min-heap based top-k algorithm (U. S. Patent, 2012). In the end, DC-Top-k is naturally implemented in a parallel computing environment, and a better scalability than Partial Quicksort is also demonstrated by experiments.

Summary Trust in social network draws more and more attentions from both the academia and industry fields. Public opinion analysis is a direct way to increase the trust in social network. Because the public opinion analysis can be expressed naturally by the graph algorithm and graph data are the default data organization mechanism used in large‐scale social network service applications, more and more research works apply the graph processing system to deal with the public opinion analysis. As the data volume is growing rapidly, the distributed graph systems are introduced to process the large‐scale public opinion analysis. Most of graph algorithms introduce a large number of data iterations, so the synchronization requirements between successive iterations can severely jeopardize the effectiveness of parallel operations, which makes the data aggregation and analysis operations become slower. In this paper, we propose a large‐scale graph data processing system to address these issues, which includes a graph data processing model, Arbor. Arbor develops a new graph data organization format to represent the social relationship, and the format can not only save storage space but also accelerate graph data processing operations. Furthermore, Arbor substitutes time‐constrained synchronization operations with non‐time‐constrained control message transmissions to increase the degree of parallelism. Based on the system, we put forward two most frequently used graph applications on Arbor: shortest path and PageRank. In order to evaluate the system, we compare Arbor with the other graph processing systems using large‐scale experimental graph data, and the results show that it outperforms the state‐of‐the‐art systems. Copyright © 2014 John Wiley & Sons, Ltd.

In this paper, we propose Marbor, a novel graph data processing framework to analyze the large-scale data in social network services. It develops an efficient graph organization model to minimize the costs of graph data accesses and reduce the memory consumption. In addition, we present a novel control message method in Marbor to improve the synchronization iterations performance. During the graph data processing, in each iteration, it analyzes the relationships among tasks and forwards the tasks to the next iteration with control messages, so no synchronization operations are used. We compare Marbor with other graph processing methods on several large-scale real world SNS datasets with two widely used applications, and the results show that Marbor outperforms the current mechanisms.

Nowadays, log sequences mining techniques are widely used in detecting anomalies for Internet services. The state-of-the-art anomaly detection methods either need significant computational costs, or require specific assumptions that the test logs are holding certain data distribution patterns in order to be effective. Therefore, it is very difficult to achieve real time responses and it greatly reduces the effectiveness of these mechanisms in reality. To address these issues, we propose an innovative anomaly detection strategy called CADM. In CADM, the relative entropy between test logs and normal logs is exploited to discover the anomalous levels. Instead of calculating the relative entropy based on certain predefined data distribution models, our solution inspects the relationship between relative entropy and compression size with an improved grammar-based compression method. No assumptions are needed. In addition, our mechanism has excellent scalability with only O(n) computational complexity. It can generate the detection results on the fly. Experimental analysis with both synthetic and real world logs proves that CADM is superior to the other methods. It can achieve very high anomaly detection accuracy with the minimal computational overhead. It is suitable for log mining tasks and can be applied on a broad variety of application fields.

SUMMARY Key‐value stores are widely used on large‐scale data management in the cloud environment. However, they can only naturally support key‐based queries, and do not have efficient solutions for value‐based queries. Thus, dealing with high‐dimensional data in key‐value stores is still a big challenge. State‐of‐the‐art solutions apply value‐based tree‐structure indexes to solve this issue. These methods suffer from the curse of dimensionality and cannot achieve satisfactory performance. They also bring serious load unbalancing problem among servers, and result in dramatic system scalability degradation. Meanwhile, similarity search in high‐dimensional data space becomes more and more popular in today's cloud applications. Due to the lack of efficient algorithms for value‐based queries, users have to wait for a long time before the results are returned. To address this issue, we propose a novel approach called high‐dimensional similarity query in key‐value stores (HDKV), which can generate similarity results in a short time and maintain good database scalability. In HDKV, a strict order‐preserving hash function is designed to map nearby objects in the high‐dimensional space onto adjacent keys of a continuous linear space in key‐value stores. With this strategy, many expensive random accesses are replaced with more efficient scan accesses. The experimental evaluation on real world data set shows that compared to the state‐of‐the‐art methods, HDKV can dramatically reduce the search time with little impact on the accuracy. Copyright © 2012 John Wiley & Sons, Ltd.

Cloud computing is becoming increasingly prevalent in recent years. It introduces an efficient way to achieve management flexibility and economic savings for distributed applications. To take advantage of computing and storage resources offered by cloud service providers, data owners must outsource their data onto public cloud servers which are not within their trusted domains. Therefore, the data security and privacy become a big concern. To prevent information disclosure, sensitive data has to be encrypted before uploading onto the cloud servers. This makes plain text keyword queries impossible. As the total amount of data stored in public clouds accumulates exponentially, it is very challenging to support efficient keyword based queries and rank the matching results on encrypted data. Most current works only consider single keyword queries without appropriate ranking schemes. The multi-keyword query problem was being considered only recently. MRSE [1] is one of the first research works to define and address the problem of effective yet secure ranked multi-keyword search over encrypted cloud data. However, the keyword dictionary used in MRSE is static and must be rebuilt when the number of keywords in the dictionary increases. It also has severe out-of-order problems in the matching results and does not take the keyword access frequencies into account, which greatly affects its usability. In this paper, we propose a novel approach, called MKQE, to address these issues. Only minor changes in the dictionary structure have to be done when extra keywords are introduced. We also introduce new trapdoor generation and scoring algorithms to make in-order query results. Furthermore, the keyword access frequency is considered so as to select an adequate matching file set. We conduct extensive simulations and the results prove that our approach performs much better than previous solutions.

Large-scale search engines use hard disk drives (HDD) to store the mass index data for their capacity, whose performances are limited by the relatively low I/O performance of HDD. Caching is an effective optimization, and many caching algorithms have been proposed to improve retrieval performance. Considering the high cost of memory and huge amounts of data, the limited capacity of cache in memory cannot resolve the above problem thoroughly. In this paper, we adopt a solid state disk (SSD) based storage architecture, which uses SSD as a secondary cache for memory. We analyze the I/O patterns of search engines and propose SSD-based data management policies based on the hybrid storage architecture, including data selection, data placement and data replacement. Our main goal is to improve the performance of search engines while reducing operation cost inside SSD. The experimental results demonstrate the proposed architecture improves the hit ratio by 13.31%, the performance by 41.05%, the average access time inside SSD by 43.83%, and reduces block erasure operations by 71.52%.

NAND flash memory based Solid State Drive (SSD) is increasingly popular as one of the major non-volatile storage devices. Due to the superior performance and energy efficiency properties, it becomes an important complimentary device between the main memory and the traditional mechanical Hard Disk Drive (HDD). It is also anticipated to substitute HDD as the mainstream secondary storage. Today, flash memory is widely used in embedded systems, hand-held devices, personal computers and even enterprise computer systems. To access the data on the flash, a software component called Flash Translation Layer (FTL) has to be applied to convert the file system logical address into the corresponding physical address. FTL has great impacts on the system overall performance. Numerous FTL algorithms have been proposed in the past decade. DFTL is one of the most popular page-level address mapping FTL algorithms. It has been considered to have the best flexibility. However, it has extra mapping information I/O overhead and cannot always achieve the optimal performance. In this paper, we propose CAST, a novel and efficient pagelevel FTL algorithm to relieve this issue. CAST reserves a small portion of embedded SRAM to cache most recently accessed logical-physical address mapping information. Unlike DFTL, we use a compact packing methodology. Consecutive logical-physical page mapping information is represented with only a single entry. Thus, more address mapping information can be maintained in the caching table, and the cache hit rates can be increased. To improve the garbage collection efficiency, CAST maintains multiple current data blocks simultaneously. When a new data write request comes, the system can select an appropriate one to conduct the process based on the request issuer and/or logical address information. Our simulation results show that CAST outperforms DFTL under various workloads and it can reduce the number of erase operations and decrease the I/O response time significantly.

Today, P2P system is one of the largest Internet bandwidth consumers. In order to relieve the burden on Internet backbone and improve the user access experience, efficient caching strategies should be applied. However, due to its autonomous nature, a fully distributed caching scheme is very difficult to design and implement. Most current P2P caching approaches are using Client/Server architecture by deploying dedicated proxy servers on the edge of networks. Such architecture is expensive. It also incurs single point of failure and hot spot problems. Furthermore, it violates P2P principle and failed to utilize vast available resources on individual peers. In this paper, we investigate the techniques for efficient distributed P2P caching. We propose novel placement and replacement algorithms to make caching decisions. For each object, an adequate number of copies are generated and disseminated on topologically distant locations. Combined with the underlying hierarchical query infrastructure, our strategies relieve the over-caching problems for popular objects, and provide more cache space for other objects. This resolution greatly reduces WAN traffic for P2P applications. We conduct simulation experiments to compare our approaches with several common caching strategies. The results show that our algorithms can achieve higher cache hit rates and superior load balance property.

Network coding has been demonstrated to be able to improve the performance of P2P content distribution. However, it is vulnerable to pollution attacks, leading to substantial performance degradation. Moreover, existing corruption detection schemes for network coding are not applied well to P2P systems. More efficient scheme based on attacker identification is required to thwart such attacks. In this paper, we propose an integrated system solution for secure P2P content distribution based on network coding, referred to as ISNC. In ISNC, we first design our system architecture based on extended uniform bipartite networks that can achieve high throughput with network coding. Based on the architecture, we present a secure network coding signature scheme and an identity-based malicious peer identification scheme. The two schemes can cooperate to thwart pollution attacks effectively in P2P network, not only detecting corrupted blocks, but also identifying all the malicious peers. Simulation results show that ISNC can effectively limit the pollution spread and identify malicious peers quickly, even when they collude to launch attacks. Compared with existing related schemes, ISNC is especially applicable for P2P content distribution, and can achieve both high security and overall efficiency.

MapReduce is a widely used parallel programming model and computing platform. With MapReduce, it is very easy to develop scalable parallel programs to process data-intensive applications on clusters of commodity machines. However, it does not directly support heterogeneous related data sets processing, which is common in operations like spatial joins. This paper presents SJMR (Spatial Join with MapReduce), a novel parallel algorithm to relieve the problem. The strategies include strip-based plane sweeping algorithm, tile-based spatial partitioning function and duplication avoidance technology. We evalauted the performance of SJMR algorithm in various situations with the real world data sets. It demonstrates the applicability of computing-intensive spatial applications with MapReduce on small scale clusters.

To share and exchange the files among Internet users, peer-to-peer (P2P) applications build another layer of overlay networks on top of the Internet infrastructure. In P2P file sharing systems, a file request takes two steps. First, a routing message is generated by the client (request initiator) and spread to the overlay network. After the process finishes, the location information of the requested file is returned to the client. In the second step, the client establishes direct connection(s) with the peer(s) who store a copy of that file to start the retrieving process. While numerous research projects have been conducted to design efficient, high-performance routing algorithms, few work concentrated on file retrieving performance. In this paper, we propose a novel and efficient algorithm - PROD to improve the file retrieving performance in DHT based overlay networks. In PROD, when a file or a portion of a file is transferred from a source peer to the client, instead of creating just one direct link between these two peers, we build an application level connection chain. Along the chain, multiple network links are established. Each intermediate peer on this chain uses a store-and-forward mechanism for the data transfer. PROD also introduces a novel topological based strategy to choose these peers and guarantees the transmission delay of each intermediate link is much lower than the direct link. We conducted extensive simulation experiments and the results shown that PROD can greatly reduce the transfer time per file in DHT base P2P systems.

With the developments of network technologies, many mechanisms have been introduced to improve system performance in cluster systems by exploiting remote idle memory. However, none of them can satisfy the requirements from different applications. Most methods can only improve the performance of a particular type of applications but not for others. One important reason is they failed to provide unified interfaces. In this paper, we propose collaborative memory pool (CMP) to solve this problems. CMP brings scalability and high performance. It has five features: (1) Providing malloc-like interfaces, block device interfaces and kernel API for different applications, which benefit both user-level and kernel-level applications; (2) Retaining traditional VM mechanism, programmers and uses have the freedom to select CMP or not; (3) Improving kernel applications performance by eliminating remote swapping; (4) Avoiding loan while in debt problem with dynamic workload; (5) Providing optional memory servers to further improve performance. In our testbed with CMP-based swap devices, Qsort gets 83.28% improvement comparing with the case using disk-based swap devices.

In this paper, we propose a novel and efficient content-aware dispatching algorithm. Our approach eliminates the potential bottleneck and the single point of failure problems completely by using totally decentralized P2P architecture. It is scalable, the system throughput increases nearly linearly with the increased number of servers. Meanwhile, it does not introduce heavy communication overhead among back-end servers which appeared in the previous decentralized mechanisms. Our simulation results show that our approach is superior to the previous solutions.

In DHT based P2P systems, various issues such as peer heterogeneity, network topology, and diverse file popularity, may affect the DHT system efficiency. In this paper, we propose an effective load balancing algorithm for DHT-Based P2P systems. Our main contributions are: (1) we propose an fully distributed mechanism to maintain the history of file access information. This information is used to predict the future file access frequencies and support the load distribution and redistribution operations; (2) we design a novel load balancing algorithm, which takes the file access history and peer heterogeneity properties into account to determine the load distribution. Our algorithm can generate the best load distribution decision when a new peer comes, it can also be able to dynamically perform the load redistribution during system running time if overloaded peers appeared. In our algorithm, no virtual servers are used, thus we have less processing overhead on the expensive routing metadata maintenance; (3) finally, we design a topologically-aware data replication mechanism, the topological information of the peers are used for file replication decisions. A file is replicated only on a peer close to the group of peers which have high access frequencies.

Content delivery network (CDN) plays an important role in today's Web services. More and more content providers use CDNs to lower the server overhead, reduce client perceived latency and decrease network traffic. More research papers have been published in recent years addressing CDN system performance issues. However, most of them are concentrated on server placement policy, content distribution mechanism and request routing algorithm. In this paper, we propose a new CDN architecture to improve system performance by grouping the content servers which are topologically close into server clusters and exploiting the benefits of server cooperation. In our approach, when a server receives a request and cannot fulfil this request, it will forward the request to other nearby servers in this cluster. If there is a cache bit, the data can be fetched immediately. Only in case none of the servers can satisfy this request, the data will be fetched from the original server. Furthermore, with the server coordination, system workload can be well balanced on several servers. We conduct extensive simulations and the results show that our solution achieves significant improvement over the conventional CDN architecture

Recently, content distribution networks (CDNs) have attracted a great deal of attention from both the industry and academic communities. We design efficient object replication algorithms to achieve the optimal performance while not violating clients' QoS requirements in CDN. We use a three-stage mechanism: first, object replication constraints to meet the QoS requirements are generated; second, a minimal object replication set (MORS), which can satisfy the constraints with the minimal number of replicas on each server, is created; and finally, more objects are replicated on the servers with spare space to further improve the performance. We propose a number of heuristic algorithms and conduct trace-driven experiments to evaluate the performance

Several companies have introduced powerful network processors (NP) that can be placed in active routers to execute application level tasks in the network. An NP consists of a number of on-chip processors to carry out packet level parallel processing operations. We propose to employ them for multimedia streaming (transcoding) to convert the incoming video streams to low bit-rate media units as per the requirements of the clients. To effectively schedule the parallel transcoding operations in an active router, we propose a static sequentialized batch-coscheduling (SSBC) scheme to meet both load balancing and real-time requirements for media streaming, based on divisible load theory (DLT). We first analyze the feasibility and optimality of the load distribution schemes from the theoretical perspectives, and then present separate solutions for non-delay-sensitive streams and delay-sensitive streams. Rigorous simulations and experiments have been carried out to evaluate the performance.

Summary form only given. Web caching is the most important technique to reduce network bandwidth consumption and minimize user-perceived latency. However, most researches are focused on designing efficient architectures with dedicated proxy servers, the potential advantage of utilizing client cache is not fully exploited. We propose a new solution to improve Web caching performance using local cache on client computers. Our system has several advantages than the dedicated proxy server mechanism. First, a larger virtual cache is generated to cache more documents than a single proxy server. Second, it is scalable, system workloads are distributed all across client computers instead of concentrated on a central server, the "hot spot" and "single point of failure " problems are relieved. Third, by the introduction of the superclients, the effect of the weak clients in a fully decentralized scheme is also alleviated. The simulation results show our system can achieve better system caching performance and scalability than the previous solutions.

Summary form only given. Well-organized proxy caching systems can greatly reduce the user perceived latency and decrease the network bandwidth consumption. In this paper, we propose a new hash based Web caching architecture, Tulip. Tulip extends the locality-based algorithm in UCFS as the basic data grouping scheme in hash based proxy systems, uses it to aggregate Web objects which are likely to be accessed together into object clusters and uses these clusters as the primary access units between memory and disk. The overhead of slow disk I/Os is greatly reduced. It also presents a simple and efficient data duplication scheme. Along with the local caching strategy, Tulip can achieve both fault tolerance and load balance with minimal overhead introduced. Our simulation results show Tulip is scalable and robust, it has better performance than previous approaches.