12 March 2024 in Proceedings of the ACM on Management of Data
High-dimensional vector similarity search (HVSS) is gaining prominence as a powerful tool for various data science and AI applications. As vector data scales up, in-memory indexes pose a significant challenge due to the substantial increase in main memory requirements. A potential solution involves leveraging disk-based implementation, which stores and searches vector data on high-performance devices like NVMe SSDs. However, implementing HVSS for data segments proves to be intricate in vector databases where a single machine comprises multiple segments for system scalability. In this context, each segment operates with limited memory and disk space, necessitating a delicate balance between accuracy, efficiency, and space cost. Existing disk-based methods fall short as they do not holistically address all these requirements simultaneously. In this paper, we present Starling, an I/O-efficient disk-resident graph index framework that optimizes data layout and search strategy within the segment. It has two primary components: (1) a data layout incorporating an in-memory navigation graph and a reordered disk-based graph with enhanced locality, reducing the search path length and minimizing disk bandwidth wastage; and (2) a block search strategy designed to minimize costly disk I/O operations during vector query execution. Through extensive experiments, we validate the effectiveness, efficiency, and scalability of Starling. On a data segment with 2GB memory and 10GB disk capacity, Starling can accommodate up to 33 million vectors in 128 dimensions, offering HVSS with over 0.9 average precision and top-10 recall rate, and latency under 1 millisecond. The results showcase Starling's superior performance, exhibiting 43.9x higher throughput with 98% lower query latency compared to state-of-the-art methods while maintaining the same level of accuracy.
28 February 2020 in IEEE/ACM Transactions on Networking
Mobile Instant Messaging (IM) apps, such as WhatsApp and WeChat, frequently send heartbeat messages to remote servers to maintain their always-online status. Periodic heartbeat messages are small in size, but their transmissions incur heavy signaling traffic due to frequently establishing and releasing communication channels between Base Stations (BSs) and smartphones, known as the signaling storm. Meanwhile, smartphones also need to activate the cellular data communication module frequently for transmitting short heartbeat messages, resulting in substantial energy consumption. To address these issues, we present eDirect, an energy-efficient D2D-assIsted Relaying framEwork for Cellular signaling reducTion. eDirect selects active smartphones as relays to opportunistically collect heartbeat messages from nearby smartphones using energy-efficient D2D communication. The collected heartbeat messages are transmitted to the BS in an aggregated manner to reduce cellular signaling traffic. Based on the beating frequencies and deadlines of the collected heartbeat messages, eDirect schedules transmissions of the collected heartbeat messages to minimize signaling overhead and energy consumption while meeting the deadline constraints. We implement and evaluate our solution on Android smartphones. The results from real-world experiments show that our solution reduces signaling traffic by at least 50% and energy consumption by up to 36%.
30 June 2025 in ACM Transactions on Architecture and Code Optimization
Graph pattern mining is essential for deciphering complex networks. In the real world, graphs are dynamic and evolve over time, necessitating updates in mining patterns to reflect these changes. Traditional methods use fine-grained incremental computation to avoid full re-mining after each update, which improves speed but often overlooks potential gains from examining inter-update interactions holistically, thus missing out on overall efficiency improvements. In this article, we introduce Cheetah, a dynamic graph mining system that processes updates in a coarse-grained manner by leveraging exploration domains . These domains exploit the community structure of real-world graphs to uncover data reuse opportunities typically missed by existing approaches. Exploration domains, which encapsulate extensive portions of the graph relevant to updates, allow multiple updates to explore the same regions efficiently. Cheetah dynamically constructs these domains using a management module that identifies and maintains areas of redundancy as the graph changes. By grouping updates within these domains and employing a neighbor-centric expansion strategy, Cheetah minimizes redundant data accesses. Our evaluation of Cheetah across five real-world datasets shows it outperforms current leading systems by an average factor of 2.63×.