Résultats de recherche pour « HNSW »

Hierarchical Navigable Small World (HNSW) has demonstrated impressive accuracy and low latency for high dimensional nearest neighbor searches. However, its high computational demands and irregular, large-volume data access patterns present significant challenges to search efficiency. To address these challenges, we introduce P-HNSW, a software-hardware codesign solution for HNSW that integrates a Principal Component Analysis Filter (PCAF). On the software side, we apply PCAF to reduce dataset dimensionality, thereby lowering the volume of neighbor access and decreasing the computational load for distance calculations. On the hardware size, we design the P-HNSW processor with custom instructions to optimize search throughput and energy efficiency. Experimental results from RTL design synthesized using a 65nm technology node show that the proposed P-HNSW implementation achieves an 11.65× increase in Queries per Second (QPS) and a 56.8% reduction in energy consumption, compared to the original HNSW implementation

The rapid growth of Large Language Models (LLMs) has generated massive amounts of high-dimensional feature vectors extracted from diverse datasets. Efficient storage and retrieval of such data are critical for enabling accurate and fast query responses. Vector databases (Vector DBs) provide efficient storage and retrieval for high-dimensional vectors. These systems rely on Approximate Nearest Neighbor Search (ANNS) indexes, such as HNSW, to handle large-scale data efficiently. However, the original HNSW is implemented on DRAM, which is both costly and vulnerable to crashes. Therefore, we propose P-HNSW, a crash-consistent HNSW on persistent memory. To guarantee crash consistency, P-HNSW introduces two logs, NLog and NlistLog. We describe the logging process during the operation and the recovery process in the event of system crashes. Our experimental results demonstrate that the overhead of the proposed logging mechanism is negligible, while P-HNSW achieves superior performance compared with SSD-based recovery mechanisms.

Hierarchical Navigable Small World (HNSW) graphs are among the most widely adopted algorithms for an approximate nearest neighbor (ANN) search in high-dimensional data, supporting applications across machine learning, recommendation, and computer vision. Multiple open source libraries including FAISS-HNSW, HNSWlib, and NMSLIB-HNSW implement HNSW with different design choices and performance characteristics, yet comprehensive comparisons between them remain limited. This paper presents an empirical benchmarking study of these three libraries, systematically varying the size of the data set, the vector dimension, and key HNSW parameters (ef_construction and M). We evaluated each library on four critical metrics: indexing time, memory usage, query latency, and recall. Our results reveal distinct trade-offs: NMSLIB-HNSW provides the fastest index construction and highest recall, but suffers from significantly slower query times at scale. FAISS-HNSW offers the most balanced overall performance, while HNSWlib excels in smaller-scale settings. All benchmarks were conducted on CPU-based synthetic in-memory datasets. The findings offer actionable guidance for practitioners selecting and tuning HNSW libraries for varied deployment scenarios.

Collision detection is very important for robot motion planning. The existing accurate collision detection algorithms regard the evaluation of each node as a discrete event, ignoring the correlation between nodes, resulting in low efficiency. In this paper, we propose a novel approach that transforms collision detection into a binary classification problem. In particular, the proposed method searches the k-nearest neighbor (KNN) of the new node and estimates its collision probability by the prior node. We perform the hierarchical navigable small world (HNSW) method to query the nearest neighbor data and store the detected nodes to build the database incrementally. In addition, this research develops a KNN query technique tailored for linear data, incorporating threshold segmentation to facilitate collision detection along continuous paths. Moreover, it refines the distance function of the collision classifier to enhance the precision of probability estimations. Simulation results demonstrate the effectiveness of the proposed method.