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 10aba54..a0350bf 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
@@ -22,7 +22,7 @@
 
 public interface IRTreeFrame extends ITreeIndexFrame {
 
-	public void computeMBR(ISplitKey splitKey, MultiComparator cmp);
+	public void computeMBR(ISplitKey splitKey);
 
 	public void delete(int tupleIndex, MultiComparator cmp);
 
@@ -34,6 +34,6 @@
 
 	public void setRightPage(int rightPage);
 
-	public void adjustMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp);
+	public void adjustMBR(ITreeIndexTupleReference[] tuples);
 
 }
\ No newline at end of file
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java
index bc47e20..1129fd6 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMFrame.java
@@ -144,8 +144,7 @@
 	}
 
 	public void generateDist(ITupleReference tuple,
-			TupleEntryArrayList entries, Rectangle rec, int start, int end,
-			MultiComparator cmp) {
+			TupleEntryArrayList entries, Rectangle rec, int start, int end) {
 		int j = 0;
 		while (entries.get(j).getTupleIndex() == -1) {
 			j++;
@@ -170,28 +169,20 @@
 		return tupleWriter.createTupleReference();
 	}
 
-	public void adjustMBRImpl(ITreeIndexTupleReference[] tuples,
-			MultiComparator cmp) {
-		int maxFieldPos = cmp.getKeyFieldCount() / 2;
+	public void adjustMBRImpl(ITreeIndexTupleReference[] tuples) {
+		int maxFieldPos = keyValueProviders.length / 2;
 		for (int i = 1; i < getTupleCount(); i++) {
 			frameTuple.resetByTupleIndex(this, i);
 			for (int j = 0; j < maxFieldPos; j++) {
 				int k = maxFieldPos + j;
-				int c = cmp.getComparators()[j].compare(
-						frameTuple.getFieldData(j),
-						frameTuple.getFieldStart(j),
-						frameTuple.getFieldLength(j),
-						tuples[j].getFieldData(j), tuples[j].getFieldStart(j),
-						tuples[j].getFieldLength(j));
-				if (c < 0) {
+				double valA = keyValueProviders[j].getValue(frameTuple.getFieldData(j), frameTuple.getFieldStart(j));
+				double valB = keyValueProviders[j].getValue(tuples[j].getFieldData(j), tuples[j].getFieldStart(j));
+				if (valA < valB) {
 					tuples[j].resetByTupleIndex(this, i);
 				}
-				c = cmp.getComparators()[k].compare(frameTuple.getFieldData(k),
-						frameTuple.getFieldStart(k),
-						frameTuple.getFieldLength(k),
-						tuples[k].getFieldData(k), tuples[k].getFieldStart(k),
-						tuples[k].getFieldLength(k));
-				if (c > 0) {
+				valA = keyValueProviders[k].getValue(frameTuple.getFieldData(k), frameTuple.getFieldStart(k));
+				valB = keyValueProviders[k].getValue(tuples[k].getFieldData(k), tuples[k].getFieldStart(k));
+				if (valA > valB) {
 					tuples[k].resetByTupleIndex(this, i);
 				}
 			}
@@ -199,17 +190,17 @@
 	}
 
 	@Override
-	public void computeMBR(ISplitKey splitKey, MultiComparator cmp) {
+	public void computeMBR(ISplitKey splitKey) {
 		RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
 		RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
 
 		int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
 		frameTuple.resetByTupleOffset(buf, tupleOff);
 		int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0,
-				cmp.getKeyFieldCount());
+				keyValueProviders.length);
 
 		splitKey.initData(splitKeySize);
-		this.adjustMBR(tuples, cmp);
+		this.adjustMBR(tuples);
 		rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0,
 				rTreeSplitKey.getLeftPageBuffer(), 0);
 		rTreeSplitKey.getLeftTuple().resetByTupleOffset(
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMInteriorFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMInteriorFrame.java
index f7c234e..6f125e0 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMInteriorFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMInteriorFrame.java
@@ -300,7 +300,7 @@
     }
     
     @Override
-    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey) throws TreeIndexException {
+    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) throws TreeIndexException {
         RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
         RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
         RTreeTypeAwareTupleWriter rTreeTupleWriterRightFrame = ((RTreeTypeAwareTupleWriter) rightFrame.getTupleWriter());
@@ -313,7 +313,7 @@
         double minMargin = Double.MAX_VALUE;
         int splitAxis = 0, sortOrder = 0;
 
-        int maxFieldPos = cmp.getKeyFieldCount() / 2;
+        int maxFieldPos = keyValueProviders.length / 2;
         for (int i = 0; i < maxFieldPos; i++) {
             int j = maxFieldPos + i;
             for (int k = 0; k < getTupleCount(); ++k) {
@@ -341,10 +341,10 @@
             for (int k = 1; k <= splitDistribution; ++k) {
                 int d = m - 1 + k;
 
-                generateDist(tuple, tupleEntries1, rec[0], 0, d, cmp);
-                generateDist(tuple, tupleEntries2, rec[1], 0, d, cmp);
-                generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1, cmp);
-                generateDist(tuple, tupleEntries2, rec[3], d, getTupleCount() + 1, cmp);
+                generateDist(tuple, tupleEntries1, rec[0], 0, d);
+                generateDist(tuple, tupleEntries2, rec[1], 0, d);
+                generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1);
+                generateDist(tuple, tupleEntries2, rec[3], d, getTupleCount() + 1);
 
                 // calculate the margin of the distributions
                 lowerMargin += rec[0].margin() + rec[2].margin();
@@ -380,8 +380,8 @@
         for (int i = 1; i <= splitDistribution; ++i) {
             int d = m - 1 + i;
 
-            generateDist(tuple, tupleEntries1, rec[0], 0, d, cmp);
-            generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1, cmp);
+            generateDist(tuple, tupleEntries1, rec[0], 0, d);
+            generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1);
 
             double overlap = rec[0].overlappedArea(rec[2]);
             if (overlap < minOverlap) {
@@ -436,14 +436,14 @@
 
         int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
         frameTuple.resetByTupleOffset(buf, tupleOff);
-        int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
+        int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, keyValueProviders.length);
 
         splitKey.initData(splitKeySize);
-        this.adjustMBR(tuples, cmp);
+        this.adjustMBR(tuples);
         rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0, rTreeSplitKey.getLeftPageBuffer(), 0);
         rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(), 0);
 
-        ((IRTreeFrame) rightFrame).adjustMBR(((RTreeNSMFrame) rightFrame).getTuples(), cmp);
+        ((IRTreeFrame) rightFrame).adjustMBR(((RTreeNSMFrame) rightFrame).getTuples());
         rTreeTupleWriterRightFrame.writeTupleFields(((RTreeNSMFrame) rightFrame).getTuples(), 0,
                 rTreeSplitKey.getRightPageBuffer(), 0);
         rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(), 0);
@@ -632,12 +632,12 @@
     }
 
     @Override
-    public void adjustMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp) {
+    public void adjustMBR(ITreeIndexTupleReference[] tuples) {
         for (int i = 0; i < tuples.length; i++) {
-            tuples[i].setFieldCount(cmp.getKeyFieldCount());
+            tuples[i].setFieldCount(keyValueProviders.length);
             tuples[i].resetByTupleIndex(this, 0);
         }
 
-        adjustMBRImpl(tuples, cmp);
+        adjustMBRImpl(tuples);
     }
 }
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMLeafFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMLeafFrame.java
index 722cec4..ebd3818 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMLeafFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMLeafFrame.java
@@ -64,7 +64,7 @@
     }
 
     @Override
-    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, MultiComparator cmp, ISplitKey splitKey) throws TreeIndexException {
+    public int split(ITreeIndexFrame rightFrame, ITupleReference tuple, ISplitKey splitKey) throws TreeIndexException {
 
         RTreeSplitKey rTreeSplitKey = ((RTreeSplitKey) splitKey);
         RTreeTypeAwareTupleWriter rTreeTupleWriterLeftFrame = ((RTreeTypeAwareTupleWriter) tupleWriter);
@@ -78,7 +78,7 @@
         double minMargin = Double.MAX_VALUE;
         int splitAxis = 0, sortOrder = 0;
 
-        int maxFieldPos = cmp.getKeyFieldCount() / 2;
+        int maxFieldPos = keyValueProviders.length / 2;
         for (int i = 0; i < maxFieldPos; i++) {
             int j = maxFieldPos + i;
             for (int k = 0; k < getTupleCount(); ++k) {
@@ -107,10 +107,10 @@
             for (int k = 1; k <= splitDistribution; ++k) {
                 int d = m - 1 + k;
 
-                generateDist(tuple, tupleEntries1, rec[0], 0, d, cmp);
-                generateDist(tuple, tupleEntries2, rec[1], 0, d, cmp);
-                generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1, cmp);
-                generateDist(tuple, tupleEntries2, rec[3], d, getTupleCount() + 1, cmp);
+                generateDist(tuple, tupleEntries1, rec[0], 0, d);
+                generateDist(tuple, tupleEntries2, rec[1], 0, d);
+                generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1);
+                generateDist(tuple, tupleEntries2, rec[3], d, getTupleCount() + 1);
 
                 // calculate the margin of the distributions
                 lowerMargin += rec[0].margin() + rec[2].margin();
@@ -146,8 +146,8 @@
         for (int i = 1; i <= splitDistribution; ++i) {
             int d = m - 1 + i;
 
-            generateDist(tuple, tupleEntries1, rec[0], 0, d, cmp);
-            generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1, cmp);
+            generateDist(tuple, tupleEntries1, rec[0], 0, d);
+            generateDist(tuple, tupleEntries1, rec[2], d, getTupleCount() + 1);
 
             double overlap = rec[0].overlappedArea(rec[2]);
             if (overlap < minOverlap) {
@@ -202,14 +202,14 @@
 
         int tupleOff = slotManager.getTupleOff(slotManager.getSlotEndOff());
         frameTuple.resetByTupleOffset(buf, tupleOff);
-        int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, cmp.getKeyFieldCount());
+        int splitKeySize = tupleWriter.bytesRequired(frameTuple, 0, keyValueProviders.length);
 
         splitKey.initData(splitKeySize);
-        this.adjustMBR(tuples, cmp);
+        this.adjustMBR(tuples);
         rTreeTupleWriterLeftFrame.writeTupleFields(tuples, 0, rTreeSplitKey.getLeftPageBuffer(), 0);
         rTreeSplitKey.getLeftTuple().resetByTupleOffset(rTreeSplitKey.getLeftPageBuffer(), 0);
 
-        ((IRTreeFrame) rightFrame).adjustMBR(((RTreeNSMFrame) rightFrame).getTuples(), cmp);
+        ((IRTreeFrame) rightFrame).adjustMBR(((RTreeNSMFrame) rightFrame).getTuples());
         rTreeTupleWriterRightFrame.writeTupleFields(((RTreeNSMFrame) rightFrame).getTuples(), 0,
                 rTreeSplitKey.getRightPageBuffer(), 0);
         rTreeSplitKey.getRightTuple().resetByTupleOffset(rTreeSplitKey.getRightPageBuffer(), 0);
@@ -248,11 +248,10 @@
     }
 
     @Override
-    public void adjustMBR(ITreeIndexTupleReference[] tuples, MultiComparator cmp) {
+    public void adjustMBR(ITreeIndexTupleReference[] tuples) {
         for (int i = 0; i < tuples.length; i++) {
             tuples[i].resetByTupleIndex(this, 0);
         }
-
-        adjustMBRImpl(tuples, cmp);
+        adjustMBRImpl(tuples);
     }
 }
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 b673d47..cccd326 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
@@ -454,7 +454,7 @@
                         rightFrame.setPage(rightNode);
                         rightFrame.initBuffer((byte) ctx.interiorFrame.getLevel());
                         //rightFrame.setPageTupleFieldCount(cmp.getKeyFieldCount());
-                        ret = ctx.interiorFrame.split(rightFrame, tuple, cmp, ctx.splitKey);
+                        ret = ctx.interiorFrame.split(rightFrame, tuple, ctx.splitKey);
                         ctx.interiorFrame.setRightPage(rightPageId);
                         rightFrame.setPageNsn(ctx.interiorFrame.getPageNsn());
                         incrementGlobalNsn();
@@ -467,7 +467,7 @@
                         rightFrame = (IRTreeFrame) leafFrameFactory.createFrame();
                         rightFrame.setPage(rightNode);
                         rightFrame.initBuffer((byte) 0);
-                        ret = ctx.leafFrame.split(rightFrame, tuple, cmp, ctx.splitKey);
+                        ret = ctx.leafFrame.split(rightFrame, tuple, ctx.splitKey);
                         ctx.leafFrame.setRightPage(rightPageId);
                         rightFrame.setPageNsn(ctx.leafFrame.getPageNsn());
                         incrementGlobalNsn();
@@ -720,7 +720,7 @@
 
                 ctx.splitKey.reset();
                 if (!ctx.pathList.isEmpty()) {
-                    ctx.interiorFrame.computeMBR(ctx.splitKey, cmp);
+                    ctx.interiorFrame.computeMBR(ctx.splitKey);
                     ctx.splitKey.setLeftPage(parentId);
                 }
             } else {
@@ -837,7 +837,7 @@
 
         // if the page is empty, just leave it there for future inserts
         if (pageId != rootPage && ctx.leafFrame.getTupleCount() > 0) {
-            ctx.leafFrame.computeMBR(ctx.splitKey, cmp);
+            ctx.leafFrame.computeMBR(ctx.splitKey);
             ctx.splitKey.setLeftPage(pageId);
         }
     }
diff --git a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeFieldPrefixNSMTest.java b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeFieldPrefixNSMTest.java
index ea32d58..49403a1 100644
--- a/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeFieldPrefixNSMTest.java
+++ b/hyracks-tests/hyracks-storage-am-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/btree/BTreeFieldPrefixNSMTest.java
@@ -115,9 +115,10 @@
         try {
 
             ITreeIndexTupleWriter tupleWriter = new TypeAwareTupleWriter(typeTraits);
-            BTreeFieldPrefixNSMLeafFrame frame = new BTreeFieldPrefixNSMLeafFrame(tupleWriter);
+            BTreeFieldPrefixNSMLeafFrame frame = new BTreeFieldPrefixNSMLeafFrame(tupleWriter);            
             frame.setPage(page);
             frame.initBuffer((byte) 0);
+            frame.setMultiComparator(cmp);
             frame.setPrefixTupleCount(0);
 
             String before = new String();