path: root/bordeaux/service/src/android/bordeaux/services/ClusterManager.java

/*
 * 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.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
 * stream. Clusters are updated online using leader based clustering algorithm. The input
 * locations initially are kept by the clusters. Periodially, a cluster consolidating
 * procedure is carried out to refine the cluster centers. After consolidation, the
 * location data are released.
 */
public class ClusterManager {

    private static String TAG = "ClusterManager";

    private static float LOCATION_CLUSTER_RADIUS = 25; // meter

    private static float SEMANTIC_CLUSTER_RADIUS = 75; // meter

    // Consoliate location clusters (and check for new semantic clusters)
    // 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 24 hours (86400 seconds).
    private static final long LOCATION_REFRESH_PERIOD = 86400; // seconds

    private static String UNKNOWN_LOCATION = "Unknown Location";

    private Location mLastLocation = null;

    private long mClusterDuration;

    private long mConsolidateRef = 0;

    private long mRefreshRef = 0;

    private long mSemanticClusterCount = 0;

    private ArrayList<LocationCluster> mLocationClusters = new ArrayList<LocationCluster>();

    private ArrayList<BaseCluster> mSemanticClusters = new ArrayList<BaseCluster>();

    private AggregatorRecordStorage mStorage;

    private static String SEMANTIC_TABLE = "SemanticTable";

    private static String SEMANTIC_ID = "ID";

    private static final String SEMANTIC_LONGITUDE = "Longitude";

    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,
                      TimeStatsAggregator.NOON,
                      TimeStatsAggregator.AFTERNOON,
                      TimeStatsAggregator.EVENING,
                      TimeStatsAggregator.NIGHT,
                      TimeStatsAggregator.LATENIGHT };

    private static final int mFeatureValueStart = 4;
    private static final int mFeatureValueEnd = 11;

    public ClusterManager(Context context) {
        mStorage = new AggregatorRecordStorage(context, SEMANTIC_TABLE, SEMANTIC_COLUMNS);

        loadSemanticClusters();
    }

    public void addSample(Location location) {
        float bestClusterDistance = Float.MAX_VALUE;
        int bestClusterIndex = -1;
        long lastDuration;
        long currentTime = location.getTime() / 1000; // measure time in seconds

        if (mLastLocation != null) {
            if (location.getTime() == mLastLocation.getTime()) {
                return;
            }
            // get the duration spent in the last location
            long duration = (location.getTime() - mLastLocation.getTime()) / 1000;
            mClusterDuration += duration;

            Log.v(TAG, "sample duration: " + duration +
                  ", number of clusters: " + mLocationClusters.size());

            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);
                  mLocationClusters.add(cluster);
                }
            }
        } else {
            mConsolidateRef = currentTime;
            mRefreshRef = currentTime;

            if (mLocationClusters.isEmpty()) {
                mClusterDuration = 0;
            }
        }

        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();
            mConsolidateRef = currentTime;

            long refreshDuration = currentTime - mRefreshRef;
            Log.v(TAG, "refresh duration: " + refreshDuration);
            if (refreshDuration >  LOCATION_REFRESH_PERIOD) {
                updateSemanticClusters();
                mRefreshRef = currentTime;
            }
            saveSemanticClusters();
        }

        mLastLocation = location;
    }

    private void consolidateClusters() {
        synchronized (mSemanticClusters) {
            LocationCluster locationCluster;
            for (int i = mLocationClusters.size() - 1; i >= 0; --i) {
                locationCluster = mLocationClusters.get(i);
                locationCluster.consolidate();
            }

            // 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;
                }

                // 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());

                    if (distance < bestClusterDistance) {
                        bestClusterDistance = distance;
                        bestClusterId = cluster.getSemanticId();
                    }
                }

                // 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);
                }
            }
            Log.v(TAG, mSemanticClusters.size() + " semantic clusters after consolidate");
        }
    }

    private void updateSemanticClusters() {
        synchronized (mSemanticClusters) {
            // 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.hasSemanticClusterId()) {
                    BaseCluster semanticCluster =
                        semanticIdMap.get(cluster.getSemanticClusterId());
                    semanticCluster.absorbCluster(cluster);
                }
            }
            // reset location clusters.
            mLocationClusters.clear();
        }
    }

    private void loadSemanticClusters() {
        List<Map<String, String> > allData = mStorage.getAllData();
        HashMap<String, Long> histogram = new HashMap<String, Long>();

        synchronized (mSemanticClusters) {
            mSemanticClusters.clear();
            for (Map<String, String> map : allData) {
                String semanticId = map.get(SEMANTIC_ID);
                double longitude = Double.parseDouble(map.get(SEMANTIC_LONGITUDE));
                double latitude = Double.parseDouble(map.get(SEMANTIC_LATITUDE));
                long duration = Long.parseLong(map.get(SEMANTIC_DURATION));
                BaseCluster cluster =
                    new BaseCluster(semanticId, longitude, latitude, duration);

                histogram.clear();
                for (int i = mFeatureValueStart; i <= mFeatureValueEnd; i++) {
                    String featureValue = SEMANTIC_COLUMNS[i];
                    if (map.containsKey(featureValue)) {
                      histogram.put(featureValue, Long.valueOf(map.get(featureValue)));
                    }
                }
                cluster.setHistogram(histogram);
                mSemanticClusters.add(cluster);
            }
            mSemanticClusterCount = mSemanticClusters.size();
            Log.e(TAG, "load " + mSemanticClusterCount + " semantic clusters.");
        }
    }

    private void saveSemanticClusters() {
        HashMap<String, String> rowFeatures = new HashMap<String, String>();

        mStorage.removeAllData();
        synchronized (mSemanticClusters) {
            for (BaseCluster 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()));
                rowFeatures.put(SEMANTIC_DURATION,
                            String.valueOf(cluster.getDuration()));

                HashMap<String, Long> histogram = cluster.getHistogram();
                for (Map.Entry<String, Long> entry : histogram.entrySet()) {
                    rowFeatures.put(entry.getKey(), String.valueOf(entry.getValue()));
                }
                mStorage.addData(rowFeatures);
                Log.e(TAG, "saving semantic cluster: " + rowFeatures);
            }
        }
    }

    public String getSemanticLocation() {
        String label = LocationStatsAggregator.UNKNOWN_LOCATION;

        // instead of using the last location, try acquiring the latest location.
        if (mLastLocation != null) {
            // TODO: use fast neatest neighbor search speed up location search
            synchronized (mSemanticClusters) {
                for (BaseCluster cluster: mSemanticClusters) {
                    if (cluster.distanceToCenter(mLastLocation) < SEMANTIC_CLUSTER_RADIUS) {
                        return cluster.getSemanticId();
                    }
                }
            }
        }
        return label;
    }

    public List<String> getClusterNames() {
        ArrayList<String> clusters = new ArrayList<String>();
        synchronized (mSemanticClusters) {
            for (BaseCluster cluster: mSemanticClusters) {
                clusters.add(cluster.getSemanticId());
            }
        }
        return clusters;
    }
}