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]]

