diff --git a/src/main/java/org/apache/sysds/runtime/lineage/LineageCache.java b/src/main/java/org/apache/sysds/runtime/lineage/LineageCache.java
index be58d79..eef8bfb 100644
--- a/src/main/java/org/apache/sysds/runtime/lineage/LineageCache.java
+++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageCache.java
@@ -62,6 +62,7 @@
 	static {
 		long maxMem = InfrastructureAnalyzer.getLocalMaxMemory();
 		LineageCacheEviction.setCacheLimit((long)(CACHE_FRAC * maxMem));
+		LineageCacheEviction.setStartTimestamp();
 	}
 	
 	// Cache Synchronization Approach:
@@ -220,7 +221,7 @@
 	
 	public static boolean probe(LineageItem key) {
 		//TODO problematic as after probe the matrix might be kicked out of cache
-		boolean p = (_cache.containsKey(key) || LineageCacheEviction.spillListContains(key));
+		boolean p = _cache.containsKey(key);  // in cache or in disk
 		if (!p && DMLScript.STATISTICS && LineageCacheEviction._removelist.contains(key))
 			// The sought entry was in cache but removed later 
 			LineageCacheStatistics.incrementDelHits();
diff --git a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheConfig.java b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheConfig.java
index f17e055..45fd34b 100644
--- a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheConfig.java
+++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheConfig.java
@@ -224,6 +224,11 @@
 				break;
 			case HYBRID:
 				WEIGHTS[0] = 1; WEIGHTS[1] = 0.0033;
+				// FIXME: Relative timestamp fix reduces the absolute
+				// value of the timestamp component of the scoring function
+				// to a comparatively much smaller number. W[1] needs to be
+				// re-tuned accordingly.
+				// TODO: Automatic tuning of weights.
 				break;
 		}
 		_cachepolicy = policy;
diff --git a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEntry.java b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEntry.java
index 773dce6..983572c 100644
--- a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEntry.java
+++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEntry.java
@@ -35,6 +35,7 @@
 	protected LineageCacheStatus _status;
 	protected LineageCacheEntry _nextEntry;
 	protected LineageItem _origItem;
+	private String _outfile = null;
 	protected double score;
 	
 	public LineageCacheEntry(LineageItem key, DataType dt, MatrixBlock Mval, ScalarObject Sval, long computetime) {
@@ -122,8 +123,18 @@
 		_status = LineageCacheStatus.EMPTY;
 	}
 	
+	protected synchronized void setOutfile(String outfile) {
+		_outfile = outfile;
+	}
+	
+	protected synchronized String getOutfile() {
+		return _outfile;
+	}
+	
 	protected synchronized void setTimestamp() {
-		_timestamp = System.currentTimeMillis();
+		_timestamp =  System.currentTimeMillis() - LineageCacheEviction.getStartTimestamp();
+		if (_timestamp < 0)
+			throw new DMLRuntimeException ("Execution timestamp shouldn't be -ve. Key: "+_key);
 		recomputeScore();
 	}
 	
diff --git a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEviction.java b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEviction.java
index 43fa7c5..31fccc7 100644
--- a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEviction.java
+++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEviction.java
@@ -20,7 +20,6 @@
 package org.apache.sysds.runtime.lineage;
 
 import java.io.IOException;
-import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Map;
 import java.util.Set;
@@ -37,8 +36,8 @@
 {
 	private static long _cachesize = 0;
 	private static long CACHE_LIMIT; //limit in bytes
+	private static long _startTimestamp = 0;
 	protected static final Set<LineageItem> _removelist = new HashSet<>();
-	private static final Map<LineageItem, SpilledItem> _spillList = new HashMap<>();
 	private static String _outdir = null;
 	private static TreeSet<LineageCacheEntry> weightedQueue = new TreeSet<>(LineageCacheConfig.LineageCacheComparator);
 	
@@ -46,7 +45,6 @@
 		// reset cache size, otherwise the cache clear leads to unusable 
 		// space which means evictions could run into endless loops
 		_cachesize = 0;
-		_spillList.clear();
 		weightedQueue.clear();
 		_outdir = null;
 		if (DMLScript.STATISTICS)
@@ -240,6 +238,14 @@
 
 	//---------------- COSTING RELATED METHODS -----------------
 
+	protected static void setStartTimestamp() {
+		_startTimestamp = System.currentTimeMillis();
+	}
+	
+	protected static long getStartTimestamp() {
+		return _startTimestamp;
+	}
+
 	private static double getDiskSpillEstimate(LineageCacheEntry e) {
 		if (!e.isMatrixValue() || e.isNullVal())
 			return 0;
@@ -299,6 +305,15 @@
 		if (entry.isNullVal())
 			throw new DMLRuntimeException ("Cannot spill null value to disk. Key: "+entry._key);
 		
+		// Do nothing if the entry is already spilled before.
+		if (entry._origItem == null && entry.getOutfile() != null)
+			return;
+		if (entry._origItem != null) {
+			LineageCacheEntry tmp = cache.get(entry._origItem); //head
+			if (tmp.getOutfile() != null)
+				return;
+		}
+		
 		long t0 = System.nanoTime();
 		if (_outdir == null) {
 			_outdir = LocalFileUtils.getUniqueWorkingDir(LocalFileUtils.CATEGORY_LINEAGE);
@@ -316,12 +331,12 @@
 		
 		// Add all the entries associated with this matrix to spillList.
 		if (entry._origItem == null) {
-			_spillList.put(entry._key, new SpilledItem(outfile));
+			entry.setOutfile(outfile);
 		}
 		else {
 			LineageCacheEntry h = cache.get(entry._origItem); //head
 			while (h != null) {
-				_spillList.put(h._key, new SpilledItem(outfile));
+				h.setOutfile(outfile);
 				h = h._nextEntry;
 			}
 		}
@@ -336,19 +351,20 @@
 		if (cache.get(key) == null)
 			throw new DMLRuntimeException ("Spilled item should present in cache. Key: "+key);
 
+		LineageCacheEntry e = cache.get(key);
 		long t0 = System.nanoTime();
 		MatrixBlock mb = null;
 		// Read from local FS
 		try {
-			mb = LocalFileUtils.readMatrixBlockFromLocal(_spillList.get(key)._outfile);
-		} catch (IOException e) {
-			throw new DMLRuntimeException ("Read from " + _spillList.get(key)._outfile + " failed.", e);
+			mb = LocalFileUtils.readMatrixBlockFromLocal(e.getOutfile());
+		} catch (IOException exp) {
+			throw new DMLRuntimeException ("Read from " + e.getOutfile() + " failed.", exp);
 		}
-		LocalFileUtils.deleteFileIfExists(_spillList.get(key)._outfile, true);
+		// Keep the entry in disk to save re-spilling.
+		//LocalFileUtils.deleteFileIfExists(_spillList.get(key)._outfile, true);
 		long t1 = System.nanoTime();
 
 		// Restore to cache
-		LineageCacheEntry e = cache.get(key);
 		e.setValue(mb);
 		if (e._origItem != null) {
 			// Restore to all the entries having the same data.
@@ -365,30 +381,10 @@
 		// Adjust disk reading speed
 		adjustReadWriteSpeed(e, ((double)(t1-t0))/1000000000, true);
 		// TODO: set cache status as RELOADED for this entry
-		_spillList.remove(key);
 		if (DMLScript.STATISTICS) {
 			LineageCacheStatistics.incrementFSReadTime(t1-t0);
 			LineageCacheStatistics.incrementFSHits();
 		}
 		return cache.get(key);
 	}
-	
-	protected static boolean spillListContains(LineageItem key) {
-		return _spillList.containsKey(key);
-	}
-
-	// ---------------- INTERNAL DATA STRUCTURES FOR EVICTION -----------------
-
-	// TODO: Remove this class, and add outfile to LineageCacheEntry.
-	private static class SpilledItem {
-		String _outfile;
-		//long _computeTime;
-		//protected LineageItem _origItem;
-
-		public SpilledItem(String outfile) {
-			_outfile = outfile;
-			//_computeTime = computetime;
-			//_origItem = origItem;
-		}
-	}
 }