summaryrefslogtreecommitdiff
path: root/bordeaux/service/src/android/bordeaux/services/ClusterManager.java
diff options
context:
space:
mode:
Diffstat (limited to 'bordeaux/service/src/android/bordeaux/services/ClusterManager.java')
-rw-r--r--bordeaux/service/src/android/bordeaux/services/ClusterManager.java338
1 files changed, 0 insertions, 338 deletions
diff --git a/bordeaux/service/src/android/bordeaux/services/ClusterManager.java b/bordeaux/service/src/android/bordeaux/services/ClusterManager.java
deleted file mode 100644
index 71e77a34e..000000000
--- a/bordeaux/service/src/android/bordeaux/services/ClusterManager.java
+++ /dev/null
@@ -1,338 +0,0 @@
-/*
- * 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.content.Context;
-import android.location.Location;
-import android.text.format.Time;
-import android.util.Log;
-
-import java.util.ArrayList;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.List;
-import java.util.Map;
-
-/**
- * ClusterManager incrementally indentify representitve clusters from the input location
- * stream. Clusters are updated online using leader based clustering algorithm. The input
- * locations initially are kept by the clusters. Periodially, a cluster consolidating
- * procedure is carried out to refine the cluster centers. After consolidation, the
- * location data are released.
- */
-public class ClusterManager {
-
- private static String TAG = "ClusterManager";
-
- private static float LOCATION_CLUSTER_RADIUS = 25; // meter
-
- private static float SEMANTIC_CLUSTER_RADIUS = 75; // meter
-
- // Consoliate location clusters (and check for new semantic clusters)
- // every 10 minutes (600 seconds).
- private static final long CONSOLIDATE_INTERVAL = 600;
-
- // A location cluster can be labeled as a semantic cluster if it has been
- // stayed for at least 10 minutes (600 seconds) within a day.
- private static final long SEMANTIC_CLUSTER_THRESHOLD = 600; // seconds
-
- // Reset location cluters every 24 hours (86400 seconds).
- private static final long LOCATION_REFRESH_PERIOD = 86400; // seconds
-
- private static String UNKNOWN_LOCATION = "Unknown Location";
-
- private Location mLastLocation = null;
-
- private long mClusterDuration;
-
- private long mConsolidateRef = 0;
-
- private long mRefreshRef = 0;
-
- private long mSemanticClusterCount = 0;
-
- private ArrayList<LocationCluster> mLocationClusters = new ArrayList<LocationCluster>();
-
- private ArrayList<BaseCluster> mSemanticClusters = new ArrayList<BaseCluster>();
-
- private AggregatorRecordStorage mStorage;
-
- private static String SEMANTIC_TABLE = "SemanticTable";
-
- private static String SEMANTIC_ID = "ID";
-
- private static final String SEMANTIC_LONGITUDE = "Longitude";
-
- private static final String SEMANTIC_LATITUDE = "Latitude";
-
- private static final String SEMANTIC_DURATION = "Duration";
-
- private static final String[] SEMANTIC_COLUMNS =
- new String[]{ SEMANTIC_ID,
- SEMANTIC_LONGITUDE,
- SEMANTIC_LATITUDE,
- SEMANTIC_DURATION,
- TimeStatsAggregator.WEEKEND,
- TimeStatsAggregator.WEEKDAY,
- TimeStatsAggregator.MORNING,
- TimeStatsAggregator.NOON,
- TimeStatsAggregator.AFTERNOON,
- TimeStatsAggregator.EVENING,
- TimeStatsAggregator.NIGHT,
- TimeStatsAggregator.LATENIGHT };
-
- private static final int mFeatureValueStart = 4;
- private static final int mFeatureValueEnd = 11;
-
- public ClusterManager(Context context) {
- mStorage = new AggregatorRecordStorage(context, SEMANTIC_TABLE, SEMANTIC_COLUMNS);
-
- loadSemanticClusters();
- }
-
- public void addSample(Location location) {
- float bestClusterDistance = Float.MAX_VALUE;
- int bestClusterIndex = -1;
- long lastDuration;
- long currentTime = location.getTime() / 1000; // measure time in seconds
-
- if (mLastLocation != null) {
- if (location.getTime() == mLastLocation.getTime()) {
- return;
- }
- // get the duration spent in the last location
- long duration = (location.getTime() - mLastLocation.getTime()) / 1000;
- mClusterDuration += duration;
-
- Log.v(TAG, "sample duration: " + duration +
- ", number of clusters: " + mLocationClusters.size());
-
- synchronized (mLocationClusters) {
- // add the last location to cluster.
- // first find the cluster it belongs to.
- for (int i = 0; i < mLocationClusters.size(); ++i) {
- float distance = mLocationClusters.get(i).distanceToCenter(mLastLocation);
- Log.v(TAG, "clulster " + i + " is within " + distance + " meters");
- if (distance < bestClusterDistance) {
- bestClusterDistance = distance;
- bestClusterIndex = i;
- }
- }
-
- // add the location to the selected cluster
- if (bestClusterDistance < LOCATION_CLUSTER_RADIUS) {
- mLocationClusters.get(bestClusterIndex).addSample(mLastLocation, duration);
- } else {
- // if it is far away from all existing clusters, create a new cluster.
- LocationCluster cluster = new LocationCluster(mLastLocation, duration);
- mLocationClusters.add(cluster);
- }
- }
- } else {
- mConsolidateRef = currentTime;
- mRefreshRef = currentTime;
-
- if (mLocationClusters.isEmpty()) {
- mClusterDuration = 0;
- }
- }
-
- long collectDuration = currentTime - mConsolidateRef;
- Log.v(TAG, "collect duration: " + collectDuration);
- if (collectDuration > CONSOLIDATE_INTERVAL) {
- // TODO : conslidation takes time. move this to a separate thread later.
- consolidateClusters();
- mConsolidateRef = currentTime;
-
- long refreshDuration = currentTime - mRefreshRef;
- Log.v(TAG, "refresh duration: " + refreshDuration);
- if (refreshDuration > LOCATION_REFRESH_PERIOD) {
- updateSemanticClusters();
- mRefreshRef = currentTime;
- }
- saveSemanticClusters();
- }
-
- mLastLocation = location;
- }
-
- private void consolidateClusters() {
- synchronized (mSemanticClusters) {
- LocationCluster locationCluster;
- for (int i = mLocationClusters.size() - 1; i >= 0; --i) {
- locationCluster = mLocationClusters.get(i);
- locationCluster.consolidate();
- }
-
- // merge clusters whose regions are overlapped. note that after merge
- // cluster center changes but cluster size remains unchanged.
- for (int i = mLocationClusters.size() - 1; i >= 0; --i) {
- locationCluster = mLocationClusters.get(i);
- for (int j = i - 1; j >= 0; --j) {
- float distance =
- mLocationClusters.get(j).distanceToCluster(locationCluster);
- if (distance < LOCATION_CLUSTER_RADIUS) {
- mLocationClusters.get(j).absorbCluster(locationCluster);
- mLocationClusters.remove(locationCluster);
- }
- }
- }
- Log.v(TAG, mLocationClusters.size() + " location clusters after consolidate");
-
- // assign each candidate to a semantic cluster and check if new semantic
- // clusters are found
- for (LocationCluster candidate : mLocationClusters) {
- if (candidate.hasSemanticId() ||
- candidate.hasSemanticClusterId() ||
- !candidate.passThreshold(SEMANTIC_CLUSTER_THRESHOLD)) {
- continue;
- }
-
- // find the closest semantic cluster
- float bestClusterDistance = Float.MAX_VALUE;
- String bestClusterId = "Unused Id";
- for (BaseCluster cluster : mSemanticClusters) {
- float distance = cluster.distanceToCluster(candidate);
- Log.v(TAG, distance + "distance to semantic cluster: " +
- cluster.getSemanticId());
-
- if (distance < bestClusterDistance) {
- bestClusterDistance = distance;
- bestClusterId = cluster.getSemanticId();
- }
- }
-
- // if candidate doesn't belong to any semantic cluster, create a new
- // semantic cluster
- if (bestClusterDistance > SEMANTIC_CLUSTER_RADIUS) {
- candidate.generateSemanticId(mSemanticClusterCount++);
- mSemanticClusters.add(candidate);
- } else {
- candidate.setSemanticClusterId(bestClusterId);
- }
- }
- Log.v(TAG, mSemanticClusters.size() + " semantic clusters after consolidate");
- }
- }
-
- private void updateSemanticClusters() {
- synchronized (mSemanticClusters) {
- // create index to cluster map
- HashMap<String, BaseCluster> semanticIdMap =
- new HashMap<String, BaseCluster>();
- for (BaseCluster cluster : mSemanticClusters) {
- // TODO: apply forgetting factor on existing semantic cluster stats,
- // duration, histogram, etc.
- cluster.forgetPastHistory();
- semanticIdMap.put(cluster.getSemanticId(), cluster);
- }
-
- // assign each candidate to a semantic cluster
- for (LocationCluster cluster : mLocationClusters) {
- if (cluster.hasSemanticClusterId()) {
- BaseCluster semanticCluster =
- semanticIdMap.get(cluster.getSemanticClusterId());
- semanticCluster.absorbCluster(cluster);
- }
- }
- // reset location clusters.
- mLocationClusters.clear();
- }
- }
-
- private void loadSemanticClusters() {
- List<Map<String, String> > allData = mStorage.getAllData();
- HashMap<String, Long> histogram = new HashMap<String, Long>();
-
- synchronized (mSemanticClusters) {
- mSemanticClusters.clear();
- for (Map<String, String> map : allData) {
- String semanticId = map.get(SEMANTIC_ID);
- double longitude = Double.parseDouble(map.get(SEMANTIC_LONGITUDE));
- double latitude = Double.parseDouble(map.get(SEMANTIC_LATITUDE));
- long duration = Long.parseLong(map.get(SEMANTIC_DURATION));
- BaseCluster cluster =
- new BaseCluster(semanticId, longitude, latitude, duration);
-
- histogram.clear();
- for (int i = mFeatureValueStart; i <= mFeatureValueEnd; i++) {
- String featureValue = SEMANTIC_COLUMNS[i];
- if (map.containsKey(featureValue)) {
- histogram.put(featureValue, Long.valueOf(map.get(featureValue)));
- }
- }
- cluster.setHistogram(histogram);
- mSemanticClusters.add(cluster);
- }
- mSemanticClusterCount = mSemanticClusters.size();
- Log.e(TAG, "load " + mSemanticClusterCount + " semantic clusters.");
- }
- }
-
- private void saveSemanticClusters() {
- HashMap<String, String> rowFeatures = new HashMap<String, String>();
-
- mStorage.removeAllData();
- synchronized (mSemanticClusters) {
- for (BaseCluster cluster : mSemanticClusters) {
- rowFeatures.clear();
- rowFeatures.put(SEMANTIC_ID, cluster.getSemanticId());
-
- rowFeatures.put(SEMANTIC_LONGITUDE,
- String.valueOf(cluster.getCenterLongitude()));
- rowFeatures.put(SEMANTIC_LATITUDE,
- String.valueOf(cluster.getCenterLatitude()));
- rowFeatures.put(SEMANTIC_DURATION,
- String.valueOf(cluster.getDuration()));
-
- HashMap<String, Long> histogram = cluster.getHistogram();
- for (Map.Entry<String, Long> entry : histogram.entrySet()) {
- rowFeatures.put(entry.getKey(), String.valueOf(entry.getValue()));
- }
- mStorage.addData(rowFeatures);
- Log.e(TAG, "saving semantic cluster: " + rowFeatures);
- }
- }
- }
-
- public String getSemanticLocation() {
- String label = LocationStatsAggregator.UNKNOWN_LOCATION;
-
- // instead of using the last location, try acquiring the latest location.
- if (mLastLocation != null) {
- // TODO: use fast neatest neighbor search speed up location search
- synchronized (mSemanticClusters) {
- for (BaseCluster cluster: mSemanticClusters) {
- if (cluster.distanceToCenter(mLastLocation) < SEMANTIC_CLUSTER_RADIUS) {
- return cluster.getSemanticId();
- }
- }
- }
- }
- return label;
- }
-
- public List<String> getClusterNames() {
- ArrayList<String> clusters = new ArrayList<String>();
- synchronized (mSemanticClusters) {
- for (BaseCluster cluster: mSemanticClusters) {
- clusters.add(cluster.getSemanticId());
- }
- }
- return clusters;
- }
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-28 05:42:15 +0000