[BioRuby] searching through large sets of features

[Michael Barton]

You could use the kd-tree to narrow the search to the 1000 features each
side of the middle point, then traverse this set to exclude those outside of
the visualisation range. It's a bit of hack but it could save creating an
R-tree if there's no existing implementation.

2009/4/10 Jan Aerts <jan.aerts at gmail.com>

> That is a _really_ good resource. Unfortunately, R-Trees are not in there
> (or I didn't look well enough). I was thinking of sending him an email to
> ask if he could quickly add that to his library :-), but saw that he's
> switching to python. (But that particular announcement was on the 1st of
> April, so let's hope it's a joke)
> j.
>
>
> 2009/4/10 Michael Barton <mail at michaelbarton.me.uk>
>
>> There's also some ruby searching algorithms here
>> http://algorithms.rubyforge.org/
>>
>> I'm happy to try and help if I can
>>
>> Cheers
>>
>> Mike
>>
>> 2009/4/10 Michael Barton <mail at michaelbarton.me.uk>
>>
>> > Would a bloom tree fit this problem?
>> >
>> http://www.igvita.com/2008/12/27/scalable-datasets-bloom-filters-in-ruby/
>> >
>> > 2009/4/10 Jan Aerts <jan.aerts at gmail.com>
>> >
>> > Hi all,
>> >> I need to be able to handle millions of features for a visualization
>> and
>> >> therefore be able to search through them efficiently. I've been made
>> aware
>> >> of a so-called R-Tree (http://en.wikipedia.org/wiki/R-tree) data
>> >> structure
>> >> that could do just that. One of the issues that this approach would
>> solve
>> >> is
>> >> that it doesn't need to load every single feature when the display
>> >> resolution is not high enough (no use trying to plot 5 million points
>> next
>> >> to each other on a screen of 800 pixels wide; you can only plot 800
>> >> points....)
>> >>
>> >> I'm now trying to write a ruby-implementation of an R-Tree that is more
>> >> fit
>> >> for loci (i.e. one less dimension than an R-Tree, and has to handle
>> >> chromosome as well) at http://github.com/jandot/locustree. I'm trying
>> to
>> >> make it a module that can be mixed in, so anything which has a
>> chromosome,
>> >> start and stop can be indexed and searched using this R-Tree
>> adaptation.
>> >>
>> >> Does anyone know a ruby-implementation of R-Tree? Or is anyone
>> interested
>> >> in
>> >> helping me out?
>> >>
>> >> Thanks,
>> >> jan.
>> >> _______________________________________________
>> >> BioRuby mailing list
>> >> BioRuby at lists.open-bio.org
>> >> http://lists.open-bio.org/mailman/listinfo/bioruby
>> >>
>> >
>> >
>> _______________________________________________
>> BioRuby mailing list
>> BioRuby at lists.open-bio.org
>> http://lists.open-bio.org/mailman/listinfo/bioruby
>>
>
>