1f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin/* 2f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * Copyright (C) 2012 The Android Open Source Project 3f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * 4f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * Licensed under the Apache License, Version 2.0 (the "License"); 5f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * you may not use this file except in compliance with the License. 6f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * You may obtain a copy of the License at 7f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * 8f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * http://www.apache.org/licenses/LICENSE-2.0 9f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * 10f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * Unless required by applicable law or agreed to in writing, software 11f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * distributed under the License is distributed on an "AS IS" BASIS, 12f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * See the License for the specific language governing permissions and 14f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * limitations under the License. 15f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin */ 16f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linpackage android.bordeaux.services; 17f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 18f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linimport android.location.Location; 19f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linimport android.text.format.Time; 20f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linimport android.util.Log; 21f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 22f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linimport java.lang.Math; 23f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linimport java.util.ArrayList; 245d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Linimport java.util.HashMap; 255d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Linimport java.util.Map; 26f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 27f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linpublic class LocationCluster extends BaseCluster { 28f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin public static String TAG = "LocationCluster"; 29f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 30f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin private ArrayList<Location> mLocations = new ArrayList<Location>(); 315d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin private HashMap<String, Long> mNewHistogram = new HashMap<String, Long>(); 32f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 331253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin private String mSemanticClusterId = null; 341253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin 351253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin public void setSemanticClusterId(String semanticClusterId) { 361253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin mSemanticClusterId = semanticClusterId; 371253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin } 381253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin 391253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin public String getSemanticClusterId() { 401253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin return mSemanticClusterId; 411253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin } 421253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin 431253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin public boolean hasSemanticClusterId() { 441253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin return mSemanticClusterId != null; 451253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin } 461253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin 475d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin // TODO: make it a singleton class 4878a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin public LocationCluster(Location location, long duration) { 4978a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin super(location); 505d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin addSample(location, duration); 51f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 52f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 535d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin public void addSample(Location location, long duration) { 545d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin updateTemporalHistogram(location.getTime(), duration); 555d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 565d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin // use time field to store duation of this location 575d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin // TODO: extend Location class with additional field for this. 585d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin location.setTime(duration); 59f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin mLocations.add(location); 60f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 61f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 621253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin public void consolidate() { 631253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // If there is no new location added during this period, do nothing. 641253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin if (mLocations.size() == 0) { 651253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin return; 661253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin } 671253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin 68f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin double[] newCenter = {0f, 0f, 0f}; 69f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin long newDuration = 0l; 70f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin // update cluster center 71f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin for (Location location : mLocations) { 72f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin double[] vector = getLocationVector(location); 7383954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin long duration = location.getTime(); // in seconds 74f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 751253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin if (duration == 0) { 761253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin throw new RuntimeException("location duration is zero"); 771253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin } 781253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin 79f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin newDuration += duration; 801253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin for (int i = 0; i < VECTOR_LENGTH; ++i) { 81f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin newCenter[i] += vector[i] * duration; 82f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 83f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 841253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin if (newDuration == 0l) { 851253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin throw new RuntimeException("new duration is zero!"); 861253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin } 871253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin for (int i = 0; i < VECTOR_LENGTH; ++i) { 88f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin newCenter[i] /= newDuration; 89f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 90f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin // remove location data 91f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin mLocations.clear(); 92f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 931253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // The updated center is the weighted average of the existing and the new 941253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // centers. Note that if the cluster is consolidated for the first time, 951253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // the weight for the existing cluster would be zero. 961253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin averageCenter(newCenter, newDuration); 971253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin 981253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // update histogram 991253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin for (Map.Entry<String, Long> entry : mNewHistogram.entrySet()) { 1001253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin String timeLabel = entry.getKey(); 1011253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin long duration = entry.getValue(); 1021253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin if (mHistogram.containsKey(timeLabel)) { 1031253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin duration += mHistogram.get(timeLabel); 10478a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin } 1051253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin mHistogram.put(timeLabel, duration); 106f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 1071253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin mDuration += newDuration; 10878a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin mNewHistogram.clear(); 109f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 110f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 111f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin /* 112f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * if the new created cluster whose covered area overlaps with any existing 113f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * cluster move the center away from that cluster till there is no overlap. 114f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin */ 115f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin public void moveAwayCluster(LocationCluster cluster, float distance) { 1161253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin double[] vector = new double[VECTOR_LENGTH]; 117f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 118f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin double dot = 0f; 1191253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin for (int i = 0; i < VECTOR_LENGTH; ++i) { 120f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin dot += mCenter[i] * cluster.mCenter[i]; 121f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 122f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin double norm = 0f; 1231253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin for (int i = 0; i < VECTOR_LENGTH; ++i) { 124f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin vector[i] = mCenter[i] - dot * cluster.mCenter[i]; 125f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin norm += vector[i] * vector[i]; 126f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 127f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin norm = Math.sqrt(norm); 128f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 129f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin double radian = distance / EARTH_RADIUS; 1301253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin for (int i = 0; i < VECTOR_LENGTH; ++i) { 131f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin mCenter[i] = cluster.mCenter[i] * Math.cos(radian) + 132f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin (vector[i] / norm) * Math.sin(radian); 133f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 134f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 1355d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 1365d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin private void updateTemporalHistogram(long time, long duration) { 1375d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin HashMap<String, String> timeFeatures = TimeStatsAggregator.getAllTimeFeatures(time); 1385d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 13983954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin String timeOfWeek = timeFeatures.get(TimeStatsAggregator.TIME_OF_WEEK); 14083954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin long totalDuration = (mNewHistogram.containsKey(timeOfWeek)) ? 14183954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin mNewHistogram.get(timeOfWeek) + duration : duration; 14283954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin mNewHistogram.put(timeOfWeek, totalDuration); 14383954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin 1445d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin String timeOfDay = timeFeatures.get(TimeStatsAggregator.TIME_OF_DAY); 14583954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin totalDuration = (mNewHistogram.containsKey(timeOfDay)) ? 1465d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin mNewHistogram.get(timeOfDay) + duration : duration; 1475d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin mNewHistogram.put(timeOfDay, totalDuration); 1485d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin } 149f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin} 150