I have 5 million items that have 10 features (all continuous and not categorical) each and would like to select a small subset of these items. Ideally, I want to manually specify 10 features of my own up front and find a subset of items in the pool that are all close to the features I specify. By closest, I mean the distance between the numbers I specify and the item features selected from the pool.


Simple way:

Compute the Euclidean distance between each item and the target feature specification. Sort by distance. Take the first 50 elements.

Fast way for arbitrary target features:

Since your parameters are continuous, you may define a gridding of the 10-dimensional feature space with grid spacing $d_i,i=1,\ldots,10$. Find the grid coordinates of each item by dividing the feature values $x_i$ by each $d_i$ and taking the floor of the result. Bin together items with the same grid coordinates. Next, for each target feature such as you've described, you can quickly compute its grid coordinates in the same manner and select items from that cell or its neighbors to quickly find the subsets you're looking for without having to compute all 5 million (or however many) distances every time you want to specify a feature.

  • 6
    $\begingroup$ You should generalize this to not merely use the regular Euclidean distance, since the different features may be of very different scale. Choose an appropriate distance function to define "close-ness", then apply a tree or grid-based spatial partitioning scheme to efficiently search for neighbors. $\endgroup$ – Tyler Olsen Aug 2 '18 at 18:59

Use a K-d tree. Python scipy has a fast implementation, see its doc .
Fwiw, run times on my 2.7 GHz iMac:
$\quad$ ~ 23 seconds to build a tree with 5M random points in 10d, Cauchy distributed
$\quad$ ~ 500 msec to query 50 points, 5 nearest neighbors each.

Incidentally queries in $\|\|_{\infty}$ are about twice as fast, 250 msec, as $\|\|_2$ .


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.