R help - Jun 2011 - Traversing KD-tree (or equivalent) for radius-based search

Hi,

I'm trying to implement the DBSCAN algorithm to get O(N*LogN) complexity 
and I'd need a spatial tree of some sort (kd,r,bd..), or a function that 
computes radius-based search on spatial data, i.e. given a radius eps 
finds ALL the points which fall in the corresponding hypersphere 
centered on the current examined point.  Is there a package with this 
features?

So far I found RANN and other packages whose name I can't remember (I 
don't have them with me a.t.m.), and they all seemed to offer a 
nearest-neighbour search, which asks for an upper limit to the number of 
points to be found, but no direct access to the spatial tree they used . 
The algorithms they provide are built around that limit and setting it 
to large values makes their execution impractical.
OTOH, as far as I have understood, DBSCAN needs to know all the points 
in the eps-neighbourhood, or will create too many clusters, especially 
if there are really high-density region, as it happened when I used 
RANN's nn2 function in my implementation.

thanks in advance,

Andrea Taverna

There aren't a whole lot of more complex data structures available as R
packages.  My impression is that pure R implementation offers
dissatisfactory performance and native (or e.g. java)  implementations end
up inconsistent with R's "no side effects" principles.  I'd
suggest building
an R interface to whatever spatial data structures you want, e.g. k-d or
r(+/*)-trees.

Jamie Olson
School of Computer Science
Carnegie Mellon University
5000 Forbes Ave.
Pittsburgh, PA 15213
jfolson@cs.cmu.edu


On Thu, Jun 2, 2011 at 8:43 PM, Andrea Taverna <a.tavs@libero.it> wrote:
> Hi,
>
> I'm trying to implement the DBSCAN algorithm to get O(N*LogN)
complexity
> and I'd need a spatial tree of some sort (kd,r,bd..), or a function
that
> computes radius-based search on spatial data, i.e. given a radius eps finds
> ALL the points which fall in the corresponding hypersphere centered on the
> current examined point.  Is there a package with this features?
>
> So far I found RANN and other packages whose name I can't remember (I
don't
> have them with me a.t.m.), and they all seemed to offer a nearest-neighbour
> search, which asks for an upper limit to the number of points to be found,
> but no direct access to the spatial tree they used . The algorithms they
> provide are built around that limit and setting it to large values makes
> their execution impractical.
> OTOH, as far as I have understood, DBSCAN needs to know all the points in
> the eps-neighbourhood, or will create too many clusters, especially if
there
> are really high-density region, as it happened when I used RANN's nn2
> function in my implementation.
>
> thanks in advance,
>
> Andrea Taverna
>
> ______________________________________________
> R-help@r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
> http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>
	[[alternative HTML version deleted]]