xiaolhu Goto Github PK

fastdpeak

Density Peak is not applicable for large scale data, due to the two quantities, i.e, density ρ and δ, are both obtained by brute force algorithm with complexity O(n2). Then, a simple but fast Density Peak Clustering, namely FastDPeak, is proposed, which runs in about O(nlog(n)) expected time in the intrinsic dimensionality. It replaces density with kNN-density, which is computed by fast kNN algorithm such as cover tree, yielding the huge improvement for density computations. Based on kNN-density, local density peaks and non-local density peaks are identified, and a fast algorithm, whichusestwodifferentstrategiestocomputeδ for them, is also proposed with complexity O(n). Experimental results show that FastDPeak is effective and outperforms other variants of DPeak.

rlexample

Some basic examples of playing with RL

sample-based_semi-convex_hull_tree

In this paper, a novel tree structure, namely semi-convex hull tree, is proposed, and based on it a fast nearest neighbor (NN) query algorithm for large scale data is given. In the novel tree, each node represents a convex set, in fact semi-convex hull, which consists of some linear constraints. The new NN algorithm filters large amounts of redundant distance computations by quadratic programming (QP). In order to perform the proposed algorithm on GPUs, a simplified quadratic programming is also proposed to retrieve approximate lower bound of the distance from a query point to a node. In addition, a sample based version of the proposed algorithm is developed as well, which accelerates the original semi-convex hull tree much in large scale data. Experiments conducted on different GPUs show that the proposed algorithm is promising, which yields valuable improvements and superiority to the other NN query methods, including k-d tree, cover tree etc.

semi-convex_hull_tree

A fast exact nearest neighbor search algorithm over large scale data is proposed based on semi-convex hull tree, where each node represents a semi-convex hull, which is made of a set of hyper planes. When performing the task of nearest neighbor queries, unnecessary distance computations can be greatly reduced by quadratic programming. GPUs are also used to accelerate the query process. Experiments conducted on both Intel(R) HD Graphics 4400 and Nvidia Geforce GTX1050 TI, as well as theoretical analysis show that the proposed algorithm yields significant improvements and outperforms current k-d tree based nearest neighbor query algorithms and others.

tvdo