overview-summary.html

本程序是由JAVA实现的R-树新建、结点增加、删除功能。

-9.0pt;mso-list:l0 level3 lfo1;tab-stops:list 1.5in'><![if !supportLists]><span
style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>iii.<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><![endif]>Uses a single cache for all the trees in a JVM.</p>

<p class=MsoNormal style='margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:
-9.0pt;mso-list:l0 level3 lfo1;tab-stops:list 1.5in'><![if !supportLists]><span
style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>iv.<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><![endif]>Cache cannot be adjusted at runtime, therefore we need to
predict in advance the load on the tree. Runtime cache adjustment can be added
to the code.</p>

<ol style='margin-top:0in' start=1 type=1>
 <ol style='margin-top:0in' start=3 type=a>
  <li class=MsoNormal style='mso-list:l0 level2 lfo1;tab-stops:list 1.0in'>Packing</li>
 </ol>
</ol>

<p class=MsoNormal style='margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:
-9.0pt;mso-list:l0 level3 lfo1;tab-stops:list 1.5in'><![if !supportLists]><span
style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>i.<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><![endif]>Uses Sort Tile Recursive algorithm for packing a tree.</p>

<p class=MsoNormal style='margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:
-9.0pt;mso-list:l0 level3 lfo1;tab-stops:list 1.5in'><![if !supportLists]><span
style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>ii.<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><![endif]>Best Rtrees are packed Rtrees. But for that we need prior
information of all the objects to insert. A very good feature of this Rtree
implementation is that it can be packed any time, even in the middle of
insertions. </p>

<ol style='margin-top:0in' start=1 type=1>
 <ol style='margin-top:0in' start=4 type=a>
  <li class=MsoNormal style='mso-list:l0 level2 lfo1;tab-stops:list 1.0in'>Nearest
      Neighbour search by Roussopoulos and Cheung. Have implemented both types
      of NN search:</li>
 </ol>
</ol>

<p class=MsoNormal style='margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:
-9.0pt;mso-list:l0 level3 lfo1;tab-stops:list 1.5in'><![if !supportLists]><span
style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>i.<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><![endif]>for getting the n nearest neighbours in a range</p>

<p class=MsoNormal style='margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:
-9.0pt;mso-list:l0 level3 lfo1;tab-stops:list 1.5in'><![if !supportLists]><span
style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>ii.<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><![endif]>for getting all the neighbours in a given range in an
ascending order.</p>

<ol style='margin-top:0in' start=1 type=1>
 <ol style='margin-top:0in' start=5 type=a>
  <li class=MsoNormal style='mso-list:l0 level2 lfo1;tab-stops:list 1.0in'>Rtree
      join with intersects, contains, containedBy and equals predicates.</li>
  <li class=MsoNormal style='mso-list:l0 level2 lfo1;tab-stops:list 1.0in'>Seeding:
      A seeded tree can be used to create temporary trees that result from tree
      joins. Such trees can further participate in joins. Will help in spatial
      queries.</li>
 </ol>
 <li class=MsoNormal style='mso-list:l0 level1 lfo1;tab-stops:list .5in'>Disk
     based storage only. The tree is only disk based; therefore this tree is
     not the best choice for small a very small data set. This tree was
     designed for huge data sets. I抳e tested it by inserting 10 lakh<a
     style='mso-footnote-id:ftn1' href="#_ftn1" name="_ftnref1" title=""><span
     class=MsoFootnoteReference><span style='mso-special-character:footnote'><![if !supportFootnotes]>[1]<![endif]></span></span></a>
     random objects! But it works best with max 4 to 5 lakh objects. But I抳e
     never seen layers that big.</li>
 <li class=MsoNormal style='mso-list:l0 level1 lfo1;tab-stops:list .5in'>Bulk
     Loading: The Pack.java class also supports bulk loading. Please have a
     look at the Pack(List, String) constructor.</li>
 <li class=MsoNormal style='mso-list:l0 level1 lfo1;tab-stops:list .5in'>Concurrency:
     The tree is perfectly thread safe. The tree has a simple logic of multiple
     reads and single write. Even runtime packing of the tree is threadsafe.</li>
 <li class=MsoNormal style='mso-list:l0 level1 lfo1;tab-stops:list .5in'>Documentation:
     The documentation is pathetic to say the least. And I know I still haven抰
     improved. Lot of the classes and methods are not documented at all, but
     I抦 ready to help whoever wants more information. If you are going to use
     the code as a Black Bock then documentation in class RTree.java and
     Node.java should suffice.</li>
 <li class=MsoNormal style='mso-list:l0 level1 lfo1;tab-stops:list .5in'>Page
     and Cache size configuration: please read the Node.java class documentation
     for the correct configuration.</li>
 <li class=MsoNormal style='mso-list:l0 level1 lfo1;tab-stops:list .5in'>Long
     or Integer?? Because of certain requirements the index pointers of my
     Rtree are long and not int. This is an obvious performance issue.
     Volunteers may please convert that from long to int. Its not that big a job
     as I myself had converted it from int to long. Page size may have to be
     adjusted.</li>
</ol>

<p class=MsoNormal style='margin-left:.5in'>But I must also add that even with
long, the performance was very much acceptable to me.</p>

<ol style='margin-top:0in' start=8 type=1>
 <li class=MsoNormal style='mso-list:l0 level1 lfo1;tab-stops:list .5in'>Ways
     you can use the code:</li>
 <ol style='margin-top:0in' start=1 type=a>
  <li class=MsoNormal style='mso-list:l0 level2 lfo1;tab-stops:list 1.0in'>Black
      Box: You can use the library as it is. Just look at the rTreeDemo.java
      class to see the usage. But I still suggest that such people should have
      a look at the Node.java class documentation for cache size setting.</li>
  <li class=MsoNormal style='mso-list:l0 level2 lfo1;tab-stops:list 1.0in'>Modify/Improve:
      This is the main reason why I have made the code open. Those who really
      need this index should spend some time, improve the code and further
      enhance it. Though I抦 no longer working on GIS, I will still try to
      manage time and help people out with their queries. I抦 currently working
      with for Capgemini and am no longer associated with GIS.</li>
 </ol>
 <li class=MsoNormal style='mso-list:l0 level1 lfo1;tab-stops:list .5in'>Why I
     wrote this index: to facilitate spatial queries on non-spatial databases.
     This Rtree is only a small (but most essential) part of the whole system
     that included a query and a map engine. JTS was also part of it. I
     implemented this code as part of my final semester assignment and was my
     first assignment in Java as well. Therefore the code at some places may
     seem amateurish.</li>
</ol>

</div>

<div style='mso-element:footnote-list'><![if !supportFootnotes]><br clear=all>

<hr align=left size=1 width="33%">

<![endif]>

<div style='mso-element:footnote' id=ftn1>

<p class=MsoFootnoteText><a style='mso-footnote-id:ftn1' href="#_ftnref1"
name="_ftn1" title=""><span class=MsoFootnoteReference><span style='mso-special-character:
footnote'><![if !supportFootnotes]>[1]<![endif]></span></span></a><span
style="mso-spacerun: yes">