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 jfol...@cs.cmu.edu On Thu, Jun 2, 2011 at 8:43 PM, Andrea Taverna <a.t...@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]] ______________________________________________ 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.