Large language models (LLMs) are expensive to serve because model parameters, attention computation, and KV caches impose substantial memory and latency costs.We present GRASPrune, a structured pruning framework applied after pretraining that jointly prunes FFN channels and KV head groups under a single global budget.Instead of learning importance scores without constraints and applying the budget only after training, GRASPrune learns lightweight gate scores with a projected straight-through estimator that enforces a hard mask satisfying the budget at every step while keeping the backbone weights frozen.After the mask is fixed, we calibrate scaling factors on the retained units to mitigate scale mismatch caused by pruning, and fold these factors into the pruned weights to obtain a smaller dense checkpoint with no extra parameters at inference.On LLaMA-2-7B, GRASPrune removes 50% of parameters and achieves 12.18 perplexity on WikiText-2 while maintaining competitive average zero-shot accuracy on five benchmarks, using four epochs on 512 unlabeled calibration sequences on a single NVIDIA A100 80GB GPU without any full model finetuning. 1

Qimin Zhong, Hao Liao, Haiming Qin, Mingyang Zhou, Rui Mao, Wei Chen, Naipeng Chao. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Query rewriting is essential for database performance optimization, but existing automated rule enumeration methods suffer from exponential search spaces, severe redundancy, and poor scalability, especially when handling complex query plans with five or more nodes, where a node represents an operator in the plan tree. We present SLER, a scalable system that enables efficient and effective rewrite rule discovery by combining standardized template enumeration with a learning to rank approach. SLER uses standardized templates, abstractions of query plans with operator structures preserved but data specific details removed, to eliminate structural redundancies and drastically reduce the search space. A learn to rank model guides enumeration by pre filtering the most promising template pairs, enabling scalable rule generation for large node templates. Evaluated on over 11000 real world SQL queries from both open source and commercial workloads, SLER has automatically constructed a rewrite rule repository exceeding 1 million rules - the largest empirically validated rewrite rule library to date. Notably, at the scale of one million rules, SLER supports query plan templates with complexity up to channel level depth. This unprecedented scale opens the door to discovering highly intricate transformations across diverse query patterns. Critically, SLER's template driven design and learned ranking mechanism are inherently extensible, allowing seamless integration of new and complex operators, paving the way for next generation optimizers powered by comprehensive, adaptive rule spaces.

QLC NAND flash is widely adopted in modern storage systems. By trading off read/write performance for storage density through a “time-for-space" approach, QLC enables ultra-high storage capacity. To mitigate performance degradation, Gray code and the two-step programming (TSP) algorithm are used. However, Gray code also has limitations: multiple Gray codes incur circuit overhead, while a single Gray code causes extra I/O latency overhead. This paradox seems unsolvable at first glance, requiring an innovative solution that maintains I/O performance without additional circuit overhead. A promising solution lies in selecting an appropriate Gray code and preventing hot data placement on slow physical pages. This paper proposes BDP, a novel Bi-Directional Programming scheme that adopts a single Gray code to fit both traditional (forward) and reverse programming directions based on TSP. The objective of BDP is to resolve the inherent contradiction between I/O performance preservation and implementation overhead. BDP optimizes the system performance through hardware/software co-design. At the hardware level, a fixed Gray code is employed to avoid additional circuit complexity. At the software level, two strategies (i.e. hotness-aware data allocation and background data migration) are proposed to further mitigate the misplacement of hot data on slow pages in QLC SSDs. The experimental results demonstrate that BDP significantly reduces the allocation of hot data to slow pages and enhances overall I/O performance compared to representative schemes.

Rule discovery is a fundamental task in data analysis, with broad applications in data cleaning, knowledge extraction, and decision making. However, existing methods often generate a large number of functionally redundant rules, with a high time cost. To address this, a recent line of work, the first to introduce diversified top-$k$rule discovery, aims to identify a set of top-ranked rules that are both relevant and diverse. Despite this advancement, it still suffers from high user interaction overhead, computational inefficiency, and the inability to handle a common scenario of selecting a diverse subset from an existing rule set. In this paper, we propose a user-friendly and efficient framework for diversified top-$k$rule discovery. As a testbed, we consider Entity Enhancing Rules (REEs), which subsume common association rules and data quality rules as special cases. Our method allows users to specify lightweight preference templates, which are used to train a correlation model that captures user preferences and generates subjective embeddings for predicates and rules. Based on these embeddings, we define an objective function to jointly measure the relevance and diversity of rules in a unified vector space; moreover, we formulate and study two key problems: (i) selecting diversified top-$k$rules from an existing redundant rule set, and (ii) discovering diversified top-$k$rules directly from raw data. We prove that both problems are intractable and propose effective algorithms; in particular, the second problem is more challenging and thus we further optimize its solution with carefully designed pruning strategies and parallel optimization. Extensive evaluation on real-world datasets demonstrates that our algorithms consistently identify top-ranked relevant and diverse rules, achieving an average 14.4 × speedup (up to 35.57 ×) over the state-of-the-art method.

Non-volatile memory (NVM), as an emergingstor age technology, offers several advantageous features for OLTP engines, including byte-addressability, high capacity, low energy consumption, and data persistence across power failures. Despite these benefits, the current mainstream OLTP engines still commonly adopt a hybrid architecture that deeply couples DRAM with NVM, which results in a complex system architecture and high recovery costs. In this paper, we aim to construct a highly available, stable, and recoverable OLTP engine that guarantees ACID properties through anagile system architecture. We introduce AKV (Agile Key-Value), an NVM-only OLTP storage engine designed to provide effective space utilization, high throughput, and fast failure recovery. AKV addresses the challenges of NVM space management, write redundancy, and concurrency control with two novel techniques: dual-version concurrency control and circular dual-version storage. Experimental results demonstrate that AKV achieves higher throughput (up to 69.7%) and faster recovery (up to 54×) compared to existing storage engines in most scenarios of the TPC-C benchmarks. Additionally, the codebase of AKV (4k+ lines) is more concise than that of SOTA OLTP engines like Zen (8k+ lines) and Falcon (11k+ lines). In addition, this study innovatively proposes a read abort optimization strategy based on dynamic version changes. The experimental results show that this strategy can significantly reduce the transaction abort rate of AKV in specific workload scenarios while maintaining stable system throughput, achieving a maximum reduction of up to 73% in the abort count.

Large language models (LLMs) have received lots of attention for their impressive performance in in-context dialogues and their potential to revolutionize service industries with a new business model, Model-as-a-Service (MaaS). Automated data labeling is a natural and promising service. However, labeling data with LLMs faces two main challenges: 1) the labels from LLMs may contain uncertainty, and 2) using LLMs for data labeling tasks can be prohibitively expensive, as the scales of datasets are usually tremendous. In this paper, we propose a hierarchical framework named LMCrowd that leverages multiple LLMs for efficient data labeling under budget constraints. The proposed LMCrowd framework first aggregates labels from multiple freely available LLMs, and then employs a large, paid MaaS LLM for relabeling selected instances. Furthermore, we formalize the core process as an optimization problem, aiming to select the optimal set of instances for relabeling by the MaaS LLM, given the current belief state. Extensive experimental evaluations across various real-world datasets demonstrate that our framework outperforms human labelers and GPT-4 in terms of both accuracy and efficiency.

Role-playing capabilities in large language models (LLMs) often lack cognitive consistency in complex scenarios that require deep understanding and coherent reasoning.While recent reasoning models excel in math and coding tasks, they show limited effectiveness in open-ended role-playing scenarios.We introduce R-CHAR (Role-Consistent Hierarchical Adaptive Reasoning), a metacognition-driven framework that enhances role-playing performance through guided thinking trajectories synthesis and adaptive evaluation.Our approach demonstrates that concise thinking processes can achieve superior performance efficiently compared to elaborate reasoning chains in roleplaying social intelligence tasks, outperforming existing specialized models.Experimental results on the SocialBench benchmark show significant and stable performance improvements across varying scenario complexities, showing particular strength in long-context comprehension (from 34.64% to 68.59%) and grouplevel social interactions.Our work advances the development of cognitively consistent roleplaying systems, bridging the gap between surface-level mimicry and authentic character simulation.

Deep reinforcement learning (DRL) has achieved remarkable success in dynamic decision-making tasks. However, its inherent opacity and cold start problem hinder transparency and training efficiency. To address these challenges, we propose HRL-ID, a neural-symbolic framework that combines automated rule discovery with logical reasoning within a hierarchical DRL structure. HRL-ID dynamically extracts first-order logic rules from environmental interactions, iteratively refines them through success-based updates, and leverages these rules to guide action execution during training. Extensive experiments on Atari benchmarks demonstrate that HRL-ID outperforms state-of-the-art methods in training efficiency and interpretability, achieving higher reward rates and successful knowledge transfer between domains.

Reinforcement fine-tuning (RFT) has shown great promise in achieving humanlevel reasoning capabilities of Large Language Models (LLMs), and has recently been extended to MLLMs. Nevertheless, reasoning about videos, which is a fundamental aspect of human intelligence, remains a persistent challenge due to the complex logic, temporal and causal structures inherent in video data. To fill this gap, we propose VideoRFT, a novel approach that extends the RFT paradigm to cultivate human-like video reasoning capabilities in MLLMs. VideoRFT follows the standard two-stage scheme in RFT: supervised fine-tuning (SFT) with chain-of-thought (CoT) annotations, followed by reinforcement learning (RL) to improve generalization. A central challenge to achieve this in the video domain lies in the scarcity of large-scale, high-quality video CoT datasets. We address this by building a multi-expert-driven, cognition-inspired CoT curation pipeline. First, we devise a cognition-inspired prompting strategy to elicit a reasoning LLM to generate preliminary CoTs based solely on rich, structured, and literal representations of video content. Subsequently, these CoTs are revised by a MLLM conditioned on the actual video, ensuring visual consistency and reducing visual hallucinations. This pipeline results in two new datasets, i.e.VideoRFT-CoT-102K for SFT and VideoRFT-RL-310K for RL. To further strengthen the RL phase, we introduce a novel semantic-consistency reward that explicitly promotes the alignment between textual reasoning and visual evidence. This reward encourages the model to produce coherent, context-aware reasoning outputs grounded in visual input. Extensive experiments show that VideoRFT achieves state-of-the-art performance on six video reasoning benchmarks.

Network connectivity minimization is a fundamental problem in controlling the spread of viruses in the Internet and facilitating information propagation in online social networks. The problem aims to identify a budget number of key nodes whose removal would minimize the connectivity of a network. However, the existing solutions heavily rely on the number of edges, making it challenging to handle large and densely connected social networks. In this study, we present a fast algorithm that is independent of the number of edges. To achieve this, we first introduce a surrogate matrix that approximates the residual adjacency matrix with arbitrary small predefined error. We then devise an efficient approach for inferring k influential nodes by optimizing the eigenvalues of the surrogate matrix. Remarkably, the algorithm has a small time complexity of O(knr3), with r being a small tunable number. Our algorithm thereby maintains a linear scalability in terms of the number of nodes and is unaffected by the number of edges. Hence, it has the capability to efficiently handle large and dense social networks. At last, we evaluate its performance against state-of-the-art techniques using diverse real-world datasets. The experimental results demonstrate the superiority of our proposed method in terms of both solution quality and computational efficiency.

Recent studies have made it possible to integrate learning techniques into database systems for practical utilization. In particular, the state-of-the-art studies hook the conventional query optimizer to explore multiple execution plan candidates, then choose the optimal one with a learned model. This framework simplifies the integration of learning techniques into the database system. However, these methods still have room for improvement due to their limited plan exploration space and ineffective learning from execution plans. In this work, we propose Athena, an effective learning-based framework of query optimizer enhancer. It consists of three key components: (i) an order-centric plan explorer, (ii) a Tree-Mamba plan comparator and (iii) a time-weighted loss function. We implement Athena on top of the open-source database PostgreSQL and demonstrate its superiority via extensive experiments. Specifically, We achieve 1.75x, 1.95x, 5.69x, and 2.74x speedups over the vanilla PostgreSQL on the JOB, STATS-CEB, TPC-DS, and DSB benchmarks, respectively. Athena is 1.74x, 1.87x, 1.66x, and 2.28x faster than the state-of-the-art competitor Lero on these benchmarks. Additionally, Athena is open-sourced and it can be easily adapted to other relational database systems as all these proposed techniques in Athena are generic.

Explainable recommender systems ( ERS ) aim to enhance users’ trust in the systems by offering personalized recommendations with transparent explanations. This transparency provides users with a clear understanding of the rationale behind the recommendations, fostering a sense of confidence and reliability in the system’s outputs. Generally, the explanations are presented in a familiar and intuitive way, which is in the form of natural language, thus enhancing their accessibility to users. Recently, there has been an increasing focus on leveraging reviews as a valuable source of rich information in both modeling user-item preferences and generating textual interpretations, which can be performed simultaneously in a multi-task framework. Despite the progress made in these review-based recommendation systems, the integration of implicit feedback derived from user-item interactions and user-written text reviews has yet to be fully explored. To fill this gap, we propose a model named SERMON (A s pect-enhanced E xplainable R ecommendation with M ulti-modal C o ntrast Lear n ing). Our model explores the application of multimodal contrastive learning to facilitate reciprocal learning across two modalities, thereby enhancing the modeling of user preferences. Moreover, our model incorporates the aspect information extracted from the review, which provides two significant enhancements to our tasks. Firstly, the quality of the generated explanations is improved by incorporating the aspect characteristics into the explanations generated by a pre-trained model with controlled textual generation ability. Secondly, the commonly used user-item interactions are transformed into user-item-aspect interactions, which we refer to as interaction triple, resulting in a more nuanced representation of user preference. To validate the effectiveness of our model, we conduct extensive experiments on three real-world datasets. The experimental results show that our model outperforms state-of-the-art baselines, with a 2.0% improvement in prediction accuracy and a substantial 24.5% enhancement in explanation quality for the TripAdvisor dataset.

We are pleased to welcome you to the first edition of the IEEE Services Workshop on Emerging Services in the Greater Bay Area (ES-GBA), organized within the IEEE Congress on Services in the wonderful city of Shenzhen, China.

Approximate Nearest Neighbor Search (ANNS) is a classical problem in data science. ANNS is both computationally-intensive and memory-intensive. As a typical implementation of ANNS, Inverted File with Product Quantization (IVFPQ) has the properties of high precision and rapid processing. However, the traversal of non-nearest neighbor vectors in IVFPQ leads to redundant memory accesses. This significantly impacts retrieval efficiency. A promising approach involves the utilization of learned indexes, leveraging insights from data distribution to optimize search efficiency. Existing learned indexes are primarily customized for low-dimensional data. How to tackle ANNS in high-dimensional vectors is a challenging issue.

Blockchain storage platforms reward storage nodes for keeping user-uploaded data for a certain amount of time. These storage nodes are unstable and can go online or offline unpredictably at any time, leading to potential data loss. To prevent data loss, blockchain storage platforms adopt erasure codes on user-uploaded encrypted data. Data repair processes will be performed to recover the lost data. However, the data repair processes heavily rely on time-consuming erasure coding algorithms, mainly consisting of vector-matrix multiplications. The emerging processing-in-memory technique can efficiently speed up the processing of vector-matrix multiplications. It can be integrated into blockchain storage platforms to solve the data repair issue. This paper presents Rapper, a parameter-aware repair-inmemory accelerator for blockchain storage platforms. Rapper utilizes the computing power of emerging processing-in-memory architecture so that data repair processes can be processed in a parallel manner and the overall efficiency can be improved significantly. Specifically, at the hardware level, the ReRAM memory is reorganized into our proposed double bank, XRU, XGroup, and ReRAM crossbars structure. At the software level, a parallel decoding/encoding strategy is proposed to fully exploit the internal parallelism of ReRAM. We also propose an adaptive parameter-aware mapping to handle various sizes of stripes. To demonstrate the viability of the proposed technique, a representative blockchain storage project Storj is adopted as the default storage infrastructure. Experimental results show that Rapper can achieve a 1.96 × speedup on average compared to the representative scheme.

As the most common data structure for key-value stores, LogStructured Merge Tree (LSM-tree) can eliminate random write operations and keep acceptable read performance. However, write stall and write amplification introduced by the leveled compaction of LSM-tree significantly degrade the system performance. The emerging non-volatile memory (NVM) provides byte-addressable access and low-latency data persistence. Integrating DIMM-interface NVM in the design of the LSM-tree can potentially alleviate the write stall and write amplification issue, as the access speed of NVM is several orders of magnitude faster than hard disk drives or flash memory-based solid-state drives. This hybrid storage should be carefully designed, requiring new architectural and key-value structural support. This paper presents ZigZagDB, an NVM-enabled data man-agement scheme for LSM-tree-based key-value stores. ZigZagDB adds additional layers of key-value stores and uses non-volatile memory as the storage media to hold these additional layers of data. The newly designed key-value stores alternately access the data from either SSD or NVM. This ‘ZigZag’ shape of storage collaboration and synchronization can benefit write efficiency and space utilization. By utilizing the NVM with very limited capacity, the redesigned organization of LSM-tree can effectively solve the write stall and write amplification issue. We demonstrate the viability of the proposed ZigZagDB using a set of extensive experiments. Experimental results show that ZigZagDB can significantly reduce the write amplification and boost the throughput in comparison with representative schemes.

There is a considerable body of work on data cleaning which employs various principles to rectify erroneous data and transform a dirty dataset into a cleaner one. One of prevalent approaches is probabilistic methods, including Bayesian methods. However, existing probabilistic methods often assume a simplistic distribution (e.g., Gaussian distribution), which is frequently under-fitted in practice, or they necessitate experts to provide a complex prior distribution (e.g., via a programming language). This requirement is both labor-intensive and costly, rendering these methods less suitable for real-world applications. In this paper, we propose BClean, a Bayesian Cleaning system that features automatic Bayesian network construction and user interaction. We recast the data cleaning problem as a Bayesian inference that fully exploits the relationships between attributes in the observed dataset and any prior information provided by users. To this end, we present an automatic Bayesian network construction method that extends a structure learning-based functional dependency discovery method with similarity functions to capture the relationships between attributes. Furthermore, our system allows users to modify the generated Bayesian network in order to specify prior information or correct inaccuracies identified by the automatic generation process. We also design an effective scoring model (called the compensative scoring model) necessary for the Bayesian inference. To enhance the efficiency of data cleaning, we propose several approximation strategies for the Bayesian inference, including graph partitioning, domain pruning, and pre-detection. By evaluating on both real-world and synthetic datasets, we demonstrate that BClean is capable of achieving an F-measure of up to 0.9 in data cleaning, outperforming existing Bayesian methods by 2% and other data cleaning methods by 15%.

The issue of data heterogeneity has long been a significant challenge in federated learning, impacting the speed of global model convergence and potentially lowering the overall performance of the global model, thereby impeding its development. In response to this challenge, we propose a classifier head-based method to correct the local model update direction. Unlike most existing calibration methods, our method not only ensures a global model with good performance but also guarantees the performance of a single local model. Concretely, we have introduced a new federated learning framework called FedCA. In this framework, the output of the feature extractor is imported into both a global classifier and a local classifier. The gradients are calculated separately, and then backpropagate into the model. This method ensures the performance of the local model and allows the client to maintain a consistent learning direction. Our experimental results demonstrate the feasibility of this method.

In Serverless Computing, function cold-start is a major issue that causes delay of the system. Various solutions have been proposed to address function cold-start issue, among which keeping containers alive after function completion is an easy and commonly adopted way in real serverless clouds. However, when reusing warm containers for function warm starts, existing systems only match functions to containers with the same configurations. This greatly limits the warm resource utilization. Our analysis of real-world applications reveals that many serverless applications share the same operating system and language frameworks. Thus, we propose multi-level container reuse that tries to reduce the startup latency of functions using "similar" containers to greatly improve warm resource utilization. Due to the complexity of selecting the best container reuse solutions, we designed a Deep Reinforcement Learning (DRL) based scheduler to efficiently and effectively address the problem. Moreover, we released a new serverless benchmark named FStartBench that contains detailed package information for comparing the effectiveness of different function cold-start methods. Experiments based on FStartBench show that, given a warm resource pool with fixed size, our DRL-based scheduler can achieve up to 53% reduction on the average function startup latency compared to state-of-the-art solutions.

In the face of rising global demand for video meetings, managing traffic across geographically distributed (geo-distributed) data centers presents a significant challenge due to the dynamic and limited nature of inter-DC network performance. Facing these issues, this paper introduces two novel techniques, VCRoute and WMJitter, to optimize the performance of geo-distributed video conferencing systems. VCRoute is a routing method designed for audio data packets of video conferences. It treats the routing problem as a Multi-Armed Bandit issue, and utilizes a tailored Thompson Sampling algorithm for resolution. Unlike traditional approaches, VCRoute considers transmitting latency and its variance simultaneously by using Thompson Sampling algorithm, which leads to effective end-to-end latency optimization. In conjunction with VCRoute, we present WMJitter, a watermark-based mechanism for managing network jitter, which can further reduce the end-to-end delay and keep an improved balance between latency and loss rate. Evaluations based on real geo-distributed network performance demonstrate the effectiveness and scalability of VCRoute and WMJitter, offering robust solutions for optimizing video conferencing systems in geo-distributed settings.

The influence maximization (IM) problem aims to identify a budgeted set of nodes with the highest potential to influence the largest number of users in a cascade model, a key challenge in viral marketing. Traditional \emph{IM} approaches consider each user/node independently as a potential target customer. However, in many scenarios, the target customers comprise motifs, where activating only one or a few users within a motif is insufficient for effective viral marketing, which, nevertheless, receives little attention. For instance, if a motif of three friends planning to dine together, targeting all three simultaneously is crucial for a restaurant advertisement to succeed. In this paper, we address the motif-oriented influence maximization problem under the linear threshold model. We prove that the motif-oriented IM problem is NP-hard and that the influence function is neither supermodular nor submodular, in contrast to the classical \emph{IM} setting. To simplify the problem, we establish the submodular upper and lower bounds for the influence function. By leveraging the submodular property, we propose a natural greedy strategy that simultaneously maximizes both bounds. Our algorithm has an approximation ratio of $\tau\cdot (1-1/e-\varepsilon)$ and a near-linear time complexity of $O((k+l)(m+\eta)\log \eta/\varepsilon^2)$. Experimental results on diverse datasets confirm the effectiveness of our approach in motif maximization.

Federated learning enables collaborative AI training across organizations without compromising data privacy. Decentralized federated learning (DFL) improves this by offering enhanced reliability and security through peer-to-peer (P2P) model sharing. However, DFL faces challenges in terms of slow convergence rate due to complex P2P graphs. To address this issue, we propose an efficient algorithm to accelerate DFL by introducing a limited number of k of edges into the P2P graphs. Specifically, we establish a connection between the convergence rate and the second smallest eigenvalue of the laplacian matrix of the P2P graph. We prove that finding the optimal set of edges to maximize this eigenvalue is an NP-complete problem. Our quantitative analysis shows the positive effect of strategic edge additions on improving this eigenvalue. Based on the analysis, we then propose an efficient algorithm to compute the best set of candidate edges to maximize the second smallest eigenvalue, and consequently the convergence rate is maximized. Our algorithm has a low time complexity of O(krn^2). Experimental results on diverse datasets validate the effectiveness of our proposed algorithms in accelerating DFL convergence.

Abstract In stream processing systems, Key Grouping is a commonly employed partitioning scheme for distributing input tuples among parallel instances of stateful operators. With key grouping, tuples shared public keys in the stream are designated to the specific instance responsible for that key. Typically, the implementation of key grouping involves the use of a hash function. While it is convenient and deterministic, it is also known to cause load imbalance between parallel instances, especially in the presence of skewed data streams. Key-Splitting is an effective technique that distributes tasks associated with keys to downstream operators, facilitating load balancing at a relatively low cost. However, overly increasing parallel instances can lead to excessive aggregation costs, becoming a system bottleneck. In this paper, we show the high aggregation cost brought by the Key-Splitting partitioner at different levels of key separation. To address this challenge, we introduce an adaptive Key-Splitting method which controlling the degree of key separation. We propose a partitioner named FlexD, which aims to achieve dynamic adaptation of key separation limits for streaming data. The partitioner employs key grouping to distribute rare keys and dynamic expansion of processing instances to distribute hot keys. We implemented our method on Apache Storm and evaluated it by using real-world and synthetic datasets. Experimental results show that our method achieves a good balance between load balancing and aggregation cost. Moreover, it outperforms existing methods, achieving higher throughput.

Benchmarking is crucial for evaluating a DBMS, yet existing benchmarks often fail to reflect the varied nature of user workloads. As a result, there is increasing momentum toward creating databases that incorporate real-world user data to more accurately mirror business environments. However, privacy concerns deter users from directly sharing their data, underscoring the importance of creating synthesized databases for benchmarking that also prioritize privacy protection. Differential privacy (DP)-based data synthesis has become a key method for safeguarding privacy when sharing data, but the focus has largely been on minimizing errors in aggregate queries or downstream ML tasks, with less attention given to benchmarking factors like query runtime performance. This paper delves into differentially private database synthesis specifically for benchmark publishing scenarios, aiming to produce a synthetic database whose benchmarking factors closely resemble those of the original data. Introducing PrivBench , an innovative synthesis framework based on sum-product networks (SPNs), we support the synthesis of high-quality benchmark databases that maintain fidelity in both data distribution and query runtime performance while preserving privacy. We validate that PrivBench can ensure database-level DP even when generating multi-relation databases with complex reference relationships. Our extensive experiments show that PrivBench efficiently synthesizes data that maintains privacy and excels in both data distribution similarity and query runtime similarity.

In comparison with upper-layer authentication mechanisms, the tag-based Physical-Layer Authentication (PLA) attracts many research interests because of high security and low complexity. This paper mainly concerns two problems in prior tag-based PLA schemes, where the first one is extra overhead and vulnerability due to the reason that the parameter is broadcasted and the other one is the problem of setting the parameter empirically. Therefore, two new tag-based PLA schemes are proposed to address the above limitations. Specifically, a blind tag-based PLA scheme (BTP) is presented to achieve accurate authentication without knowing the tag parameter of the legitimate transmitter, which not only saves the communication overhead but also improves security. Then, an adaptive blind tag-based PLA scheme (ABTP) is further proposed, which adaptively sets the tag parameter according to the wireless channel state to achieve a better balance among robustness, security, and compatibility. Rigorous theoretical analyses are provided for the two proposed schemes and the prior schemes’ performance comparisons are given. The accuracy of the theoretical analyses is verified through simulation results. At last, the advantages and disadvantages of the two proposed schemes are discussed, and suggestions are given according to different scenarios.

Graph Convolutional Networks (GCNs) are powerful learning approaches for graph-structured data. GCNs are both computing- and memory-intensive. The emerging 3D-stacked computation-in-memory (CIM) architecture provides a promising solution to process GCNs efficiently. The CIM architecture can provide near-data computing, thereby reducing data movement between computing logic and memory. However, previous works do not fully exploit the CIM architecture in both dataflow and mapping, leading to significant energy consumption.This paper presents Lift, an energy-efficient GCN accelerator based on 3D CIM architecture using software and hardware co-design. At the hardware level, Lift introduces a hybrid architecture to process vertices with different characteristics. Lift adopts near-bank processing units with a push-based dataflow to process vertices with strong re-usability. A dedicated unit is introduced to reduce massive data movement caused by high-degree vertices. At the software level, Lift adopts a hybrid mapping to further exploit data locality and fully utilize the hybrid computing resources. The experimental results show that the proposed scheme can significantly reduce data movement and energy consumption compared with representative schemes.

Predicting urban crowd patterns/flows is a challenging task due to complex spatial–temporal (ST) dependencies. In this article, we aim to examine and report the capability and effectiveness of the current most widely used graph convolutional networks (GCNs) on mobile data analysis in ST networks for crowd flow forecasting. Specifically, we propose a novel dual-stream framework leveraging multigraph with attentive ST networks (MG-ASTN) to simultaneously predict crowd in–out flow and origin–destination (OD) flow based on the trajectory data collected by on-board devices (e.g., GPS). MG-ASTN utilizes multi-GCNs encoding non-Euclidean correlations to explore pairwise relationships among regions. In addition, we further apply a cross-channel attention mechanism with 3-D temporal convolutional network to address the heterogeneity of ST features and capture more meaningful data representations for multitask learning. In the evaluation, we conduct experiments based on two real-world data sets and verify most well-known state-of-the-art methods for crowd flow prediction. The results demonstrate that MG-ASTN could outperform other solutions—in–out flow prediction with lowest RMSE and MAE, and OD flow prediction beyond others in most cases, thus it has great potential in modeling the complex correlations among regions in ST networks and enabling accurate prediction in urban computing.

In this paper, we present an algorithmic study on how to surpass competitors in popularity by strategic promotions in social networks. We first propose a novel model, in which we integrate the Preferential Attachment (PA) model for popularity growth with the Independent Cascade (IC) model for influence propagation in social networks called PA-IC model. In PA-IC, a popular item and a novice item grab shares of popularity from the natural popularity growth via the PA model, while the novice item tries to gain extra popularity via influence cascade in a social network. The popularity ratio is defined as the ratio of the popularity measure between the novice item and the popular item. We formulate Popularity Ratio Maximization (PRM) as the problem of selecting seeds in multiple rounds to maximize the popularity ratio in the end. We analyze the popularity ratio and show that it is monotone but not submodular. To provide an effective solution, we devise a surrogate objective function and show that empirically it is very close to the original objective function while theoretically, it is monotone and submodular. We design two efficient algorithms, one for the overlapping influence and non-overlapping seeds (across rounds) setting and the other for the non-overlapping influence and overlapping seed setting, and further discuss how to deal with other models and problem variants. Our empirical evaluation further demonstrates that our proposed method consistently achieves the best popularity promotion compared to other methods. Our theoretical and empirical analyses shed light on the interplay between influence maximization and preferential attachment in social networks.

Decentralized storage systems such as blockchain storage applications adopt the distributed storage technology and use distributed storage nodes to store the persistent data. For each off-chain storage node, key-value (KV) stores are normally used to manage data. As the most common data structure for KV store, Log Structured Merge Tree (LSM-Tree) eliminates random write operations and keeps acceptable read performance. Although LSM-Tree-based decentralized storage system can provide a secure and reliable storage platform, the unique feature of blockchain applications is not fully exploited. In blockchain storage applications, the generation of keys for KV stores is based on the encrypted data, and the key determines the allocation of data. Since the granularity for a read/write request at the level of blockchain storage platform is much smaller than that at the level of LSM-Tree or flash memory, a physical block in a solid-state drive (SSD) could be filled with data from different system users. This mixture of workloads will lead to the inefficient usage of physical spaces in the SSD and cause extra compaction operations for LSM-Tree. This paper presentsMeta-Block, a cross-layer and efficient storage management strategy for decentralized blockchain storage applications. Meta-Block utilizes rich functionalities provided by the system infrastructure of open-channel SSD to provide direct storage accesses for the off-chain storage node. The objective is to capture the features of blockchain storage applications and reduce unnecessary read and write operations across different storage layers. As a cross-layer design, Meta-Block redesigns the organization of LSM-Tree, which can effectively reduce the write amplification. We also design a data prefetching strategy to speed up the indexing and enable direct storage access. We demonstrate the viability of the proposed technique using a set of extensive experiments. Experimental results show that Meta-Block can effectively reduce the write amplification and extend the lifetime of SSDs in comparison with representative schemes.

The log-structured merge-tree (LSM-tree)-based key-value store has been widely adopted by many large-scale data storage applications for its excellent write performance. However, such write performance gains mainly come from scarifying read performance due to the leveled and log-structured intrinsic characteristics of the LSM-tree. Therefore, the critical challenge of the existing LSM-tree is how to improve the read efficiency by reducing read amplification. This article for the first time proposes Tidal-tree-Mem, a novel data structure where data flow inside the LSM-tree-like Tidal waves. First, a floating strategy is proposed to allow frequently accessed files at the bottom of the LSM-tree to move to higher positions, reducing read amplification. Second, a stretching strategy is proposed to vary the shape of the LSM-tree to adapt to workloads with different characteristics. To evaluate the performance of Tidal-tree-Mem, we conduct a series of experiments using standard benchmarks from YCSB. The experimental results show that Tidal-tree-Mem can effectively reduce read amplification and the overall latency by over 71.94% and 47.34%, respectively, compared with representative schemes.

Autism spectrum disorder (ASD) is characterized by poor social communication abilities and repetitive behaviors or restrictive interests, which has brought a heavy burden to families and society. In many attempts to understand ASD neurobiology, resting-state functional magnetic resonance imaging (rs-fMRI) has been an effective tool. However, current ASD diagnosis methods based on rs-fMRI have two major defects. First, the instability of rs-fMRI leads to functional connectivity (FC) uncertainty, affecting the performance of ASD diagnosis. Second, many FCs are involved in brain activity, making it difficult to determine effective features in ASD classification. In this study, we propose an interpretable ASD classifier DeepTSK, which combines a multi-output Takagi-Sugeno-Kang (MO-TSK) fuzzy inference system (FIS) for composite feature learning and a deep belief network (DBN) for ASD classification in a unified network. To avoid the suboptimal solution of DeepTSK, a joint optimization procedure is employed to simultaneously learn the parameters of MO-TSK and DBN. The proposed DeepTSK was evaluated on datasets collected from three sites of the Autism Brain Imaging Data Exchange (ABIDE) database. The experimental results showed the effectiveness of the proposed method, and the discriminant FCs are presented by analyzing the consequent parameters of Deep MO-TSK.

Core decomposition on uncertain graphs is a fundamental problem in graph analysis. Given an uncertain graph G, the core decomposition problem is to determine all (k, \eta)-cores in G, where a (k, \eta)-core is a maximal subgraph of G such that each node has an \eta-degree no less than k within the subgraph. The state-of-the-art algorithm for solving this problem is based on a peeling technique which iteratively removes nodes with the smallest \eta-degrees and also dynamically updates their neighbors' \eta-degrees. Unfortunately, we find that such a peeling algorithm with the dynamical \eta-degree updating technique is incorrect due to the inaccuracy of the recursive floating-point number division operations involved in the dynamical updating procedure. To solve this problem, we propose a bottom-up algorithm based on an on-demand computational strategy. To further improve the efficiency, we also develop a more-efficient top-down algorithm with several nontrivial optimization techniques. Both of our algorithms do not involve any floating-point number division operations, thus the correctness can be guaranteed. We conduct extensive experiments to evaluate our algorithms using five large real-life datasets. The results show that our algorithms are at least three orders of magnitude faster than the existing exact algorithms on large uncertain graphs.

The set similarity join finds all pairs of similar sets from two collections of sets. It has many real world applications, such as personalized recommendation and community mining. In this paper, we study the problem of computing the similarity join in a dynamic context, where the sets are updated dynamically. This, however, is inefficient with the state-of-the-art join methods, because they usually assume that data collections are static and have to compute the join result from scratch whenever a set is updated. To address this issue, we propose${{\sf ALJoin}}$, an adaptive filtering approach that computes the join result incrementally based on the update logs. We first investigate the effect of set updates on the similarity values, and on this basis we propose to build a neighborhood index for each set. The neighborhood index of a specific set consists of any other sets that can be transformed into its similar sets within a threshold number of update operations.${{\sf ALJoin}}$then uses this index to effectively identify both similar and dissimilar set pairs based on their update logs. To efficiently build the neighborhood index, we devise several filtering techniques and propose a “lazy-forward” method to reduce the computational cost. In addition, to improve the efficiency on varying workloads, we propose an analytical cost model, and design an online algorithm with performance guarantees to dynamically consolidate the update logs and adapt the neighborhood indexes. We evaluated our method using four real-world datasets. Experimental results show that our approach outperforms existing methods by up to$3.7\times$.

In Spatial crowdsourcing, mobile users perform spatio-temporal tasks that involve travel to specified locations. Spatial crowdsourcing (SC) is enabled by SC platforms that support mobile worker recruitment and retention, as well as task assignment, which is essential to maximize profits that are accrued from serving task requests. Specifically, how to best achieve task assignment in a cost-effective manner while contending with spatio-temporal constraints is a key challenge in SC. To address this challenge, we formalize and study a novel Profit-driven Task Assignment problem. We first establish a task reward pricing model that takes into account the temporal constraints (i.e., expected completion time and deadline) of tasks. Then we adopt an optimal algorithm based on tree decomposition to achieve an optimal task assignment and propose greedy algorithms based on Random Tuning Optimization to improve the computational efficiency. To balance effectiveness and efficiency, we also provide a heuristic task assignment algorithm based on Ant Colony Optimization that assigns tasks by simulating behavior of ant colonies foraging for food. Finally, we conduct extensive experiments using real and synthetic data, offering detailed insight into effectiveness and efficiency of the proposed methods.

LSM-tree-based key-value stores are popular in embedded storage systems. With the growing demands of data analysis, the secondary index is created to support non-primary-key lookups. However, the lookup efficiency and space consumption of secondary index remain for further optimization. Inspired by the learned index, this paper presents Lark, a learned secondary index toward LSM-tree for resource-constrained embedded storage systems. Lark employs machine learning to speed up the non-primary-key queries and compress secondary indexes. Our preliminary evaluations show that, in comparison with traditional secondary index schemes, Lark achieves better lookup performance with less space consumption.

Emerging Shingled Magnetic Recording (SMR) Disk can improve the storage capacity significantly by overlapping multiple tracks with the shingled direction. However, the shingled-like structure leads to severe write amplification caused by RMW operations inner SMR disks. As the mainstream solid-state storage technology, NAND flash has the advantages of tiny size, cost-effective, high performance, making it suitable and promising to be incorporated into SMR disks to boost the system performance. In this hybrid embedded storage system (i.e., the Embedded Flash with SMR disk (EF-SMR) system), we observe that physical flash blocks can contain a mixture of data associated with different SMR data bands; when garbage collecting such flash blocks, multiple RMW operations are triggered to rewrite the involved SMR bands and the performance is further exacerbated. Therefore, in this paper, we for the first time present MU-RMW to guarantee data from different SMR bands will not be mixed up within the flash blocks with an aim at minimizing unnecessary RMW operations. The effectiveness of MU-RMW was evaluated with realistic and intensive I/O workloads and the results are encouraging.

The bloom of the Internet and the recent breakthroughs in deep learning techniques open a new door to AI for E-commence, with a trend evolved from using a few financial factors such as liquidity and profitability to using more advanced AI techniques to process complex and multi-modal data.In this paper, we tackle the practical problem of restaurant survival prediction.We argue that traditional methods ignore two essential aspects, which are very helpful for the task: 1) modeling customer reviews and 2) jointly considering status prediction and result explanation.Thus, we propose a novel joint learning framework for explainable restaurant survival prediction based on the multi-modal data of user-restaurant interactions and users' textual reviews.Moreover, we design a graph neural network to capture the high-order interactions and design a co-attention mechanism to capture the most informative and meaningful signal from noisy textual reviews.Our results on two datasets show a significant and consistent improvement over the SOTA techniques (average 6.8% improvement in prediction and 45.3% improvement in explanation).

Core decomposition on uncertain graphs is shown to be a key problem in graph analysis. However, existing algorithms for solving this problem are based on a peeling algorithm with the dynamically updating technique, which can lead to relatively large errors due to the inaccuracy of the recursive floating-point number division operations. In this paper, we first develop two novel algorithms, a bottom-up approach and a top-down approach, which do not involve any floating-point number division operations to guarantee correctness. Then, we develop a parallel version for each approach to deal with large graphs. Extensive experimental results evidence the efficiency, effectiveness, and scalability of our proposed algorithms.

Graph partitioning is an important problem to the performance and cost optimization of graph analytics in geo-distributed environments. Modern hybrid-cut model is expected to obtain better performance and cost optimizations than traditional partitioning models, but can further complicate geo-distributed graph partitioning which is already a challenging problem due to large graph sizes and network heterogeneities of geo-distributed DCs. Existing studies usually adopt heuristic-based methods to achieve fast partitioning for large graphs, which unfortunately sacrifices optimization effectiveness. Further, graph structures of many applications can change at various frequencies. Dynamic partitioning methods usually focus on achieving low latency to quickly adapt to changes, which may again sacrifice partitioning effectiveness. Also, such methods are not aware of the dynamicity of graphs and can over sacrifice effectiveness for unnecessarily low latency. In this paper, we propose RLCut, which uses Reinforcement Learning (RL) to help taming the complexity of the problem. Specifically, RLCut uses multi-agent learning which is more efficient than single agent RL and incorporates a sampling based optimization to adaptively control the training process to satisfy required trade-off between partitioning effectiveness and efficiency according to graph dynamicity. Experiments using real cloud DCs and real-world graphs show that, compared to state-of-the-art static partitioning methods, RLCut improves the performance of geo-distributed graph analytics by 10%-100% with comparable overhead. When users tolerate longer partitioning overhead, we can further improve the performance by up to 43%. With varying graph changing frequencies, RLCut can improve the performance by up to 60% compared to state-of-the-art dynamic partitioning.

Graph convolutional networks (GCNs) have become a powerful deep learning approach for graph-structured data. Different from traditional neural networks such as convolutional neural networks, GCNs handle irregular input graph data, and GCNs are both computation-bound and memory-bound. How to efficiently utilize the underlying computation and memory resource becomes a critical issue. The emerging 3D-stacked computation-in-memory (CIM) architecture can reduce the data movement between computing logic and memory, thereby presenting a promising solution for the processing of GCNs. An unsolved key challenge is how to allocate GCNs to take advantage of fast near-data processing of the 3D-stacked CIM architecture. This article presents GCIM, a software–hardware co-design approach to exploit the efficient processing of GCNs on the CIM architecture. At the level of hardware design, GCIM integrates lightweight computing units near memory banks to fully exploit bank-level bandwidth and parallelism. At the level of software design, a locality-aware data mapping algorithm is proposed to partition the input graph and achieve workload balancing. GCIM is evaluated through a set of representative GCN models and standard graph datasets. The experimental results show that GCIM can significantly reduce the processing latency and data movement overhead compared with representative schemes.

As the mainstream solid-state storage technology, NAND flash has the advantages of tiny size, cost-effective, and high performance, which make it a promising candidate to be embedded into the shingled magnetic recording (SMR) disk to build a faster, denser, and cheaper storage system. However, such an embedded flash with SMR (EF-SMR) disk system suffers from lengthy tail-latency due to “reclamation issues” in both the NAND flash and the SMR disk. Our preliminary observations reveal that tremendous idle time intervals exist in real-world scenarios, and few prior works have focused on addressing the tail-latency issue in the EF-SMR disk. In this article, we propose a novel method termed MAID-Q to fully exploit the idle time intervals to minimize the lengthy tail-latency of the EF-SMR disk based on a lightweight reinforcement learning model (i.e., the$Q$-learning model). In addition, fine-grained block-level space management and a parallel reclamation strategy are proposed to improve the reclamation efficiency and hide the reclamation overheads. The effectiveness of our proposed design was evaluated with realistic I/O traces, and the results show that the proposed design can remedy the tail-latency by 88.31% and improve the overall performance by 79.03%.

Three-dimensional (3D) flash memory is an emerging memory technology that enables a number of improvements to conventional planar NAND flash memory, including larger capacity, less program disturb, and lower access latency. Despite these advantages, 3D flash memory brings a number of new challenges. First, in 3D flash memory, NAND strings punch through multiple stacked layers to form the 3D infrastructure. Current etching process is unable to manufacture perfect channels with identical feature size. Second, with more stacked layers, the cell current in 3D flash memory is only 20% compared to planar flash memory, making it difficult to give a reliable sensing margin. These issues are affected by process variation, and they pose threats to the integrity of data stored in 3D flash memory. This article presentPVSensing, a process-variation-aware space allocation strategy for open-channel SSD with 3D charge-trap flash memory. PVSensing is a novel hardware and file system interface that can transparently allocate physical space in the presence of process variation. PVSensing utilizes the rich functionalities provided by the system infrastructure of open-channel SSD to reduce the uncorrectable bit errors. Three reliability enhancement strategies (i.e., the adaptive creation of fault cubes, the physical block mining, and the live migration of write requests) are proposed. We demonstrate the viability of the proposed technique using a set of extensive experiments. Experimental results show that PVSensing can effectively reduce uncorrectable bit errors, and improve the reliability of critical data with negligible extra erase operations in comparison with representative schemes.

Recently, semisupervised feature selection has gained more attention in many real applications due to the high cost of obtaining labeled data. However, existing methods cannot solve the "multimodality" problem that samples in some classes lie in several separate clusters. To solve the multimodality problem, this article proposes a new feature selection method for semisupervised task, namely, semisupervised structured manifold learning (SSML). The new method learns a new structured graph which consists of more clusters than the known classes. Meanwhile, we propose to exploit the submanifold in both labeled data and unlabeled data by consuming the nearest neighbors of each object in both labeled and unlabeled objects. An iterative optimization algorithm is proposed to solve the new model. A series of experiments was conducted on both synthetic and real-world datasets and the experimental results verify the ability of the new method to solve the multimodality problem and its superior performance compared with the state-of-the-art methods.

Map inference algorithm aims to construct a digital map from other data sources automatically. Due to the labour intensity of traditional map creation and the frequent road change nowadays, map inference is deemed to be a promising solution to automatic map construction and update. However, existing map inference from GPS trajectories suffers from low GPS data quality, which makes the quality of the constructed map unsatisfactory. In this paper, we study the existing map inference algorithms using GPS trajectories. Different from previous surveys, we (1) include the most recent solutions and propose a new categorisation of method; (2) study how different types of GPS errors affect the quality of inference results; (3) evaluate the existing map inference quality measures regarding their ability to identify map quality issues. To achieve these goals, we conduct a comprehensive experimental study on several representative algorithms using both real-world datasets and synthetic datasets, which are generated from our proposed synthetic trajectory generator and artificial map generator. Overall, our study provides insightful observations regarding (1) which inference method performs better in each working scenario, (2) the general data quality requirements for map inference, (3) the direction of future works for quantitative map quality measures.

Degeneracy is an important concept to measure the sparsity of a graph which has been widely used in many network analysis applications. Many network analysis algorithms, such as clique enumeration and truss decomposition, perform very well in graphs having small degeneracies. In this paper, we propose an I/O-efficient algorithm to compute the degeneracy of the massive graph that cannot be fully kept in the main memory. The proposed algorithm only uses$O(n)$memory, where$n$denotes the number of nodes of the graph. We also develop an I/O-efficient algorithm to incrementally maintain the degeneracy on dynamic graphs. Extensive experiments show that our algorithms significantly outperform the state-of-the-art degeneracy computation algorithms in terms of both running time and I/O costs. The results also demonstrate high scalability of the proposed algorithms. For example, in a real-world web graph with 930 million nodes and 13.3 billion edges, the proposed algorithm takes only 633 seconds and uses less than 4.5GB memory to compute the degeneracy.

Recently, we have witnessed many HPC applications developed and hosted in the cloud, which can benefit from the elastic and diversified resources on the cloud, while on the other hand confronting high costs for executing the long-running HPC applications. Although public clouds such as Amazon EC2 offer spot instances with dynamic and usually low prices compared to on-demand ones, the spot prices can vary significantly and sometimes can even be more expensive than on-demand prices of the same type. Previous work on reducing the monetary cost for HPC applications using spot instances focused on designing fault tolerance techniques or selecting appropriate instance types/bid prices to make good usage of the low spot prices. However, with the recent update of spot pricing model on Amazon EC2, these work may become either inefficient or invalid. In this paper, we present FarSpot which is an optimization framework for HPC applications in the latest cloud spot market with the goal of minimizing application cost while ensuring performance constraints. FarSpot provides accurate long-term price prediction for a wide range of spot instance types using ensemble-based learning method. It further incorporates a cost-aware deadline assignment algorithm to distribute application deadline to each task according to spot price changes. With the assigned subdeadline of each task, FarSpot dynamically migrates tasks among spot instances to reduce execution cost. Evaluation results using real HPC benchmark show that 1) the prediction error of FarSpot is very low (below 3%), 2) FarSpot reduced the monetary cost by 32% on average compared to state-of-the-art algorithms, and 3) FarSpot satisfies the user-specified deadline constraints at all time.

Abstract Big data analysis requires the speedup of parallel computing. However, in the virtualized systems, the power of parallel computing is not fully exploited due to the limit of current VMM schedulers. Xen, one of the most popular virtualization platforms, has been widely used by industry to host parallel job. In practice, the virtualized systems are expected to accommodate both parallel jobs and serial jobs, and resource contention between virtual machines results in severe performance degradation of the parallel jobs. Moreover, the physical resource is vastly wasted during the communication process due to the ineffective scheduling of parallel jobs. Unfortunately, the existing schedulers of Xen are initially targeting at serial jobs, which are not capable of correctly scheduling the parallel jobs. This paper presents vChecker, an application-level co-scheduler which mitigates the performance degradation of the parallel job and optimizes the utilization of the hardware resource. Our co-scheduler takes number of available CPU cores in one hand, and satisfies need of the parallel jobs in other hand, which helps the credit scheduler of Xen to appropriately schedule the parallel job. As our co-scheduler is implemented at application level, no modifications on the hypervisor is required. The experimental result shows that the vChecker optimizes the performance of the parallel job in Xen and enhances the utilization of the system.

Oblivious RAM (ORAM) conceals memory access pattern by translating a single read/write operation into the accesses to a set of randomized locations. The obliviousness is achieved by adding redundancy to the memory system, which comes at the expense of increased performance overhead. In memory systems, locality has always been a critical factor, as accessing the data with temporal or spatial locality would result in a performance gain. Although the two design considerations of obliviousness and locality may seem contradictory at first glance, combining them in a unified design can potentially hide long memory access latency in ORAM without sacrificing provable data security.This paper presents LolliRAM, a cross-layer design to exploit data locality in Oblivious RAM. LolliRAM optimizes ORAM system through two different layers: (i) the data structure in ORAM, and (ii) the fast and secure cache in ORAM controller. The reuse of redundant memory accesses at the layer of data structure in ORAM can effectively reduce memory footprints. Both temporal and spatial locality can be exploited through the elastic grouping of blocks and the optimization at the layer of ORAM controller. We conduct a set of experiments using realistic workloads that are generated from standard benchmarks. Experimental results show that LolliRAM can reduce access latency by 71.57% on average (up to 81.50%) with negligible space overhead in comparison with representative schemes.

Shortest path finding is the building block of various applications in road networks and the index-based algorithms, especially hub labeling, can boost the query performance dramatically. However, the traffic condition keeps changing in real life, making the pre-computed index unable to answer the query correctly. In this work, we adopt the state-of-the-art tree decomposition-based hub labeling as the underlying index, and design efficient algorithms to incrementally maintain the index. Specifically, we first analyze the structural stability of the index in dynamic road networks which enables us to concentrate on label value maintenance. We then introduce the minimum weight property and minimum distance property to guarantee the index correctness without graph traversal. Moreover, we propose the star-centric paradigm for tracing index change and design various pruning techniques to further accelerate the index maintenance. Finally, we extend our algorithms to batch mode for shared computation, extend to structural maintenance for full types of update, and generalize to all kinds of TDHL. Our experimental results validate the superiority of our proposals over existing solutions on both index maintenance and query processing.

Selectivity estimation aims at estimating the number of database objects that satisfy a selection criterion. Answering this problem accurately and efficiently is essential to many applications, such as density estimation, outlier detection, query optimization, and data integration. The estimation problem is especially challenging for large-scale high-dimensional data due to the curse of dimensionality, the large variance of selectivity across different queries, and the need to make the estimator consistent (i.e., the selectivity is non-decreasing in the threshold). We propose a new deep learning-based model that learns a query-dependent piecewise linear function as selectivity estimator, which is flexible to fit the selectivity curve of any distance function and query object, while guaranteeing that the output is non-decreasing in the threshold. To improve the accuracy for large datasets, we propose to partition the dataset into multiple disjoint subsets and build a local model on each of them. We perform experiments on real datasets and show that the proposed model consistently outperforms state-of-the-art models in accuracy in an efficient way and is useful for real applications.

Federated learning (FL) has attracted increasing attention as a promising approach to driving a vast number of end devices with artificial intelligence. However, it is very challenging to guarantee the efficiency of FL considering the unreliable nature of end devices while the cost of device-server communication cannot be neglected. In this article, we propose SAFA, a semi-asynchronous FL protocol, to address the problems in federated learning such as low round efficiency and poor convergence rate in extreme conditions (e.g., clients dropping offline frequently). We introduce novel designs in the steps of model distribution, client selection and global aggregation to mitigate the impacts of stragglers, crashes and model staleness in order to boost efficiency and improve the quality of the global model. We have conducted extensive experiments with typical machine learning tasks. The results demonstrate that the proposed protocol is effective in terms of shortening federated round duration, reducing local resource wastage, and improving the accuracy of the global model at an acceptable communication cost.

Bike-sharing systems are becoming popular and generate a large volume of trajectory data. In a bike-sharing system, users can borrow and return bikes at different stations. In particular, a bike-sharing system will be affected by weather, the time period, and other dynamic factors, which challenges the scheduling of shared bikes. In this article, a new shared-bike demand forecasting model based on dynamic convolutional neural networks, called SDF , is proposed to predict the demand of shared bikes. SDF chooses the most relevant weather features from real weather data by using the Pearson correlation coefficient and transforms them into a two-dimensional dynamic feature matrix, taking into account the states of stations from historical data. The feature information in the matrix is extracted, learned, and trained with a newly proposed dynamic convolutional neural network to predict the demand of shared bikes in a dynamical and intelligent fashion. The phase of parameter update is optimized from three aspects: the loss function, optimization algorithm, and learning rate. Then, an accurate shared-bike demand forecasting model is designed based on the basic idea of minimizing the loss value. By comparing with classical machine learning models, the weight sharing strategy employed by SDF reduces the complexity of the network. It allows a high prediction accuracy to be achieved within a relatively short period of time. Extensive experiments are conducted on real-world bike-sharing datasets to evaluate SDF. The results show that SDF significantly outperforms classical machine learning models in prediction accuracy and efficiency.

Mobile Edge Computing (MEC), which incorporates the Cloud, edge nodes, and end devices, has shown great potential in bringing data processing closer to the data sources. Meanwhile, Federated learning (FL) has emerged as a promising privacy-preserving approach to facilitating AI applications. However, it remains a big challenge to optimize the efficiency and effectiveness of FL when it is integrated with the MEC architecture. Moreover, the unreliable nature (e.g., stragglers and intermittent drop-out) of end devices significantly slows down the FL process and affects the global model's quality in such circumstances. In this article, a multi-layer federated learning protocol called HybridFL is designed for the MEC architecture. HybridFL adopts two levels (the edge level and the cloud level) of model aggregation enacting different aggregation strategies. Moreover, in order to mitigate stragglers and end device drop-out, we introduce regional slack factors into the stage of client selection performed at the edge nodes using a probabilistic approach without identifying or probing the state of end devices (whose reliability is agnostic). We demonstrate the effectiveness of our method in modulating the proportion of clients selected and present the convergence analysis for our protocol. We have conducted extensive experiments with machine learning tasks in different scales of MEC system. The results show that HybridFL improves the FL training process significantly in terms of shortening the federated round length, speeding up the global model's convergence (by up to 12×) and reducing end device energy consumption (by up to 58 percent).

Key-value store has played a critical role in many large-scale data storage applications. The log-structured merge-tree (LSM-tree) based key-value store achieves excellent performance on write-intensive workloads which is mainly benefited from the mechanism of converting a batch of random writes into sequential writes. However, LSM-tree doesn't improve a lot in read-intensive workloads which takes a higher latency. The main reason lies in the hierarchical search mechanism in LSM-tree structure. The key challenge is how to propose new strategies based on the existing LSM-tree structure to improve read efficiency and reduce read amplifications.This paper proposes Tidal-tree, a novel data structure where data flows inside LSM-tree like Tidal waves. Tidal-tree targets at improving read efficiency in read-intensive workloads. Tidal-tree allows frequently accessed files at the bottom of LSM-tree to move to higher positions, thereby reducing read latency. Tidal-tree also makes LSM-tree into a variable shape to cater for different characteristic workloads. To evaluate the performance of Tidal-tree, we conduct a series of experiments using standard benchmarks from YCSB. The experimental results show that Tidal-tree can significantly improve read efficiency and reduce read amplifications compared with representative schemes.

Training Deep Neural Network is a computation-intensive and time-consuming task. Asynchronous Stochastic Gradient Descent (ASGD) is an effective solution to accelerate the training process since it enables the network to be trained in a distributed fashion, but with a main issue of the delayed gradient update. A recent notable work called DC-ASGD improves the performance of ASGD by compensating the delay using a cheap approximation of the Hessian matrix. DC-ASGD works well with a short delay; however, the performance drops considerably with an increasing delay between the workers and the server. In real-life large-scale distributed training, such gradient delay experienced by the worker is usually high and volatile. In this paper, we propose a novel algorithm called LC-ASGD to compensate for the delay, basing on Loss Prediction. It effectively extends the tolerable delay duration for the compensation mechanism. Specifically, LC-ASGD utilizes additional models that reside in the parameter server and predict the loss to compensate for the delay, basing on historical losses collected from each worker. The algorithm is evaluated on the popular networks and benchmark datasets. The experimental results show that our LC-ASGD significantly improves over existing methods, especially when the networks are trained with a large number of workers.

Nowadays, with the development of web services, the survival of online service has captured public attention significantly. Future prediction of business is crucial to the shopkeepers. Predicting how the business will develop and explaining what key factors are leading to it are two most important tasks. Existing literatures usually tackle only one of these two tasks, ignoring that they are two closely related tasks and complement each other. In this paper, we propose a review-based neural model, named Deep Concept-aware Model (DCA), to predict restaurants' future status and provide explainable sentences simultaneously in an end2end framework. Specifically, we use co-attention to select concepts and implement prediction and explanation tasks through Factorization Machine and Gated Recurrent Unit, respectively. We conduct extensive experiments on three Chinese cities' datasets. The proposed joint model outperforms the state-of-the-art baseline methods for both prediction (average 40.96% improvement in AUC) and explanation (average 9.72% improvement in BLEU and 86.05% in Precision metric of ROUGE).

Measuring similarities among different nodes is important in graph analysis. SimRank is one of the most popular similarity measures. Given a graph G ( V , E ) and a source node u , a single-source Sim-Rank query returns the similarities between u and each node v ∈ V. This type of query is often used in link prediction, personalized recommendation and spam detection. While dealing with a large graph is beyond the ability of a single machine due to its limited memory and computational power, it is necessary to process single-source SimRank queries in a distributed environment, where the graph is partitioned and distributed across multiple machines. However, most current solutions are based on shared-memory model, where the whole graph is loaded into a shared memory and all processors can access the graph randomly. It is difficult to deploy such algorithms on shared-nothing model. In this paper, we present DISK, a distributed framework for processing single-source SimRank queries. DISK follows the linearized formulation of SimRank, and consists of offline and online phases. In the offline phase, a tree-based method is used to estimate the diagonal correction matrix of SimRank accurately, and in the online phase, single-source similarities are computed iteratively. Under this framework, we propose different optimization techniques to boost the indexing and queries. DISK guarantees both accuracy and parallel scalability, which distinguishes itself from existing solutions. Its accuracy, efficiency, parallel scalability and scalability are also verified by extensive experimental studies. The experiments show that DISK scales up to graphs of billions of nodes and edges, and answers online queries within seconds, while ensuring the accuracy bounds.

Key-value (KV) store has been widely deployed in both embedded systems and enterprise systems. Most KV stores today use log structured merge tree (LSM-Tree), as LSM-Tree can eliminate random write operations to the secondary storage and maintain acceptable read performance. LSM-Tree is originally designed for the secondary storage device with hard disk drives. As the emerging storage media, three-dimensional (3-D) flash memory has become the mainstream technology to replace hard disk drives. Different from hard disk drives and the conventional planar flash memory, 3-D flash memory is vulnerable to temperature. High temperature will introduce both charge loss and retention degradation. Since LSM-Tree transfers random write operations to the sequential ones, the access to consecutive physical address in flash memory will cause the temperature issue. This will affect the integrity of data stored in 3-D flash memory. This article presents TLSM, a temperature-aware persistent data management scheme for LSM-Tree-based KV store on 3-D NAND flash memory. TLSM offers both application-level LSM-Tree optimization and firmware-level address management to allocate persistent data to 3-D flash. At the application-level, TLSM presents a novel temperature-aware LSM data structure to reduce the amount of data issued from LSM-Tree to 3-D flash memory. At the firmware-level, TLSM reallocates the data to physical blocks with relatively low temperature. This cross-layer optimization can effectively handle the temperature issue to ensure the data integrity of LSM-Tree in 3-D flash memory. We demonstrate the viability of the proposed scheme using a set of standard benchmarks. Our extensive evaluations show that, TLSM can significantly enhance the data integrity and reduce write amplifications compared to representative schemes.

Knee osteoarthritis (KOA) has been developed to be one of the most popular chronic joint disease in elder. Muscle shrink or force reduction of lower limb muscles such as gastrocnemius and quadriceps is a pathogenic factor about KOA. Therefore, imaging techniques such as MRI and CT for observing muscles morphological difference become popular in diagnosing KOA in clinic. However, the image information in different populations may vary according to age, weight, sex, and may be influenced by the subjective judgment according to doctor's experience. Viscoelasticity is a quantitative indicator for assessing the biomechanical properties of muscle, but there's lack of research to describe the relationship between viscoelasticity of lower limb muscles and KOA. The purpose of this study is to discuss the difference of viscoelasticity during lower limb muscles paining. We designed an experiment called muscle perfusion to simulate the muscle pain of KOA patients, and measured the lower limb muscles' viscoelasticity using shear-wave dispersion ultra-sound vibrometry (SDUV). Besides, we detected the viscoelasticity changes of a volunteer who had lower limb pain (which was similar to the symptom of KOA) during Fu's Subcutaneous Needling (FSN) treatment. Results show that during FSN treatment as well as perfusion, the elasticity and viscosity of lower limb muscles changed significantly, showing that viscoelasticity was a potential quantitative index to diagnose and qualify the disease of KOA.

Advanced three-dimensional (3D) flash memory adopts charge-trap technology that can effectively improve the hit density and reduce the coupling effect. Despite these advantages, 3D charge-trap flash brings a number of new challenges. First, current etching process is unable to manufacture perfect channels with identical feature size. Second, the cell current in 3D charge-trap flash is only 20% compared to planar flash memory, making it difficult to give a reliable sensing margin. These issues are affected by process variation, and they pose threats to the integrity of data stored in 3D charge-trap flash. This paper presents PATCH, a process-variation-resilient space allocation scheme for open-channel SSD with 3D charge-trap flash memory. PATCH is a novel hardware and file system interface that can transparently allocate physical space in the presence of process variation. PATCH utilizes the rich functionalities provided by the system infrastructure of open-channel SSD to reduce the uncorrectable bit errors. We demonstrate the viability of the proposed technique using a set of extensive experiments. Experimental results show that PATCH can effectively enhance the reliability with negligible extra erase operations in comparison with representative schemes.

Deep convolutional neural networks have become the mainstream solution for many artificial intelligence applications. However, they are still rarely deployed on mobile or edge devices due to the cost of a substantial amount of data movement among limited resources. The emerging processing-inmemory neuromorphic architecture offers a promising direction to accelerate the inference process. The key issue becomes how to effectively allocate the processing of inference between computing and storage resources on an edge device.This paper presents Mobile-I, a resource allocation scheme to accelerate the Inference process on Mobile or edge devices. Mobile-I targets at the emerging 3D neuromorphic architecture to reduce the processing latency among computing resources and fully utilize the limited on-chip storage resources. We formulate the target problem as a resource allocation problem and use a software-based solution to offer the cross-platform deployment across multiple mobile or edge devices. We conduct a set of experiments using realistic workloads that are generated from Intel Movidius neural compute stick. Experimental results show that Mobile-I can effectively reduce the processing latency and improve the utilization of computing resources with negligible overhead in comparison with representative schemes.

In the past two decades, analyzing the information network has been intensively studied from various disciplines. Small world property and scale-free property prevail in network science research. The comparison and classification of different kinds of graphs are extremely important. However, how to design a robust and accurate classification with deep learning techniques for network property still lack enough attention, which is a vital task in various application scenarios. In this paper, we proposed the reliable network property classifier based on graph embedding(RNC) to classify the network property (scale free or small world property). In order to process non-euclidean data, we embedded each network into an image and use dimensional reduction, rasterization, and convolutional neural networks to complete the classification problem. The method can effectively accomplish classification tasks in not only artificial networks but also real networks. Besides, RNC wins greatly in terms of robustness on real networks, showing the robustness of RNC against the incomplete structure of the network.

With the development of Big Data, data storage has been exposed to more challenges. Data compression which can save both storage and network bandwidth, is a very important technology to deal with the challenges. In this paper, we present an end-to-end, complete, high-throughput parallel multi-core GZIP compressor in FPGA for HDFS. The GZIP compressor is designed by the scalable architecture, which supports to increase throughput by expanding multiple compression cores based on systolic array architecture. We implemented and evaluated the hardware compressor in Alpha Data Adm-Pcie-KU3 FPGA board, utilizing RIFFA for data transfers over PCI Express. According to the evaluation results, up to 16-cores compressor can be implemented and the peak compression throughput exceeds 1.1 GB/s. It is 70X speedup compared with the software compression solution. When we load the hardware compressor into HDFS, the performance of HDFS is twice as much as that without loading the compressor.

Structural clustering is a fundamental graph mining operator which is not only able to find densely-connected clusters, but it can also identify hub vertices and outliers in the graph. Previous structural clustering algorithms are tailored to deterministic graphs. Many real-world graphs, however, are not deterministic, but are probabilistic in nature because the existence of the edge is often inferred using a variety of statistical approaches. In this paper, we formulate the problem of structural clustering on probabilistic graphs, with the aim of finding reliable clusters in a given probabilistic graph. Unlike the traditional structural clustering problem, our problem relies mainly on a novel concept called reliable structural similarity which measures the probability of the similarity between two vertices in the probabilistic graph. We develop a dynamic programming algorithm with several powerful pruning strategies to efficiently compute the reliable structural similarities. With the reliable structural similarities, we adapt an existing solution framework to calculate the structural clustering on probabilistic graphs. Comprehensive experiments on five real-life datasets demonstrate the effectiveness and efficiency of the proposed approaches.

Graphics processing units (GPUs) have become extremely important devices for accelerating computing performance in many applications. However, there have been few accurate models to estimate the performance of such applications running on modern GPUs. In this paper, we propose a performance model to estimate the execution times for massively parallel programs running on NVIDIA GPUs, one that takes on-chip resources and cost of data transfer between CPU and GPU into consideration. Four different GPUs with different architectures were used to evaluate our model. We demonstrated the effectiveness of the proposed model by applying it to various tasks in medical image registration. Experiments have demonstrated that by capturing on-chip GPU resources and data transfer time with our model, we were able to obtain a more accurate prediction of the actual running time, compared to the traditional model. Moreover, by using the optimal value of the block size parameter, estimated by our model, to accelerate the landmark tracking task on GPU devices, speedups of approximately 80×, 100×, 200× and 800×, on the C2050, K20c, M5000 and P100 can be achieved, making it possible to track massive numbers of landmarks and thereby improving the registration accuracy.

Recently, various applications including data analytics and machine learning have been developed for geo-distributed cloud data centers. For those applications, the ways of mapping parallel processes to physical nodes (i.e., “process mapping”) could significantly impact the performance of the applications because of non-uniform communication cost in geo-distributed environments. What's more, the different data privacy requirements in geo-distributed data centers pose additional constraints on process mapping solutions. While process mapping has been widely studied in grid/cluster environments, few of the existing studies have considered the problem in geo-distributed cloud environment, which is a challenging task due to the multi-level data privacy constraints, heterogeneous network performance and process failures. In this paper, we introduce the special privacy requirements in geo-distributed data centers and formulate the geo-distributed process mapping problem as an optimization problem with multiple constraints. We develop a new method to efficiently find good process mapping solutions to the problem. Experimental results on real clouds (including Amazon EC2 and Windows Azure) and simulations demonstrate that our proposed approach can achieve significant performance improvement compared to the state-of-the-art algorithms.

Due to poor cache utilization and latching contention, the B-tree like structures, which have been heavily used in traditional databases, are not suitable for modern in-memory databases running over multi-core infrastructure. To address the problem, several in-memory indices, such as FAST, Masstree, BwTree, ART and PSL, have recently been proposed, and they show good performance in concurrent settings. Given the various design choices and implementation techniques being adopted by these indices, it is therefore important to understand how these techniques and properties actually affect the indexing performance. To this end, we conduct a comprehensive performance study to compare these indices from multiple perspectives, including query throughput, scalability, latency, memory consumption as well as cache/branch miss rate, using various query workloads with different characteristics. Our results indicate that there is no one-size-fits-all solution. For example, PSL achieves better query throughput for most settings, but occupies more memory space and can incur a large overhead in updating the index. Nevertheless, the huge performance gain renders the exploitation of modern hardware features indispensable for modern database indices.

Discovering dense subgraphs in a graph is a fundamental graph mining task, which has a wide range of applications in social networks, biology and visualization to name a few. Even the problem of computing most cohesive subgraphs is NP-hard (like clique, quasi-clique, k-densest subgraph), there exists a polynomial time algorithm for computing the k-core and k-truss. In this paper, we propose a novel dense subgraph model, $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ , which leverages on a new type of important edges based on the basis of k-core and k-truss. We investigate the structural properties of the $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ model. Compared to k-core and k-truss, $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ can significantly discover the interesting and important structural information out the scope of k-core and k-truss. We study two useful problems of $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ decomposition and $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ search. In particular, we develop a k-core-truss decomposition algorithm to find all $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ in a graph G by iteratively removing edges with the smallest $${\mathsf {degree}}$$ - $${\mathsf {support}}$$ . In addition, we offer a $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ search algorithm to identifying a particular $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ containing a given query node such that the core number k is the largest. Extensive experiments on several web-scale real-world datasets show the effectiveness and efficiency of $${\mathsf {k}}$$ - $${\mathsf {core}}$$ - $${\mathsf {truss}}$$ model and proposed algorithms.

It is well known that excessive drinking could result in human diseases (e.g., liver disease and cardiovascular disease). To investigate the underlying mechanisms of the effects of alcohol consumption, dental pulp stem cells have been used due to their self-renewal capability, multi-lineage differentiation, and clonogenic efficiency. Researchers usually focus on detecting genes having different mean expression levels between different conditions. However, the variance of gene expression might also provide useful information. In this study, we applied the Brown. Forsythe (BF) test for equal variance based on a human dental pulp stem cells dataset to explore the role of alcohol on the variation of gene expression. We identified two differential variable (DV) gene probes, 213597_s_at near gene CTDSPL (FDR-adjusted p-value = 1.50x10-5) and 213993_at near gene SPON1 (FDR-adjusted p-value=0.042). To best of our knowledge, no studies have found yet the associations of CTDSPL and/or SPON1 to alcohol consumption. GeneMANIA showed that these two genes are related to 20 genes. Web based gene set analysis toolkit (WebGestalt) showed that these 22 genes are enriched in 4 alcohol-related KEGG pathways: adherens junction, TGF-beta signaling pathway, signaling pathways regulating pluripotency of stem cells, and Hippo signaling pathway.

Moderate alcohol consumption has health benefits of adults, while excessive alcohol has poisonous effects on numerous different organs. However, the underlying molecular mechanisms of this phenomenon are still largely unclear yet. Human dental pulp stem cells (hDPSCs) have been used as models to investigate the effect of alcohol (EtOH) on gene expression. It has been demonstrated that both EtOH dosage and exposure time affects gene expression. However, the investigation into whether there exists synergistic effect of EtOH dosage and exposure time on gene expression is rare. In the present study, we reported that the effect of interaction between EtOH dosage and exposure time is significantly associated with the expression of genes SLC25A36 and ZFAND5 based on an hDPSC experiment. This result is novel in that genes SLC25A36 and ZFAND5 have not been reported yet to be associated with alcohol consumption in the existing literature.

Three-dimensional (3D) flash memory is an emerging memory technology that enables a number of improvements to conventional planar NAND flash memory, including larger capacity, less program disturbance, and lower access latency. In contrast to conventional planar flash memory, 3D flash memory adopts charge-trapping mechanism. NAND strings punch through multiple stacked layers to form the three-dimensional infrastructure. However, the etching processes for NAND strings are unable to produce perfectly vertical features, especially on the scale of 20 nanometers or less. The process variation will cause uneven distribution of electrons, which poses a threat to the integrity of data stored in flash. This paper present P-Alloc , a process-variation tolerant reliability management strategy for 3D charge-trapping flash memory. P-Alloc offers both hardware and software support to allocate data to the 3D flash in the presence of process variation. P-Alloc predicts the state of a physical page, i.e., the basic unit for each write or read operation in flash memory, and tries to assign critical data to more reliable pages. A hardware-based voltage threshold compensation scheme is also proposed to further reduce the faults. We demonstrate the viability of the proposed scheme using a variety of realistic workloads. Our extensive evaluations show that, P-Alloc significantly enhances the reliability and reduces the access latency compared to the baseline scheme.

The Group Steiner Tree (GST) problem is a fundamental problem in database area that has been successfully applied to keyword search in relational databases and team search in social networks. The state-of-the-art algorithm for the GST problem is a parameterized dynamic programming (DP) algorithm, which finds the optimal tree in O(3kn+2k(n log n + m)) time, where k is the number of given groups, m and n are the number of the edges and nodes of the graph respectively. The major limitations of the parameterized DP algorithm are twofold: (i) it is intractable even for very small values of k (e.g., k=8) in large graphs due to its exponential complexity, and (ii) it cannot generate a solution until the algorithm has completed its entire execution. To overcome these limitations, we propose an efficient and progressive GST algorithm in this paper, called PrunedDP. It is based on newly-developed optimal-tree decomposition and conditional tree merging techniques. The proposed algorithm not only drastically reduces the search space of the parameterized DP algorithm, but it also produces progressively-refined feasible solutions during algorithm execution. To further speed up the PrunedDP algorithm, we propose a progressive A*-search algorithm, based on several carefully-designed lower-bounding techniques. We conduct extensive experiments to evaluate our algorithms on several large scale real-world graphs. The results show that our best algorithm is not only able to generate progressively-refined feasible solutions, but it also finds the optimal solution with at least two orders of magnitude acceleration over the state-of-the-art algorithm, using much less memory.

Real-time ride-sharing applications (e.g., Uber and Lyft) are very popular in recent years. Motivated by the ride-sharing application, we propose a new type of query in road networks, called the optimal multi-meeting-point route (OMMPR) query. Given a road network G, a source nodes, a target node t, and a set of query nodes U, the OMMPR query aims at finding the best route starting from s and ending at t such that the weighted average cost between the cost of the route and the total cost of the shortest paths from every query node to the route is minimized. We show that the problem of computing the OMMPR query is NP-hard. To answer the OMMPR query efficiently, we propose two novel parameterized solutions based on dynamic programming (DP), with the number of query nodes l (i.e., l = |U|) as a parameter, which is typically very small in practice. The two proposed parameterized algorithms run in O(3l· m + 2l· n · (l + log (n))) and O(2l· (m + n · (l + log (n)))) time, respectively, where n and m denote the number of nodes and edges in graph G, thus they are tractable in practice. To reduce the search space of the DP-based algorithms, we propose two novel optimized algorithms based on bidirectional DP and a carefully-designed lower bounding technique. We conduct extensive experimental studies on four large real-world road networks, and the results demonstrate the efficiency of the proposed algorithms.

Uncertain graph management has been recognized as an important research topic in recent years. In this paper, we first introduce two types of query evaluation problems on uncertain graphs, named expectation query evaluation and threshold query evaluation. Most previous solutions for these problems are based on naive Monte-Carlo (NMC) sampling, which typically result in large variances. To reduce the variance ofNMC, we propose two efficient estimators, calledRSS-IandRSS-IIestimators, based on the idea of recursive stratified sampling (RSS). To further reduce the variances ofRSS-IandRSS-II, we propose a recursivecut-setbased stratified sampling estimator for a particular kind of query evaluation problem. We show that all the proposed estimators are unbiased and their variances are significantly smaller than that ofNMC. Moreover, the time complexity of all the proposed estimators are the same as that ofNMCunder a mild assumption. In addition, we develop an elegant graph simplification technique to further improve the accuracy and running time of our estimators. We also apply the proposed estimators to three different uncertain graph query evaluation problems. Finally, we conduct extensive experiments to evaluate the proposed estimators, and the results show the accuracy, efficiency, and scalability of our estimators.

Automated weighted graph construction from massive data is essential to weighted graph theory based data mining processes, where the edge weight computation is time consuming or even fails to complete on a single machine when necessary resources are exhausted. In addition, existing work lacks of the measurement on the accuracy of the edge weights, which represents the graph accuracy and affects the following data mining results. This paper describes the classification, implementation and evaluation of edge weight computation algorithms with MapReduce Framework, which is a powerful parallel and distributed processing model. First, a classification of the edge weight computation algorithms is developed and how they can be applied on MapReduce is also discussed. Then we propose comprehensive measurements on the edge weight accuracy in terms of the number of edges, strength distribution, community structure, Hop-plot and effective diameters. Finally, a performance study has been conducted to evaluate these algorithms in terms of memory and disk usage, execution time and accuracy using a real massive social network application dataset. The results are presented and discussed. Our comparison results can help find out the most effective parallel and distributed edge weight computation algorithm for constructing a weighted graph for a given massive dataset.

Random walk based graph sampling has been recognized as a fundamental technique to collect uniform node samples from a large graph. In this paper, we first present a comprehensive analysis of the drawbacks of three widely-used random walk based graph sampling algorithms, called re-weighted random walk (RW) algorithm, Metropolis-Hastings random walk (MH) algorithm and maximum-degree random walk (MD) algorithm. Then, to address the limitations of these algorithms, we propose two general random walk based algorithms, named rejection-controlled Metropolis-Hastings (RCMH) algorithm and generalized maximum-degree random walk (GMD) algorithm. We show that RCMH balances the tradeoff between the limitations of RW and MH, and GMD balances the tradeoff between the drawbacks of RW and MD. To further improve the performance of our algorithms, we integrate the so-called delayed acceptance technique and the non-backtracking random walk technique into RCMH and GMD respectively. We conduct extensive experiments over four real-world datasets, and the results demonstrate the effectiveness of the proposed algorithms.

Community search is a problem of finding densely connected subgraphs that satisfy the query conditions in a network, which has attracted much attention in recent years. However, all the previous studies on community search do not consider the influence of a community. In this paper, we introduce a novel community model called k -influential community based on the concept of k -core, which can capture the influence of a community. Based on the new community model, we propose a linear-time online search algorithm to find the top- r k -influential communities in a network. To further speed up the influential community search algorithm, we devise a linear-space index structure which supports efficient search of the top- r k -influential communities in optimal time. We also propose an efficient algorithm to maintain the index when the network is frequently updated. We conduct extensive experiments on 7 real-world large networks, and the results demonstrate the efficiency and effectiveness of the proposed methods.

In this paper, we introduce two types of query evaluation problems on uncertain graphs: expectation query evaluation and threshold query evaluation. Since these two problems are #P-complete, most previous solutions for these problems are based on naive Monte-Carlo (NMC) sampling. However, NMC typically leads to a large variance, which significantly reduces its effectiveness. To overcome this problem, we propose two classes of estimators, called class-I and class-II estimators, based on the idea of stratified sampling. More specifically, we first propose two classes of basic stratified sampling estimators, named BSS-I and BSS-II, which partition the entire population into 2rand r+1 strata by picking r edges respectively. Second, to reduce the variance, we find that both BSS-I and BSS-II can be recursively performed in each stratum. Therefore, we propose two classes of recursive stratified sampling estimators called RSS-I and RSS-II respectively. Third, for a particular kind of problem, we propose two cut-set based stratified sampling estimators, named BCSS and RCSS, to further improve the accuracy of the class-I and class-II estimators. For all the proposed estimators, we prove that they are unbiased and their variances are significantly smaller than that of NMC. Moreover, the time complexity of all the proposed estimators are the same as the time complexity of NMC under a mild assumption. In addition, we also apply the proposed estimators to influence function evaluation and expected-reliable distance query problem, which are two instances of the query evaluation problems on uncertain graphs. Finally, we conduct extensive experiments to evaluate our estimators, and the results demonstrate the efficiency, accuracy, and scalability of the proposed estimators.

The k-core decomposition in a graph is a fundamental problem for social network analysis. The problem of k-core decomposition is to calculate the core number for every node in a graph. Previous studies mainly focus on k-core decomposition in a static graph. There exists a linear time algorithm for k-core decomposition in a static graph. However, in many real-world applications such as online social networks and the Internet, the graph typically evolves overtime. In such applications, a key issue is to maintain the core numbers of nodes when the graph changes overtime. A simple implementation is to perform the linear time algorithm to recompute the core number for every node after the graph is updated. Such simple implementation is expensive when the graph is very large. In this paper, we propose a new efficient algorithm to maintain the core number for every node in a dynamic graph. Our main result is that only certain nodes need to update their core numbers when the graph is changed by inserting/deleting an edge. We devise an efficient algorithm to identify and recompute the core numbers of such nodes. The complexity of our algorithm is independent of the graph size. In addition, to further accelerate the algorithm, we develop two pruning strategies by exploiting the lower and upper bounds of the core number. Finally, we conduct extensive experiments over both real-world and synthetic datasets, and the results demonstrate the efficiency of the proposed algorithm.

In traditional radio-based localization methods, the target object has to carry a transmitter (e.g., active RFID), a receiver (e.g., 802.11 × detector), or a transceiver (e.g., sensor node). However, in some applications, such as safe guard systems, it is not possible to meet this precondition. In this paper, we propose a model of signal dynamics to allow the tracking of a transceiver-free object. Based on radio signal strength indicator (RSSI), which is readily available in wireless communication, three centralized tracking algorithms, and one distributed tracking algorithm are proposed to eliminate noise behaviors and improve accuracy. The midpoint and intersection algorithms can be applied to track a single object without calibration, while the best-cover algorithm has higher tracking accuracy but requires calibration. The probabilistic cover algorithm is based on distributed dynamic clustering. It can dramatically improve the localization accuracy when multiple objects are present. Our experimental test-bed is a grid sensor array based on MICA2 sensor nodes. The experimental results show that the localization accuracy for single object can reach about 0.8 m and for multiple objects is about 1 m.

Genomics data is being produced at an unprecedented rate, especially in the context of clinical applications and grand challenge questions. There are various types of data in genomics research, most of which are stored as plain text tables. A data compression framework tailored to this file type is introduced in this paper, featuring a combination of generic compression algorithms, GPU acceleration, and column-major storage. This approach is the first to achieve both compression and decompression rates of around 100MB/s on commodity hardware without compromising compression ratio. By selecting appropriate compression schemes for each column of data, this framework efficiently exploits data redundancy while remaining applicable to a wide range of formats. The GPU-accelerated implementation also properly exploits the parallelism of compression algorithms. Finally, this paper presents a novel first-order Markov model based transformation, with evidence that it is at least as effective as Burrows-Wheeler and Move-To-Front in some contexts.

The prior studies setup the churn model by measuring the historical logs or records of a P2P network, and treat it as one whole black-box without understanding the inside of peer's population. The metrics used to characterize the churn is distributions of the node session lengths and arrival intervals. We investigate churn in a higher level point of view, and find that modeling it based on the global geographical distribution of peer nodes will result in a system which explain the fluctuation and cyclic phenomenon of network size. This model considers the user behavior pattern into account. Then we provide a Matlab tools that can provide churn events according to this model. From the output events of simulation, we do see some more future things than other models. We might expect or predict when and what nodes would return back, as well as when and what nodes would disappear at high possibility. So it is useful when designing a system optimized both to the pass and the future, which could reduce the overhead of the maintenance of underlying overlay network of DHTs and lower the redundant level of replications for P2P storage system.

Managing data with distance-based indexing methods has the potential to provide scalability and integration with relational database management systems and the SQL programming model. We previously demonstrated the advantages of such an approach for nucleotide sequences using Hamming distance (mismatch). However, the larger alphabet size of peptide sequences increases the dimensionality of the problem, making algorithmic results more challenging. The development of a metric-PAM substitution matrix enables metric-distance based indexing for peptide sequences. The performance of distance-based indexing for homologous protein retrieval entails trade-off among accuracy, scalability and computational cost. We investigate the application of the multi-vantage point (MVP) tree algorithm to index peptide k-mers based on global mPAM alignment. We show that k-mer retrieval can still maintain accuracy when k is at least as large as 6 that creates a domain of over 60 million key values and enables scalability sufficient for effective performance on large disk-resident sequence databases

MOTIVATION: We reformulate the problem of comparing mass-spectra by mapping spectra to a vector space model. Our search method leverages a metric space indexing algorithm to produce an initial candidate set, which can be followed by any fine ranking scheme. RESULTS: We consider three distance measures integrated into a multi-vantage point index structure. Of these, a semi-metric fuzzy-cosine distance using peptide precursor mass constraints performs the best. The index acts as a coarse, lossless filter with respect to the SEQUEST and ProFound scoring schemes, reducing the number of distance computations and returned candidates for fine filtering to about 0.5% and 0.02% of the database respectively. The fuzzy cosine distance term improves specificity over a peptide precursor mass filter, reducing the number of returned candidates by an order of magnitude. Run time measurements suggest proportional speedups in overall search times. Using an implementation of ProFound's Bayesian score as an example of a fine filter on a test set of Escherichia coli protein fragmentation spectra, the top results of our sample system are consistent with that of SEQUEST.

Hierarchical metric-space clustering methods have been commonly used to organize proteomes into taxonomies. Consequently, it is often anticipated that hierarchical clustering can be leveraged as a basis for scalable database index structures capable of managing the hyper-exponential growth of sequence data. M-tree is one such data structure specialized for the management of large data sets on disk. We explore the application of M-trees to the storage and retrieval of peptide sequence data. Exploiting a technique first suggested by Myers (1994), we organize the database as records of fixed length substrings. Empirical results are promising. However, metric-space indexes are subject to "the curse of dimensionality" and the ultimate performance of an index is sensitive to the quality of the initial construction of the index. We introduce new hierarchical bulk-load algorithm that alternates between top-down and bottom-up clustering to initialize the index. Using the Yeast Proteomes, the bi-directional bulk load produces a more effective index than the existing M-tree initialization algorithms.

MoBIoS is a specialized database management system whose storage manager is based on metricspace indexing, and whose query language entails biological data types. When relational database management systems are used to support biological data, important data types are relegated to blob and unstructured text fields. Thus, even simple, but critical queries are executed by sequentially dumping the data to utilities outside the database. MoBIoS provides O(log n) physical access to diverse biological data types as well as uniform logical and syntactic access. Consequently, MoBIoS provides a framework where complex bioinformatic algorithms may be effectively expressed and executed as concise declarative SQL-like (Structured Query Language) queries.