An order-clique-based approach for mining maximal co-locations

Lizhen Wang, Lihua Zhou, Joan Lu, Jim Yip

Research output: Contribution to journalArticle

63 Citations (Scopus)

Abstract

Most algorithms for mining spatial co-locations adopt an Apriori-like approach to generate size-k prevalence co-locations after size-(k - 1) prevalence co-locations. However, generating and storing the co-locations and table instances is costly. A novel order-clique-based approach for mining maximal co-locations is proposed in this paper. The efficiency of the approach is achieved by two techniques: (1) the spatial neighbor relationships and the size-2 prevalence co-locations are compressed into extended prefix-tree structures, which allows the order-clique-based approach to mine candidate maximal co-locations and co-location instances; and (2) the co-location instances do not need to be stored after computing some characteristics of the corresponding co-location, which significantly reduces the execution time and space required for mining maximal co-locations. The performance study shows that the new method is efficient for mining both long and short co-location patterns, and is faster than some other methods (in particular the join-based method and the join-less method).

Original languageEnglish
Pages (from-to)3370-3382
Number of pages13
JournalInformation Sciences
Volume179
Issue number19
Early online date8 Jun 2009
DOIs
Publication statusPublished - 9 Sep 2009

Fingerprint

Clique
Mining
Join
Co-location
Prefix
Tree Structure
Execution Time
Table

Cite this

Wang, Lizhen ; Zhou, Lihua ; Lu, Joan ; Yip, Jim. / An order-clique-based approach for mining maximal co-locations. In: Information Sciences. 2009 ; Vol. 179, No. 19. pp. 3370-3382.
@article{5fcf939fd6c842f5a60271f5c1c39bc6,
title = "An order-clique-based approach for mining maximal co-locations",
abstract = "Most algorithms for mining spatial co-locations adopt an Apriori-like approach to generate size-k prevalence co-locations after size-(k - 1) prevalence co-locations. However, generating and storing the co-locations and table instances is costly. A novel order-clique-based approach for mining maximal co-locations is proposed in this paper. The efficiency of the approach is achieved by two techniques: (1) the spatial neighbor relationships and the size-2 prevalence co-locations are compressed into extended prefix-tree structures, which allows the order-clique-based approach to mine candidate maximal co-locations and co-location instances; and (2) the co-location instances do not need to be stored after computing some characteristics of the corresponding co-location, which significantly reduces the execution time and space required for mining maximal co-locations. The performance study shows that the new method is efficient for mining both long and short co-location patterns, and is faster than some other methods (in particular the join-based method and the join-less method).",
keywords = "Co-location patterns mining, Maximal ordered co-locations, Order-clique-based approach, Spatial data mining, Table instances",
author = "Lizhen Wang and Lihua Zhou and Joan Lu and Jim Yip",
year = "2009",
month = "9",
day = "9",
doi = "10.1016/j.ins.2009.05.023",
language = "English",
volume = "179",
pages = "3370--3382",
journal = "Information Sciences",
issn = "0020-0255",
publisher = "Elsevier Inc.",
number = "19",

}

An order-clique-based approach for mining maximal co-locations. / Wang, Lizhen; Zhou, Lihua; Lu, Joan; Yip, Jim.

In: Information Sciences, Vol. 179, No. 19, 09.09.2009, p. 3370-3382.

Research output: Contribution to journalArticle

TY - JOUR

T1 - An order-clique-based approach for mining maximal co-locations

AU - Wang, Lizhen

AU - Zhou, Lihua

AU - Lu, Joan

AU - Yip, Jim

PY - 2009/9/9

Y1 - 2009/9/9

N2 - Most algorithms for mining spatial co-locations adopt an Apriori-like approach to generate size-k prevalence co-locations after size-(k - 1) prevalence co-locations. However, generating and storing the co-locations and table instances is costly. A novel order-clique-based approach for mining maximal co-locations is proposed in this paper. The efficiency of the approach is achieved by two techniques: (1) the spatial neighbor relationships and the size-2 prevalence co-locations are compressed into extended prefix-tree structures, which allows the order-clique-based approach to mine candidate maximal co-locations and co-location instances; and (2) the co-location instances do not need to be stored after computing some characteristics of the corresponding co-location, which significantly reduces the execution time and space required for mining maximal co-locations. The performance study shows that the new method is efficient for mining both long and short co-location patterns, and is faster than some other methods (in particular the join-based method and the join-less method).

AB - Most algorithms for mining spatial co-locations adopt an Apriori-like approach to generate size-k prevalence co-locations after size-(k - 1) prevalence co-locations. However, generating and storing the co-locations and table instances is costly. A novel order-clique-based approach for mining maximal co-locations is proposed in this paper. The efficiency of the approach is achieved by two techniques: (1) the spatial neighbor relationships and the size-2 prevalence co-locations are compressed into extended prefix-tree structures, which allows the order-clique-based approach to mine candidate maximal co-locations and co-location instances; and (2) the co-location instances do not need to be stored after computing some characteristics of the corresponding co-location, which significantly reduces the execution time and space required for mining maximal co-locations. The performance study shows that the new method is efficient for mining both long and short co-location patterns, and is faster than some other methods (in particular the join-based method and the join-less method).

KW - Co-location patterns mining

KW - Maximal ordered co-locations

KW - Order-clique-based approach

KW - Spatial data mining

KW - Table instances

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

U2 - 10.1016/j.ins.2009.05.023

DO - 10.1016/j.ins.2009.05.023

M3 - Article

VL - 179

SP - 3370

EP - 3382

JO - Information Sciences

JF - Information Sciences

SN - 0020-0255

IS - 19

ER -