Problem deleting from R-Tree

Help
Sergio
2007-11-14
2013-01-10
  • Sergio
    Sergio
    2007-11-14

    Hi everybody,

    I have the following problem with JSI. I create and initialize an R-Tree and then I have an application that uses it to insert, delete and query data. The only methods I use are:

    -add(Rectangle, int);

    -intersects(Rectangle, IntProcedure);

    -delete(Rectangle, int);

    Sometimes, I get the following error when deleting:

    java.lang.NullPointerException
        at com.infomatiq.jsi.rtree.RTree.chooseNode(Unknown Source)
        at com.infomatiq.jsi.rtree.RTree.add(Unknown Source)
        at com.infomatiq.jsi.rtree.RTree.condenseTree(Unknown Source)
        at com.infomatiq.jsi.rtree.RTree.delete(Unknown Source)

    I have printed log messages and in principle there should not be a problem because this happens when I am trying to delete something that I inserted previously:

    01:00:13: added in R-Tree an object with identifier 11421254 and region: (843.7014, 127.0648), (931.7014, 215.0648)!
    ...
    01:00:46: deleting object in R-Tree with ID: 11421254 and region: (843.7014, 127.0648), (931.7014, 215.0648)...

    Any ideas about what may be the problem? The ID seems to be unique (as expected)... This error always happens when I use the JSI tree during some time in a test. I hope you can give me some idea to solve it!

    Thanks in advance,

    Sergio

     
    • Mark Pollard
      Mark Pollard
      2007-12-13

      We've encountered a similar problem.  I've sent email to Aled, but here is more information, with a stacktrace with line numbers:

      We've been attempting to narrow down and reproduce an NPE in the RTree library.  After re-compiling the library with line numbers and leaving a system up for several weeks, we've encountered the NPE.

      Here is the stacktrace:

      java.lang.NullPointerException
          at com.infomatiq.jsi.rtree.RTree.chooseNode(RTree.java:805)
          at com.infomatiq.jsi.rtree.RTree.add(RTree.java:201)
          at com.infomatiq.jsi.rtree.RTree.add(RTree.java:190)

      Line 805 is: float leastEnlargement = n.getEntry(0).enlargement(r);

      Looking at the code, n can not be null, so there must not be a 0th entry.

      While we don't yet have a reproducible test case, I can tell you the following: a large number of tracked devices were recently timed-out of our system causing a fair amount of deletions from the RTree.  From inspecting your code, I can also see that the original node is no longer the root (the current root node's level is not 1).

       
    • Mark Pollard
      Mark Pollard
      2007-12-13

      Here is a program that reproduces the problem.  100 rects are added to the spatial index.  And then deleted.  Generally, somewhere between the 60-80th deletion, the NPE is thrown.  First the trace, then the code:

      Exception in thread "main" java.lang.NullPointerException
          at com.infomatiq.jsi.rtree.RTree.chooseNode(RTree.java:805)
          at com.infomatiq.jsi.rtree.RTree.add(RTree.java:201)
          at com.infomatiq.jsi.rtree.RTree.condenseTree(RTree.java:775)
          at com.infomatiq.jsi.rtree.RTree.delete(RTree.java:289)
          at com.infomatiq.jsi.TestRtree.test(TestRtree.java:51)
          at com.infomatiq.jsi.TestRtree.main(TestRtree.java:84)

      package com.infomatiq.jsi;

      import java.util.HashMap;
      import java.util.Map;
      import java.util.Properties;

      import com.infomatiq.jsi.rtree.RTree;

      /**
      * TestRtree.
      * @author Copyright (c) 2007 by InnerWireless, Inc. All Rights Reserved.
      */
      public class TestRtree implements IntProcedure {
         private final static float LAT = 41.234567f;
         private final static float LON = -72.987654f;
        
         private final static int ID_BASE = 9876;
        
         private final SpatialIndex si = new RTree();
         private final Map<Integer, Rectangle> rectsById = new HashMap<Integer, Rectangle>();

         TestRtree() {
            si.init(new Properties());
           
            for (int i = 0; i < 100; i++) {
               int id = ID_BASE + i;
              
               Rectangle newRect = genRectPoint();        
               rectsById.put(id, newRect);        
               si.add(newRect, id);
            }
         }
        
         private Rectangle genRectPoint() {
            float lat = LAT + (((float)Math.random() - 0.5f) * 0.0001f);
            float lon = LON + (((float)Math.random() - 0.5f) * 0.0001f);
            return new Rectangle(lon, lat, lon, lat);
         }
        
         private Rectangle genRectBox() {
            float lat = LAT + (((float)Math.random() - 0.5f) * 0.0001f);
            float lon = LON + (((float)Math.random() - 0.5f) * 0.0001f);
            return new Rectangle(lon, lat, lon - 0.000020f, lat - 0.000020f);
         }

         void test() {
            while (true) {
               int count = 0;
               for (Integer id : rectsById.keySet()) {
                  Rectangle oldRect = rectsById.get(id);
                  si.delete(oldRect, id);
                 
                  System.out.println(count++ + ": " + oldRect);
               }
              
      //         count = 0;
      //         for (Integer id : rectsById.keySet()) {
      //            Rectangle newRect = genRectPoint();        
      //            rectsById.put(id, newRect);
      //           
      //            System.out.println("about to add " + count++);
      //           
      //            si.add(newRect, id);
      //
      //            Rectangle box = genRectPoint();
      //            si.contains(box, this);
      //         }
            }
         }

         /**
          * @see com.infomatiq.jsi.IntProcedure#execute(int)
          */
         public boolean execute(int id) {
            System.out.println("contains");
           
            return false;
         }

         /**
          * @param args
          */
         public static void main(String[] args) {
            new TestRtree().test();
         }
      }

       
    • Aled Morris
      Aled Morris
      2007-12-15

      I have identified the cause of the NPE - there is an bug in the delete() method.

      I'll try and get a new release out next weekend.

      Aled.

       
    • Aled Morris
      Aled Morris
      2008-03-02

      This bug should be resolved in release 1.0b2p1.

      Regards, Aled.

       
  •  MJW
    MJW
    2010-03-14

    Maybe the version of this bug that was previously reported in this thread was fixed, but a version still remains.

    Just for testing, I make an RTree with at least one element per node, and at most two elements per node.  I add three items to it, remove them all, and try to add them again.  The program crashes during the last of the aforementioned steps, upon the first attempt to add one of the items.

    As reported above, the root node is at level 2, and the tree has height 2, when the tree is empty.  This seems to be the problem.

    It seems to be necessary to completely empty the tree in order to put it in the corrupt state.  This differs from the above report, wherein it is said that the problem occurs after 100 items were added and 60-80 were removed.  I tried adding 3001 and removing 3000 and there was no corruption.  But removing the last item causes trouble.

    Since this project appears to be mostly dormant, I tried fixing the bug myself.  I added this little hack to the end of the method RTree.condenseTree():

        if (n.entryCount == 0)
        {
        treeHeight = 1;
        n.level = 1;
        }

    Now all my tests pass, and all the JSI tests pass (though they appear to be designed to be difficult to read, so I can't easily tell whether they're actually testing correctness and speed both, or just speed), and the main program I'm writing doesn't crash anymore.  So I guess this change is a pretty good one, though the perfect solution may be something else entirely.

     
  • Aled Morris
    Aled Morris
    2010-05-30

    Thanks for the bug report - I'll try and reproduce the problem, and hopefully release a fixed version.

    Aled.

     
  •  MJW
    MJW
    2010-06-28

    I read your message when it was posted, but I was satisfied to go on using my own hack…  until today, when my version of JSI failed in a new way.  My hack had fixed a problem arising for a tree with minimal node size 1, maximal node size 2, and 3 nodes added and removed.  That was good.  But the newly discovered problem arose for node size limits 5 and 30, with 31 nodes added and removed.  In testing, I also saw it arise with size limits 2 and 4, with 5 nodes added and removed.  Instead of trying to fix this, I downloaded release 1.0b5, which does not exhibit either problem.  So maybe everything is fine now.  (I hope so, because I plan to increase my use of JSI soon!)

    Thanks for the help.

     
  •  MJW
    MJW
    2011-02-26

    This bug I described earlier:  "Just for testing, I make an RTree with at least one element per node, and at most two elements per node.  I add three items to it, remove them all, and try to add them again.  The program crashes during the last of the aforementioned steps, upon the first attempt to add one of the items."
    appears to have returned in the latest version (CVS).

     
  •  MJW
    MJW
    2011-03-02

    Those both pass my test.  The version in the "jsi" branch of the CVS repository does not.

    Here is the test:

    import java.util.ArrayList;
    import java.util.Properties;
    import java.util.Random;
    import org.junit.Test;
    import com.infomatiq.jsi.Rectangle;
    import com.infomatiq.jsi.rtree.RTree;
    public class Tests
    {
        @Test
        public void testSomething() throws Exception
        {
            Random random = new Random(3);
    
            RTree rTree = new RTree();
            Properties properties = new Properties();
            properties.setProperty("MinNodeEntries", "1");
            properties.setProperty("MaxNodeEntries", "2");
            rTree.init(properties);
            ArrayList<Bo> bos = new ArrayList<Bo>();
            for (int i = 0; i < 3; i++)
                bos.add(new Bo(i * 70, random));
            for (Bo bo: bos)
                bo.addTo(rTree);
            for (Bo bo: bos)
                bo.removeFrom(rTree);
            for (Bo bo: bos)
                bo.addTo(rTree);
        }
    
        private static class Bo
        {
            private final int id;
            private Rectangle rectangle;
            public Bo(int id, Random random)
            {
                this.id = id;
                rectangle = new Rectangle(random.nextFloat() + id, random.nextFloat() + id, random.nextFloat() + id, random.nextFloat() + id);
            }
            public void addTo(RTree rTree)
            {
                rTree.add(rectangle, id);
            }
    
            public void removeFrom(RTree rTree)
            {
                rTree.delete(rectangle, id);
            }
        }
    }
    
     
  • Aled Morris
    Aled Morris
    2011-03-02

    Hi, the version in cvs is out of date, I am now using github for source control. Search for jsi on there and you'll find the source tree.

    Sorry if this is confusing, there doesn't seem to be a good way to inform sourceforge users that the repository is somewhere else. Let me know if you have any suggestions.

    Aled

     
  •  MJW
    MJW
    2011-03-02

    I suppose you could check in a THIS VERSION IS OUT OF DATE.TXT file (or something similarly eye-catching and alarming) to the CVS version, in a root directory where people would be very likely to see it, and put a link to the latest version in the file.