The task of searching for similar items is the standard routine in numerous industrial applications as well as research problems in computer science and other fields. Finding the exact near (or nearest) neighbors is often expensive and typically an approximate solution would be sufficient. The research on developing efficient algorithms for approximate near neighbor (ANN) search dated back at least to the 1970's [1]}, [2]}. In recent years, ANN algorithms have become the crucial component in modern recommender systems [3]}, [4]}, [5]}, [6]}, Among many application domains. In this paper, we study ANN algorithms for an important application scenario, that is, the retrieved items must satisfy certain pre-specified constraints. More specifically, we focus on graph-based ANN algorithms under constraints. We should emphasize that, although this research problem was motivated from the production needs at Baidu, we only report experiments using public datasets.
