Similarity measurement plays a central role in various data mining and machine learning tasks. Generally, a similarity measurement solution should, in an ideal state, possess the following three properties: high accuracy, high efficiency in terms of speed and independence from prior knowledge. Yet unfortunately, vital as similarity measurements are, no previous works have addressed all of them. In this paper, we propose X-Forest, consisting of a group of approximate Random Projection Trees, such that all three targets mentioned above are tackled simultaneously. Our key techniques are as follows. First, we introduced RP Trees into similarity measurement such that accuracy is improved. In addition, we enforce certain layers in each tree to share identical projection vectors, such that exalted speed is achieved. Last but not least, we introduce randomness into partition to eliminate its reliance on prior knowledge. We conduct experiments on three real-world datasets, whose results demonstrate that our model, X-Forest, reaches an efficiency of up to 3.5 times higher than RP Trees with negligible compromise on its accuracy, while also being able to outperform traditional Euclidean distance-based similarity metrics by as much as 20% with respect to clustering tasks.
This paper proposes a new method for measuring pairwise similarity between data points. The idea is to define the similarity between two data points to be the probability (over the randomness in constructing the trees) that they are close in an RP tree. More concretely, the proposed method constructs a collection of RP trees (albeit with some modifications), and takes the similarity to be the average over different RP trees of a strictly decreasing function of the distance between the leaf nodes containing the data points in each RP tree. The key modification to the RP tree is to limit the number of projection vectors used in an RP tree and re-use previous projection vectors. 
I believe the method is more or less equivalent to Euclidean distance, for the following reason. Two data points would have the highest similarity under the proposed similarity measure if they are in the same leaf node. For this to happen, both points must be on the same side of the dividing hyperplane corresponding to each of the ancestor nodes. Because the threshold along the projection vector is chosen randomly at uniform, this means that for the two data points to have high similarity consistently, the distance between them along the projection vector must be small (so that the probability of splitting them is small). Because the projection vectors themselves are chosen randomly on the unit sphere, this implies that this must hold along most projection vectors for similarity to be high consistently, which means that the Euclidean distance between the two points must be low. 
If true, this raises several questions:
1) Why does the proposed method work better than distance similarity (which I assume means Euclidean distance) in the experiments? Are there situations when the proposed method would yield a high similarity consistently whereas Euclidean distance wouldn’t? Are the results in Fig. 6 just for a single run of the proposed method? If so, many more runs need to be performed since the decisions of the RP tree should vary significantly depending on the projection vectors and thresholds. Both the mean and standard deviation should be reported. 
2) In Sect. 1.2, the authors critiqued distance-based similarity because it often does not correspond to intuitive notions of similarity/perceptual similarity. However, it does not appear that the proposed method would correspond to perceptual similarity either. For example, consider a dataset where some coordinates are more perceptually important than others (this is the case for example for the wavelet coefficients of a natural image - the lower frequencies are typically more perceptually important than higher frequencies). A more perceptually meaningful distance than Euclidean distance would be a Mahalanobis distance (which can essentially weight different coordinates differently), but the random projections use standard inner products and so are unable to capture the appropriate weighting of the different coordinates. So, why would one expect the proposed method to be more perceptually meaningful?
3) In Sect. 1.2, the authors critiqued multi-partition-based similarity because it does depend on the data distribution and cited the elimination of “prior knowledge dependence” in Sect. 1.3 as one of the benefits of the proposed method. This appears to be at odds with the goal of devising a similarity measure that is perceptually aligned, because such a similarity measure must depend on the representation of the data (e.g.: if the data is represented in the wavelet domain, one needs to know which order the different dimensions are arranged, i.e. from lowest frequency to highest frequency or the other way around). 
Overall, it is unclear if the desiderata makes sense, and if the proposed method achieves the objectives. 
Other questions:
4) For the X-Projection tree (which re-uses projection vectors), it seems to be equivalent to a layer-by-layer RP tree with larger branching factor. If so, the presentation of the method should be changed to this, because a layer-by-layer RP tree with larger branching factor is both conceptually clearer and simpler to analyze. If not, the proposed method should be compared to a layer-by-layer RP tree with larger branching factor, to justify the increased conceptual complexity of the X-Projection tree. 
5) For the experiments, comparisons should also be made to multi-partition-based similarity, like Multiple RP+EM and RF similarity. 
6) In addition, the proposed method should be compared to two simpler baselines that computes the average and the minimum distance of the two points along multiple random projection vectors, in order to justify the increased conceptual complexity of RP trees. 
7) In Sect. 1.3, the paper claims that “it is well known that in an RP Tree, data points that are closely distributed, indicating their high level of similarity in space, are always partitioned into the same subset”. This is not true, since hyperplane could divide a cluster down the middle for example. 
8) One of the claimed contributions in the abstract that “we introduce randomness into partition to eliminate its reliance on prior knowledge”. Note that just by introducing randomness, prior knowledge is not necessarily eliminated. For example, the way in which random projection is performed (i.e. standard inner product vs. other inner products) assumes knowledge of the distance metric, which is induced from the inner product. 
9) In Fig. 6, what is the distance metric used for the baseline?
Minor issues:
pg. 2: “project all data points into one random vector” -> “project all data points along one random vector”
pg. 3: “leading to unsatisfied results“ -> “leading to unsatisfactory results”
pg. 3: “nearest neighbours finding” -> “nearest neighbour search”
pg. 3: “pattern discovering” -> “pattern discovery”
pg. 4: “similarly data points” -> “similar data points”
pg. 4: “01 matrix” -> “0-1 matrix”