Skip to main content

Discovering frequent closed partial orders from strings

Publication ,  Journal Article
Pei, J; Yu, PS; Wang, K
Published in: IEEE Transactions on Knowledge and Data Engineering
January 1, 2006

Mining knowledge about ordering from sequence data is an important problem with many applications, such as bioinformatics, Web mining, network management, and intrusion detection. For example, if many customers follow a partial order in their purchases of a series of products, the partial order can be used to predict other related customers’ future purchases and develop marketing campaigns. Moreover, some biological sequences (e.g., microarray data) can be clustered based on the partial orders shared by the sequences. Given a set of items, a total order of a subset of items can be represented as a string. A string database is a multiset of strings. In this paper, we identify a novel problem of mining frequent closed partial orders from strings. Frequent closed partial orders capture the nonredundant and interesting ordering information from string databases. Importantly, mining frequent closed partial orders can discover meaningful knowledge that cannot be disclosed by previous data mining techniques. However, the problem of mining frequent closed partial orders is challenging. To tackle the problem, we develop Frecpo (for Frequent closed partial order), a practically efficient algorithm for mining the complete set of frequent closed partial orders from large string databases. Several interesting pruning techniques are devised to speed up the search. We report an extensive performance study on both real data sets and synthetic data sets to illustrate the effectiveness and the efficiency of our approach. © 2006, IEEE. All rights reserved.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

IEEE Transactions on Knowledge and Data Engineering

DOI

ISSN

1041-4347

Publication Date

January 1, 2006

Volume

18

Issue

11

Start / End Page

1467 / 1481

Related Subject Headings

  • Information Systems
  • 46 Information and computing sciences
  • 08 Information and Computing Sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Pei, J., Yu, P. S., & Wang, K. (2006). Discovering frequent closed partial orders from strings. IEEE Transactions on Knowledge and Data Engineering, 18(11), 1467–1481. https://doi.org/10.1109/TKDE.2006.172
Pei, J., P. S. Yu, and K. Wang. “Discovering frequent closed partial orders from strings.” IEEE Transactions on Knowledge and Data Engineering 18, no. 11 (January 1, 2006): 1467–81. https://doi.org/10.1109/TKDE.2006.172.
Pei J, Yu PS, Wang K. Discovering frequent closed partial orders from strings. IEEE Transactions on Knowledge and Data Engineering. 2006 Jan 1;18(11):1467–81.
Pei, J., et al. “Discovering frequent closed partial orders from strings.” IEEE Transactions on Knowledge and Data Engineering, vol. 18, no. 11, Jan. 2006, pp. 1467–81. Scopus, doi:10.1109/TKDE.2006.172.
Pei J, Yu PS, Wang K. Discovering frequent closed partial orders from strings. IEEE Transactions on Knowledge and Data Engineering. 2006 Jan 1;18(11):1467–1481.

Published In

IEEE Transactions on Knowledge and Data Engineering

DOI

ISSN

1041-4347

Publication Date

January 1, 2006

Volume

18

Issue

11

Start / End Page

1467 / 1481

Related Subject Headings

  • Information Systems
  • 46 Information and computing sciences
  • 08 Information and Computing Sciences