diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java
index 7be43ff..9d60464 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeFrame.java
@@ -5,25 +5,28 @@
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.FindPathList;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.Rectangle;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.TupleEntryArrayList;
 
 public interface IRTreeFrame extends ITreeIndexFrame {
-    
+
+    public int findTuple(ITupleReference tuple, FindPathList findPathList, int parentId, MultiComparator cmp);
+
     public int findTuple(ITupleReference tuple, MultiComparator cmp);
-    
+
     public int getPageNsn();
-    
+
     public void setPageNsn(int pageNsn);
-    
+
     public int getRightPage();
 
     public void setRightPage(int rightPage);
 
     public int getBestChildPageId(MultiComparator cmp);
-    
-    public boolean checkEnlargement(ITupleReference tuple, TupleEntryArrayList entries, ITreeIndexTupleReference[] nodesMBRs,
-            MultiComparator cmp);
+
+    public boolean checkEnlargement(ITupleReference tuple, TupleEntryArrayList entries,
+            ITreeIndexTupleReference[] nodesMBRs, MultiComparator cmp);
 
     public void adjustNodeMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp);
 
@@ -38,6 +41,6 @@
     public Rectangle intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
 
     public int getChildPageIdIfIntersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
-    
+
     public void enlarge(ITupleReference tuple, MultiComparator cmp);
 }
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
index ed43240..7d0e886 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/NSMRTreeFrame.java
@@ -1,6 +1,5 @@
 package edu.uci.ics.hyracks.storage.am.rtree.frames;
 
-import java.nio.ByteBuffer;
 import java.util.ArrayList;
 
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
@@ -15,6 +14,7 @@
 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.impls.EntriesOrder;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.FindPathList;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSplitKey;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.Rectangle;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.TupleEntryArrayList;
@@ -42,23 +42,23 @@
         }
         cmpFrameTuple = tupleWriter.createTupleReference();
     }
-    
+
     @Override
     public void initBuffer(byte level) {
         super.initBuffer(level);
         buf.putInt(pageNsnOff, 0);
         buf.putInt(rightPageOff, -1);
     }
-    
+
     public void setTupleCount(int tupleCount) {
         buf.putInt(tupleCountOff, tupleCount);
     }
-    
+
     @Override
     public void setPageNsn(int pageNsn) {
         buf.putInt(pageNsnOff, pageNsn);
     }
-    
+
     @Override
     public int getPageNsn() {
         return buf.getInt(pageNsnOff);
@@ -80,14 +80,10 @@
         buf.putInt(rightPageOff, rightPage);
     }
 
-    public ITreeIndexTupleReference[] getTuples() {
+    private ITreeIndexTupleReference[] getTuples() {
         return tuples;
     }
 
-    public void setTuples(ITreeIndexTupleReference[] tuples) {
-        this.tuples = tuples;
-    }
-
     // for debugging
     public ArrayList<Integer> getChildren(MultiComparator cmp) {
         ArrayList<Integer> ret = new ArrayList<Integer>();
@@ -185,8 +181,7 @@
     @Override
     public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey,
             TupleEntryArrayList entries1, TupleEntryArrayList entries2, Rectangle[] rec) throws Exception {
-        
-        
+
         // RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
         // RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame =
         // ((RTreeTypeAwareTupleWriter) tupleWriter);
@@ -219,7 +214,8 @@
         // int src = rightFrame.getSlotManager().getSlotEndOff();
         // int dest = rightFrame.getSlotManager().getSlotEndOff() + tuplesToLeft
         // * rightFrame.getSlotManager().getSlotSize();
-        // int length = rightFrame.getSlotManager().getSlotSize() * tuplesToRight;
+        // int length = rightFrame.getSlotManager().getSlotSize() *
+        // tuplesToRight;
         // System.arraycopy(right.array(), src, right.array(), dest, length);
         // right.putInt(tupleCountOff, tuplesToRight);
         //
@@ -256,8 +252,7 @@
         // 0);
         //
         // return 0;
-        
-        
+
         RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
         RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
         RTreeTypeAwareTupleWriter rTreeTupleWriterRightFrame = ((RTreeTypeAwareTupleWriter) rightFrame.getTupleWriter());
@@ -392,7 +387,7 @@
         // compact both pages
         rightFrame.compact(cmp);
         compact(cmp);
-        
+
         if (!tupleInserted) {
             insert(tuple, cmp);
         }
@@ -415,7 +410,7 @@
         return 0;
     }
 
-    public void generateDist(ITupleReference tuple, TupleEntryArrayList entries, Rectangle rec, int start, int end) {
+    private void generateDist(ITupleReference tuple, TupleEntryArrayList entries, Rectangle rec, int start, int end) {
         int j = 0;
         while (entries.get(j).getTupleIndex() == -1) {
             j++;
@@ -447,10 +442,10 @@
     public int getBestChildPageId(MultiComparator cmp) {
         return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
     }
-    
+
     @Override
-    public boolean checkEnlargement(ITupleReference tuple, TupleEntryArrayList entries, ITreeIndexTupleReference[] nodesMBRs,
-            MultiComparator cmp) {
+    public boolean checkEnlargement(ITupleReference tuple, TupleEntryArrayList entries,
+            ITreeIndexTupleReference[] nodesMBRs, MultiComparator cmp) {
 
         cmpFrameTuple.setFieldCount(cmp.getFieldCount());
         frameTuple.setFieldCount(cmp.getFieldCount());
@@ -545,127 +540,130 @@
             }
         }
         entries.clear();
-        
+
         frameTuple.resetByTupleIndex(this, bestChild);
         if (minEnlargedArea > 0.0) {
             return true;
-            //enlarge(frameTuple, tuple, cmp);
+            // enlarge(frameTuple, tuple, cmp);
         } else {
             return false;
         }
-        
-        //nodesMBRs[(int) getLevel() - 1].resetByTupleIndex(this, bestChild);
 
-        
+        // nodesMBRs[(int) getLevel() - 1].resetByTupleIndex(this, bestChild);
 
         // return the page id of the bestChild tuple
-        //return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
+        // return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
     }
-    
-//    @Override
-//    public int getChildPageId(ITupleReference tuple, TupleEntryArrayList entries, ITreeIndexTupleReference[] nodesMBRs,
-//            MultiComparator cmp) {
-//
-//        cmpFrameTuple.setFieldCount(cmp.getFieldCount());
-//        frameTuple.setFieldCount(cmp.getFieldCount());
-//
-//        int bestChild = 0;
-//        double minEnlargedArea = Double.MAX_VALUE;
-//
-//        // the children pointers in the node point to leaves
-//        if (getLevel() == 1) {
-//            // find least overlap enlargement, use minimum enlarged area to
-//            // break tie, if tie still exists use minimum area to break it
-//            for (int i = 0; i < getTupleCount(); ++i) {
-//                frameTuple.resetByTupleIndex(this, i);
-//                double enlargedArea = enlargedArea(frameTuple, tuple, cmp);
-//                entries.add(i, enlargedArea);
-//                if (enlargedArea < minEnlargedArea) {
-//                    minEnlargedArea = enlargedArea;
-//                    bestChild = i;
-//                }
-//            }
-//            if (minEnlargedArea < entries.getDoubleEpsilon() || minEnlargedArea > entries.getDoubleEpsilon()) {
-//                minEnlargedArea = Double.MAX_VALUE;
-//                int k;
-//                if (getTupleCount() > nearMinimumOverlapFactor) {
-//                    // sort the entries based on their area enlargement needed
-//                    // to include the object
-//                    entries.sort(EntriesOrder.ASCENDING, getTupleCount());
-//                    k = nearMinimumOverlapFactor;
-//                } else {
-//                    k = getTupleCount();
-//                }
-//
-//                double minOverlap = Double.MAX_VALUE;
-//                int id = 0;
-//                for (int i = 0; i < k; ++i) {
-//                    double difference = 0.0;
-//                    for (int j = 0; j < getTupleCount(); ++j) {
-//                        frameTuple.resetByTupleIndex(this, j);
-//                        cmpFrameTuple.resetByTupleIndex(this, entries.get(i).getTupleIndex());
-//
-//                        int c = cmp.getIntCmp().compare(frameTuple.getFieldData(cmp.getKeyFieldCount()),
-//                                frameTuple.getFieldStart(cmp.getKeyFieldCount()),
-//                                frameTuple.getFieldLength(cmp.getKeyFieldCount()),
-//                                cmpFrameTuple.getFieldData(cmp.getKeyFieldCount()),
-//                                cmpFrameTuple.getFieldStart(cmp.getKeyFieldCount()),
-//                                cmpFrameTuple.getFieldLength(cmp.getKeyFieldCount()));
-//                        if (c != 0) {
-//                            double intersection = overlappedArea(frameTuple, tuple, cmpFrameTuple, cmp);
-//                            if (intersection != 0.0) {
-//                                difference += intersection - overlappedArea(frameTuple, null, cmpFrameTuple, cmp);
-//                            }
-//                        } else {
-//                            id = j;
-//                        }
-//                    }
-//
-//                    double enlargedArea = enlargedArea(cmpFrameTuple, tuple, cmp);
-//                    if (difference < minOverlap) {
-//                        minOverlap = difference;
-//                        minEnlargedArea = enlargedArea;
-//                        bestChild = id;
-//                    } else if (difference == minOverlap) {
-//                        if (enlargedArea < minEnlargedArea) {
-//                            minEnlargedArea = enlargedArea;
-//                            bestChild = id;
-//                        } else if (enlargedArea == minEnlargedArea) {
-//                            double area = area(cmpFrameTuple, cmp);
-//                            frameTuple.resetByTupleIndex(this, bestChild);
-//                            double minArea = area(frameTuple, cmp);
-//                            if (area < minArea) {
-//                                bestChild = id;
-//                            }
-//                        }
-//                    }
-//                }
-//            }
-//        } else { // find minimum enlarged area, use minimum area to break tie
-//            for (int i = 0; i < getTupleCount(); i++) {
-//                frameTuple.resetByTupleIndex(this, i);
-//                double enlargedArea = enlargedArea(frameTuple, tuple, cmp);
-//                if (enlargedArea < minEnlargedArea) {
-//                    minEnlargedArea = enlargedArea;
-//                    bestChild = i;
-//                } else if (enlargedArea == minEnlargedArea) {
-//                    double area = area(frameTuple, cmp);
-//                    frameTuple.resetByTupleIndex(this, bestChild);
-//                    double minArea = area(frameTuple, cmp);
-//                    if (area < minArea) {
-//                        bestChild = i;
-//                    }
-//                }
-//            }
-//        }
-//        frameTuple.resetByTupleIndex(this, bestChild);
-//        nodesMBRs[(int) getLevel() - 1].resetByTupleIndex(this, bestChild);
-//
-//        entries.clear();
-//
-//        // return the page id of the bestChild tuple
-//        return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
-//    }
+
+    // @Override
+    // public int getChildPageId(ITupleReference tuple, TupleEntryArrayList
+    // entries, ITreeIndexTupleReference[] nodesMBRs,
+    // MultiComparator cmp) {
+    //
+    // cmpFrameTuple.setFieldCount(cmp.getFieldCount());
+    // frameTuple.setFieldCount(cmp.getFieldCount());
+    //
+    // int bestChild = 0;
+    // double minEnlargedArea = Double.MAX_VALUE;
+    //
+    // // the children pointers in the node point to leaves
+    // if (getLevel() == 1) {
+    // // find least overlap enlargement, use minimum enlarged area to
+    // // break tie, if tie still exists use minimum area to break it
+    // for (int i = 0; i < getTupleCount(); ++i) {
+    // frameTuple.resetByTupleIndex(this, i);
+    // double enlargedArea = enlargedArea(frameTuple, tuple, cmp);
+    // entries.add(i, enlargedArea);
+    // if (enlargedArea < minEnlargedArea) {
+    // minEnlargedArea = enlargedArea;
+    // bestChild = i;
+    // }
+    // }
+    // if (minEnlargedArea < entries.getDoubleEpsilon() || minEnlargedArea >
+    // entries.getDoubleEpsilon()) {
+    // minEnlargedArea = Double.MAX_VALUE;
+    // int k;
+    // if (getTupleCount() > nearMinimumOverlapFactor) {
+    // // sort the entries based on their area enlargement needed
+    // // to include the object
+    // entries.sort(EntriesOrder.ASCENDING, getTupleCount());
+    // k = nearMinimumOverlapFactor;
+    // } else {
+    // k = getTupleCount();
+    // }
+    //
+    // double minOverlap = Double.MAX_VALUE;
+    // int id = 0;
+    // for (int i = 0; i < k; ++i) {
+    // double difference = 0.0;
+    // for (int j = 0; j < getTupleCount(); ++j) {
+    // frameTuple.resetByTupleIndex(this, j);
+    // cmpFrameTuple.resetByTupleIndex(this, entries.get(i).getTupleIndex());
+    //
+    // int c =
+    // cmp.getIntCmp().compare(frameTuple.getFieldData(cmp.getKeyFieldCount()),
+    // frameTuple.getFieldStart(cmp.getKeyFieldCount()),
+    // frameTuple.getFieldLength(cmp.getKeyFieldCount()),
+    // cmpFrameTuple.getFieldData(cmp.getKeyFieldCount()),
+    // cmpFrameTuple.getFieldStart(cmp.getKeyFieldCount()),
+    // cmpFrameTuple.getFieldLength(cmp.getKeyFieldCount()));
+    // if (c != 0) {
+    // double intersection = overlappedArea(frameTuple, tuple, cmpFrameTuple,
+    // cmp);
+    // if (intersection != 0.0) {
+    // difference += intersection - overlappedArea(frameTuple, null,
+    // cmpFrameTuple, cmp);
+    // }
+    // } else {
+    // id = j;
+    // }
+    // }
+    //
+    // double enlargedArea = enlargedArea(cmpFrameTuple, tuple, cmp);
+    // if (difference < minOverlap) {
+    // minOverlap = difference;
+    // minEnlargedArea = enlargedArea;
+    // bestChild = id;
+    // } else if (difference == minOverlap) {
+    // if (enlargedArea < minEnlargedArea) {
+    // minEnlargedArea = enlargedArea;
+    // bestChild = id;
+    // } else if (enlargedArea == minEnlargedArea) {
+    // double area = area(cmpFrameTuple, cmp);
+    // frameTuple.resetByTupleIndex(this, bestChild);
+    // double minArea = area(frameTuple, cmp);
+    // if (area < minArea) {
+    // bestChild = id;
+    // }
+    // }
+    // }
+    // }
+    // }
+    // } else { // find minimum enlarged area, use minimum area to break tie
+    // for (int i = 0; i < getTupleCount(); i++) {
+    // frameTuple.resetByTupleIndex(this, i);
+    // double enlargedArea = enlargedArea(frameTuple, tuple, cmp);
+    // if (enlargedArea < minEnlargedArea) {
+    // minEnlargedArea = enlargedArea;
+    // bestChild = i;
+    // } else if (enlargedArea == minEnlargedArea) {
+    // double area = area(frameTuple, cmp);
+    // frameTuple.resetByTupleIndex(this, bestChild);
+    // double minArea = area(frameTuple, cmp);
+    // if (area < minArea) {
+    // bestChild = i;
+    // }
+    // }
+    // }
+    // }
+    // frameTuple.resetByTupleIndex(this, bestChild);
+    // nodesMBRs[(int) getLevel() - 1].resetByTupleIndex(this, bestChild);
+    //
+    // entries.clear();
+    //
+    // // return the page id of the bestChild tuple
+    // return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
+    // }
 
     @Override
     public void reinsert(ITupleReference tuple, ITreeIndexTupleReference nodeMBR, TupleEntryArrayList entries,
@@ -737,7 +735,7 @@
         entries.clear();
     }
 
-    public double area(ITupleReference tuple, MultiComparator cmp) {
+    private double area(ITupleReference tuple, MultiComparator cmp) {
         double area = 1.0;
         int maxFieldPos = cmp.getKeyFieldCount() / 2;
         for (int i = 0; i < maxFieldPos; i++) {
@@ -748,7 +746,7 @@
         return area;
     }
 
-    public double overlappedArea(ITupleReference tuple1, ITupleReference tupleToBeInserted, ITupleReference tuple2,
+    private double overlappedArea(ITupleReference tuple1, ITupleReference tupleToBeInserted, ITupleReference tuple2,
             MultiComparator cmp) {
         double area = 1.0;
         double f1, f2;
@@ -796,7 +794,7 @@
         return area;
     }
 
-    public double enlargedArea(ITupleReference tuple, ITupleReference tupleToBeInserted, MultiComparator cmp) {
+    private double enlargedArea(ITupleReference tuple, ITupleReference tupleToBeInserted, MultiComparator cmp) {
         double areaBeforeEnlarge = area(tuple, cmp);
         double areaAfterEnlarge = 1.0;
 
@@ -837,15 +835,15 @@
                     frameTuple.getFieldLength(i), tuple.getFieldData(i), tuple.getFieldStart(i),
                     tuple.getFieldLength(i));
             if (c > 0) {
-                System.arraycopy(tuple.getFieldData(i), tuple.getFieldStart(i),
-                        frameTuple.getFieldData(i), frameTuple.getFieldStart(i), tuple.getFieldLength(i));
+                System.arraycopy(tuple.getFieldData(i), tuple.getFieldStart(i), frameTuple.getFieldData(i),
+                        frameTuple.getFieldStart(i), tuple.getFieldLength(i));
             }
-            c = cmp.getComparators()[j].compare(frameTuple.getFieldData(j), frameTuple.getFieldStart(j), frameTuple.getFieldLength(j),
-                    tuple.getFieldData(j), tuple.getFieldStart(j),
+            c = cmp.getComparators()[j].compare(frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
+                    frameTuple.getFieldLength(j), tuple.getFieldData(j), tuple.getFieldStart(j),
                     tuple.getFieldLength(j));
             if (c < 0) {
-                System.arraycopy(tuple.getFieldData(j), tuple.getFieldStart(j),
-                        frameTuple.getFieldData(j), frameTuple.getFieldStart(j), tuple.getFieldLength(j));
+                System.arraycopy(tuple.getFieldData(j), tuple.getFieldStart(j), frameTuple.getFieldData(j),
+                        frameTuple.getFieldStart(j), tuple.getFieldLength(j));
             }
         }
     }
@@ -858,11 +856,41 @@
             tupleWriter.writeTuple(tuple, buf, getTupleOffset(tupleIndex));
         }
     }
-    
+
     @Override
     public int findTuple(ITupleReference tuple, MultiComparator cmp) {
         frameTuple.setFieldCount(cmp.getFieldCount());
-        return slotManager.findTupleIndex(tuple, frameTuple, cmp, null, null);
+        for (int i = 0; i < getTupleCount(); i++) {
+            frameTuple.resetByTupleIndex(this, i);
+            int c = cmp.getIntCmp().compare(frameTuple.getFieldData(cmp.getKeyFieldCount()),
+                    frameTuple.getFieldStart(cmp.getKeyFieldCount()),
+                    frameTuple.getFieldLength(cmp.getKeyFieldCount()), tuple.getFieldData(cmp.getKeyFieldCount()),
+                    tuple.getFieldStart(cmp.getKeyFieldCount()), tuple.getFieldLength(cmp.getKeyFieldCount()));
+            if (c == 0) {
+                return i;
+            }
+        }
+        return -1;
+    }
+
+    @Override
+    public int findTuple(ITupleReference tuple, FindPathList findPathList, int parentIndex, MultiComparator cmp) {
+        frameTuple.setFieldCount(cmp.getFieldCount());
+        for (int i = 0; i < getTupleCount(); i++) {
+            frameTuple.resetByTupleIndex(this, i);
+            int c = cmp.getIntCmp().compare(frameTuple.getFieldData(cmp.getKeyFieldCount()),
+                    frameTuple.getFieldStart(cmp.getKeyFieldCount()),
+                    frameTuple.getFieldLength(cmp.getKeyFieldCount()), tuple.getFieldData(cmp.getKeyFieldCount()),
+                    tuple.getFieldStart(cmp.getKeyFieldCount()), tuple.getFieldLength(cmp.getKeyFieldCount()));
+            if (c == 0) {
+                return i;
+            } else {
+                int pageId = IntegerSerializerDeserializer.getInt(frameTuple.getFieldData(cmp.getKeyFieldCount()),
+                        frameTuple.getFieldStart(cmp.getKeyFieldCount()));
+                findPathList.add(pageId, parentIndex);
+            }
+        }
+        return -1;
     }
 
     @Override
@@ -916,27 +944,6 @@
         return buf.getInt(frameTuple.getFieldStart(cmp.getKeyFieldCount()));
     }
 
-    public boolean contains(ITupleReference tuple, MultiComparator cmp) {
-        frameTuple.setFieldCount(cmp.getFieldCount());
-        int maxFieldPos = cmp.getKeyFieldCount() / 2;
-        for (int i = 0; i < maxFieldPos; i++) {
-            int j = maxFieldPos + i;
-            int c = cmp.getComparators()[i].compare(tuple.getFieldData(i), tuple.getFieldStart(i),
-                    tuple.getFieldLength(i), frameTuple.getFieldData(j), frameTuple.getFieldStart(j),
-                    frameTuple.getFieldLength(j));
-            if (c > 0) {
-                return false;
-            }
-            c = cmp.getComparators()[i].compare(tuple.getFieldData(j), tuple.getFieldStart(j), tuple.getFieldLength(j),
-                    frameTuple.getFieldData(i), frameTuple.getFieldStart(i), frameTuple.getFieldLength(i));
-
-            if (c < 0) {
-                return false;
-            }
-        }
-        return true;
-    }
-    
     @Override
     public Rectangle intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp) {
         frameTuple.setFieldCount(cmp.getFieldCount());
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/FindPathList.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/FindPathList.java
new file mode 100644
index 0000000..2522e17
--- /dev/null
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/FindPathList.java
@@ -0,0 +1,103 @@
+/*
+ * 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.impls;
+
+public class FindPathList {
+    private int[] pageIds;
+    private int[] pageLsns;
+    private int[] parentIndexes;
+    private int size;
+    private final int growth;
+    private int first;
+
+    public FindPathList(int initialCapacity, int growth) {
+        pageIds = new int[initialCapacity];
+        pageLsns = new int[initialCapacity];
+        parentIndexes = new int[initialCapacity];
+        size = 0;
+        this.growth = growth;
+        first = 0;
+    }
+
+    public int size() {
+        return size;
+    }
+
+    public void add(int pageId, int parentId) {
+        if (size == pageIds.length) {
+            int[] newPageIds = new int[pageIds.length + growth];
+            System.arraycopy(pageIds, 0, newPageIds, 0, pageIds.length);
+            pageIds = newPageIds;
+
+            int[] newPageLsns = new int[pageLsns.length + growth];
+            System.arraycopy(pageLsns, 0, newPageLsns, 0, pageLsns.length);
+            pageLsns = newPageLsns;
+            
+            int[] newParentIds = new int[parentIndexes.length + growth];
+            System.arraycopy(parentIndexes, 0, newParentIds, 0, parentIndexes.length);
+            parentIndexes = newParentIds;
+        }
+
+        pageIds[size] = pageId;
+        parentIndexes[size] = parentId;
+        size++;
+    }
+
+    public void moveFirst() {
+        first++;
+    }
+
+    public int getFirstPageId() {
+        return pageIds[first];
+    }
+    
+    public int getFirstPageLsn() {
+        return pageLsns[first];
+    }
+
+    public int getFirstParentIndex() {
+        return parentIndexes[first];
+    }
+
+    public int getPageId(int i) {
+        return pageIds[i];
+    }
+    
+    public int getPageLsn(int i) {
+        return pageLsns[i];
+    }
+    
+    public void setPageLsn(int i, int pageLsn) {
+        pageLsns[i] = pageLsn;
+    }
+
+    public int getParentIndex(int i) {
+        return parentIndexes[i];
+    }
+    
+    public boolean isLast() {
+        return size == first;
+    }
+
+    public void clear() {
+        size = 0;
+        first = 0;
+    }
+
+    public boolean isEmpty() {
+        return size == 0;
+    }
+}
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
index 6554bb4..534ca50 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
@@ -400,7 +400,7 @@
                 writeLatchesAcquired++;
                 ctx.interiorFrame.setPage(parentNode);
             }
-        }
+        } 
         if (foundParent) {
             ctx.interiorFrame.adjustKey(ctx.splitKey.getLeftTuple(), interiorCmp);
             insertTuple(parentNode, parentId, ctx.splitKey.getRightTuple(), ctx, ctx.interiorFrame.isLeaf());
@@ -411,71 +411,68 @@
             writeLatchesReleased++;
             bufferCache.unpin(parentNode);
             unpins++;
+            return;
         }
 
-        // // very rare situation when the there is a root split, search for the
-        // parent tuple
-        // ctx.path.clear();
-        // ctx.pageLsns.clear();
-        // findPath(ctx, isLeaf);
+        // very rare situation when the there is a root split, do an exhaustive
+        // breadth-first traversal looking for the parent tuple
 
-        // newstack = findPath( item->parent )
-        // replace part of stack to new one
-        // latch( parent->page, X-mode )
-        // findParent( item );
-
+        ctx.path.clear();
+        ctx.pageLsns.clear();
+        ctx.findPathList.clear();
+        findPath(ctx);
+        updateParent(ctx);
     }
 
-    // public void findPath(RTreeOpContext ctx, boolean isLeaf) throws Exception
-    // {
-    // int pageId = rootPage;
-    // int parentLsn = 0;
-    // ctx.path.add(pageId);
-    // ctx.pageLsns.add(parentLsn);
-    //
-    // while (!ctx.path.isEmpty()) {
-    // pageId = ctx.path.getLast();
-    // parentLsn = ctx.pageLsns.getLast();
-    // ICachedPage node =
-    // bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
-    // pins++;
-    // node.acquireReadLatch();
-    // readLatchesAcquired++;
-    // ctx.interiorFrame.setPage(node);
-    //
-    // if (pageId != rootPage && parentLsn < ctx.interiorFrame.getPageNsn()) {
-    // ctx.path.add(ctx.interiorFrame.getRightPage());
-    // ctx.pageLsns.add(0);
-    // }
-    //
-    //
-    // }
-    //
-    // push stack, [root, 0, 0] // page, LSN, parent
-    // while( stack )
-    // ptr = top of stack
-    // latch( ptr->page, S-mode )
-    // if ( ptr->parent->page->lsn < ptr->page->nsn )
-    // push stack, [ ptr->page->rightlink, 0, ptr->parent ]
-    // end
-    // for( each tuple on page )
-    // if ( tuple->pagepointer == item->page )
-    // return stack
-    // else
-    // add to stack at the end [tuple->pagepointer,0, ptr]
-    // end
-    // end
-    // unlatch( ptr->page )
-    // pop stack
-    // end
-    //
-    //
-    //
-    //
-    //
-    //
-    // }
+    public void findPath(RTreeOpContext ctx) throws Exception {
+        int pageId = rootPage;
+        int parentIndex = -1;
+        int parentLsn = 0;
+        int pageLsn, pageIndex;
+        ctx.findPathList.add(pageId, parentIndex);
 
+        while (!ctx.findPathList.isLast()) {
+            pageId = ctx.findPathList.getFirstPageId();
+            parentIndex = ctx.findPathList.getFirstParentIndex();
+            ctx.findPathList.moveFirst();
+            ICachedPage node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
+            pins++;
+            node.acquireReadLatch();
+            readLatchesAcquired++;
+            ctx.interiorFrame.setPage(node);
+            pageLsn = ctx.interiorFrame.getPageLsn();
+            pageIndex = ctx.findPathList.size() - 1;
+            ctx.findPathList.setPageLsn(pageIndex, pageLsn);
+
+            if (pageId != rootPage && parentLsn < ctx.interiorFrame.getPageNsn()) {
+                ctx.findPathList.add(ctx.interiorFrame.getRightPage(), parentIndex);
+            }
+            parentLsn = pageLsn;
+            
+            if (ctx.interiorFrame.findTuple(ctx.splitKey.getLeftTuple(), ctx.findPathList, pageIndex, interiorCmp) != -1) {
+                fillPath(ctx, pageIndex);
+
+                node.releaseReadLatch();
+                readLatchesReleased++;
+                bufferCache.unpin(node);
+                unpins++;
+                return;
+            }
+            node.releaseReadLatch();
+            readLatchesReleased++;
+            bufferCache.unpin(node);
+            unpins++;
+        } 
+    }
+
+    public void fillPath(RTreeOpContext ctx, int pageIndex) throws Exception {
+        if (pageIndex != -1) {
+            fillPath(ctx, ctx.findPathList.getParentIndex(pageIndex));
+            ctx.path.add(ctx.findPathList.getPageId(pageIndex));
+            ctx.pageLsns.add(ctx.findPathList.getPageLsn(pageIndex));
+        }
+    }
+    
     public ICachedPage findLeaf(RTreeOpContext ctx) throws Exception {
         int pageId = rootPage;
         boolean writeLatched = false;
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
index f321efc..6a07c93 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
@@ -20,6 +20,7 @@
     public ITreeIndexTupleReference[] nodesMBRs;
     public final IntArrayList path;
     public final IntArrayList pageLsns;
+    public final FindPathList findPathList; // works as a queue
     public Rectangle[] rec;
 
     public RTreeOpContext(TreeIndexOp op, IRTreeFrame interiorFrame, IRTreeFrame leafFrame,
@@ -38,6 +39,7 @@
         nodesMBRs = new ITreeIndexTupleReference[treeHeightHint];
         path = new IntArrayList(treeHeightHint, treeHeightHint);
         pageLsns = new IntArrayList(treeHeightHint, treeHeightHint);
+        findPathList = new FindPathList(100, 100);
         for (int i = 0; i < treeHeightHint; i++) {
             nodesMBRs[i] = interiorFrame.getTupleWriter().createTupleReference();
             nodesMBRs[i].setFieldCount(nodesMBRs[i].getFieldCount());
@@ -72,5 +74,8 @@
         if (pageLsns != null) {
             pageLsns.clear();
         }
+        if (findPathList != null) {
+            pageLsns.clear();
+        }
     }
 }
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java
index d65aff1..77bddd7 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/UnorderedSlotManager.java
@@ -12,18 +12,6 @@
     @Override
     public int findTupleIndex(ITupleReference searchKey, ITreeIndexTupleReference frameTuple, MultiComparator multiCmp,
             FindTupleMode mode, FindTupleNoExactMatchPolicy matchPolicy) {
-        for (int i = 0; i < frame.getTupleCount(); i++) {
-            frameTuple.resetByTupleIndex(frame, i);
-            int cmp = multiCmp.getIntCmp().compare(frameTuple.getFieldData(multiCmp.getKeyFieldCount()),
-                    frameTuple.getFieldStart(multiCmp.getKeyFieldCount()),
-                    frameTuple.getFieldLength(multiCmp.getKeyFieldCount()),
-                    searchKey.getFieldData(multiCmp.getKeyFieldCount()),
-                    searchKey.getFieldStart(multiCmp.getKeyFieldCount()),
-                    searchKey.getFieldLength(multiCmp.getKeyFieldCount()));
-            if (cmp == 0) {
-                return i;
-            }
-        }
         return -1;
     }