A New Join-less Approach for Co-location Pattern Mining

Lizhen Wang, Yuzhen Bao, Joan Lu, Jim Yip

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

41 Citations (Scopus)

Abstract

With the rapid growth and extensive applications of the spatial dataset, it's getting more important to solve how to find spatial knowledge automatically from spatial dataseis. Spatial co-location patterns represent the subsets of features whose instances are frequently located together in geographic space. It's difficult to discovery co-location patterns because of the huge amount of data brought by the instances of spatial features. A large fraction of the computation time is devoted to generating the table instances of colocation patterns. The essence of co-location patterns discovery and three kinds of co-location patterns mining algorithms proposed in recent years are analyzed, and a new join-less approach for co-location patterns mining, which based on a data structure--CPI-tree (Co-location Pattern Instance Tree), is proposed. The CPI-tree materializes spatial neighbor relationships. All co-location table instances can be generated quickly with a CPI-tree. This paper proves the correctness and completeness of the new approach. Finally, an experimental evaluation using synthetic dataseis and a real world dataset shows that the algorithm is computationally more efficient than the join-less algorithm.

Original languageEnglish
Title of host publicationProceedings - 2008 8th IEEE International Conference on Computer and Information Technology, CIT 2008
EditorsQiang Xu, Xiangjian He, Quang Vinh Nguyen, Wenjing Jia, Maolin Huang
PublisherIEEE
Pages197-202
Number of pages6
ISBN (Print)9781424423576
DOIs
Publication statusPublished - 8 Aug 2008
EventIEEE 8th International Conference on Computer and Information Technology - Sydney, Australia
Duration: 8 Jul 200811 Jul 2008
Conference number: 8

Conference

ConferenceIEEE 8th International Conference on Computer and Information Technology
Abbreviated titleCIT2008
CountryAustralia
CitySydney
Period8/07/0811/07/08

Fingerprint

Data structures

Cite this

Wang, L., Bao, Y., Lu, J., & Yip, J. (2008). A New Join-less Approach for Co-location Pattern Mining. In Q. Xu, X. He, Q. V. Nguyen, W. Jia, & M. Huang (Eds.), Proceedings - 2008 8th IEEE International Conference on Computer and Information Technology, CIT 2008 (pp. 197-202). [4594673] IEEE. https://doi.org/10.1109/CIT.2008.4594673
Wang, Lizhen ; Bao, Yuzhen ; Lu, Joan ; Yip, Jim. / A New Join-less Approach for Co-location Pattern Mining. Proceedings - 2008 8th IEEE International Conference on Computer and Information Technology, CIT 2008. editor / Qiang Xu ; Xiangjian He ; Quang Vinh Nguyen ; Wenjing Jia ; Maolin Huang. IEEE, 2008. pp. 197-202
@inproceedings{a97d9e28231141ea8ec4433c9a9a44cd,
title = "A New Join-less Approach for Co-location Pattern Mining",
abstract = "With the rapid growth and extensive applications of the spatial dataset, it's getting more important to solve how to find spatial knowledge automatically from spatial dataseis. Spatial co-location patterns represent the subsets of features whose instances are frequently located together in geographic space. It's difficult to discovery co-location patterns because of the huge amount of data brought by the instances of spatial features. A large fraction of the computation time is devoted to generating the table instances of colocation patterns. The essence of co-location patterns discovery and three kinds of co-location patterns mining algorithms proposed in recent years are analyzed, and a new join-less approach for co-location patterns mining, which based on a data structure--CPI-tree (Co-location Pattern Instance Tree), is proposed. The CPI-tree materializes spatial neighbor relationships. All co-location table instances can be generated quickly with a CPI-tree. This paper proves the correctness and completeness of the new approach. Finally, an experimental evaluation using synthetic dataseis and a real world dataset shows that the algorithm is computationally more efficient than the join-less algorithm.",
keywords = "spatial databases, algorithm design and analysis, distance measurement, scalability, data mining, complexity theory",
author = "Lizhen Wang and Yuzhen Bao and Joan Lu and Jim Yip",
year = "2008",
month = "8",
day = "8",
doi = "10.1109/CIT.2008.4594673",
language = "English",
isbn = "9781424423576",
pages = "197--202",
editor = "Qiang Xu and Xiangjian He and Nguyen, {Quang Vinh} and Wenjing Jia and Maolin Huang",
booktitle = "Proceedings - 2008 8th IEEE International Conference on Computer and Information Technology, CIT 2008",
publisher = "IEEE",

}

Wang, L, Bao, Y, Lu, J & Yip, J 2008, A New Join-less Approach for Co-location Pattern Mining. in Q Xu, X He, QV Nguyen, W Jia & M Huang (eds), Proceedings - 2008 8th IEEE International Conference on Computer and Information Technology, CIT 2008., 4594673, IEEE, pp. 197-202, IEEE 8th International Conference on Computer and Information Technology, Sydney, Australia, 8/07/08. https://doi.org/10.1109/CIT.2008.4594673

A New Join-less Approach for Co-location Pattern Mining. / Wang, Lizhen; Bao, Yuzhen; Lu, Joan; Yip, Jim.

Proceedings - 2008 8th IEEE International Conference on Computer and Information Technology, CIT 2008. ed. / Qiang Xu; Xiangjian He; Quang Vinh Nguyen; Wenjing Jia; Maolin Huang. IEEE, 2008. p. 197-202 4594673.

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

TY - GEN

T1 - A New Join-less Approach for Co-location Pattern Mining

AU - Wang, Lizhen

AU - Bao, Yuzhen

AU - Lu, Joan

AU - Yip, Jim

PY - 2008/8/8

Y1 - 2008/8/8

N2 - With the rapid growth and extensive applications of the spatial dataset, it's getting more important to solve how to find spatial knowledge automatically from spatial dataseis. Spatial co-location patterns represent the subsets of features whose instances are frequently located together in geographic space. It's difficult to discovery co-location patterns because of the huge amount of data brought by the instances of spatial features. A large fraction of the computation time is devoted to generating the table instances of colocation patterns. The essence of co-location patterns discovery and three kinds of co-location patterns mining algorithms proposed in recent years are analyzed, and a new join-less approach for co-location patterns mining, which based on a data structure--CPI-tree (Co-location Pattern Instance Tree), is proposed. The CPI-tree materializes spatial neighbor relationships. All co-location table instances can be generated quickly with a CPI-tree. This paper proves the correctness and completeness of the new approach. Finally, an experimental evaluation using synthetic dataseis and a real world dataset shows that the algorithm is computationally more efficient than the join-less algorithm.

AB - With the rapid growth and extensive applications of the spatial dataset, it's getting more important to solve how to find spatial knowledge automatically from spatial dataseis. Spatial co-location patterns represent the subsets of features whose instances are frequently located together in geographic space. It's difficult to discovery co-location patterns because of the huge amount of data brought by the instances of spatial features. A large fraction of the computation time is devoted to generating the table instances of colocation patterns. The essence of co-location patterns discovery and three kinds of co-location patterns mining algorithms proposed in recent years are analyzed, and a new join-less approach for co-location patterns mining, which based on a data structure--CPI-tree (Co-location Pattern Instance Tree), is proposed. The CPI-tree materializes spatial neighbor relationships. All co-location table instances can be generated quickly with a CPI-tree. This paper proves the correctness and completeness of the new approach. Finally, an experimental evaluation using synthetic dataseis and a real world dataset shows that the algorithm is computationally more efficient than the join-less algorithm.

KW - spatial databases

KW - algorithm design and analysis

KW - distance measurement

KW - scalability

KW - data mining

KW - complexity theory

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

U2 - 10.1109/CIT.2008.4594673

DO - 10.1109/CIT.2008.4594673

M3 - Conference contribution

AN - SCOPUS:52049125200

SN - 9781424423576

SP - 197

EP - 202

BT - Proceedings - 2008 8th IEEE International Conference on Computer and Information Technology, CIT 2008

A2 - Xu, Qiang

A2 - He, Xiangjian

A2 - Nguyen, Quang Vinh

A2 - Jia, Wenjing

A2 - Huang, Maolin

PB - IEEE

ER -

Wang L, Bao Y, Lu J, Yip J. A New Join-less Approach for Co-location Pattern Mining. In Xu Q, He X, Nguyen QV, Jia W, Huang M, editors, Proceedings - 2008 8th IEEE International Conference on Computer and Information Technology, CIT 2008. IEEE. 2008. p. 197-202. 4594673 https://doi.org/10.1109/CIT.2008.4594673