ClusterManager.java revision f0f78449e8ab7d63894964c54b6ef390ca9ce044 
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.location.Location;
20import android.text.format.Time;
21import android.util.Log;
22
23import java.util.ArrayList;
24import java.util.HashSet;
25
26/**
27 * ClusterManager incrementally indentify representitve clusters from the input location
28 * stream. Clusters are updated online using leader based clustering algorithm. The input
29 * locations initially are kept by the clusters. Periodially, a cluster consolidating
30 * procedure is carried out to refine the cluster centers. After consolidation, the
31 * location data are released.
32 */
33public class ClusterManager {
34
35    private static String TAG = "ClusterManager";
36
37    private static float LOCATION_CLUSTER_RADIUS = 25; // meter
38
39    private static float SEMANTIC_CLUSTER_RADIUS = 50; // meter
40
41    private static long CONSOLIDATE_INTERVAL = 90000; // is milliseconds
42
43    private static long LOCATION_CLUSTER_THRESHOLD = 1000; // in milliseconds
44
45    private static long SEMANTIC_CLUSTER_THRESHOLD = 30000; // in milliseconds
46
47    private Location mLastLocation = null;
48
49    private long mTimeRef = 0;
50
51    private long mSemanticClusterCount = 0;
52
53    private ArrayList<LocationCluster> mLocClusters = new ArrayList<LocationCluster>();
54
55    private ArrayList<SemanticCluster> mSemanticClusters = new ArrayList<SemanticCluster>();
56
57    public ClusterManager() {
58    }
59
60    public void addSample(Location location) {
61        float bestClusterDistance = Float.MAX_VALUE;
62        int bestClusterIndex = -1;
63        long lastDuration;
64        long currentTime = location.getTime();
65
66        if (mLastLocation != null) {
67            // get the duration spent in the last location
68            long duration = location.getTime() - mLastLocation.getTime();
69            // TODO: set duration is a separate field
70            mLastLocation.setTime(duration);
71            Log.v(TAG, "sample duration: " + duration +
72                  ", number of clusters: " + mLocClusters.size());
73
74            // add the last location to cluster.
75            // first find the cluster it belongs to.
76            for (int i = 0; i < mLocClusters.size(); ++i) {
77                float distance = mLocClusters.get(i).distanceToCenter(mLastLocation);
78                Log.v(TAG, "clulster " + i + " is within " + distance + " meters");
79                if (distance < bestClusterDistance) {
80                    bestClusterDistance = distance;
81                    bestClusterIndex = i;
82                }
83            }
84
85            // add the location to the selected cluster
86            if (bestClusterDistance < LOCATION_CLUSTER_RADIUS) {
87              Log.v(TAG, "add sample to cluster: " + bestClusterIndex + ",( " +
88                    location.getLongitude() + ", " + location.getLatitude() + ")");
89                mLocClusters.get(bestClusterIndex).addSample(mLastLocation);
90            } else {
91                // if it is far away from all existing clusters, create a new cluster.
92                LocationCluster cluster =
93                        new LocationCluster(mLastLocation, CONSOLIDATE_INTERVAL);
94                // move the center of the new cluster if its covering region overlaps
95                // with an existing cluster.
96                if (bestClusterDistance < 2 * LOCATION_CLUSTER_RADIUS) {
97                    cluster.moveAwayCluster(mLocClusters.get(bestClusterIndex),
98                            ((float) 2 * LOCATION_CLUSTER_RADIUS));
99                }
100                mLocClusters.add(cluster);
101            }
102        } else {
103            mTimeRef = currentTime;
104        }
105
106        long collectDuration = currentTime - mTimeRef;
107        Log.e(TAG, "collect duration: " + collectDuration);
108        if (collectDuration > CONSOLIDATE_INTERVAL) {
109            // TODO : conslidation takes time. move this to a separate thread later.
110            consolidateClusters(collectDuration);
111            mTimeRef = currentTime;
112        }
113
114        /*
115        // TODO: this could be removed
116        Log.i(TAG, "location : " +  location.getLongitude() + ", " + location.getLatitude());
117        if (mLastLocation != null) {
118            Log.i(TAG, "mLastLocation: " +  mLastLocation.getLongitude() + ", " +
119                  mLastLocation.getLatitude());
120        }  // end of deletion
121        */
122
123        mLastLocation = location;
124    }
125
126    private void consolidateClusters(long duration) {
127        Log.e(TAG, "considalating " + mLocClusters.size() + " clusters");
128        LocationCluster cluster;
129
130        // TODO: which should be first? considate or merge?
131        for (int i = mLocClusters.size() - 1; i >= 0; --i) {
132            cluster = mLocClusters.get(i);
133            cluster.consolidate(duration);
134
135            // TODO: currently set threshold to 1 sec so almost none of the location
136            // clusters will be removed.
137            if (!cluster.passThreshold(LOCATION_CLUSTER_THRESHOLD)) {
138                mLocClusters.remove(cluster);
139            }
140        }
141
142        // merge clusters whose regions are overlapped. note that after merge
143        // translates the cluster center but keeps the region size unchanged.
144        for (int i = mLocClusters.size() - 1; i >= 0; --i) {
145            cluster = mLocClusters.get(i);
146            for (int j = i - 1; j >= 0; --j) {
147                float distance = mLocClusters.get(j).distanceToCluster(cluster);
148                if (distance < LOCATION_CLUSTER_RADIUS) {
149                    mLocClusters.get(j).absorbCluster(cluster);
150                    mLocClusters.remove(cluster);
151                }
152            }
153        }
154        updateSemanticClusters();
155    }
156
157    private void updateSemanticClusters() {
158        // select candidate location clusters
159        ArrayList<LocationCluster> candidates = new ArrayList<LocationCluster>();
160        for (LocationCluster cluster : mLocClusters) {
161            if (cluster.passThreshold(SEMANTIC_CLUSTER_THRESHOLD)) {
162                candidates.add(cluster);
163            }
164        }
165        for (LocationCluster candidate : candidates) {
166            float bestClusterDistance = Float.MAX_VALUE;
167            SemanticCluster bestCluster = null;
168            for (SemanticCluster cluster : mSemanticClusters) {
169                float distance = cluster.distanceToCluster(candidate);
170
171                Log.e(TAG, "distance to semantic cluster: " + cluster.getSemanticId());
172
173                if (distance < bestClusterDistance) {
174                    bestClusterDistance = distance;
175                    bestCluster = cluster;
176                }
177            }
178
179            // add the location to the selected cluster
180            SemanticCluster semanticCluster;
181            if (bestClusterDistance < SEMANTIC_CLUSTER_RADIUS) {
182                bestCluster.absorbCluster(candidate);
183            } else {
184                // if it is far away from all existing clusters, create a new cluster.
185                semanticCluster = new SemanticCluster(candidate, CONSOLIDATE_INTERVAL,
186                        mSemanticClusterCount++);
187                mSemanticClusters.add(semanticCluster);
188            }
189        }
190        Log.e(TAG, "location: " + candidates.size() + ", semantic: " + mSemanticClusters.size());
191
192        candidates.clear();
193    }
194
195    public String getSemanticLocation() {
196        String label = "unknown";
197
198        if (mLastLocation != null) {
199            for (SemanticCluster cluster: mSemanticClusters) {
200                if (cluster.distanceToCenter(mLastLocation) < SEMANTIC_CLUSTER_RADIUS) {
201                    return cluster.getSemanticId();
202                }
203            }
204        }
205        return label;
206    }
207}
208