diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/HashMultiSet.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/HashMultiSet.java
new file mode 100644
index 0000000..e4ccdcb
--- /dev/null
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/util/HashMultiSet.java
@@ -0,0 +1,113 @@
+/*
+ * 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.common.util;
+
+import java.util.AbstractCollection;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Quick and dirty implementation of a HashMultiSet backed by a HashMap.
+ * It only implements a minimal subset of the collection interface to make our tests work.
+ */
+public class HashMultiSet<E> extends AbstractCollection<E> {
+
+    private final Map<E, List<E>> map = new HashMap<E, List<E>>(); 
+    private int size = 0;
+    
+    @Override
+    public boolean add(E e) {
+        List<E> list = map.get(e);
+        if (list == null) {
+            list = new ArrayList<E>();
+            map.put(e, list);
+        }
+        list.add(e);
+        size++;
+        return true;
+    }
+    
+    @Override
+    public boolean contains(Object o) {
+        return map.containsKey(o);
+    }
+    
+    @Override
+    public boolean remove(Object o) {
+        List<E> list = map.get(o);
+        if (list == null) {
+            return false;            
+        }
+        list.remove(list.size() - 1);
+        if (list.isEmpty()) {
+            map.remove(o);
+        }
+        size--;
+        return true;
+    }
+    
+    @Override
+    public Iterator<E> iterator() {
+        return new HashMultiSetIterator();
+    }
+
+    @Override
+    public int size() {
+        return size;
+    }
+    
+    @Override
+    public void clear() {
+        map.clear();
+        size = 0;
+    }
+    
+    private class HashMultiSetIterator implements Iterator<E> {
+
+        private Iterator<Map.Entry<E, List<E>>> mapIter;
+        private Iterator<E> listIter;
+        
+        public HashMultiSetIterator() {
+            mapIter = map.entrySet().iterator();
+        }
+        
+        @Override
+        public boolean hasNext() {
+            if (mapIter.hasNext() || (listIter != null && listIter.hasNext())) {
+                return true;
+            }
+            return false;
+        }
+
+        @Override
+        public E next() {
+            if (listIter == null || (listIter != null && !listIter.hasNext())) {
+                Map.Entry<E, List<E>> entry = mapIter.next();
+                listIter = entry.getValue().iterator();
+                return listIter.next();
+            }
+            return listIter.next();
+        }
+
+        @Override
+        public void remove() {
+            throw new IllegalStateException("Not implemented");
+        }
+    }
+}
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexTestUtils.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexTestUtils.java
index a053dde..9909e2f 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexTestUtils.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/OrderedIndexTestUtils.java
@@ -43,8 +43,8 @@
                     actual.getFieldLength(i));
             DataInput dataIn = new DataInputStream(inStream);
             Object actualObj = fieldSerdes[i].deserialize(dataIn);
-            if (!actualObj.equals(expected.get(i))) {
-                fail("Actual and expected fields do not match on field " + i + ".\nExpected: " + expected.get(i)
+            if (!actualObj.equals(expected.getField(i))) {
+                fail("Actual and expected fields do not match on field " + i + ".\nExpected: " + expected.getField(i)
                         + "\nActual  : " + actualObj);
             }
         }
@@ -64,13 +64,13 @@
             boolean geLowKey = true;
             boolean leHighKey = true;
             for (int i = 0; i < lowKey.getNumKeys(); i++) {
-                if (t.get(i).compareTo(lowKey.get(i)) < 0) {
+                if (t.getField(i).compareTo(lowKey.getField(i)) < 0) {
                     geLowKey = false;
                     break;
                 }
             }
             for (int i = 0; i < highKey.getNumKeys(); i++) {
-                if (t.get(i).compareTo(highKey.get(i)) > 0) {
+                if (t.getField(i).compareTo(highKey.getField(i)) > 0) {
                     leHighKey = false;
                     break;
                 }
@@ -317,7 +317,7 @@
             // Update check tuple's non-key fields.
             for (int j = keyFieldCount; j < fieldCount; j++) {
                 Comparable newValue = getRandomUpdateValue(ctx.getFieldSerdes()[j], rnd);
-                checkTuple.set(j, newValue);
+                checkTuple.setField(j, newValue);
             }
 
             createTupleFromCheckTuple(checkTuple, updateTupleBuilder, updateTuple, ctx.getFieldSerdes());
@@ -334,7 +334,7 @@
     public CheckTuple createStringCheckTuple(String[] fieldValues, int numKeyFields) {
         CheckTuple<String> checkTuple = new CheckTuple<String>(fieldValues.length, numKeyFields);
         for (String s : fieldValues) {
-            checkTuple.add((String) s);
+            checkTuple.appendField((String) s);
         }
         return checkTuple;
     }
@@ -396,7 +396,7 @@
     protected CheckTuple createIntCheckTuple(int[] fieldValues, int numKeyFields) {
         CheckTuple<Integer> checkTuple = new CheckTuple<Integer>(fieldValues.length, numKeyFields);
         for (int v : fieldValues) {
-            checkTuple.add(v);
+            checkTuple.appendField(v);
         }
         return checkTuple;
     }
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/CheckTuple.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/CheckTuple.java
index 4b4b90b..9e31f71 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/CheckTuple.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/CheckTuple.java
@@ -17,42 +17,60 @@
 
 @SuppressWarnings({"rawtypes", "unchecked"})
 public class CheckTuple<T extends Comparable<T>> implements Comparable<T> {
-    protected final int numKeys;    
-    protected final Comparable[] tuple;
+    protected final int numKeys;
+    protected final Comparable[] fields;
     protected int pos;
 
     public CheckTuple(int numFields, int numKeys) {
         this.numKeys = numKeys;
-        this.tuple = new Comparable[numFields];
+        this.fields = new Comparable[numFields];
         pos = 0;
     }
 
-    public void add(T e) {
-        tuple[pos++] = e;
+    public void appendField(T e) {
+        fields[pos++] = e;
     }
 
-    @Override
-    public int compareTo(T o) {
-        CheckTuple<T> other = (CheckTuple<T>)o;
-        for (int i = 0; i < numKeys; i++) {            
-            int cmp = tuple[i].compareTo(other.get(i));
-            if (cmp != 0) {
-                return cmp;
-            }
-        }
-        return 0;
-    }
+	@Override
+	public int compareTo(T o) {
+		CheckTuple<T> other = (CheckTuple<T>) o;
+		for (int i = 0; i < numKeys; i++) {
+			int cmp = fields[i].compareTo(other.getField(i));
+			if (cmp != 0) {
+				return cmp;
+			}
+		}
+		return 0;
+	}
 
-    public T get(int idx) {
-        return (T)tuple[idx];
-    }
+	@Override
+	public boolean equals(Object o) {
+		if (!(o instanceof Comparable<?>)) {
+			return false;
+		}
+		return compareTo((T) o) == 0;
+	}
     
-    public void set(int idx, T e) {
-        tuple[idx] = e;
+	@Override
+	public int hashCode() {
+		//int hash = 37 * numKeys + fields.length;
+		int hash = 0;
+		for (int i = 0; i < numKeys; i++) {
+			hash = 37 * hash + fields[i].hashCode();
+		}
+		return hash;
+	}
+	
+	public T getField(int idx) {
+		return (T) fields[idx];
+	}
+    
+    public void setField(int idx, T e) {
+        fields[idx] = e;
     }
     
     public int size() {
-        return tuple.length;
+        return fields.length;
     }
     
     public int getNumKeys() {
@@ -62,9 +80,9 @@
     @Override
     public String toString() {
         StringBuilder strBuilder = new StringBuilder();
-        for (int i = 0; i < tuple.length; i++) {
-            strBuilder.append(tuple[i].toString());
-            if (i != tuple.length-1) {
+        for (int i = 0; i < fields.length; i++) {
+            strBuilder.append(fields[i].toString());
+            if (i != fields.length-1) {
                 strBuilder.append(" ");
             }
         }
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TreeIndexTestUtils.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TreeIndexTestUtils.java
index 000f7d0..6406a5e 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TreeIndexTestUtils.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TreeIndexTestUtils.java
@@ -33,9 +33,9 @@
 import edu.uci.ics.hyracks.dataflow.common.comm.io.ArrayTupleReference;
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.dataflow.common.util.TupleUtils;
+import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoader;
 import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
-import edu.uci.ics.hyracks.storage.am.common.api.IIndexBulkLoader;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
 import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
@@ -72,7 +72,7 @@
         DataOutput dos = tupleBuilder.getDataOutput();
         tupleBuilder.reset();
         for (int i = 0; i < fieldCount; i++) {
-            fieldSerdes[i].serialize(checkTuple.get(i), dos);
+            fieldSerdes[i].serialize(checkTuple.getField(i), dos);
             tupleBuilder.addFieldEndOffset();
         }
         tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
@@ -88,7 +88,7 @@
                     tuple.getFieldLength(i));
             DataInput dataIn = new DataInputStream(inStream);
             Comparable fieldObj = (Comparable) fieldSerdes[i].deserialize(dataIn);
-            checkTuple.add(fieldObj);
+            checkTuple.appendField(fieldObj);
         }
         return checkTuple;
     }
@@ -106,7 +106,7 @@
     }
 
     public void checkDiskOrderScan(ITreeIndexTestContext ctx) throws Exception {
-        try {
+    	try {
             if (LOGGER.isLoggable(Level.INFO)) {
                 LOGGER.info("Testing Disk-Order Scan.");
             }
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/config/AccessMethodTestsConfig.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/config/AccessMethodTestsConfig.java
index 994db2a..29cf35e 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/config/AccessMethodTestsConfig.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/config/AccessMethodTestsConfig.java
@@ -45,10 +45,10 @@
     public static final int RTREE_HYRACKS_FRAME_SIZE = 128;
 
     // Mem configuration for LSMRTree and LSMRTreeWithAntiMatterTuples.
-    public static final int LSM_RTREE_DISK_PAGE_SIZE = 256;
+    public static final int LSM_RTREE_DISK_PAGE_SIZE = 512;
     public static final int LSM_RTREE_DISK_NUM_PAGES = 1000;
     public static final int LSM_RTREE_DISK_MAX_OPEN_FILES = 2000;
-    public static final int LSM_RTREE_MEM_PAGE_SIZE = 256;
+    public static final int LSM_RTREE_MEM_PAGE_SIZE = 512;
     public static final int LSM_RTREE_MEM_NUM_PAGES = 1000;
     public static final int LSM_RTREE_HYRACKS_FRAME_SIZE = 128;
 
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeTestContext.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeTestContext.java
index 9affc47..32afdad 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeTestContext.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeTestContext.java
@@ -15,17 +15,17 @@
 
 package edu.uci.ics.hyracks.storage.am.rtree;
 
-import java.util.ArrayList;
 import java.util.Collection;
 
 import edu.uci.ics.hyracks.api.dataflow.value.ISerializerDeserializer;
 import edu.uci.ics.hyracks.storage.am.common.TreeIndexTestContext;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndex;
+import edu.uci.ics.hyracks.storage.am.common.util.HashMultiSet;
 
 @SuppressWarnings("rawtypes")
 public abstract class AbstractRTreeTestContext extends TreeIndexTestContext<RTreeCheckTuple> {
-    private final ArrayList<RTreeCheckTuple> checkTuples = new ArrayList<RTreeCheckTuple>();
-
+    private final HashMultiSet<RTreeCheckTuple> checkTuples = new HashMultiSet<RTreeCheckTuple>();
+	
     public AbstractRTreeTestContext(ISerializerDeserializer[] fieldSerdes, ITreeIndex treeIndex) {
         super(fieldSerdes, treeIndex);
     }
@@ -34,5 +34,4 @@
     public Collection<RTreeCheckTuple> getCheckTuples() {
         return checkTuples;
     }
-
 }
\ No newline at end of file
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeCheckTuple.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeCheckTuple.java
index 98800e5..c498136 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeCheckTuple.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeCheckTuple.java
@@ -27,8 +27,8 @@
     @Override
     public boolean equals(Object o) {
         RTreeCheckTuple<T> other = (RTreeCheckTuple<T>) o;
-        for (int i = 0; i < tuple.length; i++) {
-            int cmp = tuple[i].compareTo(other.get(i));
+        for (int i = 0; i < fields.length; i++) {
+            int cmp = fields[i].compareTo(other.getField(i));
             if (cmp != 0) {
                 return false;
             }
@@ -41,11 +41,11 @@
         int maxFieldPos = numKeys / 2;
         for (int i = 0; i < maxFieldPos; i++) {
             int j = maxFieldPos + i;
-            int cmp = tuple[i].compareTo(other.get(j));
+            int cmp = fields[i].compareTo(other.getField(j));
             if (cmp > 0) {
                 return false;
             }
-            cmp = tuple[j].compareTo(other.get(i));
+            cmp = fields[j].compareTo(other.getField(i));
             if (cmp < 0) {
                 return false;
             }
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTestUtils.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTestUtils.java
index a23f375..9f5e861 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTestUtils.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeTestUtils.java
@@ -21,6 +21,7 @@
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.util.HashMultiSet;
 import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchPredicate;
 import edu.uci.ics.hyracks.storage.am.rtree.util.RTreeUtils;
 
@@ -32,9 +33,9 @@
 
     @SuppressWarnings("unchecked")
     // Create a new ArrayList containing the elements satisfying the search key
-    public ArrayList<RTreeCheckTuple> getRangeSearchExpectedResults(ArrayList<RTreeCheckTuple> checkTuples,
+    public HashMultiSet<RTreeCheckTuple> getRangeSearchExpectedResults(Collection<RTreeCheckTuple> checkTuples,
             RTreeCheckTuple key) {
-        ArrayList<RTreeCheckTuple> expectedResult = new ArrayList<RTreeCheckTuple>();
+        HashMultiSet<RTreeCheckTuple> expectedResult = new HashMultiSet<RTreeCheckTuple>();
         Iterator<RTreeCheckTuple> iter = checkTuples.iterator();
         while (iter.hasNext()) {
             RTreeCheckTuple t = iter.next();
@@ -61,9 +62,9 @@
         RTreeCheckTuple keyCheck = (RTreeCheckTuple) createCheckTupleFromTuple(key, ctx.getFieldSerdes(),
                 cmp.getKeyFieldCount());
 
-        ArrayList<RTreeCheckTuple> expectedResult = null;
+        HashMultiSet<RTreeCheckTuple> expectedResult = null;
 
-        expectedResult = getRangeSearchExpectedResults((ArrayList<RTreeCheckTuple>) ctx.getCheckTuples(), keyCheck);
+        expectedResult = getRangeSearchExpectedResults(ctx.getCheckTuples(), keyCheck);
         checkExpectedResults(searchCursor, expectedResult, ctx.getFieldSerdes(), ctx.getKeyFieldCount(), null);
     }
 
@@ -122,7 +123,7 @@
     protected CheckTuple createDoubleCheckTuple(double[] fieldValues, int numKeyFields) {
         RTreeCheckTuple<Double> checkTuple = new RTreeCheckTuple<Double>(fieldValues.length, numKeyFields);
         for (double v : fieldValues) {
-            checkTuple.add(v);
+            checkTuple.appendField(v);
         }
         return checkTuple;
     }
@@ -194,7 +195,7 @@
     protected CheckTuple createIntCheckTuple(int[] fieldValues, int numKeyFields) {
         RTreeCheckTuple<Integer> checkTuple = new RTreeCheckTuple<Integer>(fieldValues.length, numKeyFields);
         for (int v : fieldValues) {
-            checkTuple.add(v);
+            checkTuple.appendField(v);
         }
         return checkTuple;
     }
diff --git a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java
index 8be3e8c..799cdaa 100644
--- a/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java
+++ b/hyracks-tests/hyracks-storage-am-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/rtree/RTreeSearchCursorTest.java
@@ -43,6 +43,7 @@
 import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManager;
 import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.util.HashMultiSet;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
 import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
 import edu.uci.ics.hyracks.storage.am.rtree.frames.RTreeNSMInteriorFrameFactory;
@@ -142,11 +143,11 @@
             } catch (TreeIndexException e) {
             }
             RTreeCheckTuple checkTuple = new RTreeCheckTuple(fieldCount, keyFieldCount);
-            checkTuple.add(Math.min(p1x, p2x));
-            checkTuple.add(Math.min(p1y, p2y));
-            checkTuple.add(Math.max(p1x, p2x));
-            checkTuple.add(Math.max(p1y, p2y));
-            checkTuple.add(pk);
+            checkTuple.appendField(Math.min(p1x, p2x));
+            checkTuple.appendField(Math.min(p1y, p2y));
+            checkTuple.appendField(Math.max(p1x, p2x));
+            checkTuple.appendField(Math.max(p1y, p2y));
+            checkTuple.appendField(pk);
 
             checkTuples.add(checkTuple);
         }
@@ -162,7 +163,7 @@
 
         RTreeCheckTuple keyCheck = (RTreeCheckTuple) rTreeTestUtils.createCheckTupleFromTuple(key, fieldSerdes,
                 keyFieldCount);
-        ArrayList<RTreeCheckTuple> expectedResult = rTreeTestUtils.getRangeSearchExpectedResults(checkTuples, keyCheck);
+        HashMultiSet<RTreeCheckTuple> expectedResult = rTreeTestUtils.getRangeSearchExpectedResults(checkTuples, keyCheck);
 
         rTreeTestUtils.getRangeSearchExpectedResults(checkTuples, keyCheck);
         indexAccessor.search(searchCursor, searchPredicate);