Hierarchical clustering is a popular classic technique for cluster analysis, in particular, because it is easy to understand and explain. The key limitation of hierarchical agglomerative clustering is its run time: the standard algorithm runs in cubic time, and improved methods use at least quadratic time. We propose novel strategies for accelerating hierarchical clustering using incremental similarity search. Using a priority search on a vantage-point tree, we often find the next merge without computing all pairwise distances. We propose two strategies based on heaps of searches for single linkage and a third strategy based on the nearest-neighbor chain algorithm for Ward, centroid, and median linkage, other linkages are not supported efficiently (yet). Experimentally, we demonstrate 2 to 10-fold speedups on real data sets and show that subquadratic scalability is possible although it can not be guaranteed.