Mining time-aware transit patterns for route recommendation in big check-in data

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In current location-based services, there are numerous travel route patterns hidden in the user check-in behaviors over locations in a city. Such records rapidly accumulate and update over time, so that an efficient and scalable algorithm is demanded to mine the useful travel patterns from the big check-in data. However, discovering travel patterns under efficiency and scalability concerns from large-scaled location data had not ever carefully tackled yet. In this paper, we propose to mine the Time-aware Transit Patterns (TTP), which capture the representative traveling behaviors over consecutive locations, from the big check-in data. We model the travel behaviors among different locations into a Route Transit Graph (RTG), in which nodes represents locations, and edges denotes the transit behaviors of users between locations with certain time intervals. The time-aware transit patterns, which are required to satisfy frequent, closed, and connected requirements due to respectively physical meanings, are mined based on the RTG transaction database. To achieve such goal, we propose a novel TTPM-algorithm, which is devised to only need to scan the database once and generate no unnecessary candidates, and thus guarantee better time efficiency lower and memory usage. Experiments conducted on different cities demonstrate the promising performance of our TTPM-algorithm, comparing to a modified Apriori method.

Original languageEnglish
Title of host publicationTrends and Applications in Knowledge Discovery and Data Mining - PAKDD 2014 International Workshops
Subtitle of host publicationDANTH, BDM, MobiSocial, BigEC, CloudSD, MSMV-MBI, SDA, DMDA-Health, ALSIP, SocNet, DMBIH, BigPMA, Revised Selected Papers
EditorsWen-Chih Peng, Haixun Wang, Zhi-Hua Zhou, Tu Bao Ho, Vincent S. Tseng, Arbee L.P. Chen, James Bailey
PublisherSpringer Verlag
Pages818-830
Number of pages13
ISBN (Electronic)9783319131856
DOIs
Publication statusPublished - 2014 Jan 1
EventInternational Workshops on Data Mining and Decision Analytics for Public Health, Biologically Inspired Data Mining Techniques, Mobile Data Management, Mining, and Computing on Social Networks, Big Data Science and Engineering on E-Commerce, Cloud Service Discovery, MSMV-MBI, Scalable Dats Analytics, Data Mining and Decision Analytics for Public Health and Wellness, Algorithms for Large-Scale Information Processing in Knowledge Discovery, Data Mining in Social Networks, Data Mining in Biomedical informatics and Healthcare, Pattern Mining and Application of Big Data in conjunction with 18th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2014 - Tainan, Taiwan
Duration: 2014 May 132014 May 16

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8643
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherInternational Workshops on Data Mining and Decision Analytics for Public Health, Biologically Inspired Data Mining Techniques, Mobile Data Management, Mining, and Computing on Social Networks, Big Data Science and Engineering on E-Commerce, Cloud Service Discovery, MSMV-MBI, Scalable Dats Analytics, Data Mining and Decision Analytics for Public Health and Wellness, Algorithms for Large-Scale Information Processing in Knowledge Discovery, Data Mining in Social Networks, Data Mining in Biomedical informatics and Healthcare, Pattern Mining and Application of Big Data in conjunction with 18th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2014
CountryTaiwan
CityTainan
Period14-05-1314-05-16

Fingerprint

Mining
Recommendations
Location based services
Accumulate
Graph in graph theory
Scalability
Transactions
Consecutive
Data storage equipment
Update
Denote
Closed
Interval
Requirements
Vertex of a graph
Demonstrate
Experiment
Experiments

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Hsieh, H-P., & Li, C-T. (2014). Mining time-aware transit patterns for route recommendation in big check-in data. In W-C. Peng, H. Wang, Z-H. Zhou, T. B. Ho, V. S. Tseng, A. L. P. Chen, & J. Bailey (Eds.), Trends and Applications in Knowledge Discovery and Data Mining - PAKDD 2014 International Workshops: DANTH, BDM, MobiSocial, BigEC, CloudSD, MSMV-MBI, SDA, DMDA-Health, ALSIP, SocNet, DMBIH, BigPMA, Revised Selected Papers (pp. 818-830). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8643). Springer Verlag. https://doi.org/10.1007/978-3-319-13186-3_73
Hsieh, Hsun-Ping ; Li, Cheng-Te. / Mining time-aware transit patterns for route recommendation in big check-in data. Trends and Applications in Knowledge Discovery and Data Mining - PAKDD 2014 International Workshops: DANTH, BDM, MobiSocial, BigEC, CloudSD, MSMV-MBI, SDA, DMDA-Health, ALSIP, SocNet, DMBIH, BigPMA, Revised Selected Papers. editor / Wen-Chih Peng ; Haixun Wang ; Zhi-Hua Zhou ; Tu Bao Ho ; Vincent S. Tseng ; Arbee L.P. Chen ; James Bailey. Springer Verlag, 2014. pp. 818-830 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{c8c8372063774e0185d7f602d9bccafa,
title = "Mining time-aware transit patterns for route recommendation in big check-in data",
abstract = "In current location-based services, there are numerous travel route patterns hidden in the user check-in behaviors over locations in a city. Such records rapidly accumulate and update over time, so that an efficient and scalable algorithm is demanded to mine the useful travel patterns from the big check-in data. However, discovering travel patterns under efficiency and scalability concerns from large-scaled location data had not ever carefully tackled yet. In this paper, we propose to mine the Time-aware Transit Patterns (TTP), which capture the representative traveling behaviors over consecutive locations, from the big check-in data. We model the travel behaviors among different locations into a Route Transit Graph (RTG), in which nodes represents locations, and edges denotes the transit behaviors of users between locations with certain time intervals. The time-aware transit patterns, which are required to satisfy frequent, closed, and connected requirements due to respectively physical meanings, are mined based on the RTG transaction database. To achieve such goal, we propose a novel TTPM-algorithm, which is devised to only need to scan the database once and generate no unnecessary candidates, and thus guarantee better time efficiency lower and memory usage. Experiments conducted on different cities demonstrate the promising performance of our TTPM-algorithm, comparing to a modified Apriori method.",
author = "Hsun-Ping Hsieh and Cheng-Te Li",
year = "2014",
month = "1",
day = "1",
doi = "10.1007/978-3-319-13186-3_73",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "818--830",
editor = "Wen-Chih Peng and Haixun Wang and Zhi-Hua Zhou and Ho, {Tu Bao} and Tseng, {Vincent S.} and Chen, {Arbee L.P.} and James Bailey",
booktitle = "Trends and Applications in Knowledge Discovery and Data Mining - PAKDD 2014 International Workshops",
address = "Germany",

}

Hsieh, H-P & Li, C-T 2014, Mining time-aware transit patterns for route recommendation in big check-in data. in W-C Peng, H Wang, Z-H Zhou, TB Ho, VS Tseng, ALP Chen & J Bailey (eds), Trends and Applications in Knowledge Discovery and Data Mining - PAKDD 2014 International Workshops: DANTH, BDM, MobiSocial, BigEC, CloudSD, MSMV-MBI, SDA, DMDA-Health, ALSIP, SocNet, DMBIH, BigPMA, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8643, Springer Verlag, pp. 818-830, International Workshops on Data Mining and Decision Analytics for Public Health, Biologically Inspired Data Mining Techniques, Mobile Data Management, Mining, and Computing on Social Networks, Big Data Science and Engineering on E-Commerce, Cloud Service Discovery, MSMV-MBI, Scalable Dats Analytics, Data Mining and Decision Analytics for Public Health and Wellness, Algorithms for Large-Scale Information Processing in Knowledge Discovery, Data Mining in Social Networks, Data Mining in Biomedical informatics and Healthcare, Pattern Mining and Application of Big Data in conjunction with 18th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2014, Tainan, Taiwan, 14-05-13. https://doi.org/10.1007/978-3-319-13186-3_73

Mining time-aware transit patterns for route recommendation in big check-in data. / Hsieh, Hsun-Ping; Li, Cheng-Te.

Trends and Applications in Knowledge Discovery and Data Mining - PAKDD 2014 International Workshops: DANTH, BDM, MobiSocial, BigEC, CloudSD, MSMV-MBI, SDA, DMDA-Health, ALSIP, SocNet, DMBIH, BigPMA, Revised Selected Papers. ed. / Wen-Chih Peng; Haixun Wang; Zhi-Hua Zhou; Tu Bao Ho; Vincent S. Tseng; Arbee L.P. Chen; James Bailey. Springer Verlag, 2014. p. 818-830 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8643).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Mining time-aware transit patterns for route recommendation in big check-in data

AU - Hsieh, Hsun-Ping

AU - Li, Cheng-Te

PY - 2014/1/1

Y1 - 2014/1/1

N2 - In current location-based services, there are numerous travel route patterns hidden in the user check-in behaviors over locations in a city. Such records rapidly accumulate and update over time, so that an efficient and scalable algorithm is demanded to mine the useful travel patterns from the big check-in data. However, discovering travel patterns under efficiency and scalability concerns from large-scaled location data had not ever carefully tackled yet. In this paper, we propose to mine the Time-aware Transit Patterns (TTP), which capture the representative traveling behaviors over consecutive locations, from the big check-in data. We model the travel behaviors among different locations into a Route Transit Graph (RTG), in which nodes represents locations, and edges denotes the transit behaviors of users between locations with certain time intervals. The time-aware transit patterns, which are required to satisfy frequent, closed, and connected requirements due to respectively physical meanings, are mined based on the RTG transaction database. To achieve such goal, we propose a novel TTPM-algorithm, which is devised to only need to scan the database once and generate no unnecessary candidates, and thus guarantee better time efficiency lower and memory usage. Experiments conducted on different cities demonstrate the promising performance of our TTPM-algorithm, comparing to a modified Apriori method.

AB - In current location-based services, there are numerous travel route patterns hidden in the user check-in behaviors over locations in a city. Such records rapidly accumulate and update over time, so that an efficient and scalable algorithm is demanded to mine the useful travel patterns from the big check-in data. However, discovering travel patterns under efficiency and scalability concerns from large-scaled location data had not ever carefully tackled yet. In this paper, we propose to mine the Time-aware Transit Patterns (TTP), which capture the representative traveling behaviors over consecutive locations, from the big check-in data. We model the travel behaviors among different locations into a Route Transit Graph (RTG), in which nodes represents locations, and edges denotes the transit behaviors of users between locations with certain time intervals. The time-aware transit patterns, which are required to satisfy frequent, closed, and connected requirements due to respectively physical meanings, are mined based on the RTG transaction database. To achieve such goal, we propose a novel TTPM-algorithm, which is devised to only need to scan the database once and generate no unnecessary candidates, and thus guarantee better time efficiency lower and memory usage. Experiments conducted on different cities demonstrate the promising performance of our TTPM-algorithm, comparing to a modified Apriori method.

UR - http://www.scopus.com/inward/record.url?scp=84915745461&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84915745461&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-13186-3_73

DO - 10.1007/978-3-319-13186-3_73

M3 - Conference contribution

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 818

EP - 830

BT - Trends and Applications in Knowledge Discovery and Data Mining - PAKDD 2014 International Workshops

A2 - Peng, Wen-Chih

A2 - Wang, Haixun

A2 - Zhou, Zhi-Hua

A2 - Ho, Tu Bao

A2 - Tseng, Vincent S.

A2 - Chen, Arbee L.P.

A2 - Bailey, James

PB - Springer Verlag

ER -

Hsieh H-P, Li C-T. Mining time-aware transit patterns for route recommendation in big check-in data. In Peng W-C, Wang H, Zhou Z-H, Ho TB, Tseng VS, Chen ALP, Bailey J, editors, Trends and Applications in Knowledge Discovery and Data Mining - PAKDD 2014 International Workshops: DANTH, BDM, MobiSocial, BigEC, CloudSD, MSMV-MBI, SDA, DMDA-Health, ALSIP, SocNet, DMBIH, BigPMA, Revised Selected Papers. Springer Verlag. 2014. p. 818-830. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-13186-3_73