bordeaux/services/LocationCluster.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.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 LocationCluster extends BaseCluster {
    public static String TAG = "LocationCluster";

    private static double FORGETTING_FACTOR = 0.1;

    private boolean mIsNewCluster;

    private ArrayList<Location> mLocations = new ArrayList<Location>();
    private HashMap<String, Long> mNewHistogram = new HashMap<String, Long>();

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

    public void consolidate(long interval) {
        // TODO: add check on interval
        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

            newDuration += duration;
            for (int i = 0; i < 3; ++i) {
                newCenter[i] += vector[i] * duration;
            }
        }
        for (int i = 0; i < 3; ++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);
            mNewHistogram.clear();

            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);
            newWeight *= FORGETTING_FACTOR;
            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;
            }
            consolidateHistogram(newWeight, newDuration);
            mNewHistogram.clear();
        }
    }

    /*
     * if the new created cluster whose covered area overlaps with any existing
     * 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 dot = 0f;
        for (int i = 0; i < 3; ++i) {
            dot += mCenter[i] * cluster.mCenter[i];
        }
        double norm = 0f;
        for (int i = 0; i < 3; ++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) {
            mCenter[i] = cluster.mCenter[i] * Math.cos(radian) +
                    (vector[i] / norm) * Math.sin(radian);
        }
    }

    private void updateTemporalHistogram(long time, long duration) {
        HashMap<String, String> timeFeatures = TimeStatsAggregator.getAllTimeFeatures(time);

        String timeOfWeek = timeFeatures.get(TimeStatsAggregator.TIME_OF_WEEK);
        long totalDuration = (mNewHistogram.containsKey(timeOfWeek)) ?
            mNewHistogram.get(timeOfWeek) + duration : duration;
        mNewHistogram.put(timeOfWeek, totalDuration);

        String timeOfDay = timeFeatures.get(TimeStatsAggregator.TIME_OF_DAY);
        totalDuration = (mNewHistogram.containsKey(timeOfDay)) ?
            mNewHistogram.get(timeOfDay) + duration : duration;
        mNewHistogram.put(timeOfDay, 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;
    }
}