fix clustering bugs

Change-Id: Ia1161055bff5e2e222422d07243524bf0a34d775

5 files changed, 287 insertions, 259 deletions

diff --git a/bordeaux/learning/predictor_histogram/java/android/bordeaux/learning/HistogramPredictor.java b/bordeaux/learning/predictor_histogram/java/android/bordeaux/learning/HistogramPredictor.java
index c4e7e28f0..ef57939fd 100644
--- a/bordeaux/learning/predictor_histogram/java/android/bordeaux/learning/HistogramPredictor.java
+++ b/bordeaux/learning/predictor_histogram/java/android/bordeaux/learning/HistogramPredictor.java
@@ -52,6 +52,9 @@ public class HistogramPredictor {
     private HashMap<String, HistogramCounter> mPredictor =
             new HashMap<String, HistogramCounter>();
 
+    private HashMap<String, Integer> mClassCounts = new HashMap<String, Integer>();
+    private int mTotalClassCount = 0;
+
     private static final double FEATURE_INACTIVE_LIKELIHOOD = 0.00000001;
     private static final double LOG_INACTIVE = Math.log(FEATURE_INACTIVE_LIKELIHOOD);
 
@@ -91,9 +94,9 @@ public class HistogramPredictor {
             if (!mCounter.containsKey(featureValue)) {
                 classCounts = new HashMap<String, Integer>();
                 mCounter.put(featureValue, classCounts);
+            } else {
+                classCounts = mCounter.get(featureValue);
             }
-            classCounts = mCounter.get(featureValue);
-
             int count = (classCounts.containsKey(className)) ?
                     classCounts.get(className) + 1 : 1;
             classCounts.put(className, count);
@@ -140,6 +143,8 @@ public class HistogramPredictor {
         HashMap<String, Double> appScores = new HashMap<String, Double>();
         double defaultLikelihood = getDefaultLikelihood(features);
 
+        HashMap<String, Integer> appearCounts = new HashMap<String, Integer>();
+
         // compute all app scores
         for (Map.Entry<String, HistogramCounter> entry : mPredictor.entrySet()) {
             String featureName = entry.getKey();
@@ -152,13 +157,34 @@ public class HistogramPredictor {
                 for (Map.Entry<String, Double> item : scoreMap.entrySet()) {
                     String appName = item.getKey();
                     double appScore = item.getValue();
-
                     double score = (appScores.containsKey(appName)) ?
                         appScores.get(appName) : defaultLikelihood;
                     score += appScore - LOG_INACTIVE;
-
                     appScores.put(appName, score);
+
+                    int count = (appearCounts.containsKey(appName)) ?
+                        appearCounts.get(appName) + 1 : 1;
+                    appearCounts.put(appName, count);
+                }
+            }
+        }
+
+        // TODO: this check should be unnecessary
+        if (mClassCounts.size() != 0 && mTotalClassCount != 0) {
+            for (Map.Entry<String, Double> entry : appScores.entrySet()) {
+                String appName = entry.getKey();
+                double appScore = entry.getValue();
+                if (!appearCounts.containsKey(appName)) {
+                    throw new RuntimeException("appearance count error!");
                 }
+                int appearCount = appearCounts.get(appName);
+
+                if (!mClassCounts.containsKey(appName)) {
+                    throw new RuntimeException("class count error!");
+                }
+                double appPrior =
+                    Math.log(mClassCounts.get(appName)) - Math.log(mTotalClassCount);
+                appScores.put(appName, appScore - appPrior * (appearCount - 1));
             }
         }
 
@@ -173,7 +199,7 @@ public class HistogramPredictor {
             }
         });
 
-        Log.e(TAG, "findTopApps appList: " + appList);
+        Log.v(TAG, "findTopApps appList: " + appList);
         return appList;
     }
 
@@ -190,6 +216,10 @@ public class HistogramPredictor {
                 counter.addSample(sampleId, featureValue);
             }
         }
+
+        int sampleCount = (mClassCounts.containsKey(sampleId)) ?
+            mClassCounts.get(sampleId) + 1 : 1;
+        mClassCounts.put(sampleId, sampleCount);
     }
 
     /*
@@ -201,6 +231,9 @@ public class HistogramPredictor {
             counter.resetCounter();
         }
         mPredictor.clear();
+
+        mClassCounts.clear();
+        mTotalClassCount = 0;
     }
 
     /*
@@ -258,6 +291,39 @@ public class HistogramPredictor {
             useFeature(entry.getKey());
             mPredictor.get(entry.getKey()).setCounter(entry.getValue());
         }
+
+        // TODO: this is a temporary fix for now
+        loadClassCounter();
+
         return true;
     }
+
+    private void loadClassCounter() {
+        String TIME_OF_WEEK = "Time of Week";
+
+        if (!mPredictor.containsKey(TIME_OF_WEEK)) {
+            throw new RuntimeException("Precition model error: missing Time of Week!");
+        }
+
+        HashMap<String, HashMap<String, Integer> > counter =
+            mPredictor.get(TIME_OF_WEEK).getCounter();
+
+        mTotalClassCount = 0;
+        mClassCounts.clear();
+        for (HashMap<String, Integer> map : counter.values()) {
+            for (Map.Entry<String, Integer> entry : map.entrySet()) {
+                int classCount = entry.getValue();
+                String className = entry.getKey();
+                mTotalClassCount += classCount;
+
+                if (mClassCounts.containsKey(className)) {
+                    classCount += mClassCounts.get(className);
+                }
+                mClassCounts.put(className, classCount);
+            }
+        }
+
+        Log.e(TAG, "class counts: " + mClassCounts + ", total count: " +
+              mTotalClassCount);
+    }
 }
diff --git a/bordeaux/service/src/android/bordeaux/services/BaseCluster.java b/bordeaux/service/src/android/bordeaux/services/BaseCluster.java
index d00e5f015..03574a9fa 100644
--- a/bordeaux/service/src/android/bordeaux/services/BaseCluster.java
+++ b/bordeaux/service/src/android/bordeaux/services/BaseCluster.java
@@ -30,6 +30,11 @@ public class BaseCluster {
     public double[] mCenter;
   // protected double[] mCenter;
 
+    protected static final int VECTOR_LENGTH = 3;
+
+    private static final long FORGETTING_ENUMERATOR = 95;
+    private static final long FORGETTING_DENOMINATOR = 100;
+
     // Histogram illustrates the pattern of visit during time of day,
     protected HashMap<String, Long> mHistogram = new HashMap<String, Long>();
 
@@ -41,24 +46,26 @@ public class BaseCluster {
 
     public BaseCluster(Location location) {
         mCenter = getLocationVector(location);
-
         mDuration = 0;
     }
 
-    public BaseCluster() {
-        mCenter = new double[] {0f, 0f, 0f};
+    public BaseCluster(String semanticId, double longitude, double latitude,
+                     long duration) {
+        mSemanticId = semanticId;
+        mCenter = getLocationVector(longitude, latitude);
+        mDuration = duration;
     }
 
     public String getSemanticId() {
         return mSemanticId;
     }
 
-    protected void generateSemanticId(long index) {
+    public void generateSemanticId(long index) {
         mSemanticId = "cluser: " + String.valueOf(index);
     }
 
-    public void setSemanticId(String semanticId) {
-        mSemanticId = semanticId;
+    public long getDuration() {
+        return mDuration;
     }
 
     public boolean hasSemanticId() {
@@ -70,7 +77,7 @@ public class BaseCluster {
     }
 
     protected double[] getLocationVector(double longitude, double latitude) {
-        double vector[] = new double[3];
+        double vector[] = new double[VECTOR_LENGTH];
         double lambda = Math.toRadians(longitude);
         double phi = Math.toRadians(latitude);
 
@@ -96,7 +103,7 @@ public class BaseCluster {
 
     private double computeDistance(double[] vector1, double[] vector2) {
         double product = 0f;
-        for (int i = 0; i < 3; ++i) {
+        for (int i = 0; i < VECTOR_LENGTH; ++i) {
             product += vector1[i] * vector2[i];
         }
         double radian = Math.acos(Math.min(product, 1f));
@@ -115,23 +122,12 @@ public class BaseCluster {
     }
 
     public void absorbCluster(BaseCluster cluster) {
-        // the new cluster center is the average of the two clusters.
-        double weight = ((double) mDuration) / (mDuration + cluster.mDuration);
-        double clusterWeight = 1f - weight;
-        double norm = 0;
-        for (int i = 0; i < 3; ++i) {
-            mCenter[i] = weight * mCenter[i] + clusterWeight * cluster.mCenter[i];
-            norm += mCenter[i] * mCenter[i];
-        }
-        // normalize the center to be unit vector
-        for (int i = 0; i < 3; ++i) {
-            mCenter[i] /= norm;
-        }
+        averageCenter(cluster.mCenter, cluster.mDuration);
         absorbHistogram(cluster);
     }
 
     public void setCluster(BaseCluster cluster) {
-        for (int i = 0; i < 3; ++i) {
+        for (int i = 0; i < VECTOR_LENGTH; ++i) {
             mCenter[i] = cluster.mCenter[i];
         }
         mHistogram.clear();
@@ -173,4 +169,45 @@ public class BaseCluster {
             mDuration += mHistogram.get(TimeStatsAggregator.WEEKDAY);
         }
     }
+
+    public void forgetPastHistory() {
+        mDuration *= FORGETTING_ENUMERATOR;
+        mDuration /= FORGETTING_DENOMINATOR;
+
+        for (Map.Entry<String, Long> entry : mHistogram.entrySet()) {
+            String key = entry.getKey();
+            long value = entry.getValue();
+
+            value *= FORGETTING_ENUMERATOR;
+            value /= FORGETTING_DENOMINATOR;
+
+            mHistogram.put(key, value);
+        }
+    }
+
+    protected void normalizeCenter() {
+        double norm = 0;
+        for (int i = 0; i < VECTOR_LENGTH; ++i) {
+            norm += mCenter[i] * mCenter[i];
+        }
+        norm = Math.sqrt(norm);
+        for (int i = 0; i < VECTOR_LENGTH; ++i) {
+            mCenter[i] /= norm;
+        }
+    }
+
+    protected void averageCenter(double[] newCenter, long newDuration) {
+        double weight = ((double) mDuration) / (mDuration + newDuration);
+        double newWeight = 1f - weight;
+
+        double norm = 0;
+        for (int i = 0; i < VECTOR_LENGTH; ++i) {
+            mCenter[i] = weight * mCenter[i] + newWeight * newCenter[i];
+            norm += mCenter[i] * mCenter[i];
+        }
+        norm = Math.sqrt(norm);
+        for (int i = 0; i < VECTOR_LENGTH; ++i) {
+            mCenter[i] /= norm;
+        }
+    }
 }
diff --git a/bordeaux/service/src/android/bordeaux/services/ClusterManager.java b/bordeaux/service/src/android/bordeaux/services/ClusterManager.java
index 4bc036995..249be860b 100644
--- a/bordeaux/service/src/android/bordeaux/services/ClusterManager.java
+++ b/bordeaux/service/src/android/bordeaux/services/ClusterManager.java
@@ -38,41 +38,36 @@ public class ClusterManager {
 
     private static String TAG = "ClusterManager";
 
-    private static float LOCATION_CLUSTER_RADIUS = 50; // meter
+    private static float LOCATION_CLUSTER_RADIUS = 25; // meter
 
-    private static float SEMANTIC_CLUSTER_RADIUS = 100; // meter
+    private static float SEMANTIC_CLUSTER_RADIUS = 75; // meter
 
     // Consoliate location clusters (and check for new semantic clusters)
-    // every 30 minutes (1800 seconds).
-    private static final long CONSOLIDATE_INTERVAL = 1800;
-
-    // Prune away clusters that are stayed for less than 3 minutes (180 seconds)
-    private static long LOCATION_CLUSTER_THRESHOLD = 180;
+    // every 10 minutes (600 seconds).
+    private static final long CONSOLIDATE_INTERVAL = 600;
 
     // A location cluster can be labeled as a semantic cluster if it has been
     // stayed for at least 10 minutes (600 seconds) within a day.
     private static final long SEMANTIC_CLUSTER_THRESHOLD = 600; // seconds
 
-    // Reset location cluters every 6 hours (21600 seconds).
-    private static final long LOCATION_REFRESH_PERIOD = 21600; // seconds
+    // Reset location cluters every 12 hours (43200 seconds).
+    private static final long LOCATION_REFRESH_PERIOD = 43200; // seconds
 
     private static String UNKNOWN_LOCATION = "Unknown Location";
 
-    private static String HOME = "Home";
-
-    private static String OFFICE = "Office";
-
     private Location mLastLocation = null;
 
     private long mClusterDuration;
 
-    private long mTimeRef = 0;
+    private long mConsolidateRef = 0;
+
+    private long mRefreshRef = 0;
 
     private long mSemanticClusterCount = 0;
 
     private ArrayList<LocationCluster> mLocationClusters = new ArrayList<LocationCluster>();
 
-    private ArrayList<SemanticCluster> mSemanticClusters = new ArrayList<SemanticCluster>();
+    private ArrayList<BaseCluster> mSemanticClusters = new ArrayList<BaseCluster>();
 
     private AggregatorRecordStorage mStorage;
 
@@ -84,10 +79,13 @@ public class ClusterManager {
 
     private static final String SEMANTIC_LATITUDE = "Latitude";
 
+    private static final String SEMANTIC_DURATION = "Duration";
+
     private static final String[] SEMANTIC_COLUMNS =
         new String[]{ SEMANTIC_ID,
                       SEMANTIC_LONGITUDE,
                       SEMANTIC_LATITUDE,
+                      SEMANTIC_DURATION,
                       TimeStatsAggregator.WEEKEND,
                       TimeStatsAggregator.WEEKDAY,
                       TimeStatsAggregator.MORNING,
@@ -97,8 +95,8 @@ public class ClusterManager {
                       TimeStatsAggregator.NIGHT,
                       TimeStatsAggregator.LATENIGHT };
 
-    private static final int mFeatureValueStart = 3;
-    private static final int mFeatureValueEnd = 10;
+    private static final int mFeatureValueStart = 4;
+    private static final int mFeatureValueEnd = 11;
 
     public ClusterManager(Context context) {
         mStorage = new AggregatorRecordStorage(context, SEMANTIC_TABLE, SEMANTIC_COLUMNS);
@@ -120,172 +118,136 @@ public class ClusterManager {
             Log.v(TAG, "sample duration: " + duration +
                   ", number of clusters: " + mLocationClusters.size());
 
-            // add the last location to cluster.
-            // first find the cluster it belongs to.
-            for (int i = 0; i < mLocationClusters.size(); ++i) {
-                float distance = mLocationClusters.get(i).distanceToCenter(mLastLocation);
-                Log.v(TAG, "clulster " + i + " is within " + distance + " meters");
-                if (distance < bestClusterDistance) {
-                    bestClusterDistance = distance;
-                    bestClusterIndex = i;
+            synchronized (mLocationClusters) {
+                // add the last location to cluster.
+                // first find the cluster it belongs to.
+                for (int i = 0; i < mLocationClusters.size(); ++i) {
+                    float distance = mLocationClusters.get(i).distanceToCenter(mLastLocation);
+                    Log.v(TAG, "clulster " + i + " is within " + distance + " meters");
+                    if (distance < bestClusterDistance) {
+                        bestClusterDistance = distance;
+                        bestClusterIndex = i;
+                    }
                 }
-            }
 
-            // add the location to the selected cluster
-            if (bestClusterDistance < LOCATION_CLUSTER_RADIUS) {
-                mLocationClusters.get(bestClusterIndex).addSample(mLastLocation, duration);
-            } else {
-                // if it is far away from all existing clusters, create a new cluster.
-                LocationCluster cluster = new LocationCluster(mLastLocation, duration);
-                // move the center of the new cluster if its covering region overlaps
-                // with an existing cluster.
-                if (bestClusterDistance < 2 * LOCATION_CLUSTER_RADIUS) {
-                    Log.v(TAG, "move away activated");
-                    cluster.moveAwayCluster(mLocationClusters.get(bestClusterIndex),
-                            ((float) 2 * LOCATION_CLUSTER_RADIUS));
+                // add the location to the selected cluster
+                if (bestClusterDistance < LOCATION_CLUSTER_RADIUS) {
+                    mLocationClusters.get(bestClusterIndex).addSample(mLastLocation, duration);
+                } else {
+                    // if it is far away from all existing clusters, create a new cluster.
+                  LocationCluster cluster = new LocationCluster(mLastLocation, duration);
+                  mLocationClusters.add(cluster);
                 }
-                mLocationClusters.add(cluster);
             }
         } else {
-            mTimeRef = currentTime;
+            mConsolidateRef = currentTime;
+            mRefreshRef = currentTime;
 
             if (mLocationClusters.isEmpty()) {
                 mClusterDuration = 0;
             }
         }
 
-        long collectDuration = currentTime - mTimeRef;
-        Log.e(TAG, "collect duration: " + collectDuration);
+        long collectDuration = currentTime - mConsolidateRef;
+        Log.v(TAG, "collect duration: " + collectDuration);
         if (collectDuration > CONSOLIDATE_INTERVAL) {
             // TODO : conslidation takes time. move this to a separate thread later.
-            consolidateClusters(collectDuration);
-            mTimeRef = currentTime;
-        }
-        mLastLocation = location;
-    }
-
-    private void consolidateClusters(long duration) {
-        LocationCluster cluster;
-        for (int i = mLocationClusters.size() - 1; i >= 0; --i) {
-            cluster = mLocationClusters.get(i);
-            cluster.consolidate(duration);
-
-            // remove transit clusters
-            if (!cluster.passThreshold(LOCATION_CLUSTER_THRESHOLD)) {
-                mLocationClusters.remove(cluster);
-            }
-        }
-
-        // merge clusters whose regions are overlapped. note that after merge
-        // cluster center changes but cluster size remains unchanged.
-        for (int i = mLocationClusters.size() - 1; i >= 0; --i) {
-            cluster = mLocationClusters.get(i);
-            for (int j = i - 1; j >= 0; --j) {
-                float distance = mLocationClusters.get(j).distanceToCluster(cluster);
-                if (distance < LOCATION_CLUSTER_RADIUS) {
-                    mLocationClusters.get(j).absorbCluster(cluster);
-                    mLocationClusters.remove(cluster);
-                }
+            consolidateClusters();
+            mConsolidateRef = currentTime;
+
+            long refreshDuration = currentTime - mRefreshRef;
+            Log.v(TAG, "refresh duration: " + refreshDuration);
+            if (refreshDuration >  LOCATION_REFRESH_PERIOD) {
+                updateSemanticClusters();
+                mRefreshRef = currentTime;
             }
-        }
-
-        // check if new semantic clusters are found
-        if (findNewSemanticClusters() &&
-            mClusterDuration < LOCATION_REFRESH_PERIOD) {
             saveSemanticClusters();
         }
 
-        if (mClusterDuration >  LOCATION_REFRESH_PERIOD) {
-            updateSemanticClusters();
-            mClusterDuration = 0;
-        }
+        mLastLocation = location;
     }
 
-    private boolean findNewSemanticClusters() {
-        // select candidate location clusters
-        ArrayList<LocationCluster> candidates = new ArrayList<LocationCluster>();
-        for (LocationCluster cluster : mLocationClusters) {
-            if (!cluster.hasSemanticId() &&
-                cluster.passThreshold(SEMANTIC_CLUSTER_THRESHOLD)) {
-                candidates.add(cluster);
+    private void consolidateClusters() {
+        synchronized (mSemanticClusters) {
+            LocationCluster locationCluster;
+            for (int i = mLocationClusters.size() - 1; i >= 0; --i) {
+                locationCluster = mLocationClusters.get(i);
+                locationCluster.consolidate();
             }
-        }
 
-        // assign each candidate to a semantic cluster
-        boolean foundNewClusters = false;
-        for (LocationCluster candidate : candidates) {
-            // find the closest semantic cluster
-            float bestClusterDistance = Float.MAX_VALUE;
-            SemanticCluster bestCluster = null;
-            for (SemanticCluster cluster : mSemanticClusters) {
-                float distance = cluster.distanceToCluster(candidate);
-                Log.v(TAG, "distance to semantic cluster: " + cluster.getSemanticId());
-
-                if (distance < bestClusterDistance) {
-                    bestClusterDistance = distance;
-                    bestCluster = cluster;
+            // merge clusters whose regions are overlapped. note that after merge
+            // cluster center changes but cluster size remains unchanged.
+            for (int i = mLocationClusters.size() - 1; i >= 0; --i) {
+                locationCluster = mLocationClusters.get(i);
+                for (int j = i - 1; j >= 0; --j) {
+                    float distance =
+                        mLocationClusters.get(j).distanceToCluster(locationCluster);
+                    if (distance < LOCATION_CLUSTER_RADIUS) {
+                        mLocationClusters.get(j).absorbCluster(locationCluster);
+                        mLocationClusters.remove(locationCluster);
+                    }
                 }
             }
+            Log.v(TAG, mLocationClusters.size() + " location clusters after consolidate");
+
+            // assign each candidate to a semantic cluster and check if new semantic
+            // clusters are found
+            for (LocationCluster candidate : mLocationClusters) {
+                if (candidate.hasSemanticId() ||
+                    candidate.hasSemanticClusterId() ||
+                    !candidate.passThreshold(SEMANTIC_CLUSTER_THRESHOLD)) {
+                    continue;
+                }
 
-            // if candidate doesn't belong to any semantic cluster, create a new
-            // semantic cluster
-            if (bestClusterDistance > SEMANTIC_CLUSTER_RADIUS) {
-                // if it is far away from all existing clusters, create a new cluster.
-                bestCluster = new SemanticCluster(candidate, mSemanticClusterCount++);
-                String id = bestCluster.getSemanticId();
+                // find the closest semantic cluster
+                float bestClusterDistance = Float.MAX_VALUE;
+                String bestClusterId = "Unused Id";
+                for (BaseCluster cluster : mSemanticClusters) {
+                    float distance = cluster.distanceToCluster(candidate);
+                    Log.v(TAG, distance + "distance to semantic cluster: " + cluster.getSemanticId());
 
-                // Add new semantic cluster to the list.
-                mSemanticClusters.add(bestCluster);
+                    if (distance < bestClusterDistance) {
+                        bestClusterDistance = distance;
+                        bestClusterId = cluster.getSemanticId();
+                    }
+                }
 
-                foundNewClusters = true;
+                // if candidate doesn't belong to any semantic cluster, create a new
+                // semantic cluster
+                if (bestClusterDistance > SEMANTIC_CLUSTER_RADIUS) {
+                    candidate.generateSemanticId(mSemanticClusterCount++);
+                    mSemanticClusters.add(candidate);
+                } else {
+                    candidate.setSemanticClusterId(bestClusterId);
+                }
             }
-            candidate.setSemanticId(bestCluster.getSemanticId());
+            Log.v(TAG, mSemanticClusters.size() + " semantic clusters after consolidate");
         }
-        candidates.clear();
-        return foundNewClusters;
     }
 
     private void updateSemanticClusters() {
         synchronized (mSemanticClusters) {
-            // initialize semanticMap
-            HashMap<String, ArrayList<BaseCluster> > semanticMap =
-                new HashMap<String, ArrayList<BaseCluster> >();
-            for (SemanticCluster cluster : mSemanticClusters) {
-                String semanticId = cluster.getSemanticId();
-                semanticMap.put(cluster.getSemanticId(), new ArrayList<BaseCluster>());
-                semanticMap.get(semanticId).add(cluster);
+            // create index to cluster map
+            HashMap<String, BaseCluster> semanticIdMap =
+                new HashMap<String, BaseCluster>();
+            for (BaseCluster cluster : mSemanticClusters) {
+                // TODO: apply forgetting factor on existing semantic cluster stats,
+                // duration, histogram, etc.
+                cluster.forgetPastHistory();
+                semanticIdMap.put(cluster.getSemanticId(), cluster);
             }
 
             // assign each candidate to a semantic cluster
             for (LocationCluster cluster : mLocationClusters) {
-                if (cluster.hasSemanticId()) {
-                    semanticMap.get(cluster.getSemanticId()).add(cluster);
+                if (cluster.hasSemanticClusterId()) {
+                    BaseCluster semanticCluster =
+                        semanticIdMap.get(cluster.getSemanticClusterId());
+                    semanticCluster.absorbCluster(cluster);
                 }
             }
             // reset location clusters.
             mLocationClusters.clear();
-            mLastLocation = null;
-            mTimeRef = 0;
-
-            // use candidates semantic cluster
-            BaseCluster newCluster = new BaseCluster();
-            for (ArrayList<BaseCluster> clusterList : semanticMap.values()) {
-                SemanticCluster semanticCluster = (SemanticCluster) clusterList.get(0);
-
-                if (clusterList.size() > 1) {
-                    newCluster.setCluster(clusterList.get(1));
-                    for (int i = 2; i < clusterList.size(); i++) {
-                      newCluster.absorbCluster(clusterList.get(i));
-                    }
-                    semanticCluster.absorbCluster(newCluster);
-                } else {
-                    // cluster with no new candidate
-                    Log.e(TAG, "semantic cluster with no new location clusters: " +
-                          semanticCluster);
-                }
-            }
         }
-        saveSemanticClusters();
     }
 
     private void loadSemanticClusters() {
@@ -298,8 +260,9 @@ public class ClusterManager {
                 String semanticId = map.get(SEMANTIC_ID);
                 double longitude = Double.valueOf(map.get(SEMANTIC_LONGITUDE));
                 double latitude = Double.valueOf(map.get(SEMANTIC_LATITUDE));
-                SemanticCluster cluster =
-                    new SemanticCluster(semanticId, longitude, latitude);
+                long duration = Long.valueOf(map.get(SEMANTIC_DURATION));
+                BaseCluster cluster =
+                    new BaseCluster(semanticId, longitude, latitude, duration);
 
                 histogram.clear();
                 for (int i = mFeatureValueStart; i <= mFeatureValueEnd; i++) {
@@ -321,7 +284,7 @@ public class ClusterManager {
 
         mStorage.removeAllData();
         synchronized (mSemanticClusters) {
-            for (SemanticCluster cluster : mSemanticClusters) {
+            for (BaseCluster cluster : mSemanticClusters) {
                 rowFeatures.clear();
                 rowFeatures.put(SEMANTIC_ID, cluster.getSemanticId());
 
@@ -329,6 +292,8 @@ public class ClusterManager {
                             String.valueOf(cluster.getCenterLongitude()));
                 rowFeatures.put(SEMANTIC_LATITUDE,
                             String.valueOf(cluster.getCenterLatitude()));
+                rowFeatures.put(SEMANTIC_DURATION,
+                            String.valueOf(cluster.getDuration()));
 
                 HashMap<String, Long> histogram = cluster.getHistogram();
                 for (Map.Entry<String, Long> entry : histogram.entrySet()) {
@@ -347,7 +312,7 @@ public class ClusterManager {
         if (mLastLocation != null) {
             // TODO: use fast neatest neighbor search speed up location search
             synchronized (mSemanticClusters) {
-                for (SemanticCluster cluster: mSemanticClusters) {
+                for (BaseCluster cluster: mSemanticClusters) {
                     if (cluster.distanceToCenter(mLastLocation) < SEMANTIC_CLUSTER_RADIUS) {
                         return cluster.getSemanticId();
                     }
@@ -360,7 +325,7 @@ public class ClusterManager {
     public List<String> getClusterNames() {
         ArrayList<String> clusters = new ArrayList<String>();
         synchronized (mSemanticClusters) {
-            for (SemanticCluster cluster: mSemanticClusters) {
+            for (BaseCluster cluster: mSemanticClusters) {
                 clusters.add(cluster.getSemanticId());
             }
         }
diff --git a/bordeaux/service/src/android/bordeaux/services/LocationCluster.java b/bordeaux/service/src/android/bordeaux/services/LocationCluster.java
index 078e64396..c9f753f76 100644
--- a/bordeaux/service/src/android/bordeaux/services/LocationCluster.java
+++ b/bordeaux/service/src/android/bordeaux/services/LocationCluster.java
@@ -27,15 +27,26 @@ import java.util.Map;
 public class LocationCluster extends BaseCluster {
     public static String TAG = "LocationCluster";
 
-    private boolean mIsNewCluster;
-
     private ArrayList<Location> mLocations = new ArrayList<Location>();
     private HashMap<String, Long> mNewHistogram = new HashMap<String, Long>();
 
+    private String mSemanticClusterId = null;
+
+    public void setSemanticClusterId(String semanticClusterId) {
+        mSemanticClusterId = semanticClusterId;
+    }
+
+    public String getSemanticClusterId() {
+        return mSemanticClusterId;
+    }
+
+    public boolean hasSemanticClusterId() {
+        return mSemanticClusterId != null;
+    }
+
     // TODO: make it a singleton class
     public LocationCluster(Location location, long duration) {
         super(location);
-        mIsNewCluster = true;
         addSample(location, duration);
     }
 
@@ -48,60 +59,52 @@ public class LocationCluster extends BaseCluster {
         mLocations.add(location);
     }
 
-    public void consolidate(long interval) {
-        // TODO: add check on interval
+    public void consolidate() {
+        // If there is no new location added during this period, do nothing.
+        if (mLocations.size() == 0) {
+            return;
+        }
+
         double[] newCenter = {0f, 0f, 0f};
         long newDuration = 0l;
-
         // update cluster center
         for (Location location : mLocations) {
             double[] vector = getLocationVector(location);
             long duration = location.getTime(); // in seconds
 
+            if (duration == 0) {
+                throw new RuntimeException("location duration is zero");
+            }
+
             newDuration += duration;
-            for (int i = 0; i < 3; ++i) {
+            for (int i = 0; i < VECTOR_LENGTH; ++i) {
                 newCenter[i] += vector[i] * duration;
             }
         }
-        for (int i = 0; i < 3; ++i) {
+        if (newDuration == 0l) {
+            throw new RuntimeException("new duration is zero!");
+        }
+        for (int i = 0; i < VECTOR_LENGTH; ++i) {
             newCenter[i] /= newDuration;
         }
         // remove location data
         mLocations.clear();
 
-        if (mIsNewCluster) {
-            for (int i = 0; i < 3; ++i) {
-                mCenter[i] = newCenter[i];
-            }
-            mDuration = newDuration;
-            mHistogram.clear();
-            mHistogram.putAll(mNewHistogram);
-            mIsNewCluster = false;
-        } else {
-            // the new center is weight average over latest and existing centers.
-            // fine tune the weight of new center
-            double newWeight = ((double) newDuration) / (newDuration + mDuration);
-            double currWeight = 1f - newWeight;
-            double norm = 0;
-            for (int i = 0; i < 3; ++i) {
-                mCenter[i] = currWeight * mCenter[i] + newWeight * newCenter[i];
-                norm += mCenter[i] * mCenter[i];
-            }
-            // normalize
-            for (int i = 0; i < 3; ++i) {
-                mCenter[i] /= norm;
-            }
-            // update histogram
-            for (Map.Entry<String, Long> entry : mNewHistogram.entrySet()) {
-                String timeLabel = entry.getKey();
-                long duration = entry.getValue();
-                if (mHistogram.containsKey(timeLabel)) {
-                    duration += mHistogram.get(timeLabel);
-                }
-                mHistogram.put(timeLabel, duration);
+        // The updated center is the weighted average of the existing and the new
+        // centers. Note that if the cluster is consolidated for the first time,
+        // the weight for the existing cluster would be zero.
+        averageCenter(newCenter, newDuration);
+
+        // update histogram
+        for (Map.Entry<String, Long> entry : mNewHistogram.entrySet()) {
+            String timeLabel = entry.getKey();
+            long duration = entry.getValue();
+            if (mHistogram.containsKey(timeLabel)) {
+                duration += mHistogram.get(timeLabel);
             }
-            mDuration += newDuration;
+            mHistogram.put(timeLabel, duration);
         }
+        mDuration += newDuration;
         mNewHistogram.clear();
     }
 
@@ -110,21 +113,21 @@ public class LocationCluster extends BaseCluster {
      * cluster move the center away from that cluster till there is no overlap.
      */
     public void moveAwayCluster(LocationCluster cluster, float distance) {
-        double[] vector = new double[3];
+        double[] vector = new double[VECTOR_LENGTH];
 
         double dot = 0f;
-        for (int i = 0; i < 3; ++i) {
+        for (int i = 0; i < VECTOR_LENGTH; ++i) {
             dot += mCenter[i] * cluster.mCenter[i];
         }
         double norm = 0f;
-        for (int i = 0; i < 3; ++i) {
+        for (int i = 0; i < VECTOR_LENGTH; ++i) {
             vector[i] = mCenter[i] - dot * cluster.mCenter[i];
             norm += vector[i] * vector[i];
         }
         norm = Math.sqrt(norm);
 
         double radian = distance / EARTH_RADIUS;
-        for (int i = 0; i < 3; ++i) {
+        for (int i = 0; i < VECTOR_LENGTH; ++i) {
             mCenter[i] = cluster.mCenter[i] * Math.cos(radian) +
                     (vector[i] / norm) * Math.sin(radian);
         }
diff --git a/bordeaux/service/src/android/bordeaux/services/SemanticCluster.java b/bordeaux/service/src/android/bordeaux/services/SemanticCluster.java
deleted file mode 100644
index b0d42ab22..000000000
--- a/bordeaux/service/src/android/bordeaux/services/SemanticCluster.java
+++ /dev/null
@@ -1,43 +0,0 @@
-/*
- * Copyright (C) 2012 The Android Open Source Project
- *
- * 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 at
- *
- *      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 android.bordeaux.services;
-
-import android.location.Location;
-import android.text.format.Time;
-import android.util.Log;
-
-import java.lang.Math;
-import java.util.ArrayList;
-import java.util.Map;
-
-public class SemanticCluster extends BaseCluster {
-
-    public static String TAG = "SemanticCluster";
-
-    public SemanticCluster(LocationCluster cluster, long semanticIndex) {
-        mCenter = new double[3];
-        for (int i = 0; i < 3; ++i) {
-            mCenter[i] = cluster.mCenter[i];
-        }
-        generateSemanticId(semanticIndex);
-    }
-
-    public SemanticCluster(String semanticId, double longitude, double latitude) {
-        setSemanticId(semanticId);
-
-        mCenter = getLocationVector(longitude, latitude);
-    }
-}