Persistent Memory (PM) and Remote Direct Memory Access (RDMA) technologies have significantly improved the storage and network performance in data centers and spawned a slew of distributed file systems (DFS) designs. Existing DFSs often consider remote storage a performance constraint, assuming it delivers lower bandwidth and higher latency than local devices. However, the advancements in RDMA technology present an opportunity to narrow the performance disparity between local and remote access, empowering DFSs to harness both local and remote I/O capabilities, thereby attaining higher aggregated throughput. We propose SwitchFS, a new DFS architecture that exploits all the available PM bandwidth in a cluster with generative I/O path assignment policy. It dynamically steers client-side I/O requests to the local cache and the remote devices accessible through RDMA network. To determine the run-time I/O path adaptively, we introduce MELON, an I/O path selection policy based on a reinforcement learning model, designed to optimize expected I/O latency. Meanwhile, SwitchFS adopts a model-driven opportunistic replication mechanism at the server-side, which further improves I/O bandwidth utilization of remote devices across the cluster. Furthermore, we adopt the fine-grained concurrency control approach to improve scalability. Across synthetic and real-world application workloads, SwitchFS improves throughput by up to 5.9× over existing DFS designs while preserving low tail latency and incurring modest learning overhead.

The log-structured nature of NAND flash storage necessitates garbage collection in SSDs. Garbage collection (GC) is a major source of runtime write amplification (WA), leading to faster device wear out and interference with host I/Os. The key to mitigating this problem is separating data by lifetime so that data in the same flash block are invalidated within temporal proximity. For higher lifetime prediction accuracy and adaptibility, prior works proposed using machine learning algorithms for data separation. However, existing learning-based solutions perform data lifetime prediction at the host side, leading to several drawbacks. First, host-side prediction does not have knowledge of the internal data movement inside the SSD during GC, and thus fails to leverage the opportunity to further separate GC writes, resulting in suboptimal WA reduction in the long term. Second, performing prediction at the host significantly prolongs the I/O critical path and consumes host resources that could otherwise be used for serving user applications. We present Shiro, a holistic FTL design that performs instorage data separation for both user writes and GC writes for maximal long-term WA reduction. For user writes, Shiro uses a sequence model to accurately predict data lifetime by learning lifetime distribution from long historical access patterns. For GC writes, Shiro incorporates a reinforcement learning-assisted page migration strategy that takes direct feedback from longterm WA to further improve data separation efficacy. To address the challenges posed by performing fine-grained and real-time machine learning decisions inside the resource-constrained SSD, we propose a suite of enabling techniques to keep computation and storage overhead low. Extensive evaluation of Shiro on real-world traces shows that Shiro can deliver 29 WA compared with conventional FTL and state-of-the-art instorage data separation schemes. Furthermore, thanks to lower data migration overhead during GC, Shiro achieves significantly higher steady-state I/O performance.

Disaggregated memory (DM) architecture physically separates computing and memory resources into distinct pools interconnected via high-speed networks within data centers, with the aim of improving resource utilization compared to traditional architectures. Most existing range indexes for DM that support variable-length keys are based on adaptive radix trees. However, these indexes exhibit suboptimal performance on DM due to excessive network round trips during tree traversal and inefficient node-based caching mechanisms.To address these issues, we propose Sphinx, a novel hybrid index for DM. Sphinx introduces an Inner Node Hash Table to minimize the network round trips during index operations by replacing the sequential tree traversal with parallel hash reads. Sphinx incorporates a Succinct Filter Cache to further minimize network overhead while keeping the computing-side cache small and coherent. Experimental results show that Sphinx outperforms state-of-the-art counterparts by up to 7.3 × in the YCSB benchmark.

Computational SSDs implement the in-storage computing (ISC) paradigm and benefit applications by taking over I/O-intensive tasks from the host. Existing works have proposed various frameworks aiming at easy access to ISC functionalities, and among them generic frameworks with file-based abstractions offer better usability. However, since intermediate output by ISC tasks may leave files in a dirty state, concurrent access to and the integrity of file data should be properly managed, which has not been fully addressed. In this paper, we present TxISC, a generic ISC framework that coordinates the host kernel and device firmware to offer a versatile file-based programming model. Under the hood, TxISC turns each invocation of an ISC task into a transaction with full ACID guarantee, fully covering concurrency control and data protection. TxISC implements transactions at low cost by leveraging the out-of-place write characteristic of NAND flash. Evaluation on full-stack hardware shows that transactions incur almost no runtime performance penalty compared with existing ISC architectures. Application case studies demonstrate that the programming model of TxISC can be used to offload complex logic and deliver significant speedup over host-only solutions.

Understanding the underlying argumentative flow in analytic argumentative writing is essential for discourse comprehension, especially in complex argumentative discourse such as think-tank commentary.However, existing structure modeling approaches often rely on surface-level topic segmentation, failing to capture the author's rhetorical intent and reasoning process.To address this limitation, we propose a Question-Focus discourse structuring framework that explicitly models the underlying argumentative flow by anchoring each argumentative unit to a guiding question (reflecting the author's intent) and a set of attentional foci (highlighting analytical pathways).To assess its effectiveness, we introduce an argument reconstruction task in which the modeled discourse structure guides both evidence retrieval and argument generation.We construct a high-quality dataset comprising 600 authoritative Chinese think-tank articles for experimental analysis.To quantitatively evaluate performance, we propose two novel metrics: (1) Claim Coverage, measuring the proportion of original claims preserved or similarly expressed in reconstructions, and (2) Evidence Coverage, assessing the completeness of retrieved supporting evidence.Experimental results show that our framework uncovers the author's argumentative logic more effectively and offers better structural guidance for reconstruction, yielding up to a 10% gain in claim coverage and outperforming strong baselines across both curated and LLM-based metrics.

As the memory demand continues to surge, the limitations of DRAM scalability have spurred the development of various new memory technologies in today's data centers. In order to harness the benefits of the heterogeneous memory architecture, tiering has become a widely adopted memory management paradigm. The effectiveness of a tiered memory management system primarily relies on its ability to accurately identify frequently accessed ("hot") pages and infrequently accessed ("cold") pages, and efficiently relocate them between tiers. However, existing systems rely on coarse-grained frequency measurement schemes that do not align with the performance characteristics of modern memory devices and memory-intensive applications. Additionally, these systems often incorporate rigid rules or manually configured parameters for page classification, resulting in inflexible migration strategies.

Retrieval-Augmented Generation (RAG) addresses large language model (LLM) hallucinations by grounding responses in external knowledge, but its effectiveness is compromised by poor-quality retrieved contexts containing irrelevant or noisy information. While existing approaches attempt to improve performance through context selection based on predefined context quality assessment metrics, they show limited gains over standard RAG. We attribute this limitation to their failure in holistically utilizing available information (query, context list, and generator) for comprehensive quality assessment. Inspired by recent advances in data selection, we reconceptualize context quality assessment as an inference-time data valuation problem and introduce the Contextual Influence Value (CI value). This novel metric quantifies context quality by measuring the performance degradation when removing each context from the list, effectively integrating query-aware relevance, list-aware uniqueness, and generator-aware alignment. Moreover, CI value eliminates complex selection hyperparameter tuning by simply retaining contexts with positive CI values. To address practical challenges of label dependency and computational overhead, we develop a parameterized surrogate model for CI value prediction during inference. The model employs a hierarchical architecture that captures both local query-context relevance and global inter-context interactions, trained through oracle CI value supervision and end-to-end generator feedback. Extensive experiments across 8 NLP tasks and multiple LLMs demonstrate that our context selection method significantly outperforms state-of-the-art baselines, effectively filtering poor-quality contexts while preserving critical information. Code is available at https://github.com/SJTU-DMTai/RAG-CSM.

This paper presents μTPS, a new thread architecture tailored for in-memory key-value stores (KVSs) that operate at tens of millions of operations per second. We show through analysis and demonstration that the widely used run-to-completion thread architecture, which executes monolithic functions from start to finish, often suffers from cache inefficiencies and contention issues. To address this, we revisit the once widely used thread-per-stage (TPS) architecture, but with a fresh perspective – separating cache-resident, contention-free stages and memory-resident, conflict-prone stages into distinct thread pools, and scheduling them with dedicated hardware resources (e.g., CPU cores, cache ways). This novel division enables independent optimization of each stage, significantly improving cache efficiency and mitigating contention. Additionally, μTPS incorporates reconfigurable RPC, resizable caching, and an auto-tuner to enhance its schedulability and performance. We implement two in-memory key-value stores, μTPS-H and μTPS-T, to demonstrate the effectiveness of this approach. Evaluation results show that μTPS achieves higher performance than the run-to-completion counterparts.

Byte-addressable storage (BAS), such as persistent memory and CXL-SSDs, does not meet system designers’ expectations for data flushing and access granularity. Persistent CPU caches, enabled by recent techniques like Intel’s eADR and CXL’s Global Persistent Flush, can mitigate these issues without sacrificing consistency. However, the shared nature of CPU caches can lead to cache contention, which can result in cached data being frequently evicted to the BAS and reloaded into caches, negating the benefits of caching. If the BAS write granularity is larger than the cacheline eviction granularity, this can also lead to severe write amplification. In this article, we identify, characterize, and propose solutions to the problem of contention in persistent CPU caches, which is largely overlooked by existing systems. These systems either simply assume that cached data is hot enough to survive cache evictions or use unsupported cache allocation techniques without testing their effectiveness. We also present FusionFS, a contention-resilient kernel file system that uses persistent CPU caches to redesign data update approaches. FusionFS employs an adaptive data update approach that chooses the most effective mechanism based on file access patterns during system calls and memory mapping accesses, minimizing BAS media writes and improving throughput. FusionFS also employs contention-aware cache allocation to minimize various types of cache contention. Experimental results show that FusionFS outperforms existing file systems and effectively mitigates various types of cache contention.

With the growing memory requirements of modern data-intensive applications for high performance and large capacity, building hybrid memory systems with different memory technologies has become a dominant trend to satisfy these demands. For better system performance, frequently accessed hot data is fetched into the fast and capacity-limited near memory (NM) while cold data is evicted to the slow and large far memory (FM). In prior works, NM is used as a cache of FM (cNM), part of OS-visible memory (mNM), and a fixed capacity of cNM and mNM. This article presents Phoenix, a novel hybrid memory architecture that harnesses the advantages of both cNM and mNM. The ratio of cNM to mNM is adjustable during runtime to better exploit both temporal and spatial locality benefits for different memory access patterns. All cNM and mNM space is multiplexed to mitigate the data movement overhead for the mode switch between cNM and mNM. In our evaluations, Phoenix outperforms state-of-the-art designs by an average of 18.2% and consumes orders of magnitude less metadata storage space.

Regular path queries (RPQs) in graph databases are bottlenecked by the memory wall. Emerging processing-in-memory (PIM) technologies offer a promising solution to dispatch and execute path matching tasks in parallel within PIM modules. We present an efficient PIM-based data management system tailored for RPQs and graph updates. Our solution, called PimBeam, facilitates efficient batch RPQs and graph updates by implementing a PIM-friendly dynamic graph partitioning algorithm. This algorithm effectively addresses graph skewness issues while maintaining graph locality with low overhead for handling RPQs. PimBeam streamlines label filtering queries by adding a filtering module on the PIM side and leveraging the parallelism of PIM. For the graph updates, PimBeam enhances processing efficiency by amortizing the host CPU's update overhead to PIM modules. Evaluation results of PimBeam indicate 3.59x speedup for RPQs and 29.33x speedup for graph update on average over the state-of-the-art traditional graph database.

Regular path queries (RPQs) in graph databases are bottlenecked by the memory wall. Emerging processing-in-memory (PIM) technologies offer a promising solution to dispatch and execute path matching tasks in parallel within PIM modules. We present Moctopus, a PIM-based data management system for graph databases that supports efficient batch RPQs and graph updates. Moctopus employs a PIM-friendly dynamic graph partitioning algorithm, which tackles graph skewness and preserves graph locality with low overhead for RPQ processing. Moctopus enables efficient graph update by amortizing the host CPU's update overhead to PIM modules. Evaluation of Moctopus demonstrates superiority over the state-of-the-art traditional graph database.

Byte-addressable persistent memory (PM) has been widely studied in the past few years. Recently, the emerging eADR technology further incorporates CPU cache into the persistence domain. The persistent CPU cache is promising to optimize the write performance of PM-based storage systems and facilitate the design of concurrent crash-consistent data structures. In this paper, we propose Spash, a highly scalable persistent hash index for PM systems with persistent CPU cache. Spash fully exploits the benefits of persistent CPU cache to implement a durable linearizable index with low PM access overhead and high concurrency. Spash employs a fine-grained extendible hash architecture and a metadata-free segment design to minimize the number of PM accesses. Moreover, Spash adopts adaptive in-place updates and compacted-flush insertions, which dramatically conserve scarce PM write bandwidth by absorbing a large amount of PM write in the persistent CPU cache. Furthermore, Spash proposes a two-phase concurrency protocol and a collaborative staged doubling mechanism, which leverage the persistent CPU cache and hardware transactional memory to achieve lock-free concurrency and durable linearizability. Spash outperforms the other state-of-the-art persistent hash indexes in YCSB workloads by up to 19.6×.

Pointer chasing becomes the performance bottleneck for today's in-memory indexes due to the memory wall. Emerging processing-in-memory (PIM) technologies are promising to mitigate this bottleneck, by enabling low-latency memory access and aggregated memory bandwidth scaling with the number of PIM modules. Prior PIM-based indexes adopt a fixed granularity to partition the key space and maintain static heights of skiplist nodes among PIM modules to accelerate index operations on skiplist, neglecting the changes in skewness and hotness of data access patterns during runtime. In this article, we present RADAR, an innovative PIM-friendly skiplist that dynamically partitions the key space among PIM modules to adapt to varying skewness. An offline learning-based model is employed to catch hotness changes to adjust the heights of skiplist nodes. In multiple datasets, RADAR achieves up to 198.2x performance improvement and consumes 47.4% less memory than state-of-the-art designs on real PIM hardware.

Persistent memory (PM) promises near-DRAM performance as well as data persistence. Recently, a new feature called eADR is available for PM-equipped platforms to guarantee the persistence of CPU cache. The emergence of eADR presents unique opportunities to build lock-free data structures and unleash the full potential of PM. In this paper, we propose NBTree, a lock-free PM-friendly B$^+$-Tree, to deliver high scalability and low PM overhead. To our knowledge, NBTree is the first persistent index designed for PM systems with persistent CPU cache. To achieve lock-free, NBTree uses atomic primitives to serialize index operations. Moreover, NBTree proposes five novel techniques to enable lock-free accesses during structural modification operations (SMO), includingthree-phase SMO,sync-on-write,sync-on-read,cooperative SMO, andshift-aware search. To reduce PM access overhead, NBTree employs a decoupled leaf node design to absorb the metadata accesses in DRAM. Moreover, NBTree devises a cache-crafty persistent allocator and adoptslog-structured insertandin-place update/deleteto enhance the access locality of write operations, absorbing a substantial amount of PM writes in persistent CPU cache. Our evaluation shows that NBTree achieves up to 11× higher throughput and 43× lower 99% tail latency than state-of-the-art persistent B$^+$-Trees under YCSB workloads.

Emerging die-stacked memories can provide higher bandwidth than traditional off-chip DRAM and serve as an off-chip DRAM cache or part of OS-visible memory (POM). This paper presents Bumblebee, a new hybrid memory architecture combining the advantages of both DRAM cache and POM. The ratio of DRAM cache to POM is adjustable in real time to better exploit both temporal and spatial locality benefits for different memory access patterns. Our evaluations indicate at least 35.2% performance improvement and 10.9% ∼ 20.1% less memory dynamic energy consumption for Bumblebee over state-of-the-art designs, as well as orders of magnitude less metadata storage space.

Garbage collection in SSDs causes write amplification. The key to mitigating this problem is separating data by lifetime. Prior works proposed using machine learning to accurately predict data lifetime but prediction is performed at the host side, burdening the host storage stack. We present PHFTL, a practical, holistic FTL design with device-side learning-based data separation. The machine learning model in PHFTL accurately and adaptively predicts the lifetime of every written page. A suite of enabling techniques are introduced to keep computation and storage overhead low. Extensive evaluation of PHFTL demonstrates superiority over state-of-the-art and feasibility on real hardware.

Concurrent indexes for persistent memory (PM) have been extensively investigated due to the appealing features of PM, such as data persistence and DRAM-comparable performance. Among them, Adaptive Radix Tree (ART) is a widely used index that performs well on variable-sized keys. Nevertheless, existing persistent ARTs still suffer from high PM overhead as well as inefficient concurrency control.In this paper, we present Heart, a persistent ART with low latency and high scalability. Heart proposes a unified node structure for different capacities with Hashed Node and Node Decoupling to reduce the PM access overhead. To achieve high scalability, especially in write-intensive scenarios, we propose an efficient concurrency control protocol with lock-free basic operations and lock-free node split. Furthermore, Heart employs Perceivable Transformation to avoid anomalies during node expansion and shrinkage. Compared to other state-of-the-art persistent ARTs, Heart achieves up to 21.6× higher performance under YCSB workloads with high memory utilization. We also deploy Heart in DRAM and obtain up to 33.4× speedup than the original in-memory ART.

Persistent Memory (PM) and Remote Direct Memory Access (RDMA) technologies have significantly improved the storage and network performance in data centers and spawned a slew of distributed file system (DFS) designs. Existing DFSs often consider remote storage a performance constraint, assuming it delivers lower bandwidth and higher latency than local storage devices. However, the advances in RDMA technology provide an opportunity to bridge the performance gap between local and remote access, enabling DFSs to leverage both local and remote PM bandwidth and achieve higher overall throughput.

A deep classifier is usually trained to (i) learn the numeric representation vector of samples and (ii) classify sample representations with learned classification boundaries. Time-travelling visualization, as an explainable AI technique, is designed to transform the model training dynamics into an animation of canvas with colorful dots and territories. Despite that the training dynamics of the high-level concepts such as sample representations and classification boundaries are now observable, the model developers can still be overwhelmed by tens of thousands of moving dots across hundreds of training epochs (i.e., frames in the animation), which makes them miss important training events.

Prediction over tabular data is often a crucial task in many real-life applications. Recent advances in deep learning give rise to various deep models for tabular data prediction. A common and essential step in these models is to vectorize raw input features in tabular data into dense embeddings. Choosing a suitable dimension for each feature is challenging yet necessary to improve model’s performance and reduce memory cost of model parameters. Existing solutions to embedding dimensionality search always choose dimensions from a restricted candidate set. This restriction improves the search efficiency but would produce suboptimal embedding dimensions that hurt model’s predictive performance. In this paper, we develop AutoSrh, a flexible embedding dimensionality search framework that can select varying dimensions for different features through differentiable optimization. The key idea of AutoSrh is to relax the search space to be continuous and optimize the selection of embedding dimensions via gradient descent. After optimization, AutoSrh performs embedding pruning to derive the mixed embedding dimensions and retrains the model to further improve the performance. Extensive experiments on five real-world tabular datasets demonstrate that AutoSrh can achieve better predictive performance than the existing approaches with 1.1$\sim$1.6x lower training time cost and reserve model’s predictive performance while reducing 50$\sim$95% embedding parameters.

Emerging fast, byte-addressable persistent memory (PM) promises substantial storage performance gains compared with traditional disks. We present TPFS, a tiered file system that combines PM and slow disks to create a storage system with near-PM performance and large capacity. TPFS steers incoming file input/output (I/O) to PM, dynamic random access memory (DRAM), or disk depending on the synchronicity, write size, and read frequency. TPFS profiles the application’s access stream online to predict the behavior of file access. In the background, TPFS estimates the “temperature” of file data and migrates the write-cold and read-hot file data from PM to disks. To fully utilize disk bandwidth, TPFS coalesces data blocks into large, sequential writes. Experimental results show that with a small amount of PM and a large solid-state drive (SSD), TPFS achieves up to 7.3× and 7.9× throughput improvement compared with EXT4 and XFS running on an SSD alone, respectively. As the amount of PM grows, TPFS’s performance improves until it matches the performance of a PM-only file system.

In recent years, deep learning obtains amazing achievements in various fields, and has been used in safety-critical scenarios. In such scenarios, bugs in deep learning software can introduce disastrous consequences. To deepen the understanding on bugs in deep learning software, researchers have conducted several empirical studies on their bug characteristics. In the prior studies, researchers analyzed the source code, bug reports, pull requests, and fixes of deep learning bugs. Although these studies provide meaningful findings, to the best of our knowledge, no prior studies have explored the runtime behaviors of deep learning bugs, because it is rather expensive to collect runtime impacts of deep learning bugs. As a result, some fundamental questions along with deep learning bugs are still open. For example, do most such bugs introduce significant impacts on prediction accuracy? The answers to these open questions are useful to a wide range of audience. In this paper, we conducted the first empirical study to analyze the runtime impacts of deep learning bugs. Our basic idea is to inject deliberately designed bugs into a typical deep learning application and its libraries with a mutation tool, and to compare the runtime differences between clean and buggy versions. In this way, we constructed 1,832 buggy versions, and compared their execution results with corresponding clean versions. Based on our comparison, we summarize 9 findings, and present our answers to 3 research questions. For example, we find that more than half of buggy versions do not lead to any observable errors, and most of them introduce only insignificant differences on the accuracy of their trained models. We interpret the significance of our findings from the perspectives of application programmers, API developers, and researchers. For example, based on our findings, better results alone are insufficient to prove better parameters nor better treatments, and researchers shall build strong theories to explain their improvements.

Persistent memory (PM) promises near-DRAM performance as well as data persistency. Recently, a new feature called eADR is available on the 2 nd generation Intel Optane PM with the 3 rd generation Intel Xeon Scalable Processors. eADR ensures that data stored within the CPU caches will be flushed to PM upon the power failure. Thus, in eADR-enabled PM systems, the globally visible data is considered persistent, and explicit data flushes are no longer necessary. The emergence of eADR presents unique opportunities to build lock-free data structures and unleash the full potential of PM. In this paper, we propose NBTree, a lock-free PM-friendly B + -Tree, to deliver high scalability and low PM overhead. To our knowledge, NBTree is the first persistent index designed for eADR-enabled PM systems. To achieve lock-free, NBTree uses atomic primitives to serialize leaf node operations. Moreover, NBTree proposes four novel techniques to enable lock-free access to the leaf during structural modification operations (SMO), including three-phase SMO, sync-on-write, sync-on-read , and cooperative SMO. For inner node operations, we develop a shift-aware search algorithm to resolve read-write conflicts. To reduce PM overhead, NBTree decouples the leaf nodes into a metadata layer and a key-value layer. The metadata layer is stored in DRAM, along with the inner nodes, to reduce PM accesses. NBTree also adopts log-structured insert and in-place update/delete to improve cache utilization. Our evaluation shows that NBTree achieves up to 11X higher throughput and 43X lower 99% tail latency than state-of-the-art persistent B + -Trees under YCSB workloads.

Emerging byte-addressable persistent memory (PM) has the potential to disrupt the boundary between memory and storage. Combined with high-speed RDMA networks, distributed PM-based storage systems offer the opportunity to provide huge increases in storage performance by closely coupling PM and RDMA features. However, existing distributed file systems adopt the conventional centralized client-server architecture designed for traditional disks, leading to excessive access latency, limited scalability, and high recovery overhead. In this paper, we propose a fully decentralized PM-based file system, Hydra. By exploiting the performance advantages of local PM, Hydra leverages data access locality to achieve high performance. To accelerate file transmission among Hydra nodes, file metadata and data are decoupled and updated differentially through one-sided RDMA reads. Hydra also batches RDMA requests and classifies RPCs into synchronous and asynchronous types to minimize network overhead. Decentralization enables Hydra to tolerate node failures and achieve load balancing. Experimental results show that Hydra outperforms existing distributed file systems by a large margin, and shows good scalability on multi-threaded and parallel workloads.

Real-world e-commerce systems need large cache capacities. Persistent memory (PM) can be employed to enlarge JVMs’ cache capacities, meanwhile they incur heavy write slowdowns and garbage collection overheads. This paper proposes JPDheap, a JVM heap design for PM-DRAM memories. A JPDheap is composed of a standard Java heap on DRAM and another heap on PM. The core insight is to separate heap objects and store them on DRAM or PM, allowing objects to be accessed much more efficiently. Our evaluation shows that JPDheap outperforms state-of-the-art heap designs by up to 115.96% in increasing applications’ throughput and by up to 87.03% in decreasing the average latency.

In recent years, with the flourish of deep learning techniques, deep learning libraries have been used by many smart applications. As smart applications are used in critical scenarios, their bugs become a concern, and bugs in deep learning libraries have far-reaching impacts on their built-on applications. Although programmers write many test cases for deep learning libraries, to the best of our knowledge, no prior study has ever explored to what degree such test cases are sufficient. As a result, some fundamental questions about these test cases are still open. For example, to what degree can existing test cases detect bugs in deep libraries? How to improve such test cases? To help programmers improve their test cases and to shed light on the detection techniques of deep learning bugs, there is a strong need for a study on the test quality of deep learning libraries. To meet the strong need, in this paper, we conduct the first empirical study on this issue. Our basic idea is to inject bugs into deep learning libraries, and to check to what degree existing test cases can detect our injected bugs. With a mutation tool, we constructed 1,545 buggy versions (i.e., mutants). By comparing the testing results between clean and buggy versions, our study leads to 11 findings, and we summarize them into the answers to three research questions. For example, we find that although existing test cases detected 60% of our injected bugs, only 30% of such bugs were detected by the assertions of these test cases. As another example, we find that some exceptions were thrown only in specific learning phases. Furthermore, we interpret our results from the perspectives of researchers, library developers, and application programmers.

Multivariate time series prediction task has long been a crucial problem in machine learning since it includes applications in real life such as energy consumption, traffic congestion and economic trending. Challenge is that there are many factors affecting the accuracy of prediction, such as information in time domain and frequency domain, as well as interdependence among sequences. Therefore, effectively capturing and combining features in different domains becomes the focus of research. In this paper, a deep learning framework enhanced by wavelet transform is proposed to predict multivariate time series. Our model captures the long-term and short-term characteristics of time series in the time domain respectively through convolutional network. Further more, we use LSTM to achieve trending vector of short-term features, while for long-term features, we use the multi-head attention mechanism to get its representation. For frequency-domain features, our framework extracts from the scalo-gram generated by applying wavelet transform to the time sequence. Through the design of CNN convolution kernel, our model also ensures that the dependence between time series can be extracted. Experimental results show that our proposed model outperforms other baseline approaches on three of the four realworld datasets with sophisticated patterns.

Among various recommendation methods, latent factor models are usually considered to be state-of-the-art techniques, which aim to learn user and item embeddings for predicting user-item preferences. When applying latent factor models to the recommendation with implicit feedback, the quality of embeddings always suffers from inadequate positive feedback and noisy negative feedback. Inspired by the idea of NSVD that represents users based on their interacted items, this article proposes a dual-embedding based deep latent factor method for recommendation with implicit feedback. In addition to learning a primitive embedding for a user (resp. item), we represent each user (resp. item) with an additional embedding from the perspective of the interacted items (resp. users) and propose attentive neural methods to discriminate the importance of interacted users/items for dual-embedding learning. We design two dual-embedding based deep latent factor models, DELF and DESEQ, for pure collaborative filtering and temporal collaborative filtering (i.e., sequential recommendation), respectively. The novel attempt of the proposed models is to capture each user-item interaction with four deep representations that are subtly fused for preference prediction. We conducted extensive experiments on four real-world datasets. The results verify the effectiveness of user/item dual embeddings and the superior performance of our methods on item recommendation.

For the emerging mobility-on-demand services, it is of great significance to predict passenger demands based on historical mobility trips towards better vehicle distribution. Prior works have focused on predicting next-step passenger demands at selected locations or hotspots. However, we argue that multi-step citywide passenger demands encapsulate both time-varying demand trends and global statuses, and hence are more beneficial to avoiding demand-service mismatching and developing effective vehicle distribution/scheduling strategies. Furthermore, we find that adaptations of single-step methods are unable to achieve robust prediction with high accuracy for further steps. In this paper, we propose an end-to-end deep neural network model to the prediction task. We employ an encoder-decoder framework based on convolutional and ConvLSTM units to identify complex features that capture spatiotemporal influence and pickup-dropoff interactions on citywide passenger demands. We introduce a multi-level attention model (global attention and temporal attention) to emphasize the effects of latent citywide mobility regularities and capture relevant temporal dependencies. We evaluate our proposed method using real-world mobility trips (taxis and bikes) and the experimental results show that our method achieves higher prediction accuracy than the state-of-the-art approaches.

Emerging non-volatile memory (also termed as persistent memory, PM) technologies promise persistence, byte-addressability, and DRAM-like read/write latency. A proliferation of persistent memory systems have been proposed to leverage PM for fast data persistence and expose malloc-like persistent APIs. By eliminating disk I/Os, these systems gain low-latency and high-throughput access performance for persistent data. However, there still exist non-negligible limitations in these systems, such as frequent context switches, inefficient allocation, heavy logging overhead, and lack of wear-leveling techniques. To solve these problems, we develop Lewat, a lightweight, efficient, and wear-aware transactional persistent memory system. Lewat is built in user-layer to avoid kernel/user layer context switches and enables lightweight persistent data access. We decouple the data space into slot zone and page zone. Based on this, we design different allocators in these two zones to achieve efficient allocation performance for both small-sized data and large-sized data. To minimize logging overhead, we propose an efficient adaptive logging framework. The main idea is to utilize different logging techniques for different workloads. We also propose a suite of system-coupled wear-leveling techniques that contain wear-aware allocation, wear-aware update, and write reduction. We evaluate Lewat on a real non-volatile memory platform and the experimental results show that compared with state-of-the-art persistent memory systems, Lewat has much lower latency and higher throughput.

Various factorization-based methods have been proposed to leverage second-order, or higher-order cross features for boosting the performance of predictive models. They generally enumerate all the cross features under a predefined maximum order, and then identify useful feature interactions through model training, which suffer from two drawbacks. First, they have to make a trade-off between the expressiveness of higher-order cross features and the computational cost, resulting in suboptimal predictions. Second, enumerating all the cross features, including irrelevant ones, may introduce noisy feature combinations that degrade model performance. In this work, we propose the Adaptive Factorization Network (AFN), a new model that learns arbitrary-order cross features adaptively from data. The core of AFN is a logarithmic transformation layer that converts the power of each feature in a feature combination into the coefficient to be learned. The experimental results on four real datasets demonstrate the superior predictive performance of AFN against the state-of-the-arts.

Emerging non-volatile memory technologies bring evolution to storage systems and durable data structures. Among them, a proliferation of researches on persistent hash table employ NVM as the storage layer for both fast access and efficient persistence. Most of them are based on the assumptions that NVM has cacheline access granularity, poor write endurance, DRAM-comparable read latency and much higher write latency. However, a commercial non-volatile memory product, named Intel Optane DC Persistent Memory (AEP), has a few interesting features that are different from previous assumptions, such as 1) block access granularity 2) hardware-layer wear-leveling and 3) much higher read latency than DRAM and DRAM-comparable write latency. Confronted with the new challenges brought by AEP, we propose Rewo-Hash, a novel read-efficient and write-optimized hash table for commercial non-volatile memory. Our design can be summarized into three key points. First, we keep a hash table copy in DRAM as a cached table to speed up search requests. Second, we design a log-free atomic mechanism to support fast writes. Third, we devise an efficient synchronization scheme between persistent table and cached table to mask the data synchronization overhead. We conduct extensive experiments using real NVM platform and the results show that compared with state-of-the-art NVM-Optimized hash tables, Rewo-Hash gains improvement of 1.73x-2.70x and 1.46x-3.11x in read latency and write latency, respectively. Rewo-Hash also outperforms its counterparts by 1.65x-4.24x in throughput for various YCSB workloads.

The goal of traffic prediction is to predict future traffic values such as speeds or flows in a transportation network. Existing studies mainly focus on exploring spatiotemporal dependencies in time and space domains. However, they generally neglect the frequency information encoded in the traffic data, which sheds light on the true spatiotemporal correlations among any vertices in the transportation network. In this paper, we aim to incorporate two kinds of frequency information, time-frequency and space-frequency, into the modeling of spatiotemporal dependencies towards more accurate traffic prediction. We investigate the importance of two frequencies using real traffic data and develop an end-to-end neural approach to utilizing both frequencies for traffic prediction effectively. Specifically, we propose an attention module to aggregate features from semantically related vertices according to their time-frequency similarities, and derive a semantic representation. A novel space-frequency-based gating mechanism is designed to control how much local information is propagated to the state updating, enforced with the graph convolution to generate an effective local representation. Finally, our model combines the semantic and local representations with gated recurrent units to predict future traffic values. Extensive experiments on two real-world traffic datasets demonstrate that our proposed approach yields better prediction performance than the state-of-the-art methods.

In this paper, we present ReoFS, a read-efficient and write-optimized PM-aware (Persistent Memory-Aware) file system that provides strong consistency guarantee. Different from traditional journaling techniques, ReoFS optimizes write requests on the write I/O path and allows concurrent reads to be served opportunistically. To reduce the write overhead for metadata-related operations, we devise a backup buffering mechanism, which keeps a replica of metadata in the backup buffer and supports fast in-place update. To minimize the write overhead for file data modifications, we design a fine-grained short logging mechanism to migrate writes to persistent log blocks and make new writes visible immediately after the log is persisted. With these two designs, ReoFS removes the double write overhead off the critical path of request execution for both metadata and data operations. We conduct extensive experiments on Intel Optane DC PM platform and the results show that ReoFS outperforms existing PM -aware file systems by 1.3x-4x.

New and emerging types of Persistent Memory (PM) technologies boost the opportunity to improve the performance of storage systems. PM can unify the main memory and secondary storage by incorporating it into legacy computer systems through the memory bus. In recent years, innovative results have been presented that exploit the byte-addressability, low latency, and non-volatility of PM; these have included local PM file systems and PM systems. However, the high overhead of ensuring data consistency has limited the performance of these systems. In this article, we propose LosPem, a novel log-structured framework for persistent memory to address the performance challenge. LosPem utilizes two techniques to accomplish this. Firstly, LosPem deploys efficient hash-indexed linked lists to maintain the log contents to reduce the significant overhead of log content retrieval. Secondly, LosPem improves the transaction throughput by decoupling a transaction into two asynchronous steps and creating a write buffer on Dynamic Random Access Memory (DRAM) write buffer for processing the frequent data writes. The experimental results show that LosPem outperforms Non-volatile Memory Library (NVML), Mnemosyne and Log-structured Non-volatile Main Memory (LSNVMM) by 27%, 1.2x, and 1.0x on a read-intensive workload. On a write-intensive workload, LosPem outperforms NVML, Mnemosyne, and LSNVMM by 1.8x, 1.2x, and 34%, respectively.

Real web datasets are often associated with multiple views such as long and short commentaries, users preference and so on. However, with the rapid growth of user generated texts, each view of the dataset has a large feature space and leads to the computational challenge during matrix decomposition process. In this paper, we propose a novel multi-view clustering algorithm based on the non-negative matrix factorization that attempts to use feature sampling strategy in order to reduce the complexity during the iteration process. In particular, our method exploits unsupervised semantic information in the learning process to capture the intrinsic similarity through a graph regularization. Moreover, we use Hilbert Schmidt Independence Criterion (HSIC) to explore the unsupervised semantic diversity information among multi-view contents of one web item. The overall objective is to minimize the loss function of multi-view non-negative matrix factorization that combines with an intra-semantic similarity graph regularizer and an inter-semantic diversity term. Compared with some state-of-the-art methods, we demonstrate the effectiveness of our proposed method on a large real-world dataset Doucom and the other three smaller datasets.

Emerging non-volatile memory (also termed as persistent memory, PM) technologies promise persistence, byte addressability and DRAM-like read/write latency. A proliferation of persistent memory systems such as Mnemosyne, NVHeaps, PMDK and HEAPO have been proposed to leverage PM for fast data persistence. However, their performance may suffer from inefficiency issues, mainly caused by kernel/user layer context switches and heavy transaction logging overhead. Concretely, getting a persistent region in Mnemosyne, NV-Heaps and PMDK needs two kernel/user layer context switches since the mmap-like system calls are used, which leads to high latency. To guarantee data consistency, existing systems employ redo or undo logging techniques but they bring non-negligible overhead due to double writes and persistence ordering. In this paper, we develop EFlightPM, an efficient and lightweight persistent memory system to manage data in a fine-grained style. We decouple the data organization for persistent regions by placing large regions in the kernel layer while exposing small regions in the user layer. We also design a lightweight transaction mechanism using hybrid logging with high efficiency by minimizing the writes in the critical path. The experimental results show that compared with state-of-the-art persistent memory systems, EFlightPM manipulates fine-grained persistent data with less persistent region operation overhead and more transaction throughput.

Minimizing network usage is often a key driver of cost control for web services in the cloud. Most of the literature focuses on resources such as CPU, memory, and disk but the bandwidth is somehow neglected. In fact, it's very challenging to predict the network throughput of modern web services due to the factors of miscellaneous service responses and complex network transportation. Previously we proposed a what-if analysis approach named Log2Sim to predict bandwidth consumption and response time of web services based on network simulation, however, how to use it to address bandwidth problems in different changing contexts is not well studied. In this paper, we work this out with some extensions of Log2Sim, and a general process of bandwidth planning in different changing contexts is given. We also use a classic web benchmark and design various controlled experiments to evaluate this extended approach from different perspectives in multiple scenarios.

Latent factor models (LFMs) such as matrix factorization have achieved the state-of-the-art performance among various collaborative filtering approaches for recommendation. Despite the high recommendation accuracy of LFMs, a critical issue to be resolved is their lack of interpretability. Extensive efforts have been devoted to interpreting the prediction results of LFMs. However, they either rely on auxiliary information which may not be available in practice, or sacrifice recommendation accuracy for interpretability. Influence functions, stemming from robust statistics, have been developed to understand the effect of training points on the predictions of black-box models. Inspired by this, we propose a novel explanation method named FIA (Fast Influence Analysis) to understand the prediction of trained LFMs by tracing back to the training data with influence functions. We present how to employ influence functions to measure the impact of historical user-item interactions on the prediction results of LFMs and provide intuitive neighbor-style explanations based on the most influential interactions. Our proposed FIA exploits the characteristics of two important LFMs, matrix factorization and neural collaborative filtering, and is capable of accelerating the overall influence analysis process. We provide a detailed complexity analysis for FIA over LFMs and conduct extensive experiments to evaluate its performance using real-world datasets. The results demonstrate the effectiveness and efficiency of FIA, and the usefulness of the generated explanations for the recommendation results.

Next-generation Storage Class Memory (SCM) offers low-latency, high-density, byte-addressable access and persistency. The potent combination of these attractive characteristics makes it possible for SCM to unify the main memory and storage to reduce the storage hierarchy. Aiming for this, several persistent memory systems were designed. However, the heavy metadata and transaction cost degrade the system performance. Moreover, neither of them pays attention to wear-leveling strategy. In this article, we present a lightweight persistent memory system, LiwePMS, which allows a fast access to persistent data stored in SCM with wear-aware memory management. LiwePMS makes performance improvement by simplifying the metadata management and the consistency method. LiwePMS abstracts SCM as heap space with container-based dynamic address mapping. Also, LiwePMS implements efficient wear-aware dynamic memory allocator and lightweight transaction mechanism for data consistency in user-space library. The experiments showed that LiwePMS persists key-value records 1.5× faster than Redis RDB mechanism. LiwePMS improves the performance of persistent region operation by more than 45%, 63%, and 1.1× comparing with HEAPO, Mnemosyne, and NVML, respectively. Also, the wear-leveling policy of memory allocator outperforms that of NVMalloc from 35% to 30%, and the transaction method promotes the transaction performance to 1.8× compared to NVML.

In-memory computing has inspired researchers to consider integrating large-capacity persistent memory (PM) into the main memory subsystem. However, several challenges still remain for providing an integration approach for DRAM-comparable PM on existing enterprise servers. Current commercial servers tend to feature multiple sockets with shared-memory NUMA organizations. Simply constructing a hybrid main memory architecture for these NUMA organizations requires considerable modifications of the system software. Another significant problem in these designs is the high latency of accessing PM on a remote socket, which results in performance degradation. To address these problems, we integrated PM as a memory-based model and as a storage-based model simultaneously on one commercial server, which offers a short-cut approach for enterprises to build commercial NUMA machines with large-capacity PM. In the memory-based model, rather than focusing on the persistence attribute, we propose an architecture that benefits managing the integrated PM and DRAM space in a unified manner and that facilitates bypassing vast modifications to the system software. We also present an adaptive mechanism that can automatically introduce a moderate amount of PM into the local socket to hinder access of a remote socket by the degree of memory pressure. In the storage-based model, under the condition of taking full advantage of the PM's persistence, we abstract a PM volume device and overcome the torn sector problem. To demonstrate the effectiveness of the proposed scheme, we design and implement Dapper, an adaptive persistent memory manager prototype. The experimental results show that, compared to typical memory management approaches, Dapper achieves performance improvements of 13.1 percent to 34.0 percent on average on Graph500 BFS_SSSP benchmarks and SPEC CPU2006 floating point workloads, respectively. Moreover, when deploying F2FS on our PM volume, we find that Dapper outperforms existing methods by 5.8 percent on tar and by 11.9 percent on untar.

Urban air pollution has attracted much attention these years for its adverse impacts on human health. While monitoring stations have been established to collect pollutant statistics, the number of stations is very limited due to the high cost. Thus, inferring fine-grained urban air quality information is becoming an essential issue for both government and people. In this paper, we propose a generic neural approach, named ADAIN, for urban air quality inference. We leverage both the information from monitoring stations and urban data that are closely related to air quality, including POIs, road networks and meteorology. ADAIN combines feedforward and recurrent neural networks for modeling static and sequential features as well as capturing deep feature interactions effectively. A novel attempt of ADAIN is an attention-based pooling layer that automatically learns the weights of features from different monitoring stations, to boost the performance. We conduct experiments on a real-world air quality dataset and our approach achieves the highest performance compared with various state-of-the-art solutions.

Measuring semantic relatedness between two words is a significant problem in many areas such as natural language processing. Existing approaches to the semantic relatedness problem mainly adopt the co-occurrence principle and regard two words as highly related if they appear in the same sentence frequently. However, such solutions suffer from low coverage and low precision because i) the two highly related words may not appear close to each other in the sentences, e.g., the synonyms; and ii) the co-occurrence of words may happen by chance rather than implying the closeness in their semantics. In this paper, we explore the latent semantics (i.e., concepts) of the words to identify highly related word pairs. We propose a hierarchical association network to specify the complex relationships among the words and the concepts, and quantify each relationship with appropriate measurements. Extensive experiments are conducted on real datasets and the results show that our proposed method improves correlation precision compared with the state-of-the-art approaches.

The great promise of in-memory computing inspires engineers to scale their main memory subsystems in a timely and efficient manner. Offering greatly expanded capacity at near-DRAM speed, today's new-generation persistent memory (PM) module is no doubt an ideal candidate for system upgrade. However, integrating DRAM-comparable PMs in current enterprise systems faces big barriers in terms of huge system modifications for software compatibility and complex runtime support. In addition, the very large PM capacity unavoidably results in massive metadata, which introduces significant performance and energy overhead. The inefficiency issue becomes even acute when the memory system reaches its capacity limit or the application requires large memory space allocation. In this paper we propose adaptive memory fusion (AMF), a novel PM integration scheme that jointly solves the above issues. Rather than struggle to adapt to the persistence property of PM through modifying the full software stack, we focus on exploiting the high capacity feature of emerging PM modules. AMF is designed to be totally transparent to user applications by carefully hiding PM devices and managing the available PM space in a DRAM-like way. To further improve the performance, we devise holistic optimization scheme that allows the system to efficiently utilize system resources. Specifically, AMF is able to adaptively release PM based on memory pressure status, smartly reclaim PM pages, and enable fast space expansion with direct PM pass-through. We implement AMF as a kernel subsystem in Linux. Compared to traditional approaches, AMF could decrease the page faults number of high-resident-set benchmarks by up to 67.8% with an average of 46.1%. Using realistic in-memory database, we show that AMF outperforms existing solutions by 57.7% on SQLite and 21.8% on Redis. Overall, AMF represents a more lightweight design approach and it would greatly encourage rapid and flexible adoption of PM in the near future.

For promising performance boost, recent trends of modern data centers tend to use Persistent Memory (PM) as storage and utilize the one-sided feature of Remote Direct Memory Access (RDMA) to directly access PM for I/O requests. However, accessing PM through one-sided RDMA faces two challenges: one-sided data races and remote data crash consistency. Existing systems that employ server-bypass mechanism either abandon server-bypass write to avoid the challenges at the cost of extra server loads, or support both server-bypass read/write through inefficient concurrency control without ensuring remote crash consistency. In this paper, we propose a novel server-bypass RDMA-to-PM framework, named Forca, to provide high concurrency and guarantee remote crash consistency at the same time. In Forca, we design an optimized log-structured mechanism to eliminate in-place updates, removing race conditions of one-sided RDMA and providing atomicity for each update simultaneously. We implement Forca as a generic module to support server-bypass RDMA to PM, and conduct experiments on a Forca-based key-value store called ForcaKV. The experiments show that Forca achieves higher throughput than state-of-the-art techniques by up to 1.4x under high concurrency scenarios, and its crash consistency mechanism incurs only 14.7%-19.1% time overhead.

For many large-scale multimedia datasets and web contents, the nearest neighbor search methods based on the hashing strategy for cross-modal retrieval have attracted considerable attention due to its fast query speed and low storage cost. Most existing hashing methods try to map different modalities to Hamming embedding in a supervised way where the semantic information comes from a large manual label matrix and each sample in different modalities is usually encoded by a sparse label vector. However, previous studies didn't address the semantic correlation learning challenges and couldn't make the best use of the prior semantic information. Therefore, they cannot preserve the accurate semantic similarities and often degrade the performance of hashing function learning. To fill this gap, we firstly proposed a novel Deep Semantic Correlation learning based Hashing framework (DSCH) that generates unified hash codes in an end-to-end deep learning architecture for cross-modal retrieval task. The major contribution in this work is to effectively automatically construct the semantic correlation between data representation and demonstrate how to utilize correlation information to generate hash codes for new samples. In particular, DSCH integrates latent semantic embedding with a unified hash embedding to strengthen the similarity information among multiple modalities. Furthermore, additional graph regularization is employed in our framework, to capture the correspondences from the inter-modal and intra-modal. Our model simultaneously learns the semantic correlation and the unified hash codes, which enhances the effectiveness of cross-modal retrieval task. Experimental results show the superior accuracy of our proposed approach to several state-of-the-art cross-modality methods on two large datasets.

Emerging non-volatile memory (NVM) technologies promise persistence, byte-addressability, low power consumption and high density. The potential of NVM implies that it can improve persistence performance and availability for high-performance computing tasks in data centers. However, NVM suffers from limited write endurance; skewed writes can extremely curtail the lifetime of NVM. Although several wear-leveling algorithms have been proposed to address the wear-out problem, based on estimation of write counts, they come with limitations in accuracy and compatibility with existing hardware and softwares. In this paper, we propose several software-based ways of monitoring NVM writes and obtaining the write counts, which are more accurate and non-intrusive for existing programs. We compare our proposed monitoring approaches in the aspects of granularity and portability; we conduct extensive experiments to evaluate them and the results show that our proposed methods can obtain good accuracy with an affordable time overhead.

Data persistence refers to an characteristic that data needs to outlive its creator. In recent years, NVM (Non-volatile Memory), a new type of computer memory supporting memory-like byte-addressable access and disk-like persistence, became a promising technique for facilitating data persistence in memory and its management. So far NVM has been supported in many programming languages such as C, C++ and Java. Meanwhile, it has not yet been well supported in JavaScript, a popular scripting language for software development. This paper presents JSNVM, an extension to JavaScript's runtime and execution engine, to support data persistence in JavaScript using NVM. JSNVM consists of (1) a JavaScript persistent object pool that serves as a persistent heap in which persistent objects are created and managed. This pool is also enhanced for guaranteeing data safety and consistency; and (2) a set of JavaScript persistent APIs that provide programmers with a support in creating, managing, and accessing persistent data in an easy-to-use and safe manner. We have implemented JSNVM and evaluated it against two database-supported data persistence styles (i.e., MongoDB's object store and indexedDB's binary store) on micro-benchmarks and real-world applications. The evaluation results show that compared with MongoDB's object store, JSNVM can achieve a 1.6× speedup; when applied to access binary data, JSNVM can achieve a 24.6× speedup over indexedDB's binary store, denoting that JSNVM can enhance performance of JavaScript applications in practice. JSNVM is planned to be publicly available by the end of 2018.

In spite of their convenience and popularity, dockless shared bikes pose several challenges to operations and city management, e.g., unbalanced supply and demand across a city, and harmful congestions in pedestrian walkways. A step towards addressing these challenges is to find whether there exist periodical patterns in dockless shared bike demands. A periodical pattern of dockless shared bike demand is a time-dependent demand profile that repeats over a time period and frequently appear in different areas across a city. Mining periodical patterns of dockless shared bike demands, however, is very challenging because of data noises and different demand scales in different areas. In this paper, we propose a two-stage method for mining the periodical patterns of dockless shared bike demands. In the first stage, we determine the areas which have periodical dockless shared bike demands. And in the second stage, we introduce the concept of magnitude-oblivious demand to handle the issue on the different scales in different areas and propose an algorithm to compute the magnitude-oblivious periodic patterns. We conduct experiments with real data in Shanghai, China, which show that 12.4% of spatial areas in Shanghai have periodicity in bike demands, and we report 157 magnitude-oblivious periodical patterns in Shanghai. We also present several case studies which show our approach produces meaningful and useful patterns. Interestingly, we find that the areas with a similar geography often share the same periodical patterns of dockless shared bike demands.

The task of automatically generating image captions draws a lot of attention in the past few years because it shows great potential in a wide range of application scenarios. The encoder-decoder structure with attention mechanism has been extensively applied to solve this task. However, most researches apply attention mechanism only to pay attention to image features but neglect the relations between image features which we think play an important role in scene understanding. To tackle this problem, we propose a novel attention mechanism named “attention to Time-Dependent Pre-Attention” (TDPA-attention) and the TDPA-attention is combined with a hierarchical LSTM decoder to compose our captioning model (TDPA-model). Within our TDPA-attention, at every time step, every image feature pays attention to all image features according to a semantic context and the attended feature is treated as an aggregated feature that contains relations between this image feature and all image features. All these aggregated features form a new feature set that the hierarchical LSTM decoder attends to. We evaluate our model on public image caption dataset Microsoft COCO and achieve state-of-the-art performance on most evaluation metrics.

For resource management purpose, administrators usually need to perform what-if analyses to predict the impact of any workload growths or planned changes on the performance of web services. A what-if analysis requires not only the design of system models, but also the workload models that represent the real-world user behavior. Existing methods of workload characterization based on probabilistic graphical models are quite complex if there are many web services provided by a system. Meanwhile, bandwidth resource is usually not taken into account in many related works, though it is a relatively expensive resource in cloud markets. In fact, it's very challenging to predict the network throughput of modern web services due to the factors of client-side caching, miscellaneous service responses and complex network transportation. In this paper we propose a methodology of what-if analysis named Log2Sim for the bandwidth management of web systems. We use a lightweight workload model to describe user behavior, an automated mining approach to obtain characteristics of workloads and responses from massive web logs, and traffic-aware simulations to predict the impact on the network throughput and the response time within changing contexts of user behavior. We also choose a real-life web system as use case to evaluate the effectiveness, accuracy and stability of this methodology.

Among various recommendation methods, latent factor models are usually considered to be state-of-the-art techniques, which aim to learn user and item embeddings for predicting user-item preferences. When applying latent factor models to recommendation with implicit feedback, the quality of embeddings always suffers from inadequate positive feedback and noisy negative feedback. Inspired by the idea of NSVD that represents users based on their interacted items, this paper proposes a dual-embedding based deep latent factor model named DELF for recommendation with implicit feedback. In addition to learning a single embedding for a user (resp. item), we represent each user (resp. item) with an additional embedding from the perspective of the interacted items (resp. users). We employ an attentive neural method to discriminate the importance of interacted users/items for dual-embedding learning. We further introduce a neural network architecture to incorporate dual embeddings for recommendation. A novel attempt of DELF is to model each user-item interaction with four deep representations that are subtly fused for preference prediction. We conducted extensive experiments on real-world datasets. The results verify the effectiveness of user/item dual embeddings and the superior performance of DELF on item recommendation.

Predicting passenger pickup/dropoff demands based on historical mobility trips has been of great importance towards better vehicle distribution for the emerging mobility-on-demand (MOD) services. Prior works focused on predicting next-step passenger demands at selected locations or hotspots. However, we argue that multi-step citywide passenger demands encapsulate both time-varying demand trends and global statuses, and hence are more beneficial to avoiding demand-service mismatching and developing effective vehicle distribution/scheduling strategies. In this paper, we propose an end-to-end deep neural network solution to the prediction task. We employ the encoder-decoder framework based on convolutional and ConvLSTM units to identify complex features that capture spatiotemporal influences and pickup-dropoff interactions on citywide passenger demands. A novel attention model is incorporated to emphasize the effects of latent citywide mobility regularities. We evaluate our proposed method using real-word mobility trips (taxis and bikes) and the experimental results show that our method achieves higher prediction accuracy than the adaptations of the state-of-the-art approaches.

To maintain a complex modern web-based system, the what-if analysis is quite useful for predicting the impact of any workload growth or planned change on the performance of individual components, even the entire system. In this paper we propose an approach based on log mining to build what-if models of web-based systems and validate them by using OPNET simulation tool. Three contributions of this paper are: (1) the construction of what-if models based on log mining to automate the task of modeling and validation, (2) the technique to address complexity of user behaviors including users' browser caching, clustering of requests and users, etc., (3) and two real-life cases to evaluate the effectiveness and accuracy of this approach. The preliminary results show that the relative errors between logged data and simulation results are less than 18% in most cases including number of requests and network throughput.

The byte-addressable Non-Volatile Memory (NVM) offers fast, fine-grained access to persistent storage. While DRAM and NVM have similar read performance, the write operations of existing NVM materials incur longer latency and lower bandwidth than DRAM. This read-write asymmetry nature of NVM causes two bottlenecks for accessing read-and write-intensive file data: expensive data block lookups via file inner structure and high-latency direct writes to data blocks in NVM. However, existing NVM-based file systems fail to address both bottlenecks well. This paper presents WARP, an adaptive prefetching module designed for NVM-based file systems, which aims to deal with two bottlenecks effectively. WARP employs two acceleration approaches: 1) mapping data blocks into kernel virtual address space to bypass the indirection of file inner structure for read-intensive file data; and 2) allocating DRAM buffer to absorb frequent writes for write-intensive file data. We design a WARP benefit model to identify read-and write-intensive access patterns for file data, and use a successor prediction model to predict future data access based on historical file access traces. With WARP, we are able to prefetch file data according to both file access patterns and traces with consistency guarantee. WARP can be implemented on various NVM-based file systems, and we choose HMVFS for the experiments. The evaluation results show that HMVFS with WARP provides high prefetching accuracy and up to 32%-83% improvement compared with the state-of-the-art NVM-based file systems.

In-memory key/value stores have been widely deployed in many large systems for high throughput and low latency data access. To offer durability and fault tolerance, many of them (e.g., Memcached, Redis) flush data to RAID or SSD in local and remote with primary backup replication (PBR), in which the RAID and network become the bottleneck of throughput and latency. Recently, two promising technologies are emerging, i.e., non-volatile memory (NVM) and remote direct memory access (RDMA). NVMs are integrating into the main memory for their high density, high access speed, low cost and byte addressability. And RDMA allows direct access to the memory of a remote machine without invoking the peer CPU, thus reducing latency. To overcome the limitations of traditional key/value stores, this paper explores the design of a distributed low-latency key/value store on non-volatile main memory by leveraging RDMA. NVM not only eliminates disk IO operations, but also makes fast repli- cation possible. For a PUT operation, we collect modifications (data and metadata) at the local NVM of the primary server and replicate them to the same positions of backup servers by RDMA writes. A prototype distributed key/value store, called NVDS, is designed and implemented. Extensive experiments on the micro benchmark show that NVDS achieves significant latency reduction, compared to existing key/value stores. It replicates a 32bytes key/value PUT operation to two backup servers in less than 2μs and the whole request latency is less than 10μs.

New non-volatile memory (NVM) technologies, e.g., Phase Change Memory (PCM), are emerging with main features such as byte addressability, cheapness and large size, and will be deployed to serve as main memory. For fast processing of big data, block device drivers have been developed for NVM such that traditional file systems (e.g., EXT4) operated on non-volatile main memory. However, the existing block driver blindly caches pages, which incurs unnecessary access delays. To overcome this drawback, this paper develops a novel block device driver, called NVMBD, for byte-addressable non-volatile main memory. It adopts two methods of processing block I/O requests, i.e., traditional block I/O and BMAP. On the one hand, traditional block I/O reads/writes 512B sectors with multiple load/store instructions. On the other hand, BMAP inserts NVM pages into the page cache tree when processing block I/O requests, which removes the page movement between the page cache and the NVM. BMAP involves in the management of page cache, but it is transparent to file systems. BMAP provides file systems with the DAX-like feature, improving the file system performance. Through comprehensive experiments, we demonstrate that the developed block device driver significantly improves the file access performance.

Emerging byte-addressable Non-Volatile Memory(NVM) technologies offer fine-grained access to persistent data with latency comparable to DRAM. This presents both challenges and opportunities to system software designers. To utilize the fascinating features of NVM, a lot of works have been done to develop NVM-based file systems. Direct access (DAX) is a key feature provided by most NVM-based file systems, it enables applications to directly access NVM without going through the page cache layer. However, DAX-style mmap may cause serious consistency issues in versioning in-memory file systems that adopt CoW to solve block sharing problem among snapshots. In this paper, we propose a new mmap mechanism called versioning-mmap which solves the consistency issue of memory-mapped I/O in DAX-enabled versioning in-memory file systems. We implement our proposed mechanism in HMVFS and do a series of experiments based on our implementation. Results show that our mechanism achieves consistency while imposing negligible performance overhead compared to PMFS and NOVA.

Modern Non-Volatile Memory (NVM) promises persistence, byte-addressability and DRAM-like read and write latency, which offers great opportunities for big data storage architecture. These excellent properties indicate that NVM has the potential to be incorporated with key-value stores to achieve high performance and durability simultaneously.

Non-volatile memory(NVM) promises a DRAM replacement in computer systems due to its attractive characteristics. However, the low endurance problem limits its practical applications. In this paper, we propose Wamalloc, an efficient NVM memory allocator to extend the lifetime of NVM in the software level. An elaborate hybrid wear-leveling policy is proposed in this paper to achieve wear-leveling without hardware overhead. The evaluations show that the wear-leveling policy of Wamalloc outperforms that of NVMalloc from 3% to 30%, and the total memory consumption of Wamalloc outperforms that of NVMalloc about 60% and 10% under uniform and random workloads. In addition, the allocation performance of Wamalloc is better than the standard glibc malloc and NVMalloc by 98% and 97% under uniform workloads, 83% and 86% under random workloads.

The byte-addressable Non-Volatile Memory (NVM) offers fast, fine-grained access to persistent storage, and a large volume of recent researches are conducted on developing NVM-based in-memory file systems. However, existing approaches focus on low-overhead access to the memory and only guarantee the consistency between data and metadata. In this paper, we address the problem of maintaining consistency among continuous snapshots for NVM-based in-memory file systems. We propose a Hybrid Memory Versioning File System (HMVFS) that achieves fault tolerance efficiently and has low impact on I/O performance. Our results show that HMVFS provides better performance on snapshotting compared with the traditional versioning file systems for many workloads. Specifically, HMVFS has lower snapshotting overhead than BTRFS and NILFS2, improving by a factor of 9.7 and 6.6, respectively. Furthermore, HMVFS imposes minor performance overhead compared with the state-of-the-art in-memory file systems like PMFS.

One of the key challenges in the software engineering lies in requirement engineering. As an important technique for modeling and analyzing requirements, software architecture has been intensively studied in recent years. Although various modeling tools have been proposed in both academy and industry, these tools typically provide limited support for analyzing non-functional requirements at architecture level. To address this problem, in this tool demo, we present a tool, called Breeze, that models, analyzes, and improves software architecture, with an emphasis on its non-functional requirements. In particular, Breeze has three key modules: (1) a modeling module that facilitates the modeling for software systems, (2) an analysis module that verifies non-functional requirements (e.g. safety, reliability and correctness) at the architecture level, and (3) a reconfiguration module that allows users to repair defects or to further improve architectures.

Quality evaluation is a critical aspect in the area of software development.If software quality problems could be found in the early design phase, the cost for software development and maintaining will be reduced.In this paper we propose an evaluation framework including a software error model and its corresponding experimental frame, which is based on Discrete Event System Specification (DEVS), to support the evaluation of multiple quality properties in the design phase.To accelerate the modeling and simulation processes, we further extend E-DEVSML to create model of system under evaluation and its experimental frame, and transform them to executable models automatically.A case study of a ticket booking system is presented to demonstrate that our approach is applicable.

Summary Various technologies have been proposed to support the processing of big data. However, such technologies require software architectures not only to adapt to the changes and achieve dynamic evolution but also to be reliable. Most of the architecture description techniques are not able to directly capture the dynamic changes in the definition of the software architecture and cannot analyze or evaluate the system reliability. In this paper, we provide a breeze graph grammar (BGG) to model the software architecture in both static and dynamic aspects and give a BGG reliability model to help supporting software system reliability modeling and evaluation. Our work expands this idea in three directions. We first present the definition of BGG to specify the software architecture and map the system dynamic evolution to BGG transformation rules. Second, a BGG reliability model is proposed in which we add error attributes to the BGG graph for capturing the system error information, and the system error state transition is performed through BGG graph rewriting rules. Then, we study the rules to map the BGG reliability model to a generalized stochastic Petri net (GSPN) model, which can be used for reliability evaluation. Throughout this paper, we use a big data‐based centralized system to demonstrate our approach. The BGG graph rewriting characteristic supports the dynamic change requirements, and the architecture is statically checked through the BGG productions. Moreover, system reliability modeling and evaluation can be achieved through the BGG reliability model by combining GSPN. Copyright © 2014 John Wiley & Sons, Ltd.

The activity diagram is widely used for describing and understanding workflows, however, it lacks a formal semantics and cannot be manipulated by computer. In this paper, we present a transformation from UML activity diagrams with time properties to timed coloured petri nets (TCPNs) in a formal way. We extend the activity diagram with time properties and a formal model named extended activity hyper graph (EAH) is defined. By mapping this formal model to a clocked transition system (CTS), we define a weak semantics for it. A list of transformation rules are proposed to show how this can be transformed to a TCPN model. We partially prove the model equivalence of the two models. Finally, an example of Game Capture application is used to validate our approach.

Architectural design modeling has emerged as a discipline in a complex system development. To implement early safety analysis, techniques for architectural design have been extended to concern the safety property. Various safety standard profiles, quantitative and qualitative analysis methods are proposed for assessment. However, few of them focuses on the feedback of the safety properties or analysis results on the adjustment to improve original architecture. In this paper, we present an approach to combine safety analysis with architecture modeling. First, we extend the meta-model of our architecture description language - Breeze/ADL with safety elements for design. Second, safety specifications are generated from Breeze/ADL, and then to be converted into Open FTA for FTA (Fault Tree Analysis). Our Breeze/ADL also supports rule definitions to adjust the architecture, to cope with safety problems. Moreover, model checking will be applied to verify the correctness of the adjustment. Finally, the tool Breeze/SA demonstrates the feasibility of our approach.

In QoS-based Web service recommendation, predicting QoS(Quality of Service) for service users will greatly aid service selection and discovery. In order to improve the prediction accuracy of Collaborative filtering algorithms, various factors are taken into account (e.g., location factor, environment, etc.). But seldom do investigators take the factor of time into account. Actually, QoS performance of Web services is highly related to the service status and network environments which are variable against time. Thus, this paper proposes a time-aware collaborative filtering algorithm to predict the missing QoS values. To validate our algorithm, this paper conducts series of large-scale experiments based on a real-world Web service QoS dataset. Experimental results show that the time-aware collaborative filtering algorithm significantly improves prediction accuracy.

Failure mode and effects analysis (FMEA) is a widely used technique for designing, identifying and eliminating known and/or potential failures from system, design and process. In the traditional FMEA, for each failure mode, risk factors of Occurrence, Severity and Detection are evaluated and simply multiplied to obtain a risk priority number. Besides, the weights of three risk factors are also ignored. To overcome these shortcomings of traditional FMEA, we propose a novel FMEA approach for obtaining a more rational ranking of failure modes by integrating entropy weighting method with 'Technique for Order Performance by Similarity to Ideal Solution'(TOPSIS). Finally, a case study about purchasing website is provided to demonstrate the feasibility and benefits of the proposed approach. A plugin in our tool-Breeze is developed to support the proposed approach.

AGG is a well established development environment which is used to model software systems in terms of graphs. Though AGG provides an appropriate basis for system modelling and verification, it can neither analyze nor evaluate the system reliability. In this paper, we propose an AGG-based strategy which, by combining generalized stochastic petri net (GSPN) and tools for reliability analysis, supports software system reliability modelling and evaluation. This work expands this idea in three directions: First, we give an AGG reliability model in which we add error attribute to AGG graph for capturing system error information, and at the same time performing the system error state transition through the AGG production. Second, we present how to map rules from the AGG reliability model into the GSPN one, which in turn can be used for reliability evaluation. The other direction is to use a Client/Server application to demonstrate our approach.

Reliability is becoming a more and more important concern for software architectures. Previous efforts mainly use the reliability model to predict the software reliability at architecture level, but most of these work do not give the formal description of software architecture. Meanwhile, many approaches have been proposed to specify software architecture, unfortunately, few of them pay attention to reliability. In this paper, we try to bridge the gap between software architecture description and reliability model. Our work expands such idea in two directions. Firstly, we propose a reliable hypergraph grammar by extending hyperedge. Secondly, we describe the software architecture by using our reliable hypergraph grammar and predict the reliability of software architecture through the state based reliability model.

Architecture description languages (ADLs) play an important role in specifying the software architectures. While most of these ADLs are unable to deal with the change directly, especially for dynamic evolution of software systems. This paper proposes an XML-based ADL, named Breeze/ADL, which is supported by Breeze Graph Grammar (BGG) - a graph grammar we defined, to describe software architecture and capture the change in the architecture definition. Our approach is explained in two directions. First, we give the basic definitions of Breeze/ADL, and then show how to map the BGG to Breeze/ADL to specify the structural model, style constraints and dynamic evolution. The other direction is that we use a Client/Server application as a running example to demonstrate our approach throughout this paper. In this approach, the software architecture description has both a textual and a graph representations, and the unplanned change can be captured and defined.

The construction of the software architecture (SA) is a key aspect in component-based software development (CBSD). The SA can characterize the system design at a high level, and focus on the computing units as well as their interactions. Nowadays, software runs in an open, dynamic and changeable environment, which requires the SA should be dynamic and able to adapt to changes. The inconsistency of the software architecture caused by adapting to changes may lead to architecture mismatching, which becomes a new challenge for the software development. In this paper, we try to ensure the correctness of architecture matching in two ways. On one hand, we extend the meta-model of xADL 2.0 by adding explicit matching features. Based on these features, we use OCL to verify whether the SA meta-model matches the requirement. On the other hand, we refine the interaction by specifying action abstractions from an implicit behavior view. With these two methods, we can weave matching properties to the SA meta-model at the design stage, which helps to guide the whole software system development.

Correctness is a critical requirement for software systems and one of the key factors in correctness is that the system be deadlock-free. In this paper, we present a Probe-Based Deadlock Detection and Recovery (PBDDR) strategy for Component-based System (CBS) which brings four contributions. First, we define a formal semantic model by using Communicating Sequential Processes (CSP) to abstract interaction behavior for statically analyzing deadlock. Second, we propose a Deadlock Detection Algorithm (DDA) to find deadlock loops in a CBS. Third, we consider two qualities of concern, Timeliness (i.e., response time) and DLC (i.e., How many deadlock loops that a component involved in). Then we give a Deadlock Recovery Algorithm (DRA) to evaluate and replace the component to solve the deadlock problem based on above quality concerns. Finally, we implement our approach using the Arch Studio tool. Experimental results show that our approach has reasonable performance.

Compared to the traditional software architecture, Dynamic Software Architectures (DSAs) should be able to describe the changes of the system and to effect modifications during system execution, especially for dynamic evolution. To reflect the changes during system execution, we present a formalism for describing architecture structure and interaction behavior, and we also specify four evolution rules for software architecture. Our work expands the idea in three directions. The first is to formalize the architecture structure and interaction behavior including components, connectors and an architectural reference model. The second direction is that we formalize four dynamic evolution rules which DSAs should support, that is, addition, removal, replacement and reconfiguration. Another direction is that we verify software architecture consistency and integrity after dynamic evolution. We use a client/server application as a running example throughout the paper to demonstrate our approach. Our work provides a precise formal specification for software architecture and a rigorous verification for dynamic evolution.

Service-oriented architecture (SOA) facilitates the construction of complex pervasive applications, but the highly dynamic nature of pervasive computing brings challenges to the regular maintenance of these applications. Furthermore, pervasive applications are required to provide continuous services during their maintenances. A promising approach for providing uninterrupted service is to permit dynamic updates while keeping applications up-to-date. In this paper, we present a dynamic service update framework to support transparent updates of running applications, and illustrate update mechanisms of the framework. Novel features of our approach are that it supports dynamic interface adaptability if the interface type of an updated service has been changed and that it can automatically recover from update failures if the behavior of an updated application is unwanted. Experiments show that our approach is effective and beneficial when applied to pervasive applications and the performance overhead is acceptable in relation to the advantages.

The continuous requirements of evolving a service-oriented application and the rising cost of shutting down services at runtime are forcing researchers to find ways of updating services while they run. Dynamic service update can solve the problem of such applications and is becoming a challenging issue. This paper presents a formal model for supporting dynamic update framework based on OSGi. The process of dynamic service update is specified using Finite State Process (FSP) and then the Labelled Transition System Analyzer (LTSA) tool for formal property verifications. We also formally analyze and prove type-safe update of such frameworks, and finally demonstrate that our model works well in practical cases.

Pervasive Computing plays an integral role in our daily life. Due to the mobility and resource limit of devices in pervasive computing environments, the design and implementation of service composition will be a more complex and challenging task. In this paper, an approach based on behavioral modeling and analysis techniques for modeling service composition is proposed. A service behavior model is represented as Concurrent Regular Expressions and then is modeled as a Labelled Transition System by transforming Concurrent Regular Expressions into Finite State Process notation. Verification of the service behavior against specified system properties, (i.e. behavior consistency, safety) is becoming more flexible and effective.

The idea of the Semantic Web (SW) is based on metadata and the future usage scenarios of the SW assume the availability of metadata needed by agents and computer programs to perform sophisticated tasks. We have proposed an architecture needed to generate metadata for the SW. Our proposed architecture is designed to generate metadata from HTML Web Pages from the domain of our interest. The domain model is represented by using domain ontology. The focus of the paper is to investigate the automatic generation of metadata for the SWby relation extraction techniques. Our assumption is that any two web pages that have some kind of relationship must be connected by a link or a path. Our algorithm exploits the link structure of web using breadth first search for relation extraction. Relation extraction results show that hyperlink structure of the Web can be used for relation extraction.

Dynamic software updating is critical for many systems that must provide continuous service. And Java language is gaining increasing popularity in developing distributed system. Most of previous works on updating concerns on safely update one class every time. It occur many limitations on updating classes, such as not allowing deleting method which is invoked in other class. In this paper, update transaction is purposed to dynamically update class set, and we also discuss some properties about it, such as ACID. Then the type-safety property is proven formally. This paper also proposes an implementation method to updating classes without changing JVM and Java program language. The method makes use of Java class loading mechanism and reflection mechanism. At the end of the paper, an experiment is made for analyzing.

The monitoring of resources is a crucial issue for the high-performance of Web computing, and the scheduling strategies, the management of resources, and the performance analysis are dependent on the monitoring data. The traditional monitoring solution does not provide a unified and consistent model to the devices, resources and services of heterogeneous environments. In this paper a novel monitoring approach is proposed based on the common information model CIM. CIM defines a basic meta-model, syntax for the description of managed object and hierarchical structure of generic object classes. The monitoring system RMCS is given that integrates and extends the existing monitoring system to gather and retrieve the monitoring information. The CIM-based method addresses the variety and heterogeneity of resources in object-oriented way that the monitoring resource is regarded as a class or object. The RMCS enables administrators and users define a wide variety of resources, customize the monitoring parameters and the display way. The experiments show that this monitoring approach provides the scalable and flexible capabilities, and satisfies the Web application requirements

With the improvement of the traffic complexity extent, the solution of traffic problems becomes more and more difficult in the reality, so traffic simulation is an effective method for analyzing the traffic states and problems. As the simulation area becomes larger and more complicate, which requires large computing and storage resources, it can't be resolved by the traditional computing technology. Due to grid technology's advantages on such aspects, a new simulation architecture named GHA, which implements the HLA 's component as grid service and combined with the agent technology is presented in this paper. Thus the simulation architecture can offer high-capable computing resources to solve the complex traffic issues with great expansibility and flexibility; moreover, it also makes solid foundation to the authenticity of traffic simulation by adopting agent model the character of traffic entity. At last, a traffic simulation platform is implemented based on GHA and the performance tests are given

Abstract The goal of the ShanghaiGrid is to provide information services to the people. It aims to construct a metropolitan‐area information service infrastructure and establish an open standard for widespread upper‐layer applications from both communities and the government. The Information Service Grid Toolkit and a typical application called the Traffic Information Grid are discussed in detail. Copyright © 2005 John Wiley & Sons, Ltd.

This paper focus on the abstract model and complexity analysis of routing in mobile ad hoc system. Based on the Abstract State Machines theory, we provide a formal model ASM PBRAgent for mobile ad hoc system, on which the position based routing runs as a query. In the result, it is shown that the problem of position based routing is PSPACE-complete when the arity of each node’s outgoing edges has a fixed upper bound, and the Yao-graph topology is an instance; on the other hand, the problem is EXPSPACE-complete if there is no fixed upper bound on the arity.