We present a new primitive for quantum algorithms that implements a discrete Hermite transform efficiently, in time that is polylogarithmic in the dimension and the inverse of the allowable error. This transform, which maps basis states to states whose amplitudes are proportional to the Hermite functions, can be interpreted as the Gaussian analogue of the Fourier transform. Our algorithm is based on a method to exponentially fast-forward the evolution of the quantum harmonic oscillator, giving a simulation algorithm with nearly optimal circuit complexity for a fundamental Hamiltonian more than four decades after Feynman posed the simulation of quantum physics as an application of quantum computers.

Cloud cache has been crucial to promoting the performance of I/O intensive applications. Due to the capacity and cost advantages over DRAM, NVM has been gradually utilized in cloud cache. However, NVM usually has limited write endurance, resulting in a frequent device replacement and a high cost. Cloud cache also needs to ensure Service-Level Agreement (SLA) such as an enough cache capacity, but there are few existing approaches that deal with the NVM writing problem without breaking SLA. Therefore, we propose a new SLA-aware cloud cache framework called MECC to extend the NVM lifetimes and thus reduce the total system cost with performance ensurance. Through dynamically allocating the two kinds of resources, i.e., NVM cache space and cache updating quota, to tenants according to their characteristics, MECC achieves the same performance for all tenants with a 56.3% cost reduction on average.

Compared with traditional storage technologies, non-volatile memory (NVM) techniques have excellent I/O performances, but high costs and limited write endurance (e.g., NAND and PCM) or high energy consumption of writing (e.g., STT-MRAM). As a result, the storage systems prefer to utilize NVM devices as read caches for performance boost. Unlike write caches, read caches have greater potential of write reduction because their writes are only triggered by cache updates. However, traditional cache algorithms like LRU and LFU have to update cached blocks frequently because it is difficult for them to predict data popularity in the long future. Although some new algorithms like SieveStore reduce cache write pressure, they still rely on those traditional cache schemes for data popularity prediction. Due to the bad long-term data popularity prediction effect, these new cache algorithms lead to a significant and unnecessary decrease of cache hit ratios. In this paper, we propose a new Macroscopic Trend (MT) cache replacement algorithm to reduce cache updates effectively and maintain high cache hit ratios. This algorithm discovers long-term hot data effectively by observing the macroscopic trend of data blocks. We have conducted extensive experiments driven by a series of real-world traces, and the results indicate that compared with LRU, the MT cache algorithm can achieve 15.28 times longer lifetime or less energy consumption of NVM caches with a similar hit ratio.

Log-structured merge (LSM) tree key-value (KV) stores have been widely deployed in many NoSQL and SQL systems, serving online big data applications such as social networking, bioinfomatics, graph processing, machine learning, etc. The batch processing of sorted data merging (i.e., compaction) in LSM-tree KV stores greatly improves the efficiency of writing, leading to good write performance and high space efficiency. Recently, some lazy compaction methods were proposed to further promote the system throughput through delaying the compaction to accumulate more data within a compaction batch. However, the batched writing manner also leads to significant tail latency, which is unacceptable for online processing, and the newly proposed lazy approaches worsen the tail latency problem. Furthermore, the unbalanced read/write performance of the widely deployed SSDs make the performance optimization harder. Aiming to optimize both the tail latency and the system throughput, in this paper, we propose a novel Lower-level Driven Compaction (LDC) method for LSM-tree KV stores. LDC breaks the limitations of the traditional upper-level driven compaction manner and triggers practical compaction actions by lower-level data. It has the benefits of both decreasing the compaction granularity effectively for smaller tail latency and reducing the write amplification of LSM-tree compaction for higher throughput. We have implemented LDC in LevelDB; the experimental results indicate that LDC can reduce the 99.9th percentile latency for 2.62 times compared with the traditional upper-level driven compaction mechanism, and achieve 56.7% ~ 72.3% higher system throughput at the same time.

Flash-based solid-state drives (SSDs) are getting popular to be deployed as the second-level cache in storage systems because of the noticeable performance acceleration and transparency for the original software. However, the frequent data updates of existing cache replacement algorithms (e.g. LRU, LIRS, and LARC) causes too many writes on SSDs, leading to short lifetime and high costs of devices. SSD-oriented cache schemes with less SSD writes have fixed strategies of selecting cache blocks, so we cannot freely choose a suitable cache algorithm to adapt to application features for higher performance. Therefore, a universal SSD lifetime extension plug-in called Elastic Queue (EQ), which can cooperate with any cache algorithm to extend the lifetime of SSDs, is proposed in this paper. EQ reduces the data updating frequency by extending the eviction border of cache blocks elastically, making SSD devices serve much longer. The experimental results based on some real-world traces indicate that for the original LRU, LIRS, and LARC schemes, adding the EQ plug-in reduces their SSD write amounts by 39.03 times, and improves the cache hit rates by 17.30% on average at the same time.

Locality Sensitive Hashing (LSH) is proposed to construct indexes for high-dimensional approximate similarity search. Multi-Probe LSH (MPLSH) is a variation of LSH which can reduce the number of hash tables. Based on the idea of MPLSH, this paper proposes a novel probability model and a query-adaptive algorithm to generate the optimal multi-probe sequence for range queries. Our probability model takes the query range into account to generate the probe sequence which is optimal for range queries. Furthermore, our algorithm does not use a fixed number of probe steps but a query-adaptive threshold to control the search quality. We do the experiments on an open dataset to evaluate our method. The experimental results show that our method can probe fewer points than MPLSH for getting the same recall. As a result, our method can get an average acceleration of 10% compared to MPLSH.

Listwise approach is an important method to solve practical Web search problem in learning to rank. In this paper, we first analyze the practical Web search problem and construct the model to solve it. Then we propose an algorithm called DiffRank which can apply boosting technology to learning to rank in listwise. Through theoretical analysis, we prove that the upper bound of training error can be reduced in our proposed algorithm. The experimental results further verify our theoretical analysis and demonstrate that our approach can better perform in practical Web search than other state-of-the-art listwise algorithms.