diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/.classpath b/hyracks-tests/hyracks-storage-am-rtree-test/.classpath
new file mode 100644
index 0000000..f2cc5f7
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/.classpath
@@ -0,0 +1,7 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<classpath>
+	<classpathentry kind="src" output="target/test-classes" path="src/test/java"/>
+	<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.6"/>
+	<classpathentry kind="con" path="org.maven.ide.eclipse.MAVEN2_CLASSPATH_CONTAINER"/>
+	<classpathentry kind="output" path="target/classes"/>
+</classpath>
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeConcurrentTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeConcurrentTest.java
new file mode 100644
index 0000000..34fcb14
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeConcurrentTest.java
@@ -0,0 +1,154 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.rtree;
+
+import java.io.File;
+
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.TypeTrait;
+import edu.uci.ics.hyracks.api.io.FileReference;
+import edu.uci.ics.hyracks.dataflow.common.data.comparators.DoubleBinaryComparatorFactory;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.common.api.IFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
+import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
+import edu.uci.ics.hyracks.test.support.TestStorageManagerComponentHolder;
+import edu.uci.ics.hyracks.test.support.TestUtils;
+
+public class RTreeConcurrentTest extends AbstractRTreeTest {
+
+    private static final int PAGE_SIZE = 1024;
+    private static final int NUM_PAGES = 10000;
+    private static final int MAX_OPEN_FILES = 10;
+    private static final int HYRACKS_FRAME_SIZE = 128;
+    private IHyracksStageletContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
+
+    @Test
+    public void test01() throws Exception {
+
+        TestStorageManagerComponentHolder.init(PAGE_SIZE, NUM_PAGES, MAX_OPEN_FILES);
+        IBufferCache bufferCache = TestStorageManagerComponentHolder.getBufferCache(ctx);
+        IFileMapProvider fmp = TestStorageManagerComponentHolder.getFileMapProvider(ctx);
+        FileReference file = new FileReference(new File(fileName));
+        bufferCache.createFile(file);
+        int fileId = fmp.lookupFileId(file);
+        bufferCache.openFile(fileId);
+
+        // declare keys
+        int keyFieldCount = 4;
+        IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
+        cmps[0] = DoubleBinaryComparatorFactory.INSTANCE.createBinaryComparator();
+        cmps[1] = cmps[0];
+        cmps[2] = cmps[0];
+        cmps[3] = cmps[0];
+
+        // declare leaf-frame-tuple fields
+        int fieldCount = 5;
+        ITypeTrait[] typeTraits = new ITypeTrait[fieldCount];
+        typeTraits[0] = new TypeTrait(8);
+        typeTraits[1] = new TypeTrait(8);
+        typeTraits[2] = new TypeTrait(8);
+        typeTraits[3] = new TypeTrait(8);
+        typeTraits[4] = new TypeTrait(4);
+
+        MultiComparator cmp = new MultiComparator(typeTraits, cmps);
+
+        RTreeTypeAwareTupleWriterFactory tupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(typeTraits);
+
+        ITreeIndexFrameFactory interiorFrameFactory = new RTreeNSMInteriorFrameFactory(tupleWriterFactory,
+                keyFieldCount);
+        ITreeIndexFrameFactory leafFrameFactory = new RTreeNSMLeafFrameFactory(tupleWriterFactory, keyFieldCount);
+        ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+        ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
+
+        IRTreeFrame interiorFrame = (IRTreeFrame) interiorFrameFactory.createFrame();
+        IRTreeFrame leafFrame = (IRTreeFrame) leafFrameFactory.createFrame();
+        IFreePageManager freePageManager = new LinkedListFreePageManager(bufferCache, fileId, 0, metaFrameFactory);
+
+        RTree rtree = new RTree(bufferCache, freePageManager, interiorFrameFactory, leafFrameFactory, cmp);
+        rtree.create(fileId, leafFrame, metaFrame);
+        rtree.open(fileId);
+
+        @SuppressWarnings("rawtypes")
+        ISerializerDeserializer[] recDescSers = { DoubleSerializerDeserializer.INSTANCE,
+                DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
+                DoubleSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+
+        RTreeWriterTest writer1 = new RTreeWriterTest(rtree, ctx, "w1");
+        writer1.start();
+
+        RTreeWriterTest writer2 = new RTreeWriterTest(rtree, ctx, "w2");
+        writer2.start();
+
+        RTreeWriterTest writer3 = new RTreeWriterTest(rtree, ctx, "w3");
+        writer3.start();
+
+        RTreeWriterTest writer4 = new RTreeWriterTest(rtree, ctx, "w4");
+        writer4.start();
+
+        RTreeWriterTest writer5 = new RTreeWriterTest(rtree, ctx, "w5");
+        writer5.start();
+
+        RTreeWriterTest writer6 = new RTreeWriterTest(rtree, ctx, "w6");
+        writer6.start();
+
+        RTreeWriterTest writer7 = new RTreeWriterTest(rtree, ctx, "w7");
+        writer7.start();
+
+        RTreeWriterTest writer8 = new RTreeWriterTest(rtree, ctx, "w8");
+        writer8.start();
+
+        RTreeWriterTest writer9 = new RTreeWriterTest(rtree, ctx, "w9");
+        writer9.start();
+
+        RTreeWriterTest writer10 = new RTreeWriterTest(rtree, ctx, "w10");
+        writer10.start();
+
+        String stats = rtree.printStats();
+        print(stats);
+
+        System.out.println();
+
+        stats = rtree.printStats();
+        print(stats);
+
+        System.out.println();
+        rtree.printTree(leafFrame, interiorFrame, recDescSers);
+        System.out.println();
+
+        // rtree.close();
+        // bufferCache.closeFile(fileId);
+        // bufferCache.close();
+
+    }
+}
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
index b0456ce..1ed8dd1 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTest.java
@@ -69,6 +69,9 @@
     private static final int HYRACKS_FRAME_SIZE = 128;
     private IHyracksStageletContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
 
+    // create an R-tree of two dimensions
+    // fill the R-tree with random values using insertions
+    // perform ordered scan
     @Test
     public void test01() throws Exception {
 
@@ -220,6 +223,9 @@
 
     }
 
+    // create an R-tree of two dimensions
+    // fill the R-tree with random values using insertions
+    // and then delete all the tuples which result of an empty R-tree
     @Test
     public void test02() throws Exception {
 
@@ -399,6 +405,9 @@
 
     }
 
+    // create an R-tree of three dimensions
+    // fill the R-tree with random values using insertions
+    // perform ordered scan
     @Test
     public void test03() throws Exception {
 
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeWriterTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeWriterTest.java
new file mode 100644
index 0000000..c1404bc
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeWriterTest.java
@@ -0,0 +1,237 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ * 
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.rtree;
+
+import java.io.DataOutput;
+import java.nio.ByteBuffer;
+import java.util.Random;
+
+import edu.uci.ics.hyracks.api.comm.IFrameTupleAccessor;
+import edu.uci.ics.hyracks.api.context.IHyracksStageletContext;
+import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparator;
+import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
+import edu.uci.ics.hyracks.api.dataflow.value.ITypeTrait;
+import edu.uci.ics.hyracks.api.dataflow.value.RecordDescriptor;
+import edu.uci.ics.hyracks.api.dataflow.value.TypeTrait;
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAccessor;
+import edu.uci.ics.hyracks.dataflow.common.comm.io.FrameTupleAppender;
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.FrameTupleReference;
+import edu.uci.ics.hyracks.dataflow.common.data.comparators.DoubleBinaryComparatorFactory;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
+import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
+import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
+import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeFrame;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMInteriorFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMLeafFrameFactory;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTree;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeOpContext;
+import edu.uci.ics.hyracks.storage.am.rtree.tuples.RTreeTypeAwareTupleWriterFactory;
+import edu.uci.ics.hyracks.test.support.TestUtils;
+
+public class RTreeWriterTest extends Thread {
+    private RTree rtree;
+    private static final int HYRACKS_FRAME_SIZE = 128;
+    private IHyracksStageletContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
+
+    public RTreeWriterTest(RTree rtree, IHyracksStageletContext ctx, String threadName) {
+        this.rtree = rtree;
+        this.setName(threadName);
+    }
+
+    private boolean keepRunning = true;
+
+    @Override
+    public void run() {
+        // while (keepRunning) {
+
+        // declare keys
+        int keyFieldCount = 4;
+        IBinaryComparator[] cmps = new IBinaryComparator[keyFieldCount];
+        cmps[0] = DoubleBinaryComparatorFactory.INSTANCE.createBinaryComparator();
+        cmps[1] = cmps[0];
+        cmps[2] = cmps[0];
+        cmps[3] = cmps[0];
+
+        // declare tuple fields
+        int fieldCount = 5;
+        ITypeTrait[] typeTraits = new ITypeTrait[fieldCount];
+        typeTraits[0] = new TypeTrait(8);
+        typeTraits[1] = new TypeTrait(8);
+        typeTraits[2] = new TypeTrait(8);
+        typeTraits[3] = new TypeTrait(8);
+        typeTraits[4] = new TypeTrait(4);
+
+        MultiComparator cmp = new MultiComparator(typeTraits, cmps);
+
+        RTreeTypeAwareTupleWriterFactory tupleWriterFactory = new RTreeTypeAwareTupleWriterFactory(typeTraits);
+
+        ITreeIndexFrameFactory interiorFrameFactory = new RTreeNSMInteriorFrameFactory(tupleWriterFactory,
+                keyFieldCount);
+        ITreeIndexFrameFactory leafFrameFactory = new RTreeNSMLeafFrameFactory(tupleWriterFactory, keyFieldCount);
+        ITreeIndexMetaDataFrameFactory metaFrameFactory = new LIFOMetaDataFrameFactory();
+        ITreeIndexMetaDataFrame metaFrame = metaFrameFactory.createFrame();
+
+        IRTreeFrame interiorFrame = (IRTreeFrame) interiorFrameFactory.createFrame();
+        IRTreeFrame leafFrame = (IRTreeFrame) leafFrameFactory.createFrame();
+
+        ByteBuffer hyracksFrame = ctx.allocateFrame();
+        FrameTupleAppender appender = new FrameTupleAppender(ctx.getFrameSize());
+        ArrayTupleBuilder tb = new ArrayTupleBuilder(cmp.getFieldCount());
+        DataOutput dos = tb.getDataOutput();
+
+        @SuppressWarnings("rawtypes")
+        ISerializerDeserializer[] recDescSers = { DoubleSerializerDeserializer.INSTANCE,
+                DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,
+                DoubleSerializerDeserializer.INSTANCE, IntegerSerializerDeserializer.INSTANCE };
+
+        RecordDescriptor recDesc = new RecordDescriptor(recDescSers);
+        IFrameTupleAccessor accessor = new FrameTupleAccessor(ctx.getFrameSize(), recDesc);
+        accessor.reset(hyracksFrame);
+        FrameTupleReference tuple = new FrameTupleReference();
+
+        RTreeOpContext insertOpCtx = rtree.createOpContext(IndexOp.INSERT, leafFrame, interiorFrame, metaFrame);
+
+        RTreeOpContext deleteOpCtx = rtree.createOpContext(IndexOp.DELETE, leafFrame, interiorFrame, metaFrame);
+
+        Random rnd = new Random();
+        rnd.setSeed(50);
+        for (int i = 0; i < 10000; i++) {
+
+            double p1x = rnd.nextDouble();
+            double p1y = rnd.nextDouble();
+            double p2x = rnd.nextDouble();
+            double p2y = rnd.nextDouble();
+
+            int pk = rnd.nextInt();
+
+            tb.reset();
+            try {
+                DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1x, p2x), dos);
+                tb.addFieldEndOffset();
+                DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1y, p2y), dos);
+                tb.addFieldEndOffset();
+                DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1x, p2x), dos);
+                tb.addFieldEndOffset();
+                DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1y, p2y), dos);
+                tb.addFieldEndOffset();
+                IntegerSerializerDeserializer.INSTANCE.serialize(pk, dos);
+                tb.addFieldEndOffset();
+            } catch (HyracksDataException e1) {
+                // TODO Auto-generated catch block
+                e1.printStackTrace();
+            }
+
+            appender.reset(hyracksFrame, true);
+            appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
+
+            tuple.reset(accessor, 0);
+
+            System.out.println(this.getName() + " INSERTING " + i + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y)
+                    + " " + Math.max(p1x, p2x) + " " + Math.max(p1y, p2y) + "\n");
+
+            try {
+                rtree.insert(tuple, insertOpCtx);
+
+            } catch (TreeIndexException e) {
+            } catch (Exception e) {
+                e.printStackTrace();
+
+                try {
+                    rtree.printTree(leafFrame, interiorFrame, recDescSers);
+                } catch (Exception e1) {
+                    // TODO Auto-generated catch block
+                    e1.printStackTrace();
+                }
+                // System.out.println();
+            }
+
+        }
+
+        rnd.setSeed(50);
+        for (int i = 0; i < 10000; i++) {
+
+            double p1x = rnd.nextDouble();
+            double p1y = rnd.nextDouble();
+            double p2x = rnd.nextDouble();
+            double p2y = rnd.nextDouble();
+
+            int pk = rnd.nextInt();
+
+            tb.reset();
+            try {
+                DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1x, p2x), dos);
+                tb.addFieldEndOffset();
+                DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1y, p2y), dos);
+                tb.addFieldEndOffset();
+                DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1x, p2x), dos);
+                tb.addFieldEndOffset();
+                DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1y, p2y), dos);
+                tb.addFieldEndOffset();
+                IntegerSerializerDeserializer.INSTANCE.serialize(pk, dos);
+                tb.addFieldEndOffset();
+            } catch (HyracksDataException e1) {
+                // TODO Auto-generated catch block
+                e1.printStackTrace();
+            }
+
+            appender.reset(hyracksFrame, true);
+            appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
+
+            tuple.reset(accessor, 0);
+
+            System.out.println(this.getName() + " Deleteing " + i + " " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y)
+                    + " " + Math.max(p1x, p2x) + " " + Math.max(p1y, p2y) + "\n");
+
+            try {
+                rtree.delete(tuple, deleteOpCtx);
+
+            } catch (TreeIndexException e) {
+            } catch (Exception e) {
+                e.printStackTrace();
+
+                try {
+                    rtree.printTree(leafFrame, interiorFrame, recDescSers);
+                } catch (Exception e1) {
+                    // TODO Auto-generated catch block
+                    e1.printStackTrace();
+                }
+                // System.out.println();
+            }
+        }
+
+        // update every seconds
+        try {
+            Thread.sleep(1000);
+        } catch (InterruptedException e) {
+            e.printStackTrace();
+        }
+        // }
+    }
+
+    public void stopWriter() {
+        this.keepRunning = false;
+        this.interrupt();
+    }
+
+}
\ No newline at end of file
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
index 9a4f496..195213b 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/SearchCursorTest.java
@@ -73,6 +73,9 @@
     private static final int HYRACKS_FRAME_SIZE = 128;
     private IHyracksStageletContext ctx = TestUtils.create(HYRACKS_FRAME_SIZE);
 
+    // create an R-tree of two dimensions
+    // fill the R-tree with random values using insertions
+    // and then perform range search
     @Test
     public void searchCursorTest() throws Exception {
 
@@ -177,27 +180,59 @@
 
         }
 
-        ITreeIndexCursor searchCursor = new RTreeSearchCursor(interiorFrame, leafFrame);
-        SearchPredicate searchPredicate = new SearchPredicate(tuple, cmp);
+        for (int i = 0; i < 50; i++) {
 
-        RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, leafFrame, interiorFrame, metaFrame);
-        rtree.search(searchCursor, searchPredicate, searchOpCtx);
+            double p1x = rnd.nextDouble();
+            double p1y = rnd.nextDouble();
+            double p2x = rnd.nextDouble();
+            double p2y = rnd.nextDouble();
 
-        ArrayList<Integer> results = new ArrayList<Integer>();
-        try {
-            while (searchCursor.hasNext()) {
-                searchCursor.next();
-                ITupleReference frameTuple = searchCursor.getTuple();
-                ByteArrayInputStream inStream = new ByteArrayInputStream(frameTuple.getFieldData(0),
-                        frameTuple.getFieldStart(0), frameTuple.getFieldLength(0));
-                DataInput dataIn = new DataInputStream(inStream);
-                Integer res = IntegerSerializerDeserializer.INSTANCE.deserialize(dataIn);
-                results.add(res);
+            int pk = rnd.nextInt();
+
+            tb.reset();
+            DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1x, p2x), dos);
+            tb.addFieldEndOffset();
+            DoubleSerializerDeserializer.INSTANCE.serialize(Math.min(p1y, p2y), dos);
+            tb.addFieldEndOffset();
+            DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1x, p2x), dos);
+            tb.addFieldEndOffset();
+            DoubleSerializerDeserializer.INSTANCE.serialize(Math.max(p1y, p2y), dos);
+            tb.addFieldEndOffset();
+            IntegerSerializerDeserializer.INSTANCE.serialize(pk, dos);
+            tb.addFieldEndOffset();
+
+            appender.reset(hyracksFrame, true);
+            appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize());
+
+            tuple.reset(accessor, 0);
+
+            print(i + " Searching for: " + Math.min(p1x, p2x) + " " + Math.min(p1y, p2y) + " " + Math.max(p1x, p2x)
+                    + " " + Math.max(p1y, p2y) + "\n");
+
+            ITreeIndexCursor searchCursor = new RTreeSearchCursor(interiorFrame, leafFrame);
+            SearchPredicate searchPredicate = new SearchPredicate(tuple, cmp);
+
+            RTreeOpContext searchOpCtx = rtree.createOpContext(IndexOp.SEARCH, leafFrame, interiorFrame, metaFrame);
+            rtree.search(searchCursor, searchPredicate, searchOpCtx);
+
+            ArrayList<Integer> results = new ArrayList<Integer>();
+            try {
+                while (searchCursor.hasNext()) {
+                    searchCursor.next();
+                    ITupleReference frameTuple = searchCursor.getTuple();
+                    ByteArrayInputStream inStream = new ByteArrayInputStream(frameTuple.getFieldData(4),
+                            frameTuple.getFieldStart(4), frameTuple.getFieldLength(4));
+                    DataInput dataIn = new DataInputStream(inStream);
+                    Integer res = IntegerSerializerDeserializer.INSTANCE.deserialize(dataIn);
+                    results.add(res);
+                }
+            } catch (Exception e) {
+                e.printStackTrace();
+            } finally {
+                searchCursor.close();
             }
-        } catch (Exception e) {
-            e.printStackTrace();
-        } finally {
-            searchCursor.close();
+
+            System.out.println("There are " + results.size() + " objects that satisfy the query");
         }
 
         rtree.close();