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 Lin 17f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linpackage android.bordeaux.services; 18f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 195d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Linimport android.content.Context; 20f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linimport android.location.Location; 21f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linimport android.text.format.Time; 22f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linimport android.util.Log; 23f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 24f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linimport java.util.ArrayList; 255d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Linimport java.util.HashMap; 26f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linimport java.util.HashSet; 275d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Linimport java.util.List; 285d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Linimport java.util.Map; 29f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 30f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin/** 31f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * ClusterManager incrementally indentify representitve clusters from the input location 32f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * stream. Clusters are updated online using leader based clustering algorithm. The input 33f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * locations initially are kept by the clusters. Periodially, a cluster consolidating 34f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * procedure is carried out to refine the cluster centers. After consolidation, the 35f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin * location data are released. 36f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin */ 37f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Linpublic class ClusterManager { 38f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 39f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin private static String TAG = "ClusterManager"; 40f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 411253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin private static float LOCATION_CLUSTER_RADIUS = 25; // meter 42f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 431253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin private static float SEMANTIC_CLUSTER_RADIUS = 75; // meter 44f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 4578a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin // Consoliate location clusters (and check for new semantic clusters) 461253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // every 10 minutes (600 seconds). 471253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin private static final long CONSOLIDATE_INTERVAL = 600; 48f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 4978a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin // A location cluster can be labeled as a semantic cluster if it has been 5078a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin // stayed for at least 10 minutes (600 seconds) within a day. 5178a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin private static final long SEMANTIC_CLUSTER_THRESHOLD = 600; // seconds 5283954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin 5347c0dc05cde9e9d9cc57e1393429006bf8b23b32Ruei-sung Lin // Reset location cluters every 24 hours (86400 seconds). 5447c0dc05cde9e9d9cc57e1393429006bf8b23b32Ruei-sung Lin private static final long LOCATION_REFRESH_PERIOD = 86400; // seconds 555d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 565d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin private static String UNKNOWN_LOCATION = "Unknown Location"; 575d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 58f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin private Location mLastLocation = null; 59f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 6078a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin private long mClusterDuration; 6178a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin 621253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin private long mConsolidateRef = 0; 631253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin 641253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin private long mRefreshRef = 0; 65f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 66f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin private long mSemanticClusterCount = 0; 67f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 6878a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin private ArrayList<LocationCluster> mLocationClusters = new ArrayList<LocationCluster>(); 69f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 701253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin private ArrayList<BaseCluster> mSemanticClusters = new ArrayList<BaseCluster>(); 71f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 725d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin private AggregatorRecordStorage mStorage; 735d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 745d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin private static String SEMANTIC_TABLE = "SemanticTable"; 755d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 765d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin private static String SEMANTIC_ID = "ID"; 775d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 7883954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin private static final String SEMANTIC_LONGITUDE = "Longitude"; 7983954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin 8083954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin private static final String SEMANTIC_LATITUDE = "Latitude"; 815d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 821253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin private static final String SEMANTIC_DURATION = "Duration"; 831253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin 8483954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin private static final String[] SEMANTIC_COLUMNS = 8583954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin new String[]{ SEMANTIC_ID, 8683954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin SEMANTIC_LONGITUDE, 8783954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin SEMANTIC_LATITUDE, 881253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin SEMANTIC_DURATION, 8983954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin TimeStatsAggregator.WEEKEND, 9083954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin TimeStatsAggregator.WEEKDAY, 9183954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin TimeStatsAggregator.MORNING, 9283954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin TimeStatsAggregator.NOON, 9383954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin TimeStatsAggregator.AFTERNOON, 9483954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin TimeStatsAggregator.EVENING, 9583954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin TimeStatsAggregator.NIGHT, 9683954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin TimeStatsAggregator.LATENIGHT }; 975d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 981253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin private static final int mFeatureValueStart = 4; 991253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin private static final int mFeatureValueEnd = 11; 1005d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 1015d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin public ClusterManager(Context context) { 1025d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin mStorage = new AggregatorRecordStorage(context, SEMANTIC_TABLE, SEMANTIC_COLUMNS); 1035d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 1045d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin loadSemanticClusters(); 105f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 106f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 107f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin public void addSample(Location location) { 108f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin float bestClusterDistance = Float.MAX_VALUE; 109f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin int bestClusterIndex = -1; 110f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin long lastDuration; 11183954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin long currentTime = location.getTime() / 1000; // measure time in seconds 112f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 113f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin if (mLastLocation != null) { 11447c0dc05cde9e9d9cc57e1393429006bf8b23b32Ruei-sung Lin if (location.getTime() == mLastLocation.getTime()) { 11547c0dc05cde9e9d9cc57e1393429006bf8b23b32Ruei-sung Lin return; 11647c0dc05cde9e9d9cc57e1393429006bf8b23b32Ruei-sung Lin } 117f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin // get the duration spent in the last location 11878a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin long duration = (location.getTime() - mLastLocation.getTime()) / 1000; 11978a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin mClusterDuration += duration; 12078a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin 121f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin Log.v(TAG, "sample duration: " + duration + 12278a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin ", number of clusters: " + mLocationClusters.size()); 123f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 1241253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin synchronized (mLocationClusters) { 1251253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // add the last location to cluster. 1261253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // first find the cluster it belongs to. 1271253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin for (int i = 0; i < mLocationClusters.size(); ++i) { 1281253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin float distance = mLocationClusters.get(i).distanceToCenter(mLastLocation); 1291253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin Log.v(TAG, "clulster " + i + " is within " + distance + " meters"); 1301253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin if (distance < bestClusterDistance) { 1311253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin bestClusterDistance = distance; 1321253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin bestClusterIndex = i; 1331253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin } 134f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 135f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 1361253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // add the location to the selected cluster 1371253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin if (bestClusterDistance < LOCATION_CLUSTER_RADIUS) { 1381253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin mLocationClusters.get(bestClusterIndex).addSample(mLastLocation, duration); 1391253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin } else { 1401253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // if it is far away from all existing clusters, create a new cluster. 1411253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin LocationCluster cluster = new LocationCluster(mLastLocation, duration); 1421253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin mLocationClusters.add(cluster); 143f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 144f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 145f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } else { 1461253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin mConsolidateRef = currentTime; 1471253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin mRefreshRef = currentTime; 14878a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin 14978a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin if (mLocationClusters.isEmpty()) { 15078a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin mClusterDuration = 0; 15178a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin } 152f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 153f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 1541253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin long collectDuration = currentTime - mConsolidateRef; 1551253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin Log.v(TAG, "collect duration: " + collectDuration); 156f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin if (collectDuration > CONSOLIDATE_INTERVAL) { 157f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin // TODO : conslidation takes time. move this to a separate thread later. 1581253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin consolidateClusters(); 1591253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin mConsolidateRef = currentTime; 1601253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin 1611253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin long refreshDuration = currentTime - mRefreshRef; 1621253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin Log.v(TAG, "refresh duration: " + refreshDuration); 1631253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin if (refreshDuration > LOCATION_REFRESH_PERIOD) { 1641253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin updateSemanticClusters(); 1651253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin mRefreshRef = currentTime; 166f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 16778a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin saveSemanticClusters(); 16878a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin } 16978a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin 1701253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin mLastLocation = location; 17178a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin } 17278a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin 1731253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin private void consolidateClusters() { 1741253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin synchronized (mSemanticClusters) { 1751253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin LocationCluster locationCluster; 1761253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin for (int i = mLocationClusters.size() - 1; i >= 0; --i) { 1771253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin locationCluster = mLocationClusters.get(i); 1781253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin locationCluster.consolidate(); 17978a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin } 18078a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin 1811253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // merge clusters whose regions are overlapped. note that after merge 1821253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // cluster center changes but cluster size remains unchanged. 1831253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin for (int i = mLocationClusters.size() - 1; i >= 0; --i) { 1841253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin locationCluster = mLocationClusters.get(i); 1851253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin for (int j = i - 1; j >= 0; --j) { 1861253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin float distance = 1871253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin mLocationClusters.get(j).distanceToCluster(locationCluster); 1881253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin if (distance < LOCATION_CLUSTER_RADIUS) { 1891253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin mLocationClusters.get(j).absorbCluster(locationCluster); 1901253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin mLocationClusters.remove(locationCluster); 1911253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin } 19278a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin } 19378a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin } 1941253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin Log.v(TAG, mLocationClusters.size() + " location clusters after consolidate"); 1951253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin 1961253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // assign each candidate to a semantic cluster and check if new semantic 1971253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // clusters are found 1981253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin for (LocationCluster candidate : mLocationClusters) { 1991253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin if (candidate.hasSemanticId() || 2001253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin candidate.hasSemanticClusterId() || 2011253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin !candidate.passThreshold(SEMANTIC_CLUSTER_THRESHOLD)) { 2021253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin continue; 2031253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin } 2045d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 2051253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // find the closest semantic cluster 2061253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin float bestClusterDistance = Float.MAX_VALUE; 2071253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin String bestClusterId = "Unused Id"; 2081253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin for (BaseCluster cluster : mSemanticClusters) { 2091253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin float distance = cluster.distanceToCluster(candidate); 21047c0dc05cde9e9d9cc57e1393429006bf8b23b32Ruei-sung Lin Log.v(TAG, distance + "distance to semantic cluster: " + 21147c0dc05cde9e9d9cc57e1393429006bf8b23b32Ruei-sung Lin cluster.getSemanticId()); 21278a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin 2131253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin if (distance < bestClusterDistance) { 2141253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin bestClusterDistance = distance; 2151253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin bestClusterId = cluster.getSemanticId(); 2161253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin } 2171253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin } 21878a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin 2191253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // if candidate doesn't belong to any semantic cluster, create a new 2201253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // semantic cluster 2211253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin if (bestClusterDistance > SEMANTIC_CLUSTER_RADIUS) { 2221253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin candidate.generateSemanticId(mSemanticClusterCount++); 2231253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin mSemanticClusters.add(candidate); 2241253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin } else { 2251253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin candidate.setSemanticClusterId(bestClusterId); 2261253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin } 22778a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin } 2281253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin Log.v(TAG, mSemanticClusters.size() + " semantic clusters after consolidate"); 22978a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin } 23078a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin } 23178a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin 23278a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin private void updateSemanticClusters() { 23378a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin synchronized (mSemanticClusters) { 2341253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // create index to cluster map 2351253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin HashMap<String, BaseCluster> semanticIdMap = 2361253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin new HashMap<String, BaseCluster>(); 2371253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin for (BaseCluster cluster : mSemanticClusters) { 2381253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // TODO: apply forgetting factor on existing semantic cluster stats, 2391253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin // duration, histogram, etc. 2401253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin cluster.forgetPastHistory(); 2411253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin semanticIdMap.put(cluster.getSemanticId(), cluster); 24278a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin } 24378a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin 24478a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin // assign each candidate to a semantic cluster 24578a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin for (LocationCluster cluster : mLocationClusters) { 2461253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin if (cluster.hasSemanticClusterId()) { 2471253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin BaseCluster semanticCluster = 2481253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin semanticIdMap.get(cluster.getSemanticClusterId()); 2491253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin semanticCluster.absorbCluster(cluster); 25078a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin } 25178a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin } 25278a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin // reset location clusters. 25378a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin mLocationClusters.clear(); 25478a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin } 2555d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin } 2565d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 2575d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin private void loadSemanticClusters() { 2585d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin List<Map<String, String> > allData = mStorage.getAllData(); 25983954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin HashMap<String, Long> histogram = new HashMap<String, Long>(); 2605d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 2619c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua synchronized (mSemanticClusters) { 2629c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua mSemanticClusters.clear(); 2639c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua for (Map<String, String> map : allData) { 2649c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua String semanticId = map.get(SEMANTIC_ID); 2659c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua double longitude = Double.valueOf(map.get(SEMANTIC_LONGITUDE)); 2669c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua double latitude = Double.valueOf(map.get(SEMANTIC_LATITUDE)); 2671253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin long duration = Long.valueOf(map.get(SEMANTIC_DURATION)); 2681253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin BaseCluster cluster = 2691253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin new BaseCluster(semanticId, longitude, latitude, duration); 2709c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua 2719c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua histogram.clear(); 2729c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua for (int i = mFeatureValueStart; i <= mFeatureValueEnd; i++) { 2739c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua String featureValue = SEMANTIC_COLUMNS[i]; 2749c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua if (map.containsKey(featureValue)) { 27578a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin histogram.put(featureValue, Long.valueOf(map.get(featureValue))); 2769c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua } 27783954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin } 2789c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua cluster.setHistogram(histogram); 2799c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua mSemanticClusters.add(cluster); 28083954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin } 2819c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua mSemanticClusterCount = mSemanticClusters.size(); 28278a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin Log.e(TAG, "load " + mSemanticClusterCount + " semantic clusters."); 2835d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin } 2845d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin } 2855d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 2865d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin private void saveSemanticClusters() { 2875d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin HashMap<String, String> rowFeatures = new HashMap<String, String>(); 2885d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 28978a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin mStorage.removeAllData(); 2909c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua synchronized (mSemanticClusters) { 2911253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin for (BaseCluster cluster : mSemanticClusters) { 2929c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua rowFeatures.clear(); 2939c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua rowFeatures.put(SEMANTIC_ID, cluster.getSemanticId()); 2945d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin 2959c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua rowFeatures.put(SEMANTIC_LONGITUDE, 29678a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin String.valueOf(cluster.getCenterLongitude())); 2979c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua rowFeatures.put(SEMANTIC_LATITUDE, 29878a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin String.valueOf(cluster.getCenterLatitude())); 2991253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin rowFeatures.put(SEMANTIC_DURATION, 3001253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin String.valueOf(cluster.getDuration())); 30183954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin 3029c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua HashMap<String, Long> histogram = cluster.getHistogram(); 3039c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua for (Map.Entry<String, Long> entry : histogram.entrySet()) { 3049c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua rowFeatures.put(entry.getKey(), String.valueOf(entry.getValue())); 3059c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua } 3069c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua mStorage.addData(rowFeatures); 30778a66d98346a69f65e9d38bb0c96a5418c007197Ruei-sung Lin Log.e(TAG, "saving semantic cluster: " + rowFeatures); 30883954e853dc1e1a28b2c3efbe1585f188266df02Ruei-sung Lin } 3095d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin } 310f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 311f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 312f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin public String getSemanticLocation() { 313c7c9cf164cc58d03156a53be35e58c3b75871a23Ruei-sung Lin String label = LocationStatsAggregator.UNKNOWN_LOCATION; 314f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin 315c7c9cf164cc58d03156a53be35e58c3b75871a23Ruei-sung Lin // instead of using the last location, try acquiring the latest location. 316f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin if (mLastLocation != null) { 3175d42ffa9462f87edbbdc61a8719f6c521c700de5Ruei-sung Lin // TODO: use fast neatest neighbor search speed up location search 3189c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua synchronized (mSemanticClusters) { 3191253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin for (BaseCluster cluster: mSemanticClusters) { 3209c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua if (cluster.distanceToCenter(mLastLocation) < SEMANTIC_CLUSTER_RADIUS) { 3219c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua return cluster.getSemanticId(); 3229c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua } 323f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 324f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 325f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 326f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin return label; 327f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin } 3289c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua 3299c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua public List<String> getClusterNames() { 3309c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua ArrayList<String> clusters = new ArrayList<String>(); 3319c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua synchronized (mSemanticClusters) { 3321253e9fb0b5570ab8adaed222655a5b052aa072eRuei-sung Lin for (BaseCluster cluster: mSemanticClusters) { 3339c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua clusters.add(cluster.getSemanticId()); 3349c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua } 3359c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua } 3369c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua return clusters; 3379c3a7dc466e2f8de02e15030b2b7f4096ba97e5aWei Hua } 338f0f78449e8ab7d63894964c54b6ef390ca9ce044Ruei-sung Lin} 339