research-article

Public Access

Toward Mining Stop-by Behaviors in Indoor Space

Authors:

Kun-Ta ChuangAuthors Info & Claims

ACM Transactions on Spatial Algorithms and Systems (TSAS), Volume 3, Issue 2

Article No.: 7, Pages 1 - 38

https://doi.org/10.1145/3106736

Published: 29 August 2017 Publication History

Abstract

In this article, we explore a new mining paradigm, called Indoor Stop-by Patterns (ISP), to discover user stop-by behavior in mall-like indoor environments. The discovery of ISPs enables new marketing collaborations, such as a joint coupon promotion, among stores in indoor spaces (e.g., shopping malls). Moreover, it can also help in eliminating the overcrowding situation. To pursue better practicability, we consider the cost-effective wireless sensor-based environment and conduct the analysis of indoor stop-by behaviors on real data. However, it is a highly challenging issue, in indoor environments, to retrieve frequent ISPs, especially when the issue of user privacy is highlighted nowadays. The mining of ISPs will face a critical challenge from spatial uncertainty. Previous work on mining indoor movement patterns usually relies on precise spatio-temporal information by a specific deployment of positioning devices, which cannot be directly applied. In this article, the proposed Probabilistic Top-k Indoor Stop-by Patterns Discovery (PTkISP) framework incorporates the probabilistic model to identify top-k ISPs over uncertain data collected from sensing logs. Moreover, we develop an uncertain model and devise an Index 1-itemset (IIS) algorithm to enhance the accuracy and efficiency. Our experimental studies show that the proposed PTkISP framework can efficiently discover high-quality ISPs and can provide insightful observations for marketing collaborations.

References

[1]

Serge Abiteboul, Paris Kanellakis, and Gosta Grahne. 1987. On the Representation and Querying of Sets of Possible Worlds. ACM

Digital Library

[2]

Charu C. Aggarwal. 2010. Managing and Mining Uncertain Data. Springer Science 8 Business Media.

[3]

Charu C. Aggarwal and Jiawei Han. 2014. Frequent Pattern Mining. Springer.

[4]

Charu C. Aggarwal, Yan Li, Jianyong Wang, and Jing Wang. 2009. Frequent pattern mining with uncertain data. In SIGKDD. ACM, 29--38.

Digital Library

[5]

Charu C. Aggarwal and S Yu Philip. 2009. A survey of uncertain data algorithms and applications. IEEE Transactions on Knowledge and Data Engineering 21, 5 (2009), 609--623.

Digital Library

[6]

Charu C. Aggarwal and Philip S. Yu. 2008. Privacy-Preserving Data Mining - Models and Algorithms. Springer.

[7]

Rakesh Agrawal, Tomasz Imieliński, and Arun Swami. 1993. Mining association rules between sets of items in large databases. In ACM Sigmod Record. ACM, 207--216.

[8]

R. Agrawal and R. Srikant. 1994. Fast algorithms for mining association rules in large databases. In VLDB. Morgan Kaufmann, 487--499.

[9]

R. Agrawal and R. Srikant. 1995. Mining sequential patterns. In ICDE. IEEE Computer Society, 3--14.

[10]

Rakesh Agrawal and Ramakrishnan Srikant. 1995. Mining sequential patterns. In ICDE. IEEE Computer Society, 3--14.

[11]

Asif Iqbal Baba, Manfred Jaeger, Hua Lu, Torben Bach Pedersen, Wei-Shinn Ku, and Xike Xie. 2016. Learning-based cleansing for indoor RFID data. In SIGMOD. ACM, 925--936.

Digital Library

[12]

Asif Iqbal Baba, Hua Lu, Torben Bach Pedersen, and Xike Xie. 2013. A graph model for false negative handling in indoor RFID tracking data. In SIGSPATIAL. ACM, 454--457.

Digital Library

[13]

Asif Iqbal Baba, Hua Lu, Torben Bach Pedersen, and Xike Xie. 2014. Handling false negatives in indoor RFID data. In MDM. IEEE Computer Society, 117--126.

Digital Library

[14]

Asif Iqbal Baba, Hua Lu, Xike Xie, and Torben Bach Pedersen. 2013. Spatiotemporal data cleansing for indoor RFID tracking data. In MDM. IEEE Computer Society, 187--196.

Digital Library

[15]

Ron Brinkmann. 2008. The Art and Science of Digital Compositing: Techniques for Visual Effects, Animation and Motion Graphics. Morgan Kaufmann.

[16]

Reynold Cheng, Dmitri V Kalashnikov, and Sunil Prabhakar. 2004. Querying imprecise data in moving object environments. IEEE Transactions on Knowledge and Data Engineering 16, 9 (2004), 1112--1127.

Digital Library

[17]

Chun-Kit Chui and Ben Kao. 2008. A decremental approach for mining frequent itemsets from uncertain data. In PAKDD. Springer, 64--75.

[18]

Chun-Kit Chui, Ben Kao, and Edward Hung. 2007. Mining frequent itemsets from uncertain data. In PAKDD. Springer, 47--58.

[19]

Myer L. Coval. 1970. Analysis of hill interaction coefficients and the invalidity of the Kwon and Brown equation. Journal of Biological Chemistry 245, 23 (1970), 6335--6336.

[20]

Bettina Fazzinga, Sergio Flesca, Filippo Furfaro, and Francesco Parisi. 2014. Cleaning trajectory data of RFID-monitored objects through conditioning under integrity constraints. In EDBT. OpenProceedings.org, 379--390.

[21]

Bettina Fazzinga, Sergio Flesca, Filippo Furfaro, and Francesco Parisi. 2014. Offline cleaning of RFID trajectory data. In SSDBM. ACM, 5:1--5:12.

Digital Library

[22]

Bettina Fazzinga, Sergio Flesca, Filippo Furfaro, and Francesco Parisi. 2016. Exploiting integrity constraints for cleaning trajectories of RFID-monitored objects. ACM Trans. Database Syst. 41, 4 (2016), 24:1--24:52.

Digital Library

[23]

Mohamed Medhat Gaber, Arkady Zaslavsky, and Shonali Krishnaswamy. 2005. Mining data streams: A review. ACM Sigmod Record 34, 2 (2005), 18--26.

Digital Library

[24]

Carl Friedrich Gauss. 1809. Theoria Motus Corporum Coelestium in Sectionibus Conicis Solem Ambientium Auctore Carolo Friderico Gauss. sumtibus Frid. Perthes et IH Besser.

[25]

Todd J. Green and Val Tannen. 2006. Models for incomplete and probabilistic information. IEEE Data Eng. Bull. 29, 1 (2006), 17--24.

Digital Library

[26]

Marco Gruteser, Graham Schelle, Ashish Jain, Richard Han, and Dirk Grunwald. 2003. Privacy-aware location sensor networks. In HotOS. USENIX, 163--168.

[27]

Antonin Guttman. 1984. R-trees: A dynamic index structure for spatial searching. In SIGMOD. ACM Press, 47--57.

Digital Library

[28]

Jiawei Han and Jian Pei. 2000. Mining frequent patterns by pattern-growth: Methodology and implications. ACM SIGKDD Explorations Newsletter 2, 2 (2000), 14--20.

Digital Library

[29]

Jiawei Han, Jian Pei, Behzad Mortazavi-Asl, Qiming Chen, Umeshwar Dayal, and Mei-Chun Hsu. 2000. FreeSpan: Frequent pattern-projected sequential pattern mining. In SIGKDD. ACM, 355--359.

Digital Library

[30]

Jiawei Han, Jian Pei, Behzad Mortazavi-Asl, Helen Pinto, Qiming Chen, Umeshwar Dayal, and MC Hsu. 2001. Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth. In ICDE. IEEE Computer Society, 215--224.

[31]

Jiawei Han, Jian Pei, and Xifeng Yan. 2005. Sequential pattern mining by pattern-growth: Principles and extensions. In StudFuzz. Springer, 183--220.

[32]

Jiawei Han, Jian Pei, Yiwen Yin, and Runying Mao. 2004. Mining frequent patterns without candidate generation: A frequent-pattern tree approach. Data Mining and Knowledge Discovery 8, 1 (2004), 53--87.

Digital Library

[33]

John Paulin Hansen, Alexandre Alapetite, Henning Boje Andersen, Lone Malmborg, and Jacob Thommesen. 2009. Location-based services and privacy in airports. In INTERACT. Springer, 168--181.

Digital Library

[34]

Archibald Vivian Hill. 1910. The possible effects of the aggregation of the molecules of haemoglobin on its dissociation curves. J Physiol 40 (1910), 4--7.

[35]

Bernhard Hofmann-Wellenhof, Herbert Lichtenegger, and James Collins. 2012. Global Positioning System: Theory and Practice. Springer Science 8 Business Media.

[36]

S. R. Jeffery, M. N. Garofalakis, and M. J. Franklin. 2006. Adaptive cleaning for RFID data streams. In VLDB. ACM, 163--174.

[37]

Christian S. Jensen, Hua Lu, and Bin Yang. 2009. Graph model based indoor tracking. In MDM. IEEE Computer Society, 122--131.

Digital Library

[38]

Mandeep Kaur, Manjeet Sandhu, Neeraj Mohan, and Parvinder S. Sandhu. 2011. RFID technology principles, advantages, limitations 8 its applications. International Journal of Computer and Electrical Engineering 3, 1 (2011), 151.

[39]

Carson Kai-Sang Leung and Dale A. Brajczuk. 2009. Efficient algorithms for mining constrained frequent patterns from uncertain data. In SIGKDD Workshop on Knowledge Discovery from Uncertain Data. ACM, 9--18.

Digital Library

[40]

Carson Kai-Sang Leung, Mark Anthony F. Mateo, and Dale A. Brajczuk. 2008. A tree-based approach for frequent pattern mining from uncertain data. In PAKDD. Springer, 653--661.

[41]

Carson Kai-Sang Leung and Boyu Hao. 2009. Mining of frequent itemsets from streams of uncertain data. In ICDE. IEEE Computer Society, 1663--1670.

Digital Library

[42]

Carson Kai-Sang Leung, Boyu Hao, and Dale A. Brajczuk. 2010. Mining uncertain data for frequent itemsets that satisfy aggregate constraints. In SAC. ACM, 1034--1038.

Digital Library

[43]

Carson Kai-Sang Leung, Mark Anthony F. Mateo, and Dale A. Brajczuk. 2008. A tree-based approach for frequent pattern mining from uncertain data. In PAKDD. Springer, 653--661.

[44]

Carson Kai-Sang Leung and Syed K. Tanbeer. 2012. Fast tree-based mining of frequent itemsets from uncertain data. In DASFAA. Springer, 272--287.

Digital Library

[45]

Y. Liu, Y. Zhao, L. Chen, J. Pei, and J. Han. 2012. Mining frequent trajectory patterns for activity monitoring using radio frequency tag arrays. IEEE Trans. Parallel Distrib. Syst. 23, 11 (2012), 2138--2149.

Digital Library

[46]

Hua Lu, Chenjuan Guo, Bin Yang, and Christian S. Jensen. 2016. Finding frequently visited indoor POIs using symbolic indoor tracking data. In EDBT. OpenProceedings.org, 449--460.

[47]

Hua Lu, Bin Yang, and Christian S. Jensen. 2011. Spatio-temporal joins on symbolic indoor tracking data. In ICDE. IEEE Computer Society, 816--827.

Digital Library

[48]

Florent Masseglia, Fabienne Cathala, and Pascal Poncelet. 1998. The PSP approach for mining sequential patterns. In PKDD. Springer, 176--184.

[49]

Betty J. Mohler, William B. Thompson, Sarah H. Creem-Regehr, Herbert L. Pick Jr, and William H. Warren Jr. 2007. Visual flow influences gait transition speed and preferred walking speed. Experimental Brain Research 181, 2 (2007), 221--228.

[50]

Jian Pei, Jiawei Han, Runying Mao, and others. 2000. CLOSET: An efficient algorithm for mining frequent closed itemsets. In SIGMOD Workshop. ACM, 21--30.

[51]

Jian Pei, Jiawei Han, and Wei Wang. 2007. Constraint-based sequential pattern mining: The pattern-growth methods. J. Intell. Inf. Syst. 28, 2 (2007), 133--160.

Digital Library

[52]

Helen Pinto, Jiawei Han, Jian Pei, Ke Wang, Qiming Chen, and Umeshwar Dayal. 2001. Multi-dimensional sequential pattern mining. In CIKM. ACM, 81--88.

Digital Library

[53]

L. Radaelli, D. Sabonis, H. Lu, and C. S. Jensen. 2013. Identifying typical movements among indoor objects - Concepts and empirical study. In MDM. IEEE Computer Society, 197--206.

Digital Library

[54]

Stephen Robertson. 2000. Evaluation in information retrieval. In ESSIR. Springer, 81--92.

[55]

Erich Schubert, Arthur Zimek, and Hans-Peter Kriegel. 2013. Geodetic distance queries on R-trees for indexing geographic data. In SSTD. Springer, 146--164.

Digital Library

[56]

Laurie Sullivan. 2005. RFID implementation challenges persist, all this time later. InformationWeek 1059 (2005), 34--40.

[57]

Kim A Taipale. 2003. Data mining and domestic security: Connecting the dots to make sense of data. Colum. Sci. 8 Tech. L. Rev. 5 (2003), 1.

[58]

Jianyong Wang. 2009. Sequential patterns. In Encyclopedia of Database Systems. Springer US, 2621--2626.

[59]

Jianyong Wang, Jiawei Han, and Jian Pei. 2003. Closet+: Searching for the best strategies for mining frequent closed itemsets. In SIGKDD. ACM, 236--245.

Digital Library

[60]

R. Want. 2004. The magic of RFID. Queue 2, 7 (2004), 40--48.

Digital Library

[61]

Stephen A. Weis. 2007. RFID (radio frequency identification): Principles and applications. System 2, 3 (2007), 1--23.

[62]

Chung-Ching Yu and Yen-Liang Chen. 2005. Mining sequential patterns from multidimensional sequence data. IEEE Transactions on Knowledge and Data Engineering 17, 1 (2005), 136--140.

Digital Library

[63]

J. Yu, W.-S. Ku, M.-T. Sun, and H. Lu. 2013. An RFID and particle filter-based indoor spatial query evaluation system. In EDBT. ACM, 263--274.

Digital Library

[64]

Mohammed Javeed Zaki and Ching-Jiu Hsiao. 2002. CHARM: An efficient algorithm for closed itemset mining. In SDM. SIAM, 457--473.

[65]

Rui Zhang, Yunzhong Liu, Yanchao Zhang, and Jinyuan Sun. 2011. Fast identification of the missing tags in a large RFID system. In SECON. IEEE, 278--286.

Cited By

Li HLiu TChan HLu H(2022)Spatial data analysis for intelligent buildings: Awareness of context and data uncertaintyFrontiers in Big Data10.3389/fdata.2022.10491985Online publication date: 7-Nov-2022
https://doi.org/10.3389/fdata.2022.1049198
Li HTang BLu HCheema MJensen CIves ZBonifati AEl Abbadi A(2022)Spatial Data Quality in the IoT Era: Management and ExploitationProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3522568(2474-2482)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3522568
Li HLu HJensen CTang BCheema M(2022)Spatial Data Quality in the Internet of Things: Management, Exploitation, and ProspectsACM Computing Surveys10.1145/349833855:3(1-41)Online publication date: 3-Feb-2022
https://dl.acm.org/doi/10.1145/3498338
Show More Cited By

Index Terms

Toward Mining Stop-by Behaviors in Indoor Space
1. Theory of computation
  1. Theory and algorithms for application domains

Recommendations

Toward mining user movement behaviors in indoor environments

In this paper, we explore a new mining paradigm, called User Visited Patterns (abbreviated as UVP), to discover user visited behavior in the mall-like indoor environment. It is a highly challenging issue, in the indoor environment, to retrieve the ...
Discovering Interesting Patterns from Hypergraphs
A hypergraph is a complex data structure capable of expressing associations among any number of data entities. Overcoming the limitations of traditional graphs, hypergraphs are useful to model real-life problems. Frequent pattern mining is one of the most ...
Discovering User-context in Indoor Space
ISA'18: Proceedings of the 9th ACM SIGSPATIAL International Workshop on Indoor Spatial Awareness

Recently, there has been a significant progress of context awareness due to sensor and mobility technologies and machine learning for their interpretation. A large part of the user's context is determined by her/his location. Since the notion of indoor ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Spatial Algorithms and Systems

ACM Transactions on Spatial Algorithms and Systems Volume 3, Issue 2

SIGSPATIAL Paper and Regular Papers

June 2017

132 pages

ISSN:2374-0353

EISSN:2374-0361

DOI:10.1145/3129284

Editor:
Hanan Samet
University of Maryland, College Park

Issue’s Table of Contents

Copyright © 2017 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 August 2017

Accepted: 01 June 2017

Revised: 01 March 2017

Received: 01 September 2016

Published in TSAS Volume 3, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Science Foundation
Ministry of Science and Technology, R.O.C.

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
251
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)4

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li HLiu TChan HLu H(2022)Spatial data analysis for intelligent buildings: Awareness of context and data uncertaintyFrontiers in Big Data10.3389/fdata.2022.10491985Online publication date: 7-Nov-2022
https://doi.org/10.3389/fdata.2022.1049198
Li HTang BLu HCheema MJensen CIves ZBonifati AEl Abbadi A(2022)Spatial Data Quality in the IoT Era: Management and ExploitationProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3522568(2474-2482)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3522568
Li HLu HJensen CTang BCheema M(2022)Spatial Data Quality in the Internet of Things: Management, Exploitation, and ProspectsACM Computing Surveys10.1145/349833855:3(1-41)Online publication date: 3-Feb-2022
https://dl.acm.org/doi/10.1145/3498338
Liu ZShi WYu YChen PYu Chen B(2022)A LSTM-based approach for modelling the movement uncertainty of indoor trajectories with mobile sensing dataInternational Journal of Applied Earth Observation and Geoinformation10.1016/j.jag.2022.102758108(102758)Online publication date: Apr-2022
https://doi.org/10.1016/j.jag.2022.102758
Monica SBergenti F(2020)An Algorithm for Accurate and Robust Indoor Localization Based on Nonlinear ProgrammingElectronics10.3390/electronics90100659:1(65)Online publication date: 1-Jan-2020
https://doi.org/10.3390/electronics9010065
Monica SBergenti F(2020)Interval arithmetic to support effective indoor positioning of software agentsIntelligenza Artificiale10.3233/IA-19004214:1(59-73)Online publication date: 17-Sep-2020
https://doi.org/10.3233/IA-190042
Li HLu HCheema MShou LChen G(2020)Indoor Mobility Semantics Annotation Using Coupled Conditional Markov Networks2020 IEEE 36th International Conference on Data Engineering (ICDE)10.1109/ICDE48307.2020.00128(1441-1452)Online publication date: Apr-2020
https://doi.org/10.1109/ICDE48307.2020.00128

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents