PhishGraph: A Disk-Aware Approximate Nearest Neighbor Index for Billion-Scale Semantic URL Search

The proliferation of algorithmically generated malicious URLs necessitates a shift from syntactic detection to semantic analysis. This paper introduces PhishGraph, a disk-aware Approximate Nearest Neighbor (ANN) search system designed to perform billion-scale semantic similarity searches on URL embeddings for threat intelligence applications. Traditional in-memory ANN indexes are prohibitively expensive at this scale, while existing disk-based solutions fail to address the unique challenges of the cybersecurity domain: the high velocity of streaming data, the complexity of hybrid queries involving rich metadata, and the highly skewed, adversarial nature of query workloads. PhishGraph addresses these challenges through a synergistic architecture built upon the foundational principles of DiskANN. Its core is a Vamana proximity graph optimized for SSD residency, but it extends this with three key innovations: a Hybrid Fusion Distance metric that natively integrates structured attributes into the graph’s topology for efficient constrained search; a dual-mode update mechanism that combines high-throughput batch consolidation with low-latency in-place updates for streaming data; and an adaptive maintenance policy that monitors query patterns and dynamically reconfigures graph hotspots to mitigate performance degradation from skewed workloads. Our comprehensive experimental evaluation on a billion-point dataset demonstrates that PhishGraph’s adaptive, hybrid design significantly outperforms strong baselines, offering a robust, scalable, and efficient solution for modern threat intelligence.