YLYi Liu

Yi Liu

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Yi Liu has a total of 16 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    d-HNSW: A High-performance Vector Search Engine on Disaggregated Memory

    by Fei Fang, Yi Liu, Chen Qian

    We present d-HNSW, an RDMA-based vector search engine for disaggregated memory that overcomes network bottlenecks and layout fragmentation through hardware-algorithm co-designed representative index caching, RDMA-friendly remote storage layout, query-aware loading, and pipelined execution.

  • Open Access

    d-HNSW: A High-performance Vector Search Engine on Disaggregated Memory

    by Fei Fang, Yi Liu, Chen Qian

    Efficient vector search is essential for powering large-scale AI applications, such as LLMs. Existing solutions are designed for monolithic architectures where compute and memory are tightly coupled. Recently, disaggregated architecture breaks this coupling by separating computation and memory resources into independently scalable pools to improve utilization. However, applying vector database to a disaggregated memory system brings unique challenges to system design due to its graph-based index. We present d-HNSW, the first RDMA-based vector search engine optimized for disaggregated memory systems. d-HNSW preserves HNSW's high accuracy while addressing the new system-level challenges introduced by disaggregation: 1) network inefficiency from pointer-chasing traversals, 2) non-contiguous remote memory layout induced by dynamic insertions, 3) redundant data transfers in batch workloads, and 4) resource underutilization due to sequential execution. d-HNSW tackles these challenges through a set of hardware-algorithm co-designed techniques, including 1) balanced clustering with a lightweight representative index to reduce network round-trips and ensure predictable latency, 2) an RDMA-friendly graph layout that preserves data contiguity under dynamic insertions, 3) query-aware data loading to eliminate redundant fetches across batch queries, and 4) a pipelined execution model that overlaps RDMA transfers with computation to hide network latency and improve throughput. Our evaluation results in a public cloud show that d-HNSW achieves up to < 10 -2 × query latency and >100× query throughput compared to other baselines, while maintaining a high recall of 94%.


  • Open Access

    Meep Hashing: Ultrafast and Compact Minimal Perfect Hashing for Practical Large-Scale Lookup Systems

    by Shouqian Shi, Diancheng Luo, Jacques Liao, Yi Liu, Xingsheng Zhao, Matthew Fahrbach, Chen Qian

    Minimal perfect hashing (MPH) is a class of algorithms that maps a set of N keys to the range {0, 1, …, N -1} without collisions. MPH is widely employed in modern large-scale applications including distributed storage indexes, network packet classification, genomic encoding in Bioinformatics, etc. In practice, these systems are often augmented with alien-key filters to ensure robustness against unexpected inputs. This paper introduces Meep hashing, a novel minimal perfect hashing algorithm designed for ultrafast lookup with an integrated alien-key filtering mechanism. Among existing lookup systems, Meep achieves the lowest on-average and tail lookup latency while maintaining a memory footprint comparable to the most compact perfect hashing data structures. It supports configurable target false positive rates for alien-key filtering, enabling flexible trade-offs between accuracy and efficiency. The performance advantages of Meep are realized through a hybrid orchestration of Cuckoo-based and probing-based hashing techniques, combined with a collision resolution strategy that handles four distinct collision types with minimal or zero additional overhead. We implement Meep and evaluate its efficacy in lookup speed, memory footprint, and construction time using microbenchmarks. Experimental results show that Meep hashing is consistently 50% to 200% faster than the other MPHs and 100% faster than the other MHTs. Meep achieves more than 7 billion queries per second under Zipfian query key distribution on a single machine with 20 parallel lookup threads.

  • A Distributed Learned Hash Table

    by Shengze Wang, Yi Liu, Xiaoxue Zhang, Liting Hu, Chen Qian

    Distributed Hash Tables (DHTs) are pivotal in numerous high-impact key-value applications built on distributed networked systems, offering a decentralized architecture that avoids single points of failure and improves data availability. Despite their widespread utility, DHTs face substantial challenges in handling range queries, which are crucial for applications such as LLM serving, distributed storage, databases, content delivery networks, and blockchains. To address this limitation, we present LEAD, a novel system incorporating learned models within DHT structures to significantly optimize range query performance. LEAD utilizes recursive machine learning models as the Learned Hash Function to map and retrieve data across a distributed system while preserving the inherent order of data. LEAD includes the designs to minimize range query latency and message cost while maintaining high scalability and resilience to network churn. Our comprehensive evaluations, conducted in both testbed implementation and simulations, demonstrate that LEAD achieves tremendous advantages in system efficiency compared to existing range query methods in large-scale distributed systems, reducing query latency and message cost by 80% to 90%+. Furthermore, LEAD exhibits scalability and robustness against system churn, providing a robust, scalable structure for efficient data retrieval in distributed key-value systems.


  • Parrot Hashing: Fast and Low-Memory Table Lookups for Network Applications With One CRC-8

    by Yi Liu, Shouqian Shi, Ruilin Zhou, Yuhang Gan, Chen Qian

    Key-value lookup functions have been widely applied to network applications, including FIBs, load balancers, and content distributions. Two key performance requirements of a lookup algorithm are high throughput and small memory cost. One limitation of existing fast network lookup algorithms is that they require multiple independent and uniform hash functions, which cost high computation time and might not be available on existing hardware network devices. Recently developed learned model hashing (LMH) proposes to use a linear machine learning model to replace hash functions to avoid hash computation, but they are not optimized for memory cost. We propose a novel network lookup method called Parrot hashing, which uses a learned model to distribute keys into different buckets and applies a simple perfect hashing method to resolve the collisions of the keys in a bucket. Parrot can be implemented with only one CRC-8, which is available on all network devices. We implement Parrot in three prototypes: a software program on end hosts, a software switch, and a FIB running on a hardware programmable switch. The experimental results show that Parrot achieves the highest lookup throughput on all three prototypes, compared to existing methods. Its memory cost is also significantly lower than that of LMH.


  • Open Access

    EdgeCut: Fast and Low-overhead Access of User-associated Contents from Edge Servers

    by Yi Liu, Minmei Wang, Shouqian Shi, Yang Wang, Chen Qian

    User-associated contents play an increasingly important role in modern network applications. With growing deployments of edge servers, the capacity of content storage in edge clusters significantly increases, which provides great potential to satisfy content requests with much shorter latency. However, the large number of contents also causes the difficulty of searching contents on edge servers in different locations because indexing contents costs huge DRAM on each edge server. In this work, we explore the opportunity of efficiently indexing user-associated contents and propose a scalable content-sharing mechanism for edge servers, called EdgeCut, that significantly reduces content access latency by allowing many edge servers to share their cached contents. We design a compact and dynamic data structure called Ludo Locator that returns the IP address of the edge server that stores the requested user-associated content. We have implemented a prototype of EdgeCut in a real network environment running in a public geo-distributed cloud. The experiment results show that EdgeCut reduces content access latency by up to 50% and reduces cloud traffic by up to 50% compared to existing solutions. The memory cost is less than 50MB for 10 million mobile users. The simulations using real network latency data show EdgeCut's advantages over existing solutions on a large scale.


  • Open Access

    Smash: Flexible, Fast, and Resource-efficient Placement and Lookup of Distributed Storage

    by Yi Liu, Shouqian Shi, Minghao Xie, Heiner Litz, Chen Qian

    Smash is a new placement and lookup method for distributed storage systems. It achieves full placement flexibility and low DRAM cost to store ID-to-location mappings, two desired features that could not be achieved simultaneously by any prior method.