research-article

Towards mobility-based clustering

Authors:

Minglu LiAuthors Info & Claims

KDD '10: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 919 - 928

https://doi.org/10.1145/1835804.1835920

Published: 25 July 2010 Publication History

Abstract

Identifying hot spots of moving vehicles in an urban area is essential to many smart city applications. The practical research on hot spots in smart city presents many unique features, such as highly mobile environments, supremely limited size of sample objects, and the non-uniform, biased samples. All these features have raised new challenges that make the traditional density-based clustering algorithms fail to capture the real clustering property of objects, making the results less meaningful. In this paper we propose a novel, non-density-based approach called mobility-based clustering. The key idea is that sample objects are employed as "sensors" to perceive the vehicle crowdedness in nearby areas using their instant mobility, rather than the "object representatives". As such the mobility of samples is naturally incorporated. Several key factors beyond the vehicle crowdedness have been identified and techniques to compensate these effects are proposed. We evaluate the performance of mobility-based clustering based on real traffic situations. Experimental results show that using 0.3% of vehicles as the samples, mobility-based clustering can accurately identify hot spots which can hardly be obtained by the latest representative algorithm UMicro.

Supplementary Material

JPG File (kdd2010_liu_tmc_01.jpg)

Download
9.00 KB

MOV File (kdd2010_liu_tmc_01.mov)

Download
77.00 MB

References

[1]

Smart City Research Group. http: //www.cse.ust.hk/scrg, May. 1st 2010.

[2]

C. Aggarwal and P. Yu. A framework for clustering uncertain data streams. In Proc. of ICDE., 2008.

Digital Library

[3]

G. Aggarwal, T. Feder, K. Kenthapadi, S. Khuller, R. Panigrahy, D. Thomas, and A. Zhu. Achieving anonymity via clustering. In Proc. of PODS, 2006.

Digital Library

[4]

R. A. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison-Wesley Longman Publishing Co., Inc., 1999.

Digital Library

[5]

C. Benjamin. Detecting the onset of congestion rapidly with existing traffic detectors. Transportation Research, 2003.

[6]

D. Chakrabarti, R. Kumar, and A. Tomkins. Evolutionary clustering. In Proc. of ACM SIGKDD, 2006.

Digital Library

[7]

Y. Chen and L. Tu. Density-based clustering for real-time stream data. In Proc. of ACM SIGKDD, 2007.

Digital Library

[8]

S. Gaffney and P. Smyth. Trajectory clustering with mixtures of regression models. In Proc. of ACM SIGKDD, 1999.

Digital Library

[9]

F. Gullo, G. Ponti, A. Tagarelli, and S. Greco. A hierarchical algorithm for clustering uncertain data via an information-theoretic approach. In Proc. of ICDM, 2008.

Digital Library

[10]

J. Han, R. B. Altman, V. Kumar, H. Mannila, and D. Pregibon. Emerging scientific applications in data mining. Commun. ACM, 45(8), 2002.

Digital Library

[11]

C. Jin, K. Yi, L. Chen, J. X. Yu, and X. Lin. Sliding-window top-k queries on uncertain streams. Proc. VLDB Endow., 2008.

Digital Library

[12]

B. Kao, S. D. Lee, D. W. Cheung, W.-S. Ho, and K. F. Chan. Clustering uncertain data using voronoi diagrams. In Proc. of ICDM, 2008.

Digital Library

[13]

H.-P. Kriegel, M. Renz, M. Schubert, and A. Zuefle. Statistical density prediction in traffic networks. In Proc. of SIAM ICDM, 2007.

[14]

T. Li and S. S. Anand. Hirel: An incremental clustering algorithm for relational datasets. In Proc. of ICDM, 2008.

Digital Library

[15]

X. Li, J. Han, J.-G. Lee, and H. Gonzalez. Traffic density-based discovery of hot routes in road networks. In Proc. of SSTD, 2007.

Digital Library

[16]

Y. Li, J. Han, and J. Yang. Clustering moving objects. In Proc. of ACM SIGKDD, 2004.

Digital Library

[17]

Y. Liu, L. Chen, J. Pei, Q. Chen, and Y. Zhao. Mining frequent trajectory patterns for activity monitoring using radio frequency tag arrays. In Proc. of IEEE PerCom, 2007.

Digital Library

[18]

L. Mo, Y. He, Y. Liu, J. Zhao, S. Tang, X. Li, and G. Dai. Canopy closure estimates with greenorbs: Sustainable sensing in the forest. In Proc. of ACM SenSys, 2009.

Digital Library

[19]

R. T. Ng and J. Han. Clarans: A method for clustering objects for spatial data mining. IEEE Trans. on Knowl. and Data Eng., 14(5), 2002.

Digital Library

[20]

J. Pei, M. Hua, Y. Tao, and X. Lin. Query answering techniques on uncertain and probabilistic data: tutorial summary. In Proc. of ACM SIGMOD, 2008.

Digital Library

[21]

J. Sander, M. Ester, H.-P. Kriegel, and X. Xu. Density-based clustering in spatial databases: The algorithm gdbscan and its applications. Data Min. Knowl. Discov., 2(2), 1998.

Digital Library

[22]

K. Sirvio and J. Hollmén. Spatio-temporal road condition forecasting with markov chains and artificial neural networks. In Proc. of HAIS, 2008.

Digital Library

[23]

T. Xu, Z. M. Zhang, P. S. Yu, and B. Long. Evolutionary clustering by hierarchical dirichlet process with hidden markov state. In Proc. of ICDM, 2008.

Digital Library

[24]

H. Yoon and C. Shahabi. Robust time-referenced segmentation of moving object trajectories. In Proc. of ICDM, 2008.

Digital Library

[25]

J. Yoon, B. Noble, and M. Liu. Surface street traffic estimation. In Proc. of ACM MobiSys, 2007.

Digital Library

[26]

T. Zhang, R. Ramakrishnan, and M. Livny. Birch: an efficient data clustering method for very large databases. SIGMOD Rec., 25(2), 1996.

Digital Library

[27]

H. Zhu, Y. Zhu, M. Li, and L. Ni. Seer: Metropolitan-scale traffic perception based on lossy sensory data. In Proc. of IEEE INFOCOM, 2009.

Cited By

Long TChen PXia YMa YSun XZhao JLyu Y(2024)A Deep Deterministic Policy Gradient-Based Method for Enforcing Service Fault-Tolerance in MECChinese Journal of Electronics10.23919/cje.2023.00.10533:4(899-909)Online publication date: Jul-2024
https://doi.org/10.23919/cje.2023.00.105
Li YSun XXia YChen PLi YPeng Q(2023)M-MNFT: A Novel Modified (m, n)-Fault Tolerance Approach for Service Migration in Vehicular Edge Computing2023 IEEE International Conference on Software Services Engineering (SSE)10.1109/SSE60056.2023.00031(170-179)Online publication date: Jul-2023
https://doi.org/10.1109/SSE60056.2023.00031
Ma YDai MShao SXia YLi FShen YLi JLi YPeng H(2023)A Performance and Reliability-Guaranteed Predictive Approach to Service Migration Path Selection in Mobile ComputingIEEE Internet of Things Journal10.1109/JIOT.2023.327888410:20(17977-17987)Online publication date: 15-Oct-2023
https://doi.org/10.1109/JIOT.2023.3278884
Show More Cited By

Index Terms

Towards mobility-based clustering
1. Information systems
  1. Information retrieval
    1. Retrieval tasks and goals
      1. Clustering and classification
  2. Information systems applications
    1. Data mining
      1. Clustering

Recommendations

Performance analysis of mobility-based d-hop (MobDHop) clustering algorithm for mobile ad hoc networks

This paper presents the performance analysis of the mobility-based d-hop (MobDHop) clustering algorithm, which forms variable-diameter clusters based on node mobility patterns in MANETs. Unlike existing clustering algorithms, the diameter of clusters is ...
A Clustering Control Scheme for V2V Live Road Surveillance (LRS)
CSE '14: Proceedings of the 2014 IEEE 17th International Conference on Computational Science and Engineering

Live Road Surveillance video streaming is a new type of safety data that can be transmitted in Vehicular Ad Hoc Networks (VANETs). Video streaming is a high-bandwidth-demanded service and causes congestion if there are many vehicles that stream video in ...
Mobility-based clustering in VANETs using affinity propagation
GLOBECOM'09: Proceedings of the 28th IEEE conference on Global telecommunications

The recent research in cluster-based MAC and routing schemes for Vehicle Ad Hoc Networks (VANETs) motivates the necessity for a stable VANET clustering algorithm. Due to the highly mobile nature of VANETs, mobility must play an integral role in cluster ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '10: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining

July 2010

1240 pages

ISBN:9781450300551

DOI:10.1145/1835804

General Chairs:
Bharat Rao
Siemens
,
Balaji Krishnapuram
Siemens
,
Program Chairs:
Andrew Tomkins
Google Inc.
,
Qiang Yang
Hong Kong University of Science and Technology

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

KDD '10

Sponsor:

KDD '10: The 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

July 25 - 28, 2010

DC, Washington, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

142
Total Citations
View Citations
1,888
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)9

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Long TChen PXia YMa YSun XZhao JLyu Y(2024)A Deep Deterministic Policy Gradient-Based Method for Enforcing Service Fault-Tolerance in MECChinese Journal of Electronics10.23919/cje.2023.00.10533:4(899-909)Online publication date: Jul-2024
https://doi.org/10.23919/cje.2023.00.105
Li YSun XXia YChen PLi YPeng Q(2023)M-MNFT: A Novel Modified (m, n)-Fault Tolerance Approach for Service Migration in Vehicular Edge Computing2023 IEEE International Conference on Software Services Engineering (SSE)10.1109/SSE60056.2023.00031(170-179)Online publication date: Jul-2023
https://doi.org/10.1109/SSE60056.2023.00031
Ma YDai MShao SXia YLi FShen YLi JLi YPeng H(2023)A Performance and Reliability-Guaranteed Predictive Approach to Service Migration Path Selection in Mobile ComputingIEEE Internet of Things Journal10.1109/JIOT.2023.327888410:20(17977-17987)Online publication date: 15-Oct-2023
https://doi.org/10.1109/JIOT.2023.3278884
Li XZhang SLuo HMa XHe J(2023)Placing Timely Refreshing Services at the Network EdgeIEEE Internet of Things Journal10.1109/JIOT.2023.326830810:18(16450-16464)Online publication date: 15-Sep-2023
https://doi.org/10.1109/JIOT.2023.3268308
Tao TDeng ZChen ZChen LChen LHuang S(2023)Intelligent Urban Sensing for Gas Leakage Risk AssessmentIEEE Access10.1109/ACCESS.2023.326743711(37900-37910)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3267437
Chai HLeng SHe JZhang K(2023)Digital twin empowered lightweight and efficient blockchain for dynamic internet of vehiclesDigital Communications and Networks10.1016/j.dcan.2023.08.004Online publication date: Aug-2023
https://doi.org/10.1016/j.dcan.2023.08.004
Jia QLong T(2023)Charging Behavior of Electric VehiclesCyber–Physical–Human Systems10.1002/9781119857433.ch11(273-297)Online publication date: 9-Jun-2023
https://doi.org/10.1002/9781119857433.ch11
Zhao JMa YXia YDai MChen PLong TShao SLi FLi YZeng F(2022)A Novel Fault-Tolerant Approach for Dynamic Redundant Path Selection Service Migration in Vehicular Edge ComputingApplied Sciences10.3390/app1219998712:19(9987)Online publication date: 4-Oct-2022
https://doi.org/10.3390/app12199987
Xu CWang JWang JYu TZhou YXu YWu DAn C(2022)Offloading Elastic Transfers to Opportunistic Vehicular Networks Based on Imperfect Trajectory PredictionIEEE/ACM Transactions on Networking10.1109/TNET.2022.3189047(1-15)Online publication date: 2022
https://doi.org/10.1109/TNET.2022.3189047
Cai MZhang ZXiong CGou C(2022)An Adaptive Staying Point Recognition Algorithm Based on Spatiotemporal Characteristics Using Cellular Signaling DataIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2021.309463623:8(10458-10468)Online publication date: Aug-2022
https://doi.org/10.1109/TITS.2021.3094636
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents