More Web Proxy on the site http://driver.im/

research-article

Discovering Spatial High Utility Itemsets in Spatiotemporal Databases

Authors:

Masashi Toyoda,

Philippe Fournier-Viger,

P. Krishna Reddy,

Masaru KitsuregawaAuthors Info & Claims

SSDBM '19: Proceedings of the 31st International Conference on Scientific and Statistical Database Management

Pages 49 - 60

https://doi.org/10.1145/3335783.3335789

Published: 23 July 2019 Publication History

Abstract

In real-world databases, high utility itemset (HUI) is an important class of regularities. Most previous studies have focused on mining HUIs in transactional databases and did not consider the spatiotemporal characteristics of items. In this study, a more flexible model of spatial HUIs (SHUIs) that exist in spatiotemporal databases is proposed. In a spatiotemporal database (STD), an itemset is said to be an SHUI if its utility is not less than a user-specified minimum utility and the distance between any two of its items is not more than a user-specified maximum distance. Identifying SHUIs is very challenging because the generated itemsets do not satisfy the anti-monotonic property. In this study, we present two novel pruning techniques for reducing computational costs. Moreover, a fast single scan algorithm is presented for effectively evaluating all SHUIs in a STD. Furthermore, two case studies are presented, in which the proposed model is used to identify useful information in traffic congestion data and air pollution data.

References

[1]

Rakesh Agrawal, Ramakrishnan Srikant, et al. 1994. Fast algorithms for mining association rules. In VLDB, Vol. 1215. 487--499.

Digital Library

[2]

Chowdhury Farhan Ahmed, Syed Khairuzzaman Tanbeer, and Byeong-Soo Jeong. 2010. Mining High Utility Web Access Sequences in Dynamic Web Log Data. In International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD '10). 76--81.

Digital Library

[3]

Chowdhury Farhan Ahmed, Syed Khairuzzaman Tanbeer, Byeong-Soo Jeong, and Young-Koo Lee. 2009. Efficient tree structures for high utility pattern mining in incremental databases. IEEE TKDE 21, 12 (2009), 1708--1721.

Digital Library

[4]

Statistics Bureau. {Online accessed on 28-Feb-2019}. Japanese Industrial Standard X0410. http://www.stat.go.jp/english/data/mesh/02.html.

[5]

C. H. Cai, A. W. C. Fu, C. H. Cheng, and W. W. Kwong. 1998. Mining association rules with weighted items. In International Database Engineering and Applications Symposium. 68--77.

Digital Library

[6]

Wei Ding, Christoph F. Eick, Jing Wang, and Xiaojing Yuan. 2006. A Framework for Regional Association Rule Mining in Spatial Datasets. In Proceedings of the Sixth International Conference on Data Mining (ICDM '06). 851--856.

Digital Library

[7]

Christoph F. Eick, Rachana Parmar, Wei Ding, Tomasz F. Stepinski, and Jean-Philippe Nicot. 2008. Finding Regional Co-location Patterns for Sets of Continuous Variables in Spatial Datasets. In Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS '08). Article 30, 10 pages.

Digital Library

[8]

Philippe Fournier-Viger, Jerry Chun-Wei Lin, Quang-Huy Duong, and Thu-Lan Dam. 2016. PHM: Mining Periodic High-Utility Itemsets. In Industrial Conference on Data Mining. 64--79.

[9]

Wensheng Gan, Jerry Chun-Wei Lin, Philippe Fournier-Viger, Han-Chieh Chao, Tzung-Pei Hong, and Hamido Fujita. 2018. A survey of incremental high-utility itemset mining. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 8, 2 (2018).

Digital Library

[10]

R. Uday Kiran, Amulya Kotni, P. Krishna Reddy, Masashi Toyoda, Subhash Bhalla, and Masaru Kitsuregawa. 2018. Efficient Discovery of Weighted Frequent Itemsets in Very Large Transactional Databases: A Re-visit. In IEEE International Conference on Big Data, Big Data 2018, Seattle, WA, USA, December 10-13, 2018. 723--732.

[11]

Guo-Cheng Lan, Tzung-Pei Hong, and Vincent S Tseng. 2014. An efficient projection-based indexing approach for mining high utility itemsets. Knowledge and information systems 38, 1 (2014), 85--107.

[12]

Bing Liu, Wynne Hsu, and Yiming Ma. 1999. Mining association rules with multiple minimum supports. In Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 337--341.

Digital Library

[13]

Junqiang Liu, Ke Wang, and Benjamin CM Fung. 2012. Direct discovery of high utility itemsets without candidate generation. In ICDM. IEEE, 984--989.

Digital Library

[14]

Mengchi Liu and Junfeng Qu. 2012. Mining high utility itemsets without candidate generation. In Proceedings of the 21st ACM international conference on Information and knowledge management. ACM, 55--64.

Digital Library

[15]

Ying Liu, Wei-keng Liao, and Alok Choudhary. 2005. A two-phase algorithm for fast discovery of high utility itemsets. In Pacific-Asia Conference on Knowledge Discovery and Data Mining. 689--695.

Digital Library

[16]

Yu-Cheng Liu, Chun-Pei Cheng, and Vincent S. Tseng. 2013. Mining differential top-k co-expression patterns from time course comparative gene expression datasets. BMC Bioinformatics 14, 1 (21 Jul 2013), 230.

[17]

Pradeep Mohan, Shashi Shekhar, James A. Shine, James P. Rogers, Zhe Jiang, and Nicole Wayant. 2011. A Neighborhood Graph Based Approach to Regional Co-location Pattern Discovery: A Summary of Results. In Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS '11). 122--132.

Digital Library

[18]

Jian Pei and Jiawei Han. 2000. Can We Push More Constraints into Frequent Pattern Mining?. In Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '00). 350--354.

Digital Library

[19]

Jian Pei, Jiawei Han, and Wei Wang. 2007. Constraint-based sequential pattern mining: the pattern-growth methods. Journal of Intelligent Information Systems 28, 2 (01 Apr 2007), 133--160.

Digital Library

[20]

Tomohiro Sato, Minh-Son Dao, Kota Kuribayashi, and Koji Zettsu. 2019. SEPHLA: Challenges and Opportunities Within Environment - Personal Health Archives. In MultiMedia Modeling - 25th International Conference, MMM 2019, Thessaloniki, Greece, January 8-11, 2019, Proceedings, Part I. 325--337.

[21]

Wei Song, Yu Liu, and Jinhong Li. 2014. BAHUI: fast and memory efficient mining of high utility itemsets based on bitmap. International Journal of Data Warehousing and Mining (IJDWM) 10, 1 (2014), 1--15.

Digital Library

[22]

Hung Tran-The and Koji Zettsu. 2017. Discovering co-occurrence patterns of heterogeneous events from unevenly-distributed spatiotemporal data. In 2017 IEEE International Conference on Big Data, BigData 2017, Boston, MA, USA, December 11-14, 2017. 1006--1011.

[23]

Vincent S. Tseng, Bai-En Shie, Cheng-Wei Wu, and Philip S. Yu. 2013. Efficient Algorithms for Mining High Utility Itemsets from Transactional Databases. IEEE Trans. on Knowl. and Data Eng. 25, 8 (Aug. 2013), 1772--1786.

Digital Library

[24]

R. Uday Kiran, T. Yashwanth Reddy, Philippe Fournier-Viger, Masashi Toyoda, P. Krishna Reddy, and Masaru Kitsuregawa. 2019. Efficiently Finding High Utility-Frequent Itemsets Using Cutoff and Suffix Utility. In Advances in Knowledge Discovery and Data Mining, Qiang Yang, Zhi-Hua Zhou, Zhiguo Gong, Min-Ling Zhang, and Sheng-Jun Huang (Eds.). Springer International Publishing, Cham, 191--203.

[25]

Hong Yao, Howard J Hamilton, and Cory J Butz. 2004. A foundational approach to mining itemset utilities from databases. In SIAM. 482--486.

[26]

Junfu Yin, Zhigang Zheng, and Longbing Cao. 2012. USpan: An Efficient Algorithm for Mining High Utility Sequential Patterns. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '12). 660--668.

Digital Library

[27]

Souleymane Zida, Philippe Fournier-Viger, Jerry Chun-Wei Lin, Cheng-Wei Wu, and Vincent S Tseng. 2017. EFIM: a fast and memory efficient algorithm for high-utility itemset mining. Knowledge and Information Systems 51, 2 (2017), 595--625.

Digital Library

[28]

Souleymane Zida, Philippe Fournier-Viger, Cheng-Wei Wu, Jerry Chun-Wei Lin, and Vincent S Tseng. 2015. Efficient mining of high-utility sequential rules. In International Workshop on Machine Learning and Data Mining in Pattern Recognition. 157--171.

Digital Library

Cited By

Zhang XChen GSong LGan WSong Y(2023)HEPM: High-efficiency pattern miningKnowledge-Based Systems10.1016/j.knosys.2023.111068281(111068)Online publication date: Dec-2023
https://doi.org/10.1016/j.knosys.2023.111068
Uday Kiran RVeena PRavikumar PVenus Vikranth Raj BDao MZettsu KBommisetti S(2023)HDSHUI-miner: a novel algorithm for discovering spatial high-utility itemsets in high-dimensional spatiotemporal databasesApplied Intelligence10.1007/s10489-022-04436-w53:8(8536-8561)Online publication date: 11-Mar-2023
https://doi.org/10.1007/s10489-022-04436-w
Chen GLi Z(2023)Discovering Skyline Periodic Itemset Patterns in Transaction SequencesAdvanced Data Mining and Applications10.1007/978-3-031-46661-8_33(494-508)Online publication date: 5-Nov-2023
https://doi.org/10.1007/978-3-031-46661-8_33
Show More Cited By

Index Terms

Discovering Spatial High Utility Itemsets in Spatiotemporal Databases
1. Information systems
  1. Information systems applications
    1. Data mining
      1. Association rules

Recommendations

Discovering Partial Periodic High Utility Itemsets in Temporal Databases
Database and Expert Systems Applications
Abstract
High Utility Itemset Mining (HUIM) is an important model with many real-world applications. Given a (non-binary) transactional database and an external utility database, the aim of HUIM is to discover all itemsets within the data that satisfy the ...
Efficient Algorithms for Mining High Utility Itemsets from Transactional Databases

Mining high utility itemsets from a transactional database refers to the discovery of itemsets with high utility like profits. Although a number of relevant algorithms have been proposed in recent years, they incur the problem of producing a large number ...
Discovering highly expected utility itemsets for revenue prediction

Identifying patterns of items that are purchased frequently and generate high profits is crucial for inventory and profit management. However, neither approaches based on frequent itemsets nor those based on high-utility itemsets (HUIs) can meet this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SSDBM '19: Proceedings of the 31st International Conference on Scientific and Statistical Database Management

July 2019

244 pages

ISBN:9781450362160

DOI:10.1145/3335783

Conference Chair:
Carlos Maltzahn,
Program Chair:
Tanu Malik

Copyright © 2019 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: 23 July 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

SSDBM '19

SSDBM '19: 31st International Conference on Scientific and Statistical Database Management

July 23 - 25, 2019

CA, Santa Cruz, USA

Acceptance Rates

Overall Acceptance Rate 56 of 146 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
180
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang XChen GSong LGan WSong Y(2023)HEPM: High-efficiency pattern miningKnowledge-Based Systems10.1016/j.knosys.2023.111068281(111068)Online publication date: Dec-2023
https://doi.org/10.1016/j.knosys.2023.111068
Uday Kiran RVeena PRavikumar PVenus Vikranth Raj BDao MZettsu KBommisetti S(2023)HDSHUI-miner: a novel algorithm for discovering spatial high-utility itemsets in high-dimensional spatiotemporal databasesApplied Intelligence10.1007/s10489-022-04436-w53:8(8536-8561)Online publication date: 11-Mar-2023
https://doi.org/10.1007/s10489-022-04436-w
Chen GLi Z(2023)Discovering Skyline Periodic Itemset Patterns in Transaction SequencesAdvanced Data Mining and Applications10.1007/978-3-031-46661-8_33(494-508)Online publication date: 5-Nov-2023
https://doi.org/10.1007/978-3-031-46661-8_33
Chen GLi Z(2022)Discovering periodic cluster patterns in event sequence databasesApplied Intelligence10.1007/s10489-022-03186-z52:13(15387-15404)Online publication date: 15-Mar-2022
https://doi.org/10.1007/s10489-022-03186-z
Kiran RPallikila PLuna JFournier-Viger PToyoda MReddy P(2021)Discovering Relative High Utility Itemsets in Very Large Transactional Databases Using Null-Invariant Measure2021 IEEE International Conference on Big Data (Big Data)10.1109/BigData52589.2021.9672064(252-262)Online publication date: 15-Dec-2021
https://doi.org/10.1109/BigData52589.2021.9672064
Pallikila PVeena PKiran RAvatar RIto SZettsu KReddy P(2021)Discovering Top-k Spatial High Utility Itemsets in Very Large Quantitative Spatiotemporal databases2021 IEEE International Conference on Big Data (Big Data)10.1109/BigData52589.2021.9671912(4925-4935)Online publication date: 15-Dec-2021
https://doi.org/10.1109/BigData52589.2021.9671912
Bommisetty SPenugonda RRage UDao MZettsu K(2021)Discovering Spatial High Utility Itemsets in High-Dimensional Spatiotemporal DatabasesAdvances and Trends in Artificial Intelligence. Artificial Intelligence Practices10.1007/978-3-030-79457-6_5(53-65)Online publication date: 19-Jul-2021
https://doi.org/10.1007/978-3-030-79457-6_5
Kiran RIto SDao MZettsu KWu CWatanobe YPaik IThang T(2020)Distributed Mining of Spatial High Utility Itemsets in Very Large Spatiotemporal Databases using Spark In-Memory Computing Architecture2020 IEEE International Conference on Big Data (Big Data)10.1109/BigData50022.2020.9377946(4724-4733)Online publication date: 10-Dec-2020
https://doi.org/10.1109/BigData50022.2020.9377946
Kiran RReddy PZettsu KToyoda MKitsuregawa MReddy P(2020)Efficient Discovery of Weighted Frequent Neighborhood Itemsets in Very Large Spatiotemporal DatabasesIEEE Access10.1109/ACCESS.2020.29701818(27584-27596)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2970181
Uday Kiran RReddy PZettsu KToyoda MKitsuregawa MKrishna Reddy P(2019)Discovering Spatial Weighted Frequent Itemsets in Spatiotemporal Databases2019 International Conference on Data Mining Workshops (ICDMW)10.1109/ICDMW.2019.00143(987-996)Online publication date: Nov-2019
https://doi.org/10.1109/ICDMW.2019.00143
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.

Figures

Tables

Media

View Table of Conten