1/*
2 * Copyright (C) 2012 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package android.bordeaux.services;
18
19import android.content.Context;
20import android.location.Location;
21import android.text.format.Time;
22import android.util.Log;
23
24import java.util.ArrayList;
25import java.util.HashMap;
26import java.util.HashSet;
27import java.util.List;
28import java.util.Map;
29
30/**
31 * ClusterManager incrementally indentify representitve clusters from the input location
32 * stream. Clusters are updated online using leader based clustering algorithm. The input
33 * locations initially are kept by the clusters. Periodially, a cluster consolidating
34 * procedure is carried out to refine the cluster centers. After consolidation, the
35 * location data are released.
36 */
37public class ClusterManager {
38
39    private static String TAG = "ClusterManager";
40
41    private static float LOCATION_CLUSTER_RADIUS = 25; // meter
42
43    private static float SEMANTIC_CLUSTER_RADIUS = 75; // meter
44
45    // Consoliate location clusters (and check for new semantic clusters)
46    // every 10 minutes (600 seconds).
47    private static final long CONSOLIDATE_INTERVAL = 600;
48
49    // A location cluster can be labeled as a semantic cluster if it has been
50    // stayed for at least 10 minutes (600 seconds) within a day.
51    private static final long SEMANTIC_CLUSTER_THRESHOLD = 600; // seconds
52
53    // Reset location cluters every 24 hours (86400 seconds).
54    private static final long LOCATION_REFRESH_PERIOD = 86400; // seconds
55
56    private static String UNKNOWN_LOCATION = "Unknown Location";
57
58    private Location mLastLocation = null;
59
60    private long mClusterDuration;
61
62    private long mConsolidateRef = 0;
63
64    private long mRefreshRef = 0;
65
66    private long mSemanticClusterCount = 0;
67
68    private ArrayList<LocationCluster> mLocationClusters = new ArrayList<LocationCluster>();
69
70    private ArrayList<BaseCluster> mSemanticClusters = new ArrayList<BaseCluster>();
71
72    private AggregatorRecordStorage mStorage;
73
74    private static String SEMANTIC_TABLE = "SemanticTable";
75
76    private static String SEMANTIC_ID = "ID";
77
78    private static final String SEMANTIC_LONGITUDE = "Longitude";
79
80    private static final String SEMANTIC_LATITUDE = "Latitude";
81
82    private static final String SEMANTIC_DURATION = "Duration";
83
84    private static final String[] SEMANTIC_COLUMNS =
85        new String[]{ SEMANTIC_ID,
86                      SEMANTIC_LONGITUDE,
87                      SEMANTIC_LATITUDE,
88                      SEMANTIC_DURATION,
89                      TimeStatsAggregator.WEEKEND,
90                      TimeStatsAggregator.WEEKDAY,
91                      TimeStatsAggregator.MORNING,
92                      TimeStatsAggregator.NOON,
93                      TimeStatsAggregator.AFTERNOON,
94                      TimeStatsAggregator.EVENING,
95                      TimeStatsAggregator.NIGHT,
96                      TimeStatsAggregator.LATENIGHT };
97
98    private static final int mFeatureValueStart = 4;
99    private static final int mFeatureValueEnd = 11;
100
101    public ClusterManager(Context context) {
102        mStorage = new AggregatorRecordStorage(context, SEMANTIC_TABLE, SEMANTIC_COLUMNS);
103
104        loadSemanticClusters();
105    }
106
107    public void addSample(Location location) {
108        float bestClusterDistance = Float.MAX_VALUE;
109        int bestClusterIndex = -1;
110        long lastDuration;
111        long currentTime = location.getTime() / 1000; // measure time in seconds
112
113        if (mLastLocation != null) {
114            if (location.getTime() == mLastLocation.getTime()) {
115                return;
116            }
117            // get the duration spent in the last location
118            long duration = (location.getTime() - mLastLocation.getTime()) / 1000;
119            mClusterDuration += duration;
120
121            Log.v(TAG, "sample duration: " + duration +
122                  ", number of clusters: " + mLocationClusters.size());
123
124            synchronized (mLocationClusters) {
125                // add the last location to cluster.
126                // first find the cluster it belongs to.
127                for (int i = 0; i < mLocationClusters.size(); ++i) {
128                    float distance = mLocationClusters.get(i).distanceToCenter(mLastLocation);
129                    Log.v(TAG, "clulster " + i + " is within " + distance + " meters");
130                    if (distance < bestClusterDistance) {
131                        bestClusterDistance = distance;
132                        bestClusterIndex = i;
133                    }
134                }
135
136                // add the location to the selected cluster
137                if (bestClusterDistance < LOCATION_CLUSTER_RADIUS) {
138                    mLocationClusters.get(bestClusterIndex).addSample(mLastLocation, duration);
139                } else {
140                    // if it is far away from all existing clusters, create a new cluster.
141                  LocationCluster cluster = new LocationCluster(mLastLocation, duration);
142                  mLocationClusters.add(cluster);
143                }
144            }
145        } else {
146            mConsolidateRef = currentTime;
147            mRefreshRef = currentTime;
148
149            if (mLocationClusters.isEmpty()) {
150                mClusterDuration = 0;
151            }
152        }
153
154        long collectDuration = currentTime - mConsolidateRef;
155        Log.v(TAG, "collect duration: " + collectDuration);
156        if (collectDuration > CONSOLIDATE_INTERVAL) {
157            // TODO : conslidation takes time. move this to a separate thread later.
158            consolidateClusters();
159            mConsolidateRef = currentTime;
160
161            long refreshDuration = currentTime - mRefreshRef;
162            Log.v(TAG, "refresh duration: " + refreshDuration);
163            if (refreshDuration >  LOCATION_REFRESH_PERIOD) {
164                updateSemanticClusters();
165                mRefreshRef = currentTime;
166            }
167            saveSemanticClusters();
168        }
169
170        mLastLocation = location;
171    }
172
173    private void consolidateClusters() {
174        synchronized (mSemanticClusters) {
175            LocationCluster locationCluster;
176            for (int i = mLocationClusters.size() - 1; i >= 0; --i) {
177                locationCluster = mLocationClusters.get(i);
178                locationCluster.consolidate();
179            }
180
181            // merge clusters whose regions are overlapped. note that after merge
182            // cluster center changes but cluster size remains unchanged.
183            for (int i = mLocationClusters.size() - 1; i >= 0; --i) {
184                locationCluster = mLocationClusters.get(i);
185                for (int j = i - 1; j >= 0; --j) {
186                    float distance =
187                        mLocationClusters.get(j).distanceToCluster(locationCluster);
188                    if (distance < LOCATION_CLUSTER_RADIUS) {
189                        mLocationClusters.get(j).absorbCluster(locationCluster);
190                        mLocationClusters.remove(locationCluster);
191                    }
192                }
193            }
194            Log.v(TAG, mLocationClusters.size() + " location clusters after consolidate");
195
196            // assign each candidate to a semantic cluster and check if new semantic
197            // clusters are found
198            for (LocationCluster candidate : mLocationClusters) {
199                if (candidate.hasSemanticId() ||
200                    candidate.hasSemanticClusterId() ||
201                    !candidate.passThreshold(SEMANTIC_CLUSTER_THRESHOLD)) {
202                    continue;
203                }
204
205                // find the closest semantic cluster
206                float bestClusterDistance = Float.MAX_VALUE;
207                String bestClusterId = "Unused Id";
208                for (BaseCluster cluster : mSemanticClusters) {
209                    float distance = cluster.distanceToCluster(candidate);
210                    Log.v(TAG, distance + "distance to semantic cluster: " +
211                          cluster.getSemanticId());
212
213                    if (distance < bestClusterDistance) {
214                        bestClusterDistance = distance;
215                        bestClusterId = cluster.getSemanticId();
216                    }
217                }
218
219                // if candidate doesn't belong to any semantic cluster, create a new
220                // semantic cluster
221                if (bestClusterDistance > SEMANTIC_CLUSTER_RADIUS) {
222                    candidate.generateSemanticId(mSemanticClusterCount++);
223                    mSemanticClusters.add(candidate);
224                } else {
225                    candidate.setSemanticClusterId(bestClusterId);
226                }
227            }
228            Log.v(TAG, mSemanticClusters.size() + " semantic clusters after consolidate");
229        }
230    }
231
232    private void updateSemanticClusters() {
233        synchronized (mSemanticClusters) {
234            // create index to cluster map
235            HashMap<String, BaseCluster> semanticIdMap =
236                new HashMap<String, BaseCluster>();
237            for (BaseCluster cluster : mSemanticClusters) {
238                // TODO: apply forgetting factor on existing semantic cluster stats,
239                // duration, histogram, etc.
240                cluster.forgetPastHistory();
241                semanticIdMap.put(cluster.getSemanticId(), cluster);
242            }
243
244            // assign each candidate to a semantic cluster
245            for (LocationCluster cluster : mLocationClusters) {
246                if (cluster.hasSemanticClusterId()) {
247                    BaseCluster semanticCluster =
248                        semanticIdMap.get(cluster.getSemanticClusterId());
249                    semanticCluster.absorbCluster(cluster);
250                }
251            }
252            // reset location clusters.
253            mLocationClusters.clear();
254        }
255    }
256
257    private void loadSemanticClusters() {
258        List<Map<String, String> > allData = mStorage.getAllData();
259        HashMap<String, Long> histogram = new HashMap<String, Long>();
260
261        synchronized (mSemanticClusters) {
262            mSemanticClusters.clear();
263            for (Map<String, String> map : allData) {
264                String semanticId = map.get(SEMANTIC_ID);
265                double longitude = Double.valueOf(map.get(SEMANTIC_LONGITUDE));
266                double latitude = Double.valueOf(map.get(SEMANTIC_LATITUDE));
267                long duration = Long.valueOf(map.get(SEMANTIC_DURATION));
268                BaseCluster cluster =
269                    new BaseCluster(semanticId, longitude, latitude, duration);
270
271                histogram.clear();
272                for (int i = mFeatureValueStart; i <= mFeatureValueEnd; i++) {
273                    String featureValue = SEMANTIC_COLUMNS[i];
274                    if (map.containsKey(featureValue)) {
275                      histogram.put(featureValue, Long.valueOf(map.get(featureValue)));
276                    }
277                }
278                cluster.setHistogram(histogram);
279                mSemanticClusters.add(cluster);
280            }
281            mSemanticClusterCount = mSemanticClusters.size();
282            Log.e(TAG, "load " + mSemanticClusterCount + " semantic clusters.");
283        }
284    }
285
286    private void saveSemanticClusters() {
287        HashMap<String, String> rowFeatures = new HashMap<String, String>();
288
289        mStorage.removeAllData();
290        synchronized (mSemanticClusters) {
291            for (BaseCluster cluster : mSemanticClusters) {
292                rowFeatures.clear();
293                rowFeatures.put(SEMANTIC_ID, cluster.getSemanticId());
294
295                rowFeatures.put(SEMANTIC_LONGITUDE,
296                            String.valueOf(cluster.getCenterLongitude()));
297                rowFeatures.put(SEMANTIC_LATITUDE,
298                            String.valueOf(cluster.getCenterLatitude()));
299                rowFeatures.put(SEMANTIC_DURATION,
300                            String.valueOf(cluster.getDuration()));
301
302                HashMap<String, Long> histogram = cluster.getHistogram();
303                for (Map.Entry<String, Long> entry : histogram.entrySet()) {
304                    rowFeatures.put(entry.getKey(), String.valueOf(entry.getValue()));
305                }
306                mStorage.addData(rowFeatures);
307                Log.e(TAG, "saving semantic cluster: " + rowFeatures);
308            }
309        }
310    }
311
312    public String getSemanticLocation() {
313        String label = LocationStatsAggregator.UNKNOWN_LOCATION;
314
315        // instead of using the last location, try acquiring the latest location.
316        if (mLastLocation != null) {
317            // TODO: use fast neatest neighbor search speed up location search
318            synchronized (mSemanticClusters) {
319                for (BaseCluster cluster: mSemanticClusters) {
320                    if (cluster.distanceToCenter(mLastLocation) < SEMANTIC_CLUSTER_RADIUS) {
321                        return cluster.getSemanticId();
322                    }
323                }
324            }
325        }
326        return label;
327    }
328
329    public List<String> getClusterNames() {
330        ArrayList<String> clusters = new ArrayList<String>();
331        synchronized (mSemanticClusters) {
332            for (BaseCluster cluster: mSemanticClusters) {
333                clusters.add(cluster.getSemanticId());
334            }
335        }
336        return clusters;
337    }
338}
339