Approximate Nearest-Neighbor Search (ANNS) has become the standard approach for querying in vector databases, especially with the recent surge in large-scale, high-dimensional data driven by LLM-based applications. Recently, graph-based ANNS has demonstrated enhanced throughput by constructing a graph from the dataset, where edges reflect the similarities between data points, and employing best-first search algorithms for query evaluation.

This work demonstrates that the design space for both graph construction and searching is under-explored. First, the construction phase overlooks the potential temporal correlation between input queries and final results. Second, in the search phase, the parameters of the best-first search have not been fully examined.

To address these limitations, we introduce the \texttt{PANNS} system. \texttt{PANNS} constructs a proximity graph that incorporates temporal information, revealing correlations between queries and results. It also features a fully parameterized search algorithm, allowing extensive performance tuning. \texttt{PANNS} can achieve up to a $3.7\times$ speedup in query throughput compared to the state-of-the-art graph-based ANNS solutions while maintaining the same recall levels. Moreover, the size of the constructed graph can be reduced by up to 30% without compromising query quality.