Large-scale search is an essential task in modern information systems. Numerous learning based models are proposed to capture semantic level similarity measures for searching or ranking. However, these measures are usually complicated and beyond metric distances. As Approximate Nearest Neighbor Search (ANNS) techniques have specifications on metric distances, efficient searching by advanced measures is still an open question. In this paper, we formulate largescale search as a general task, Optimal Binary Functional Search (OBFS), which contains ANNS as special cases. We analyze existing OBFS methods' limitations and explain they are not applicable for complicated searching measures. We propose a flexible graph based solution for OBFS, Search on L2 Graph (SL2G). SL2G can achieve approximate optimal, with accessible conditions. Experiments demonstrate SL2G's efficiency in searching by advanced matching measures (i.e., Neural Network based measures).
Post-rebuttal
------------------
I have read the rebuttal and I better understand the paper. Given that, I am going to raise my rating by one point for the following reason:
- The manuscript presents a novel solution to a general problem and it is a valid solution. However, the solution is somewhat obvious, which is not necessarily a bad thing, which is why I am raising my rating by a point. However, an easy solution like the one proposed in the manuscript means that OBFS considered in this manuscript is not as general as the authors let on -- there is an implicit assumption that f(x_i, q) is close to f(x_j, q) if x_i is close to x_j.
- While the authors answered a lot of my clarification questions, the manuscript seems still a little hard to parse and can be significantly improved for easier reading and understanding.
=========================================
Pros
-------
[Originality/Significance] The manuscript focuses on a very general and important problem and proposes a scheme to solve this general problem. The authors present some theoretical and empirical results to demonstrate the utility of the proposed scheme.
Limitations
----------------
[Clarity] While the problem being addressing is extremely important, and the proposed solution seems reasonable, the manuscript is really hard to follow. For example, Definition 3 and Theorem 1 are extremely hard to understand. 
[Clarity/Significance] Moreover, I feel that the authors should be more precise in pointing out why current graph based search algorithms are just not trivially applicable to OBFS. The nature of the approximate Delaunay graph is that it can be built for any given similarity function (the level of approximation obviously depends on the similarity function, but that is an existing issue with graph-based methods). Given the graph, I do not understand why the basic search algorithm on this similarity graph would not be an approximate solution to OBFS. Hence I believe the authors need to clarify why the existing graph based algorithms do not directly translate. 
[Significance] While Definition 1 considers topological spaces, SL2G is assuming that X and (maybe) Y are in R^d (for different values of d). So does that mean that SL2G does not solve the general OBFS?
[Significance/Correctness/Clarity] The assumptions in Theorem 2 (as well as the supporting Proposition 1 in Appendix B) seems quite unreasonable. In moderately high dimensional X, doesn't the curse of dimensionality imply that this condition will not hold in most case? In there any reason why/how this would be circumvented? Moreover, in Proposition 1 (in Appendix B), the quantity C_r needs to be precisely defined since it could in general be exponential in the number of dimensions. Also, the assumption in Proposition 1 where \lambda^* > 0 is fairly strong in high dimensional data since data gets really sparse in high dimensions. Finally, the last step in Proposition 1 (where the failure probability obtained from the union bound is connected to condition (b) in Theorem 2) is not clear at all -- it is not apparent how E and F related to S and how p relates to every ball containing a point in S. This is a very important step and needs better exposition. 
[Clarity/Significance] I am unable to understand the baseline HNSW-SBFG (or the motivation for it) in the empirical section. It would be good to clarify this. 
General comments
---------------------------
[Significance] Finally, I believe that it would be good to see a connection between the success of SL2G to relationship between |f(x1, q) - f(x2, q)| and ||x1 - x2 ||_2 since the author emphasize that the proposed scheme can be seen as "gradient descent in Euclidean space" (although the authors would need to also precisely explain what they mean by that statement).
[Originality] Some related work that the authors should position their proposed problem/solution against:
- There is some work on "max-kernel search" which can perform similarity search with general notions of similarity (than just Euclidean metrics).
- There is some work on search with Bregman divergences which handle asymmetric similarity functions and also incorporate notions of gradient descent over convex sets.
Minor comments/typos
---------------------------------
- The authors should present the precise SL2G algorithm given the graph in the manuscript.
- l^2 --> \ell_2
- gradient decent --> gradient descent
- Table 1, f(q, x) --> f(x, q)