revise loation clustering :

1. add temporal histogram to clusters
2. load and save semantic clusters
3. tune up semantic clustering module

Change-Id: I1ab1d06603c818181c4182795630dbc1438c0e32

10 files changed, 351 insertions, 201 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 d79afc548..e9490ce7f 100644
--- a/bordeaux/learning/predictor_histogram/java/android/bordeaux/learning/HistogramPredictor.java
+++ b/bordeaux/learning/predictor_histogram/java/android/bordeaux/learning/HistogramPredictor.java
@@ -43,7 +43,8 @@ import java.util.Map.Entry;
  * The first level key is the feature value and the second level key is the app id.
  */
 
-// TODO: Use Parceable or Serializable to load and save this class
+// TODO: use forgetting factor to downweight istances propotional to the time
+// difference between the occurrance and now.
 public class HistogramPredictor {
     final static String TAG = "HistogramPredictor";
 
diff --git a/bordeaux/learning/predictor_histogram/java/android/bordeaux/learning/PredictorHist.java b/bordeaux/learning/predictor_histogram/java/android/bordeaux/learning/PredictorHist.java
deleted file mode 100644
index c332be560..000000000
--- a/bordeaux/learning/predictor_histogram/java/android/bordeaux/learning/PredictorHist.java
+++ /dev/null
@@ -1,84 +0,0 @@
-/*
- * Copyright (C) 2011 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.learning;
-
-import java.util.HashMap;
-import java.util.Map;
-import android.util.Log;
-
-/**
- * A simple impelentation of histograms with sparse enteries using HashMap.
- * User can push examples or extract probabilites from this histogram.
- */
-public class PredictorHist {
-    private HashMap<String, Integer> mCountHist;
-    private int mSampleCount;
-    String TAG = "PredicrtHist";
-
-    public PredictorHist() {
-        mCountHist = new HashMap<String, Integer>();
-        mSampleCount = 0;
-    }
-
-    // reset histogram
-    public void resetPredictorHist() {
-        mCountHist.clear();
-        mSampleCount = 0;
-    }
-
-    // getters
-    public final HashMap<String, Integer> getHist() {
-        return mCountHist;
-    }
-
-    public int getHistCounts() {
-        return mSampleCount;
-    }
-
-    //setter
-    public void set(HashMap<String, Integer> hist) {
-        resetPredictorHist();
-        for (Map.Entry<String, Integer> x : hist.entrySet()) {
-            mCountHist.put(x.getKey(), x.getValue());
-            mSampleCount = mSampleCount + x.getValue();
-        }
-    }
-
-    /**
-     * pushes a new example to the histogram
-     */
-    public void pushSample( String fs) {
-        int histValue = 1;
-        if (mCountHist.containsKey(fs)) {
-            histValue = histValue + mCountHist.get(fs);
-        }
-        mCountHist.put(fs,histValue);
-        mSampleCount++;
-    }
-
-    /**
-     * return probabilty of an exmple using the histogram
-     */
-    public float getProbability(String fs) {
-        float res = 0;
-        if (mCountHist.containsKey(fs)) {
-            res = ((float) mCountHist.get(fs)) / ((float)mSampleCount);
-        }
-        return res;
-    }
-}
diff --git a/bordeaux/service/src/android/bordeaux/services/AggregatorRecordStorage.java b/bordeaux/service/src/android/bordeaux/services/AggregatorRecordStorage.java
index 647f638a6..5c407b75d 100644
--- a/bordeaux/service/src/android/bordeaux/services/AggregatorRecordStorage.java
+++ b/bordeaux/service/src/android/bordeaux/services/AggregatorRecordStorage.java
@@ -90,9 +90,12 @@ class AggregatorRecordStorage extends AggregatorStorage {
     // Return all data as a list of Map.
     // Notice that the column names are repeated for each row.
     public List<Map<String, String>> getAllData() {
-        Cursor cursor = mDatabase.rawQuery("select * from " + mTableName + ";", null);
         ArrayList<Map<String, String> > allData = new ArrayList<Map<String, String> >();
-        if (cursor == null) return allData;
+
+        Cursor cursor = mDatabase.rawQuery("select * from " + mTableName + ";", null);
+        if (cursor.getCount() == 0) {
+            return allData;
+        }
         cursor.moveToFirst();
         do {
             HashMap<String, String> oneRow = new HashMap<String, String>();
diff --git a/bordeaux/service/src/android/bordeaux/services/BaseCluster.java b/bordeaux/service/src/android/bordeaux/services/BaseCluster.java
index 1d595f75a..433bb8771 100644
--- a/bordeaux/service/src/android/bordeaux/services/BaseCluster.java
+++ b/bordeaux/service/src/android/bordeaux/services/BaseCluster.java
@@ -14,27 +14,31 @@
  * 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.HashMap;
+import java.util.Map;
 
 public class BaseCluster {
 
     public static String TAG = "BaseCluster";
 
-    protected double[] mCenter;
+    public double[] mCenter;
+  // protected double[] mCenter;
+
+    // Histogram illustrates the pattern of visit during time of day,
+    protected HashMap<String, Long> mHistogram = new HashMap<String, Long>();
 
     protected long mAvgInterval;
     protected long mDuration;
 
-    protected static final double EARTH_RADIUS = 6378100f;
+    protected String mSemanticId;
 
-    public BaseCluster() {
-    }
+    protected static final double EARTH_RADIUS = 6378100f;
 
     public BaseCluster(Location location, long avgInterval) {
         mAvgInterval = avgInterval;
@@ -43,16 +47,54 @@ public class BaseCluster {
         mDuration = 0;
     }
 
+    public BaseCluster() {
+    }
+
+    public String getSemanticId() {
+        return mSemanticId;
+    }
+
+    protected void generateSemanticId(long index) {
+        mSemanticId = "cluser: " + String.valueOf(index);
+    }
+
+    public void setSemanticId(String semanticId) {
+        mSemanticId = semanticId;
+    }
+
+    public boolean hasSemanticId() {
+        return mSemanticId != null;
+    }
+
     protected double[] getLocationVector(Location location) {
+        return getLocationVector(location.getLongitude(), location.getLatitude());
+    }
+
+    protected double[] getLocationVector(double longitude, double latitude) {
         double vector[] = new double[3];
-        double lambda = Math.toRadians(location.getLongitude());
-        double phi = Math.toRadians(location.getLatitude());
+        double lambda = Math.toRadians(longitude);
+        double phi = Math.toRadians(latitude);
+
         vector[0] = Math.cos(lambda) * Math.cos(phi);
         vector[1] = Math.sin(lambda) * Math.cos(phi);
         vector[2] = Math.sin(phi);
         return vector;
     }
 
+    protected double getCenterLongitude() {
+        // Because latitude ranges from -90 to 90 degrees, cosPhi >= 0.
+        double cosPhi = Math.cos(Math.asin(mCenter[2]));
+        double longitude = Math.toDegrees(Math.asin(mCenter[1] / cosPhi));
+        if (mCenter[0] < 0) {
+            longitude = (longitude > 0) ? 180f - longitude : -180 - longitude;
+        }
+        return longitude;
+    }
+
+    protected double getCenterLatitude() {
+        return Math.toDegrees(Math.asin(mCenter[2]));
+    }
+
     private double computeDistance(double[] vector1, double[] vector2) {
         double product = 0f;
         for (int i = 0; i < 3; ++i) {
@@ -79,6 +121,7 @@ public class BaseCluster {
                     "aborbing cluster failed: inconsistent average invergal ");
         }
 
+        // the new cluster center is the average of the two clusters.
         double currWeight = ((double) mDuration) / (mDuration + cluster.mDuration);
         double newWeight = 1f - currWeight;
         double norm = 0;
@@ -86,10 +129,32 @@ public class BaseCluster {
             mCenter[i] = currWeight * mCenter[i] + newWeight * cluster.mCenter[i];
             norm += mCenter[i] * mCenter[i];
         }
-        // normalize
+        // normalize the center to be unit vector
         for (int i = 0; i < 3; ++i) {
             mCenter[i] /= norm;
         }
+        absorbHistogram(cluster);
+    }
+
+    public void setCluster(BaseCluster cluster) {
+        for (int i = 0; i < 3; ++i) {
+            mCenter[i] = cluster.mCenter[i];
+        }
+        mHistogram.clear();
+        mHistogram.putAll(cluster.mHistogram);
+        mDuration = cluster.mDuration;
+    }
+
+    private void absorbHistogram(BaseCluster cluster) {
+        for (Map.Entry<String, Long> entry : cluster.mHistogram.entrySet()) {
+            String timeLabel = entry.getKey();
+            long duration = entry.getValue();
+
+            if (mHistogram.containsKey(timeLabel)) {
+                duration += mHistogram.get(timeLabel);
+            }
+            mHistogram.put(timeLabel, duration);
+        }
         mDuration += cluster.mDuration;
     }
 
diff --git a/bordeaux/service/src/android/bordeaux/services/BordeauxPredictor.java b/bordeaux/service/src/android/bordeaux/services/BordeauxPredictor.java
index 54d96a2c3..4e0223fa7 100644
--- a/bordeaux/service/src/android/bordeaux/services/BordeauxPredictor.java
+++ b/bordeaux/service/src/android/bordeaux/services/BordeauxPredictor.java
@@ -97,8 +97,6 @@ public class BordeauxPredictor {
             for (int i = 0; i < topList.size(); ++i) {
                 topSamples.add(new Pair<String, Float>(topList.get(i).key, topList.get(i).value));
             }
-            Log.e(TAG, "getTopSamples: " + topSamples);
-
             return topSamples;
         } catch(RemoteException e) {
             Log.e(TAG,"Exception: getTopSamples");
diff --git a/bordeaux/service/src/android/bordeaux/services/ClusterManager.java b/bordeaux/service/src/android/bordeaux/services/ClusterManager.java
index 88ba1f3ab..625f5ad4b 100644
--- a/bordeaux/service/src/android/bordeaux/services/ClusterManager.java
+++ b/bordeaux/service/src/android/bordeaux/services/ClusterManager.java
@@ -16,12 +16,16 @@
 
 package android.bordeaux.services;
 
+import android.content.Context;
 import android.location.Location;
 import android.text.format.Time;
 import android.util.Log;
 
 import java.util.ArrayList;
+import java.util.HashMap;
 import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
 
 /**
  * ClusterManager incrementally indentify representitve clusters from the input location
@@ -38,11 +42,17 @@ public class ClusterManager {
 
     private static float SEMANTIC_CLUSTER_RADIUS = 50; // meter
 
-    private static long CONSOLIDATE_INTERVAL = 90000; // is milliseconds
+    private static long CONSOLIDATE_INTERVAL = 21600000; //
 
-    private static long LOCATION_CLUSTER_THRESHOLD = 1000; // in milliseconds
+    private static long LOCATION_CLUSTER_THRESHOLD = 180000; // in milliseconds
 
-    private static long SEMANTIC_CLUSTER_THRESHOLD = 30000; // in milliseconds
+    private static long SEMANTIC_CLUSTER_THRESHOLD = 1800000; // in milliseconds
+
+    private static String UNKNOWN_LOCATION = "Unknown Location";
+
+    private static String HOME = "Home";
+
+    private static String OFFICE = "Office";
 
     private Location mLastLocation = null;
 
@@ -54,7 +64,23 @@ public class ClusterManager {
 
     private ArrayList<SemanticCluster> mSemanticClusters = new ArrayList<SemanticCluster>();
 
-    public ClusterManager() {
+    private AggregatorRecordStorage mStorage;
+
+    private static String SEMANTIC_TABLE = "SemanticTable";
+
+    private static String SEMANTIC_ID = "ID";
+
+    private static String SEMANTIC_LONGITUDE = "Longitude";
+
+    private static String SEMANTIC_LATITUDE = "Latitude";
+
+    private static String[] SEMANTIC_COLUMNS =
+            new String[]{ SEMANTIC_ID, SEMANTIC_LONGITUDE, SEMANTIC_LATITUDE};
+
+    public ClusterManager(Context context) {
+        mStorage = new AggregatorRecordStorage(context, SEMANTIC_TABLE, SEMANTIC_COLUMNS);
+
+        loadSemanticClusters();
     }
 
     public void addSample(Location location) {
@@ -66,8 +92,6 @@ public class ClusterManager {
         if (mLastLocation != null) {
             // get the duration spent in the last location
             long duration = location.getTime() - mLastLocation.getTime();
-            // TODO: set duration is a separate field
-            mLastLocation.setTime(duration);
             Log.v(TAG, "sample duration: " + duration +
                   ", number of clusters: " + mLocClusters.size());
 
@@ -84,16 +108,17 @@ public class ClusterManager {
 
             // add the location to the selected cluster
             if (bestClusterDistance < LOCATION_CLUSTER_RADIUS) {
-              Log.v(TAG, "add sample to cluster: " + bestClusterIndex + ",( " +
+                Log.v(TAG, "add sample to cluster: " + bestClusterIndex + ",( " +
                     location.getLongitude() + ", " + location.getLatitude() + ")");
-                mLocClusters.get(bestClusterIndex).addSample(mLastLocation);
+                mLocClusters.get(bestClusterIndex).addSample(mLastLocation, duration);
             } else {
                 // if it is far away from all existing clusters, create a new cluster.
                 LocationCluster cluster =
-                        new LocationCluster(mLastLocation, CONSOLIDATE_INTERVAL);
+                    new LocationCluster(mLastLocation, duration, CONSOLIDATE_INTERVAL);
                 // move the center of the new cluster if its covering region overlaps
                 // with an existing cluster.
                 if (bestClusterDistance < 2 * LOCATION_CLUSTER_RADIUS) {
+                    Log.e(TAG, "move away activated");
                     cluster.moveAwayCluster(mLocClusters.get(bestClusterIndex),
                             ((float) 2 * LOCATION_CLUSTER_RADIUS));
                 }
@@ -124,10 +149,8 @@ public class ClusterManager {
     }
 
     private void consolidateClusters(long duration) {
-        Log.e(TAG, "considalating " + mLocClusters.size() + " clusters");
         LocationCluster cluster;
 
-        // TODO: which should be first? considate or merge?
         for (int i = mLocClusters.size() - 1; i >= 0; --i) {
             cluster = mLocClusters.get(i);
             cluster.consolidate(duration);
@@ -140,7 +163,7 @@ public class ClusterManager {
         }
 
         // merge clusters whose regions are overlapped. note that after merge
-        // translates the cluster center but keeps the region size unchanged.
+        // cluster center changes but cluster size remains unchanged.
         for (int i = mLocClusters.size() - 1; i >= 0; --i) {
             cluster = mLocClusters.get(i);
             for (int j = i - 1; j >= 0; --j) {
@@ -151,10 +174,58 @@ public class ClusterManager {
                 }
             }
         }
+
         updateSemanticClusters();
+
+        saveSemanticClusters();
+    }
+
+
+    private void loadSemanticClusters() {
+        List<Map<String, String> > allData = mStorage.getAllData();
+
+        mSemanticClusters.clear();
+        for (Map<String, String> map : allData) {
+            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, CONSOLIDATE_INTERVAL);
+            mSemanticClusters.add(cluster);
+        }
+
+        mSemanticClusterCount = mSemanticClusters.size();
+        Log.e(TAG, "load " + mSemanticClusterCount + " semantic clusters.");
+    }
+
+    private void saveSemanticClusters() {
+        HashMap<String, String> rowFeatures = new HashMap<String, String>();
+        Log.e(TAG, "save " + mSemanticClusters.size() + " semantic clusters.");
+
+        mStorage.removeAllData();
+        for (SemanticCluster cluster : mSemanticClusters) {
+            rowFeatures.clear();
+            rowFeatures.put(SEMANTIC_ID, cluster.getSemanticId());
+
+            rowFeatures.put(SEMANTIC_LONGITUDE,
+                            String.valueOf(cluster.getCenterLongitude()));
+            rowFeatures.put(SEMANTIC_LATITUDE,
+                            String.valueOf(cluster.getCenterLatitude()));
+            mStorage.addData(rowFeatures);
+        }
     }
 
     private void updateSemanticClusters() {
+
+        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);
+        }
+
         // select candidate location clusters
         ArrayList<LocationCluster> candidates = new ArrayList<LocationCluster>();
         for (LocationCluster cluster : mLocClusters) {
@@ -162,12 +233,19 @@ public class ClusterManager {
                 candidates.add(cluster);
             }
         }
+
+        // assign each candidate to a semantic cluster
         for (LocationCluster candidate : candidates) {
+            if (candidate.hasSemanticId()) {
+                // candidate has been assigned to a semantic cluster
+                continue;
+            }
+
+            // find the closest semantic cluster
             float bestClusterDistance = Float.MAX_VALUE;
             SemanticCluster bestCluster = null;
             for (SemanticCluster cluster : mSemanticClusters) {
                 float distance = cluster.distanceToCluster(candidate);
-
                 Log.e(TAG, "distance to semantic cluster: " + cluster.getSemanticId());
 
                 if (distance < bestClusterDistance) {
@@ -178,24 +256,45 @@ public class ClusterManager {
 
             // add the location to the selected cluster
             SemanticCluster semanticCluster;
-            if (bestClusterDistance < SEMANTIC_CLUSTER_RADIUS) {
-                bestCluster.absorbCluster(candidate);
-            } else {
+            if (bestClusterDistance > SEMANTIC_CLUSTER_RADIUS) {
                 // if it is far away from all existing clusters, create a new cluster.
-                semanticCluster = new SemanticCluster(candidate, CONSOLIDATE_INTERVAL,
-                        mSemanticClusterCount++);
-                mSemanticClusters.add(semanticCluster);
+                bestCluster = new SemanticCluster(candidate, CONSOLIDATE_INTERVAL,
+                                                  mSemanticClusterCount++);
+                String id = bestCluster.getSemanticId();
+                semanticMap.put(id, new ArrayList<BaseCluster>());
+                semanticMap.get(id).add(bestCluster);
             }
+            String semanticId = bestCluster.getSemanticId();
+            candidate.setSemanticId(semanticId);
+            semanticMap.get(semanticId).add(candidate);
         }
-        Log.e(TAG, "location: " + candidates.size() + ", semantic: " + mSemanticClusters.size());
-
         candidates.clear();
+        Log.e(TAG, "number of semantic clusters: " + semanticMap.size());
+
+        // use candidates semantic cluster
+        mSemanticClusters.clear();
+        for (ArrayList<BaseCluster> clusterList : semanticMap.values()) {
+            SemanticCluster semanticCluster = (SemanticCluster) clusterList.get(0);
+
+            Log.e(TAG, "id: " + semanticCluster.getSemanticId() + ", list size: " +
+                clusterList.size());
+
+            if (clusterList.size() > 1) {
+                // cluster with no new candidate
+                semanticCluster.setCluster(clusterList.get(1));
+                for (int i = 2; i < clusterList.size(); i++) {
+                    semanticCluster.absorbCluster(clusterList.get(i));
+                }
+            }
+            mSemanticClusters.add(semanticCluster);
+        }
     }
 
     public String getSemanticLocation() {
-        String label = "unknown";
+        String label = UNKNOWN_LOCATION;
 
         if (mLastLocation != null) {
+            // TODO: use fast neatest neighbor search speed up location search
             for (SemanticCluster cluster: mSemanticClusters) {
                 if (cluster.distanceToCenter(mLastLocation) < SEMANTIC_CLUSTER_RADIUS) {
                     return cluster.getSemanticId();
diff --git a/bordeaux/service/src/android/bordeaux/services/LocationCluster.java b/bordeaux/service/src/android/bordeaux/services/LocationCluster.java
index 9745d1314..2797e18b1 100644
--- a/bordeaux/service/src/android/bordeaux/services/LocationCluster.java
+++ b/bordeaux/service/src/android/bordeaux/services/LocationCluster.java
@@ -21,6 +21,8 @@ import android.util.Log;
 
 import java.lang.Math;
 import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.Map;
 
 public class LocationCluster extends BaseCluster {
     public static String TAG = "LocationCluster";
@@ -30,13 +32,21 @@ public class LocationCluster extends BaseCluster {
     private boolean mIsNewCluster;
 
     private ArrayList<Location> mLocations = new ArrayList<Location>();
+    private HashMap<String, Long> mNewHistogram = new HashMap<String, Long>();
 
-    public LocationCluster(Location location, long avgInterval) {
+    // TODO: make it a singleton class
+    public LocationCluster(Location location, long duration, long avgInterval) {
         super(location, avgInterval);
         mIsNewCluster = true;
+        addSample(location, duration);
     }
 
-    public void addSample(Location location) {
+    public void addSample(Location location, long duration) {
+        updateTemporalHistogram(location.getTime(), duration);
+
+        // use time field to store duation of this location
+        // TODO: extend Location class with additional field for this.
+        location.setTime(duration);
         mLocations.add(location);
     }
 
@@ -66,6 +76,10 @@ public class LocationCluster extends BaseCluster {
                 mCenter[i] = newCenter[i];
             }
             mDuration = newDuration;
+            mHistogram.clear();
+            mHistogram.putAll(mNewHistogram);
+            mNewHistogram.clear();
+
             mIsNewCluster = false;
         } else {
             // the new center is weight average over latest and existing centers.
@@ -82,10 +96,8 @@ public class LocationCluster extends BaseCluster {
             for (int i = 0; i < 3; ++i) {
                 mCenter[i] /= norm;
             }
-
-            newWeight = FORGETTING_FACTOR;
-            currWeight = 1f - newWeight;
-            mDuration = (long) (mDuration * currWeight + newDuration * newWeight);
+            consolidateHistogram(newWeight, newDuration);
+            mNewHistogram.clear();
         }
     }
 
@@ -113,4 +125,44 @@ public class LocationCluster extends BaseCluster {
                     (vector[i] / norm) * Math.sin(radian);
         }
     }
+
+    private void updateTemporalHistogram(long time, long duration) {
+        HashMap<String, String> timeFeatures = TimeStatsAggregator.getAllTimeFeatures(time);
+
+        String timeOfDay = timeFeatures.get(TimeStatsAggregator.TIME_OF_DAY);
+        long totalDuration = (mNewHistogram.containsKey(timeOfDay)) ?
+            mNewHistogram.get(timeOfDay) + duration : duration;
+        mNewHistogram.put(timeOfDay, totalDuration);
+
+        String periodOfDay = timeFeatures.get(TimeStatsAggregator.PERIOD_OF_DAY);
+        totalDuration = (mNewHistogram.containsKey(periodOfDay)) ?
+            mNewHistogram.get(periodOfDay) + duration : duration;
+        mNewHistogram.put(periodOfDay, totalDuration);
+    }
+
+    private void consolidateHistogram(double weight, long newDuration) {
+        long base = 1000;
+        long newWeight = (long) (weight * base);
+        long currWeight = base - newWeight;
+
+        for (Map.Entry<String, Long> entry : mHistogram.entrySet()) {
+            String timeLabel = entry.getKey();
+            long duration = entry.getValue() * currWeight;
+            if (mNewHistogram.containsKey(timeLabel)) {
+                duration += mNewHistogram.get(timeLabel) * newWeight;
+            }
+            duration /= base;
+            mHistogram.put(timeLabel, duration);
+        }
+
+        for (Map.Entry<String, Long> entry : mNewHistogram.entrySet()) {
+            String timeLabel = entry.getKey();
+            if (!mHistogram.containsKey(timeLabel)) {
+                long duration = newWeight * entry.getValue();
+                duration /= base;
+                mHistogram.put(timeLabel, duration);
+            }
+        }
+        mDuration = (mDuration * currWeight + newDuration * newWeight) / base;
+    }
 }
diff --git a/bordeaux/service/src/android/bordeaux/services/LocationStatsAggregator.java b/bordeaux/service/src/android/bordeaux/services/LocationStatsAggregator.java
index d6512cb24..165fb28ec 100644
--- a/bordeaux/service/src/android/bordeaux/services/LocationStatsAggregator.java
+++ b/bordeaux/service/src/android/bordeaux/services/LocationStatsAggregator.java
@@ -31,51 +31,62 @@ import android.util.Log;
 import java.util.HashMap;
 import java.util.Map;
 
+// TODO: add functionality to detect speed (use GPS) when needed
+// withouth draining the battery quickly
 public class LocationStatsAggregator extends Aggregator {
     final String TAG = "LocationStatsAggregator";
     public static final String CURRENT_LOCATION = "Current Location";
+    public static final String CURRENT_SPEED = "Current Speed";
+
+    // TODO: Collect location on every minute
+    private static final long MINIMUM_TIME = 60000; // milliseconds
+
+    // reset best location provider on every 5 minutes
+    private static final int BEST_PROVIDER_DURATION = 300000;
 
-    private static final long MINIMUM_TIME = 30000; // milliseconds
     private static final float MINIMUM_DISTANCE = 0f; // meter
-    private static final int LOCATION_CHANGE = 1;
 
-    private static final int BEST_PROVIDER_DURATION = 120000;
+    private static final int LOCATION_CHANGE = 1;
 
+    // record time when the location provider is set
     private long mProviderSetTime;
 
-    private final Criteria mCriteria = new Criteria();
-
     private Handler mHandler;
     private HandlerThread mHandlerThread;
     private LocationManager mLocationManager;
     private ClusterManager mClusterManager;
 
     public LocationStatsAggregator(final Context context) {
-
-        Log.e(TAG, "initialize location manager");
-
-        mLocationManager = (LocationManager) context.getSystemService(Context.LOCATION_SERVICE);
-        setClusteringThread();
-
+        mLocationManager =
+            (LocationManager) context.getSystemService(Context.LOCATION_SERVICE);
+        setClusteringThread(context);
         requestLocationUpdate();
     }
 
     public String[] getListOfFeatures(){
-        String [] list = new String[1];
-        list[0] = CURRENT_LOCATION;
+        String[] list = { CURRENT_LOCATION } ;
         return list;
     }
 
     public Map<String,String> getFeatureValue(String featureName) {
         HashMap<String,String> feature = new HashMap<String,String>();
+
         if (featureName.equals(CURRENT_LOCATION)) {
-            feature.put(CURRENT_LOCATION, mClusterManager.getSemanticLocation());
+
+          // TODO: check last known location first before sending out location request.
+          /*
+            Location location =
+                mLocationManager.getLastKnownLocation(LocationManager.GPS_PROVIDER);
+          */
+
+          // TODO: instead of outputing "unknow" should just not output anything.
+          feature.put(CURRENT_LOCATION, mClusterManager.getSemanticLocation());
         }
         return (Map) feature;
     }
 
-    private void setClusteringThread() {
-        mClusterManager = new ClusterManager();
+    private void setClusteringThread(Context context) {
+        mClusterManager = new ClusterManager(context);
 
         mHandlerThread = new HandlerThread("Location Handler",
                 Process.THREAD_PRIORITY_BACKGROUND);
@@ -103,18 +114,23 @@ public class LocationStatsAggregator extends Aggregator {
         Criteria criteria = new Criteria();
         criteria.setAccuracy(Criteria.ACCURACY_COARSE);
         criteria.setPowerRequirement(Criteria.POWER_LOW);
+        /*
         criteria.setAltitudeRequired(false);
         criteria.setBearingRequired(false);
-        criteria.setSpeedRequired(false);
+        criteria.setSpeedRequired(true);
+        */
         criteria.setCostAllowed(true);
 
-        String bestProvider = mLocationManager.getBestProvider(criteria, true);
+        String bestProvider = mLocationManager.getBestProvider(criteria, false);
         Log.i(TAG, "Best Location Provider: " + bestProvider);
 
+        String bestAvailableProvider = mLocationManager.getBestProvider(criteria, true);
+        Log.i(TAG, "Best Available Location Provider: " + bestAvailableProvider);
+
         mProviderSetTime = System.currentTimeMillis();
-        if (bestProvider != null) {
+        if (bestAvailableProvider != null) {
             mLocationManager.requestLocationUpdates(
-                bestProvider, MINIMUM_TIME, MINIMUM_DISTANCE, mLocationListener);
+                bestAvailableProvider, MINIMUM_TIME, MINIMUM_DISTANCE, mLocationListener);
         }
     }
 
diff --git a/bordeaux/service/src/android/bordeaux/services/SemanticCluster.java b/bordeaux/service/src/android/bordeaux/services/SemanticCluster.java
index cfc028c7f..222111d3a 100644
--- a/bordeaux/service/src/android/bordeaux/services/SemanticCluster.java
+++ b/bordeaux/service/src/android/bordeaux/services/SemanticCluster.java
@@ -26,24 +26,20 @@ public class SemanticCluster extends BaseCluster {
 
     public static String TAG = "SemanticCluster";
 
-    private String mSemanticId;
-
     public SemanticCluster(LocationCluster cluster, long avgInterval, long semanticIndex) {
         mCenter = new double[3];
         for (int i = 0; i < 3; ++i) {
             mCenter[i] = cluster.mCenter[i];
         }
-        mDuration = cluster.mDuration;
         mAvgInterval = avgInterval;
-
-        setSemanticId(semanticIndex);
+        generateSemanticId(semanticIndex);
     }
 
-    public String getSemanticId() {
-        return mSemanticId;
-    }
+    public SemanticCluster(String semanticId, double longitude, double latitude,
+                           long avgInterval) {
+        setSemanticId(semanticId);
+        mAvgInterval = avgInterval;
 
-    private void setSemanticId(long index) {
-        mSemanticId = "cluser: " + String.valueOf(index);
+        mCenter = getLocationVector(longitude, latitude);
     }
 }
diff --git a/bordeaux/service/src/android/bordeaux/services/TimeStatsAggregator.java b/bordeaux/service/src/android/bordeaux/services/TimeStatsAggregator.java
index 377d9c3f3..2b94cd44b 100644
--- a/bordeaux/service/src/android/bordeaux/services/TimeStatsAggregator.java
+++ b/bordeaux/service/src/android/bordeaux/services/TimeStatsAggregator.java
@@ -39,7 +39,7 @@ public class TimeStatsAggregator extends Aggregator {
     static final String MONDAY = "Monday";
     static final String TUESDAY = "Tuesday";
     static final String WEDNESDAY = "Wednesday";
-    static final String THURSDAY = "Tuesday";
+    static final String THURSDAY = "Thursday";
     static final String FRIDAY = "Friday";
     static final String SATURDAY = "Saturday";
     static final String SUNDAY = "Sunday";
@@ -52,9 +52,6 @@ public class TimeStatsAggregator extends Aggregator {
     static final String DAYTIME = "Daytime";
     static final String NIGHTTIME = "Nighttime";
 
-    final Time mTime = new Time();
-    final HashMap<String, String> mFeatures = new HashMap<String, String>();
-
     public String[] getListOfFeatures(){
         String [] list = new String[4];
         list[0] = TIME_OF_WEEK;
@@ -67,69 +64,76 @@ public class TimeStatsAggregator extends Aggregator {
     public Map<String,String> getFeatureValue(String featureName) {
         HashMap<String,String> feature = new HashMap<String,String>();
 
-        updateFeatures();
-        if (mFeatures.containsKey(featureName)) {
-          feature.put(featureName, mFeatures.get(featureName));
+        HashMap<String, String> features =
+            getAllTimeFeatures(System.currentTimeMillis());
+        if (features.containsKey(featureName)) {
+            feature.put(featureName, features.get(featureName));
         } else {
             Log.e(TAG, "There is no Time feature called " + featureName);
         }
         return (Map)feature;
     }
 
-    private void updateFeatures() {
-        mFeatures.clear();
-        mTime.set(System.currentTimeMillis());
+    private static String getTimeOfDay(int hour) {
+        if (hour >= 5 && hour < 11) {
+            return MORNING;
+        } else if (hour >= 11 && hour < 14) {
+            return NOON;
+        } else if (hour >= 14 && hour < 18) {
+            return AFTERNOON;
+        } else if (hour >= 18 && hour < 21) {
+            return EVENING;
+        } else if ((hour >= 21 && hour < 24) ||
+                   (hour >= 0 && hour < 1))  {
+            return NIGHT;
+        } else {
+            return LATENIGHT;
+        }
+    }
 
-        switch (mTime.weekDay) {
+    private static String getDayOfWeek(int day) {
+        switch (day) {
             case Time.SATURDAY:
-                mFeatures.put(DAY_OF_WEEK, SATURDAY);
-                break;
+                return SATURDAY;
             case Time.SUNDAY:
-                mFeatures.put(DAY_OF_WEEK, SUNDAY);
-                break;
+                return SUNDAY;
             case Time.MONDAY:
-                mFeatures.put(DAY_OF_WEEK, MONDAY);
-                break;
+                return MONDAY;
             case Time.TUESDAY:
-                mFeatures.put(DAY_OF_WEEK, TUESDAY);
-                break;
+                return TUESDAY;
             case Time.WEDNESDAY:
-                mFeatures.put(DAY_OF_WEEK, WEDNESDAY);
-                break;
+                return WEDNESDAY;
             case Time.THURSDAY:
-                mFeatures.put(DAY_OF_WEEK, THURSDAY);
-                break;
+                return THURSDAY;
             default:
-                mFeatures.put(DAY_OF_WEEK, FRIDAY);
+                return FRIDAY;
         }
+    }
 
-        if (mTime.hour > 6 && mTime.hour < 19) {
-            mFeatures.put(PERIOD_OF_DAY, DAYTIME);
+    private static String getPeriodOfDay(int hour) {
+        if (hour > 6 && hour < 19) {
+            return DAYTIME;
         } else {
-            mFeatures.put(PERIOD_OF_DAY, NIGHTTIME);
+            return NIGHTTIME;
         }
+    }
 
-        if (mTime.hour >= 5 && mTime.hour < 12) {
-            mFeatures.put(TIME_OF_DAY, MORNING);
-        } else if (mTime.hour >= 12 && mTime.hour < 14) {
-            mFeatures.put(TIME_OF_DAY, NOON);
-        } else if (mTime.hour >= 14 && mTime.hour < 18) {
-            mFeatures.put(TIME_OF_DAY, AFTERNOON);
-        } else if (mTime.hour >= 18 && mTime.hour < 22) {
-            mFeatures.put(TIME_OF_DAY, EVENING);
-        } else if ((mTime.hour >= 22 && mTime.hour < 24) ||
-                   (mTime.hour >= 0 && mTime.hour < 1))  {
-            mFeatures.put(TIME_OF_DAY, NIGHT);
-        } else {
-            mFeatures.put(TIME_OF_DAY, LATENIGHT);
-        }
+    static HashMap<String, String> getAllTimeFeatures(long utcTime) {
+        HashMap<String, String> features = new HashMap<String, String>();
+        Time time = new Time();
+        time.set(utcTime);
+
+        features.put(DAY_OF_WEEK, getDayOfWeek(time.weekDay));
+        features.put(PERIOD_OF_DAY, getPeriodOfDay(time.hour));
+        features.put(TIME_OF_DAY, getTimeOfDay(time.hour));
 
-        if (mTime.weekDay == Time.SUNDAY || mTime.weekDay == Time.SATURDAY ||
-                (mTime.weekDay == Time.FRIDAY &&
-                mFeatures.get(PERIOD_OF_DAY).equals(NIGHTTIME))) {
-            mFeatures.put(TIME_OF_WEEK, WEEKEND);
+        if (time.weekDay == Time.SUNDAY || time.weekDay == Time.SATURDAY ||
+                (time.weekDay == Time.FRIDAY &&
+                features.get(PERIOD_OF_DAY).equals(NIGHTTIME))) {
+            features.put(TIME_OF_WEEK, WEEKEND);
         } else {
-            mFeatures.put(TIME_OF_WEEK, WEEKDAY);
+            features.put(TIME_OF_WEEK, WEEKDAY);
         }
+        return features;
     }
 }