Accurately representing synonymy using distributional similarity requires large volumes of data to reliably represent infrequent words. However, the na¨ve nearestı neighbour approach to comparing context vectors extracted from large corpora scales poorly (O(n2 ) in the vocabulary size). In this paper, we compare several existing approaches to approximating the nearestneighbour search for distributional similarity. We investigate the trade-off between efficiency and accuracy, and find that SASH (Houle and Sakuma, 2005) provides the best balance. .
