Add a new search type CountWithinRange?

[kahaaga]

I've encountered a use case where I need to construct a tree search structure, and for a list of query points, I need to find how many points are within a certain radius r of each of those points (see this comment).

A way of doing this is to use WithinRange(r) with bulkisearch. However, this is inefficient, because it allocates the index vectors (thus, allocations grow with the number of input points).

NearestNeighbors.jl recently added the inrangecount function, which simply counts the number of neighbors without allocating neither indices nor distances. In my specific application, using inrangecount instead of bulkisearch reduces runtime by half and allocations by many orders of magnitude (depending on size of input data).

It would be nice to have a generic search structure representing this use case in Neighborhood.jl too. Perhaps something like the following?

Base.@kwdef struct CountWithinRange <: SearchType
    r
    self_count::bool = false
end

where r is the radius and self_count flag determines whether the query point itself should be counted or not.

[Datseris]

Hi, yes sounds good, but I'd vote to remove the self_count stuff; a user can literally do x + 1 if they want to include the self count, and this seems like a much larger complexity in the source code with extra fields and stuff.

[Datseris]

However, I'm not sure if this struct is the way to go, because then what would bulksearch return? Wouldn't it make more sense to just implement here the inrangecount function, which means just re-exporting it?

[kahaaga]

However, I'm not sure if this struct is the way to go, because then what would bulksearch return? Wouldn't it make more sense to just implement here the inrangecount function, which means just re-exporting it?

Good point. think re-exporting inrangecount may work better. I suggest

function inrangecount(tree, query_pts, r)
    [inrangecount(tree, pᵢ, r) for pᵢ in pts]
end

where tree is a pre-computed tree, query_pts[i], where i = 1, 2, ..., N, is a point for which we want to know how many points lie within a radius of r from it (given the metric that was used to construct the tree).

If you're okay with that @Datseris, I'll submit a PR (also including an in-place version where the count vector is pre-allocated).

[Datseris]

sounds good, but if there is no performant version for getting in a vector of points already in NearestNeighbors.jl, I'd say that inrangecount(tree, pᵢ, r) is the only thing necessary to export. Thankfully a user can write this list comprehension just as easily.

[kahaaga]

Solved by #17.

[kahaaga]

Is there a reason why this was given version 0.2.4? In the list of tagged releases, 0.2.2 was the previous one.