Web Information Systems - WISE 2006 Workshops: WISE 2006 International Workshops, Wuhan, China, October 23-26, 2006, Proceedings

Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen

Editorial Board David Hutchison Lancaster University, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen University of Dortmund, Germany Madhu Sudan Massachusetts Institute of Technology, MA, USA Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Moshe Y. Vardi Rice University, Houston, TX, USA Gerhard Weikum Max-Planck Institute of Computer Science, Saarbruecken, Germany

4256

Ling Feng Guoren Wang Cheng Zeng Ruhua Huang (Eds.)

Web Information Systems – WISE 2006 Workshops WISE 2006 International Workshops Wuhan, China, October 23-26, 2006 Proceedings

13

Volume Editors Ling Feng University of Twente Department of Computer Science P.O. Box 217, 7500 AE Enschede, Netherlands E-mail: [email protected] Guoren Wang Northeastern University College of Information Science and Engineering Shenyang 110004, China E-mail: [email protected] Cheng Zeng Wuhan University State Key Lab of Software Engineering Wuhan 430072, China E-mail: [email protected] Ruhua Huang Wuhan University School of Information Management Wuhan 430072, China E-mail: [email protected] Library of Congress Control Number: 2006934581 CR Subject Classification (1998): H.4, H.3, H.2, C.2.4, I.2, H.5.1 LNCS Sublibrary: SL 3 – Information Systems and Application, incl. Internet/Web and HCI ISSN ISBN-10 ISBN-13

0302-9743 3-540-47663-6 Springer Berlin Heidelberg New York 978-3-540-47663-4 Springer Berlin Heidelberg New York

This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. Springer is a part of Springer Science+Business Media springer.com © Springer-Verlag Berlin Heidelberg 2006 Printed in Germany Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acid-free paper SPIN: 11906070 06/3142 543210

WISE 2006 Workshop Chairs’ Message

This book constitutes the joint refereed proceedings of the three workshops held in conjunction with the 7th International Conference on Web Information Systems Engineering, WISE 2006, in Wuhan, China, in October 2006. Workshop 1: Web Information Access and Digital Library Web information access systems such as search engines provide the necessary means to access the information on the Web. However, search engines are not very effective in searching scholarly information on the Web. The digital library is a key component of national and global information infrastructure, which aims at improving and facilitating Web information access. The workshop examined various existing approaches to Web information access. Of the 41 submitted manuscripts, 14 papers were selected for publication. Workshop 2: Web-Based Massive Data Processing With the fast development of the Internet and communication technology, massive data have been accumulated in many Web-based applications such as deep Web applications and Web search engines. How to collect, extract, store, index, query and analyze such massive data effectively and efficiently poses grand challenges and opportunities for ongoing research. This workshop brought together researchers and industry pioneers to discuss this important frontier. Of the 39 submitted manuscripts, 13 papers were selected for publication. Workshop 3: Advances in Web-Based Learning Today, the Web overcomes time and space limitations in traditional school education. Teachers and students are now using the Web to access a vast amount of information and resources in cyberspace. The Web also allows educators to implement a range of new teaching and learning practices, which redefine classroom-learning experiences. This workshop invited researchers from various fields to present and discuss their ideas on Web-based learning. Of the ten submitted manuscripts, four papers were selected for publication. We are grateful to all the many people directly or indirectly involved in the organization of the WISE 2006 workshop series. We especially thank the three workshop organizers and the reviewers for their great efforts, and all of the authors who submitted papers to the workshops. On behalf of the workshop Organizing Committee, we do hope that the results of this workshop series contribute to your work.

October 2006

Ling Feng, University of Twente, Netherlands Guoren Wang, Northeastern University, China

Web-Based Massive Data Processing Workshop Chairs’ Message

With the fast development of the Internet and communication technology, massive data have been accumulated in many Web-based applications such as deep Web applications and Web search engines. How to collect, extract, store, index, query and analyze such massive data effectively and efficiently poses grand challenges and opportunities for ongoing research. The WISE Workshop on WebBased Massive Data Processing (WMDP 2006) brought together researchers and industry pioneers to discuss this important frontier. The present volume contains the papers that were independently peer-reviewed and selected by the WMDP Program Committees. Thirty-three percent of the paper submissions were accepted. The workshop included a mini-panel on the research directions, and paper presentations and discussion.

Yan Jia, National University of Defense Technology, China Jian Pei, Simon Fraser University, Canada

Web Information Access and Digital Library Workshop Chairs’ Message

Information resources and technology are profoundly influencing everyone in society. The Web provides vast information in almost all subjects of science, culture and economy. The digital library is a component of information infrastructure, which aims at facilitating Web information access. How to use information technologies in order to improve access to information and information management and How to make information access effective in the right time on demand are topics in both computer science and library and information sciences. Information systems and services must meet human needs. The workshop focused on new challenges and initiatives in Web information access and digital library technology. WIADL was designed to bring together researchers and practitioners from interdisciplinary areas of information storage, retrieval and dissemination, Web information organization, information system designing and data mining, digital right management, metadata and library cataloging, and to act as a platform for discussions on experiences and visions. The present volume contains the papers that were independently peer-reviewed and selected by the WIADL Program Committees. Thirty-four percent of the paper submissions were accepted.

Feicheng Ma, Wuhan University, Changping Hu, Wuhan University, Chuanfu Chen, Wuhan University, Zhiyong Peng, State Key Lab of Software Engineering,

China China China China

Advances in Web-Based Learning Workshop Chairs’ Message

Among various Internet technologies, the Web has become the most important tool for educational fields. This is because the Web provides comprehensive services. The Web can provide many benefits to education. First of all, with Web-based education, students can study anytime anywhere. Also, students can get tremendous information in cyberspace. With technical advances in Web technologies, many research efforts are focused on Web-based instruction. The aim of this workshop was to invite researchers from various fields to present and discuss their ideas on Web-based learning. Areas of interest included various aspects of Web-based learning such as learning management systems, user interface design, educational standards, quality management in Web-based learning, infrastructure of Web-based learning environments, curriculum design in Web-based learning, assessment strategy in Web-based learning, instructional design methods for Web-based learning, collaborative Web-based learning, and virtual university, etc. A total of ten research papers were submitted and were reviewed by international Program Committees. Each paper was reviewed by two internationally renowned Program Committees. Papers were rigorously examined and selected based on their significance, originality, technical quality, relevance, and clarity of presentation. Finally, four papers were selected to be presented at the workshop. I would like to take this opportunity to thank all the authors who submitted papers to the workshop. I also thank the Program Committee members. Thanks also go to the conference organizers for their support.

Woochun Jun, Seoul National University of Education, Korea

Organization

Organization Committee Ling Feng, University of Twente, Netherlands Guoren Wang, Northeastern University, China Yan Jia, National University of Defense Technology, China Jian Pei, Simon Fraser University, Canada Feicheng Ma, Wuhan University, China Changping Hu, Wuhan University, China Chuanfu Chen, Wuhan University, China Zhiyong Peng, State Key Lab of Software Engineering, China Woochun Jun, Seoul National University of Education, Korea

Program Committee Workshop on Web-Based Massive Data Processing Lei Chen, Hong Kong University of Science and Technology, China Zhiyuan Chen, University of Maryland, Baltimore County, USA Jianlin Feng, UIUC Ying Feng, Microsoft Hong Gao, Harbin Institute of Technology, China Li Guo, Institute of Computer Technology, Academy of China, China Weihong Han, National University of Defense Technology, China Yan Huang, University of North Texas, USA Daxin Jiang, Nanyang Technology University, Singapore Ning Jing, National University of Defense Technology, China Jiejun Kong, University of California, Los Angles, USA Quanzhong Li, IBM Research Chun Tang, Yale University, USA Guoren Wang, Northeastern University, China Haiyang Wang, Shandong University, China Haixun Wang, IBM Research Lidong Wang, National Information Security Center of China, China Tengjiao Wang, Peking University, China Wei Wang, Fudan University, China Yuqing Wu, Indiana University, USA Shuqiang Yang, National University of Defense Technology, China Ge Yu, Northeastern University, China Aoying Zhou, Fudan University, China

X

Organization

Workshop on Web Information Access and Digital Library Hsinchun Chen, University of Arizona, USA Jin Zhang,University of Wisconsin-Madison, USA Marcia Lei Zeng, Kent State University, USA Li Chen, National Library of China, China Longji Dai, Management Center of Chinese Academic Library and Information System, China Jiangping Chen, University of North Texas, USA Zongying Yang , Shanghai Jiao Tong University Library, China Wei Liu, Shanghai Library, China Gang Li, Wuhan University, China Hui Dong, Wuhan University, China Ning Zhou, Wuhan University, China Xiangxing Shen, Wuhan University, China Ruhua Huang, Wuhan University, China Cheng Zeng, Wuhan University, China Workshop on Advances in Web-Based Learning Ilkyeun Ra, University of Colorado at Denver, USA Yan Liu, The Hong Kong Polytechnic University, Hong Kong Young-Cheol Bang, Korea Polytechnic University, Korea Philip Hingston, Edith Cowan University, Australia Leandro Balladares, National Polytechnic Institute, Mexico Danli Wang, The Chinese Academy of Science, China

Table of Contents

Workshop on Web-Based Massive Data Processing Session 1: Streaming Data Efficient Filtering Query Indexing in Data Stream Ying Wang, Shuo Bai, Jianlong Tan, Li Guo . . . . . . . . . . . . . . . . . . . . . .

1

Modelling and Guaranteeing Quality of Service over Data Streams Shanshan Wu, Yu Gu, Yanfei Lv, Ge Yu . . . . . . . . . . . . . . . . . . . . . . . . .

13

Research on Prediction Models over Distributed Data Streams Li Tian, AiPing Li, Peng Zou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

A Grid-Based Subspace Clustering Algorithm for High-Dimensional Data Streams Yufen Sun, Yansheng Lu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

Session 2: Mining Massive Data Mining h-Dimensional Enhanced Semantic Association Rule Based on Immune-Based Gene Expression Programming Tao Zeng, Changjie Tang, Yintian Liu, Jiangtao Qiu, Mingfang Zhu, Shucheng Dai, Yong Xiang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

An Efficient Algorithm for Distributed Incremental Updating of Frequent Item-Sets on Massive Database Jiangtao Qiu, Changjie Tang, Lei Duan, Chuan Li, Shaojie Qiao, Peng Chen, Qihong Liu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

Mining Maximum Frequent Access Patterns in Web Logs Based on Unique Labeled Tree Ling Zhang, Jian-ping Yin, Yu-bin Zhan . . . . . . . . . . . . . . . . . . . . . . . . . .

73

Short Documents Clustering in Very Large Text Databases Yongheng Wang, Yan Jia, ShuQiang Yang . . . . . . . . . . . . . . . . . . . . . . . .

83

A Simple Yet Efficient Approach for Maximal Frequent Subtrees Extraction from a Collection of XML Documents Juryon Paik, Ung Mo Kim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

94

XII

Table of Contents

Session 3: Massive Data Systems A Web-Based Transformation System for Massive Scientific Data Shi Feng, Jie Song, Xuhui Bai, Daling Wang, Ge Yu . . . . . . . . . . . . . . . 104 Supporting Complex Query with Structured Overlays in Schema-Based P2P System Min Yu, Zhanhuai Li, Longbo Zhang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 DRO+: A Systemic and Economical Approach to Improve Availability of Massive Database Systems Kai Du, Huaimin Wang, Bo Deng, Yongheng Wang, ShuQiang Yang . 122 Research and Implement of Real-Time Data Loading System IMIL WeiHong Han, Yan Jia, ShuQiang Yang . . . . . . . . . . . . . . . . . . . . . . . . . . 133

Workshop on Web Information Access and Digital Library Session 1: Information Organization and Retrieval Blogs in American Academic Libraries: An Overview of Their Present Status and Possible Future Use Zhuo Fu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Rebuilding the Library OPAC Zhigeng Wang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 Web Content Mining for Market Intelligence Acquiring from B2C Websites Danxiang Ai, Yufeng Zhang, Hui Zuo, Quan Wang . . . . . . . . . . . . . . . . . 159 Design of Chinese Word Segmentation System Based on Improved Chinese Converse Dictionary and Reverse Maximum Matching Algorithm Liyi Zhang, Yazi Li, Jian Meng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 Cross-Media Database Retrieval System Based on TOTEM Cheng Zeng, Haiyang Zhou, Bing Yan . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

Session 2: Information System Semantic Query Planning Mechanism on XML Based Web Information Systems Jinguang Gu, Bo Hu, Yi Zhou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194

Table of Contents

XIII

Analysis on the Construction of Management Modes of E-Government Information Exchange in China Cui Huang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 Aggregated Framework of Enterprise Information System Based on Synergic Theory Gang Li, Quan Wei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 Web Personalization Based on Artificial Psychology Quan Lu, Jing Chen, Bo Meng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 Grid Resource Management Based on Mobile Agent Xiaobo Tang, Huang Li . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230

Session 3: Digital Library The Use of Intelligent Information Access Technologies in Digital Libraries Jiangping Chen, Yuhua Li, Gang Li . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 Encryption and Program Realization of Information Resources in DRM Chuanfu Chen, Zhiqiang Wu, Laichu Tang, Congjing Ran . . . . . . . . . . . 251 Knowledge Organization Systems and Interfaces of Digital Libraries in China Li Si, Lixiao Xu, Hongyan Chen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 Study on Distribution Model of Internet Information Resources in China Hui Liu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269

Advances in Web-Based Learning Collaborative User Tracking for Community Organization on Blogosphere: A Case Study of eLearning@BlogGrid Jason J. Jung, Inay Ha, Supratip Ghose, Geun-Sik Jo . . . . . . . . . . . . . . 276 Adaptive UI Storytelling System Using MOL Sunghan Bae, Rohae Myung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 Construction of a Distributed Learning Resource Management System Based on RSS Technology Chengling Zhao, Liyong Wan, Ying Yu, Qi Luo . . . . . . . . . . . . . . . . . . . . 298

XIV

Table of Contents

A Semantic Web Application to Automate the Construction of Didactic Material for Web-Based Education System Rub´en Peredo, Leandro Balladares, Iv´ an Peredo . . . . . . . . . . . . . . . . . . . . 306 Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

Efficient Filtering Query Indexing in Data Stream Ying Wang1,2, Shuo Bai1, Jianlong Tan1, and Li Guo1 1

Software Laboratory, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080, China 2 Graduate School, Chinese Academy of Sciences, Beijing 100039, China {wangying, bai, tan, guoli}@software.ict.ac.cn

Abstract. Filtering queries are widely used in data stream applications. As more and more filtering queries are registered in high-speed data stream management system, the processing efficiency becomes crucial. This paper presents an efficient query index structure based on decision tree. The index structure makes full use of predicate indices on single attributes, as well as the conjunction relationship between predicates in a single query. It is easy to integrate various predicate indices into this structure. How to select dividing attributes during construction is crucial to the performance of the index tree. Two dividing attribute selection algorithms are described. One is based on information gain (IG) and the other is based on estimated time cost (ETC). The latter takes some sample tuples as a training data set and is able to build more efficient trees. Our experiments demonstrate that. Keywords: filtering query, query indexing, predicate index, data stream.

1 Introduction With the rapid development of the Internet, more and more data stream applications emerged in recent years. Continuous query is the most important query paradigm in data stream [1]. Continuous queries are registered in data stream management system (DSMS) in advance and evaluated continuously as stream data continues to arrive. Among continuous queries, filtering query is most widely used. In short, a filtering query is a condition on stream data. When a data tuple arrives and the condition test result is true, we say the filtering query is satisfied (or matched). A satisfied filtering query will trigger some specified action in an application system. Filtering queries are widely used in typical data stream applications, such as network intrusion detection systems (IDS), web log mining, sensor networks, financial applications, telecommunication data management, and so on. First we give filtering query a formal definition. Assume that a data stream is characterized by a relation R(a1:Ω 1, a2: Ω2, …, am: Ωm), where Ωi is the domain of attribute ai (1≤i≤m), and m is the number of attributes. Each attribute can be of any data type and the cardinality of its domain can be unbounded. A filtering query FQ is defined as a conjunction of m unary predicates, where predicate i only depends on attribute i: FQ = P(a1) ∧ P(a2) ∧…∧ P(am) L. Feng et al. (Eds.): WISE 2006 Workshops, LNCS 4256, pp. 1 – 12, 2006. © Springer-Verlag Berlin Heidelberg 2006

2

Y. Wang et al.

P(ai) can be described equivalently by a subdomain ω of ai’s domain Ωi, as ai∈ω then P(ai)=true, otherwise P(ai)=false. So P(ai) can divide Ωi into 2 disjoint subsets (ω and Ωi-ω). If a filtering query does not care about attribute ai (ai doesn’t appear in the query for convenience), we regard P(ai) as always true. There are usually many filtering queries registered in a DSMS. When a data tuple arrives, the DSMS should compute which queries are satisfied. A straightforward way to handle multiple queries is to evaluate query one by one for each arrived tuple. In a typical data stream application, there may be thousands of filtering queries and data arrive at a high speed of tens of thousands of tuples per second. The one-by-one method does not work in such high-speed applications. Another approach to evaluate multiple filtering queries more quickly is to use query indexing. Registered queries are preprocessed to create indices before any stream data arrives. Each data tuple in the incoming stream is used to search the query index to find out quickly which queries are satisfied. There has been much work on query indexing, mainly focusing on indexing queries of a single attribute with numeric data type. Query index on a single attribute is also called predicate index. A predicate on numeric attribute can always be represented by one or more intervals. Classic interval index structures include interval binary search trees (IBS-trees) [2], interval skip lists (IS-lists) [3, 4], containmentencoded intervals (CEIs) [5, 6, 7], etc. Psoup can handle queries on multiple numeric attributes [8]. Psoup creates a red-black tree for predicates on each numeric attribute and intersects the results of all attributes when a data tuple arrives. This method does not take full advantage of conjunction relationship between predicates in a single query. There are some efficient filtering algorithms in publish/subscribe systems [9, 10, 11], whose main idea is to find common sub-queries among multiple queries and the shared sub-queries would be evaluated only once for each incoming data tuple. These pub/sub filtering algorithms do not make much use of predicate indices on single attributes and it is not an easy task to adapt them for more complex predicates. We present a more efficient query index structure (index tree) in this paper. The index structure is based on decision tree. The index tree makes full use of not only the conjunction relationship between predicates in a single query, but also predicate indices on single attributes. In theory, all kinds of predicate indices on single attributes can be easily integrated into the index tree, no matter how complex the predicates are. More important, in the worst case, matching time for each incoming tuple is bounded by O(Mf(N)), where M is the number of attributes, N is the number of registered queries, and f(N) is the cost to match a tuple in predicate indices on single attributes (in general, f(N)=O(logN)). During the construction of an index tree, how to select dividing attributes is crucial to the average performance of the built tree. We present two dividing attribute selection algorithms. One is based on information gain (IG) and the other is based on estimated time cost (ETC). The latter one uses some sample data as a training set and is able to build a more efficient index tree. Our experiments show that in a simulated IDS environment, on average, only few nodes need to be visited in the index tree built by ETC for each arrived data tuple. We wish the ETC algorithm would lay the foundation for fully adaptive processing of multiple filtering queries in data stream.

Efficient Filtering Query Indexing in Data Stream

3

Section 2 introduces our query index structure and its update algorithms. Section 3 presents two dividing attribute selection algorithms. Section 4 describes some implementation issues in our experimental system. Section 5 gives some experimental results. Section 6 concludes.

2 Query Index Tree Our query index structure is essentially a decision tree. A decision tree is a classifier, which takes an object (usually represented by a vector) as input and labels the object with a class tag. Decision tree is widely used in the field of machine learning. The engine handling multiple filtering queries in a DSMS can be considered as a classifier. Suppose there are N registered filtering queries, we can create a classifying system with N+1 classes for all possible data tuples. If a data tuple satisfies query i, this tuple belongs to the i-th class (note that a tuple may belong to more than one class). If a data tuple satisfies no query, it belongs to the N+1-th class. The processing of a tuple with multiple queries can also be considered as a procedure of classification. A tree node in our query index has the form of {dividing-attribute, matcher, satisfied-query-set, child-pointer-array}: dividing-attribute: when a tuple visits the current node, we test its value of the dividing-attribute. Leaf nodes have no dividing-attribute. matcher: a predicate index on dividing-attribute. We use the matcher to find out which child to follow for a traversing tuple. Leaf nodes have no matcher. satisfied-query-set: a set of queries which can be decided as satisfied when a tuple arrives at the current node. child-pointer-array: an array of pointers to the children of the node. 2.1 Query Index Tree Construction The index tree is built in a top-down manner. Each node is associated with a query set and an attribute set during the construction of the tree. We start with the root associated with a query set including all queries and an attribute set including all attributes. A queue is used to contain tree nodes (along with their query sets and attribute sets) that will be extended. The queue is initialized with the root. Each time we pop out a node from the head of the queue, extend it and push the newly extended child nodes into the tail, until the queue is empty. Now we consider extending a node with a query set Qset{Q1,Q2,…,Qn} and an attribute set Aset{a1, a2, …, am}. If an attribute ai does not appear in any query of the Qset (i.e., none of Qset cares about ai), we exclude ai from Aset. If a query Qi has no predicates on any attribute of Aset, we insert Qi into the node’s satisfied-query-set and exclude Qi from Qset. If Qset or Aset is empty, there will be no child derived from the current node (i.e., we get to a leaf node). At each non-leaf node, we first select a dividing attribute from Aset using some algorithm. The dividing attribute selection algorithms will be detailed in section 3. Suppose that we have chosen attribute aj as the dividing attribute and query Qi’s predicate on attribute aj is P[i, j]. P[i, j] corresponds to a subdomain ωi of attribute aj (i.e., P[i, j](aj) is true iff aj∈ωi). We use ω1,…, ωn to divide aj’s domain Ω into s noninterleaved subdomains σ1,…, σs, which satisfy:

4

Y. Wang et al.

(σ1 ∪ σ2 ∪…∪ σs = Ω) AND (σk ≠ Φ), ∀ 1≤k≤s

(I)

σh ∩ σk = Φ, ∀ h≠k, 1≤h,k≤s

(II)

(σk ∩ ωi= σk) OR (σk ∩ ωi = Φ), ∀ 1≤k≤s, 1≤i≤n

(III)

Condition I and II guarantee that any given value of aj will fall into one and only one subdomain σk(1≤k≤s). Condition III guarantees that any two distinct values x and y in σk, P[i, j](x) equals P[i, j](y), with any i, j, k. In addition, we should make s as small as possible. Then we create s children for the current node with each child corresponding to a subdomain respectively. Each child node is associated with an attribute set of Aset{aj}, where aj is the dividing attribute of the current node. Each child is initially associated with an empty query set. Then for each query Qi in Qset and each subdomain σk, if ωi covers σk we add Qi to child k’s query set (denoted as Qset'[k] later). Note that a query may be added to more than one child’s query set. Then all the children along with their query sets and attribute sets are pushed into the building queue. A child node’s attribute set size is at least 1 less than the parent’s. So the depth of the index tree is at most M, where M is the number of attributes. Finally, we build the matcher for the node. The matcher is an index of Qset’s predicates on the dividing attribute. With the matcher, we can figure out quickly which subdomain a given value falls into. All kinds of index algorithms of predicates on a single attribute are applicable here. We give a simple example. Suppose a node with a query set of: Q1: (50
a1 [0,50]

ah

[51,79]

{Q2}

…

[120,65535]

[80,119]

ai {Q1,Q2}

aj {Q1,Q3}

ak

…

…

…

{Q3}

Fig. 1. An example of node extending

2.2 Matching Algorithm The matching algorithm for an incoming tuple is straightforward. The matched query set is initially set to be empty. The tuple traverses the index tree from the root downward to a leaf node. At each node: Step 1. Add the node’s satisfied-query-set to the matched query set Step 2. If the node is a leaf node then return; else go to step 3

Efficient Filtering Query Indexing in Data Stream

5

Step 3. Use the tuple’s value of dividing-attribute to search the node’s matcher. Suppose that the value falls into the k-th subdomain, set the k-th child to be current node and go to step 1. Since in step 3 all other subtrees are ignored except the k-th subtree, only the query subset associated with the k-th child will be concerned in the subsequent steps. So the conjunction relationship between predicates in a single query is fully used here. At most M nodes will be tested in the matching algorithm, where M is the maximal depth of the index tree, i.e., the number of attributes. If the matcher’s searching time in Step 3 is bounded by O(logN), then the matching algorithm has a time cost of O(MlogN), where N is the number of queries. In general, the searching time of predicate index (matcher of a node) on a single attribute can meet the bound of O(logN). 2.3 Updating Index Tree 1. Insertion. Query insertion is also done in a top-down manner from the root. At each node: Step 1. If all predicates of the query have been checked, add the query to the satisfied-query-set of the node and return. Step 2. Suppose the query’s predicate on dividing-attribute is equivalent to a subdomain ω, then for each child of the node, suppose the child corresponds to a subdomain σ: (1) If there is no overlap between ω and σ, ignore the child. (2) If ω totally covers σ, insert the query into the subtree recursively. (3) If ω partially covers σ, divide σ into two subdomains σ1 and σ2, with σ1 totally covered by ω and σ2 without overlap with ω. Accordingly two duplicates substitute the child node along with its subtree. Furthermore, the matcher of the node must be rebuilt. Then we recursively insert the query into the subtree corresponding to σ1. 2. Removal. Removal of a query from the index tree is similar to insertion but simpler. At each node: Step 1. If the query is a member of the satisfied-query-set, remove it from the satisfied-query-set and return. Step 2. Suppose the query’s predicate on dividing-attribute is equivalent to a subdomain ω, then for each child of the node, suppose the child corresponds to a subdomain σ: (1) If ω covers σ, remove the query from the subtree recursively. (2) Else ignore the child. In the worst case, almost all the tree nodes would be traversed in the process of insertion or removal. Note that there is no merging of subtrees in our removal algorithm because of its complexity. On the whole, tree update is time costly. Fortunately query update is usually relatively infrequent in most data stream applications.

6

Y. Wang et al.

3 Dividing Attribute Selection During the construction of the tree, how to select dividing attributes is crucial to the tree shape and the tree’s matching performance. Matching performance is our main concern. It’s difficult to measure matching performance accurately since it is related to not only the tree structure but also the performance of the matcher of each node. In addition, it is also related to the distribution of incoming data. We measure the matching performance by counting the average number of tree nodes that are visited during the match for each incoming tuple. We will present two dividing attribute selection algorithms, one based on information gain and the other based on estimated time cost. Thereinafter we discuss how to select a dividing attribute for a node associated with a query set Qset{Q1,Q2,…,Qn} and an attribute set Aset{a1, a2, …, am} during the tree construction. 3.1 Information Gain Algorithm (IG) Kruegel et al. uses decision trees to improve the performance of intrusion detection [12]. Their engine structure is similar to our query index tree. They adapt the classical decision tree construction algorithm, ID3 to build the engine and get good performance. The information gain based method is also applicable in our dividing attribute selection. Suppose each query appears in Qset with the same probability, the entropy of Qset is calculated as [15]: Entropy (Qset ) =

|Qset|

1

∑ − | Qset | log i =1

2

1 1 = − log 2 = log 2 | Qset | | Qset | | Qset |

(1)

where |Qset| denotes the size of Qset. Suppose we have chosen ai as the dividing attribute. According to section 2.1, we then divide its domain into s subdomains and create s corresponding query subsets Qset'[1..s], one for each child. Then the information gain of the split of the query set with dividing attribute ai is defined as: s

| Qset ' [k ] | log 2 (| Qset ' [k ] |) | Qset | k =1

Gain(Qset , a i ) = log 2 (| Qset |) − ∑

(2)

We will choose the attribute with the highest information gain as the dividing attribute. 3.2 Estimated Time Cost Algorithm (ETC) In general, the IG algorithm will not build an optimal tree under our measurement, for it does not take the distribution of incoming data into account. We will give a data sensitive algorithm in this section. Some sample tuples are used as a training data set, which characterizes the distribution of incoming data. Now, each node is associated with a tuple set during the tree construction, besides a query set and an attribute set. We represent the tuple set as Dset{D1, D2, …, Dd}. After the division of the dividing attribute’s domain and the creation of s query subsets Qset'[1..s], we create s empty

Efficient Filtering Query Indexing in Data Stream

7

tuple sets Dset'[1..s], one for each child. Then for each tuple Di in Dset, if Di’s value of dividing attribute falls into subdomain σk, we insert Di into Dset’[k]. Now we consider how to build an optimal index tree under our measurement. Consider the subtree rooted by the current node. Suppose attribute A is chosen as the dividing attribute, then the average number of nodes visited by each tuple in Dset can be defined as a function AvgVisit(Qset, Aset, Dset) A , which can be recursively computed as: s

AvgVisit (Qset , Aset , Dset ) A = 1 + ∑ p i AvgVisit (Qset ' [i ], Aset − { A}, Dset ' [i ]) i =1

(3)

where p i =| Dset'[i] | / | Dset | , i.e. the ratio of tuples falling into the i-th child. It is easy to prove that if the tree has the minimal cost, each of its subtrees must also have the minimal cost. Therefore the minimal cost of the tree can be recursively computed as: MinAvgVisi t (Qset , Aset , Dset ) = s

1 + min (∑ p i MinAvgVisi t (Qset ' [i ], Aset − { A}, Dset ' [i ])) A∈ Aset

(4)

i =1

If we use directly the above formula to build the optimal tree, the construction time cost is extremely high. Actually we can estimate the cost of each subtree in an approximate way. In general, the larger the query set is, the higher time cost the index tree will have. So we use the size of Qset'[i] to estimate the i-th subtree’s time cost. Then the cost of the subtree rooted by the current node can be computed as: s

EstTime ( Qset , Aset , Dset ) A =| Qset | + ∑ p i | Qset ' [ i ] |

(5)

i =1

The first term |Qset| on the right side is the same for all attributes in Aset, so actually it can be ignored. We choose the attribute with the minimal EstTime as the dividing attribute for the current node. We call this algorithm Estimated Time Cost (ETC). ETC is a kind of greedy algorithm, so is IG. In general, ETC can’t build an optimal tree, but it is a good approximation. Finally we consider a special case. Suppose that with a given dividing attribute A, the node’s k-th child has an empty query set (i.e. |Qset'[k]|=0). That is, any tuple that falls into Dset'[k] won’t match any query. Apparently the more tuples in Dset fall into Dset'[k], the less cost the subtree will have. We usually call p k =| Dset'[k] | / | Dset | the selectivity of attribute A. In general, the ETC algorithm can always choose the most selective attribute as the dividing attribute.

4 Implementation Issues 4.1 Predicates and Matchers Our experimental system supports 3 classes of predicates: Class 1: on a numeric (integer or float) attribute ai, to decide if the attribute value falls into any of a given group of intervals.

8

Y. Wang et al.

Class 2: on a bit-field attribute ai, given a group of (mask, target) pairs, to decide if there exists any pair that satisfies (mask&ai)=target, where & is the bitwise-AND operator. This class of predicates is usually used to test if an IP address belongs to some subnet. Class 3: on a string attribute ai, to decide if the attribute value contains all of a given group of keywords. An example query includes all three classes of predicates: (80
5 Experiments We did our experiments in an assumed IDS application environment. The well-known Snort’s rule set was used as our query set [14]. Each Snort rule was translated into one

Efficient Filtering Query Indexing in Data Stream

9

query, which had an SQL-like form in our experimental system. The translation was not fully equivalent, for some Snort rules have complex predicates that our system doesn’t support and those predicates were simplified during the translation. Some Snort rules need application layer protocols (such as HTTP) analysis and those rules were discarded. Therefore, we got a query set with the size of a little more than 2,000, and each query had 3 to 8 predicates. As for the data, each tuple represents a network packet, which consists of 16 integer attributes, 5 bit-field attributes and 1 string attribute. We captured about 1 million packets from our sub-network gateway and stored them in tcpdump format. For the ETC algorithm, we uniformly sampled 10,000 packets as the training data set. To reduce the influence of reading from disk, all data were loaded into main memory before any performance test.

LQGH[WUHHVL]H

QXPEHURIQRGHV

 ,*



(7&

     



















number of queries (×100)

Fig. 2. Index tree size for increasing size of query set

DYHUDJHQXPEHURI YLVLWHGQRGHVQRGHV

DYHUDJHQXPEHURIYLVLWHGQRGHV 

,*



(7&

    



















number of queries (×100)

Fig. 3. Average number of visited nodes by each incoming tuple

10

Y. Wang et al.

VSHHGWXSOHVVHF

SURFHVVLQJVSHHG      

,* (7&

2

4

6

8

10

12

14

16

18

20

number of queries (×100)

Fig. 4. Processing speed of the index trees

We compared the performances of index trees built by IG and ETC, as well as the tree size. All index trees were built and stored in disk in advance. The IG build algorithm was always several times faster than ETC. For example, to build an index tree of 2,000 queries with the ETC algorithm took about one and a half minutes while it took only 13 seconds with IG.. The build time was not our main concern. To test the matching performance of index trees, we loaded the index tree and data into main memory, and then processed the tuples one by one as fast as possible. When a tuple matched some query, the only action was to print the query ID on screen. We increased the size of the testing query set from 200 to 2,000, and measured the tree size (number of tree nodes), the average number of nodes visited by each tuple and the processing speed (tuples per second) of the trees. We did the speed test 10 times and averaged the results for each query set. The experiment results are given in Fig. 2, Fig. 3 and Fig. 4 respectively. Fig. 2 shows that the tree built by ETC is much larger than the tree built by IG with the same query set. This is because ETC always chooses the most selective attribute as dividing-attribute at each node, and predicates on the most selective attribute tend to divide the domain into more subdomains. Therefore, the ETC trees are extended much wider. In contrast, the IG algorithm prefers smaller trees [15]. Even so, the tree of 2,000 queries built by ETC has a moderately large size of about half a million nodes. Fig. 3 shows that in the trees built by ETC, only very few nodes are visited by each incoming tuple on average. In contrast, in the trees built by IG the average number of visited nodes is several times larger. The reason is, with the most selective attributes (i.e., attributes with the most strict filtering conditions) selected as dividing attributes, the top levels of trees built by ETC can stop a tuple from visiting the lower levels with higher probability than those of trees built by IG can do. Note that the average number of visited nodes in trees built by IG is even larger than the number of attributes, for more than one child of a node may be visited because of the space reduction in section 4. Fig. 4 shows that the performance of a tree built by ETC is about 50%-90% better than the one of the same query set built by IG. It also shows that the performances of

Efficient Filtering Query Indexing in Data Stream

11

both kinds of trees degrade approximately in a logarithm way as the number of queries increases.

6 Conclusion Filtering queries are widely used in data stream applications. As more and more filtering queries are registered in a DSMS and the speed of data stream becomes higher and higher, the performance of the query processor is increasingly crucial. This paper presents a query index structure, which is essentially a decision tree. The index structure makes full use of predicate indices on single attributes, as well as the conjunction relationship between predicates in a single query. Various predicate indices on single attributes are easily integrated into this structure. How to select dividing attributes during tree construction is crucial to the performance of the index tree. We give two dividing attribute selection algorithms: one based on information gain (IG) and the other based on estimated time cost (ETC). The latter takes some sample tuples as a training data set. Our experiments in simulated IDS application demonstrate that, the trees built by ETC are more efficient than the trees built by IG. The ETC algorithm takes the distribution of incoming data into account and lays the foundation for fully adaptive processing of multiple filtering queries in data stream. Our future work will focus on how to improve the index tree dynamically as the distribution of incoming data changes.

References 1. B. Babcock, S. Babu, M. Datar, R. Motwani, J. Widom. Models and Issues in Data Stream. In Proc. ACM Symp. on Principles of Database Systems (2002) 1-16. 2. E. Hanson, M. Chaaboun, C.-H. Kim, and Y.-W. Wang. A predicate matching algorithm for database rule systems. In Proc. of ACM SIGMOD Int. Conf. on Management of Data, (1990) 271-280. 3. Eric N. Hanson, Thedore Johnson. The Interval Skip List: A data structure for finding all intervals that overlap a point, 2nd WADS, LNCS Vol. 519 (1991) 153-164. 4. E. Hanson and T. Johnson. Selection predicate indexing for active database using interval skip lists. Information Systems, 21(3):269-298, (1996). 5. K.-L. Wu, S.-K. Chen, and P. S. Yu. Interval Query Indexing for Efficient Stream Processing. In Proc. of ACM CIKM (2004). 6. K.-L. Wu, S.-K. Chen, P. S. Yu. Query indexing with containment-encoded intervals for efficient stream processing. Knowl. Inf. Syst. 9(1): 62-90 (2006) 7. K.-L. Wu, S.-K. Chen, and P. S. Yu. On-Demand Index for Efficient Structural Joins. IBM Research Report (2006). 8. Sirish Chandrasekaran, Michael J. Franklin. Streaming Queries over Streaming Data. Proceedings of the 28th VLDB Conference, Hong Kong, China (2002). 9. Aguilera MK, Strom RE, Sturman DC, Astley M, Chandra TD. Matching events in a content-based subscription system. In: Proc. of the 18th ACM Symp. on Principles of Distributed Computing. Atlanta (1999) 53-61.

12

Y. Wang et al.

10. Campailla A, Chaki S, Clarke E, Jha S, Veith H. Efficient filtering in publish-subscribe systems using binary decision diagrams. In: Proc. of the ICSE 2001. Toronto: IEEE Computer Society (2001) 443-452. 11. F. Fabret, H. A. Jacobsen, F. Llirbat, J. Pereira, K. A. Ross, and D. Shasha. Filtering algorithms and implementation for very fast publish/subscribe systems. In Proc. of ACM SIGMOD Int. Conf. on Management of Data (2001). 12. Christopher Kruegel and Thomas Toth, Using decision trees to improve signature-based intrusion detection, RAID. (2003). 13. Gonzalo Navarro and Mathieu Raffinot, Flexibale Pattern Matching in Strings, Cambridge University Press (2002) 49-54. 14. Snort. Open-source Network Intrusion Detection System. http://www.snort.org. 15. Tom M. Mitchell. Machine Learning. McGraw-Hill (1997) 63-66.

Modelling and Guaranteeing Quality of Service over Data Streams Shanshan Wu, Yu Gu, Yanfei Lv, and Ge Yu School of Information Science & Engineering, Northeastern University, Shenyang 110004, P.R. China [email protected]

Abstract. In a growing number of web-based applications, massive data takes the form of continuous data streams. Most of these applications have deterministic and sophisticated performance requirements that need to be met under unbounded, high-volume and time-varying data streams. To be different from besteffort service providing, deterministic quality of service is generalized and modelled based on the theory of network calculus in this paper. A simple and efficient admission control mechanism is provided to determine the schedulability of several continuous queries with their QoS requirements satisfied simultaneously. Once the queries are admitted into the DSMS, our proposed QoS-Guaranteed scheduling algorithm assigns priorities to ready tuples that ensure all the QoS requirements. Furthermore, a QoS-Guaranteed batch-processing scheme is extended to reduce the query-scheduling overhead. Experiments are presented to illustrate and validate our strategies.

1 Introduction With the fast development of the Internet and communication technology, massive data has been generated in the form of streaming data in many web-based applications, such as performance measurements in network monitoring and traffic management, ATM operations in banks, log records generated by web servers, and a wide variety of other online monitoring of streaming data from trend-related analysis, web-click streams, intrusion detection, etc. How to manage and process such massive streaming data efficiently and effectively poses grand challenges and opportunities for data management research community. Stream processing applications are expected to support a wide variety of services. These services will have input characteristics and quality of service requirements that may be dramatically different for one another. For example, the control of a nuclear plant or telemedicine application requires strict real-time response constraint, and audio/video playback or teleconferencing requires that the delay jitter be bounded by the network multimedia application, etc. These applications present a formidable challenge to DSMS (Data Stream Processing System) that has to efficiently allocate limited computation resources to many continuous queries by promoting sharing while also providing 

Supported by the National Natural Science Foundation of China under Grant No.60473073, 60503036, and Fok Ying Tung Education Foundation under No. 104027.

L. Feng et al. (Eds.): WISE 2006 Workshops, LNCS 4256, pp. 13–24, 2006. c Springer-Verlag Berlin Heidelberg 2006 

14

S. Wu et al.

quality of service for each query. At present, most existing DSMS provide best-effort services to data stream processing [1][2][3], and they can only provide statistic quality of service, such as average response delay, overall throughput, etc. The issue of providing guaranteed service for data stream processing has drawn little consideration in data stream research field. Therefore, we dedicate to the guaranteeing of quality of service over data stream processing. In this paper, we propose a novel approach for modelling and guaranteeing QoS in data stream processing. Our approach is based on service curve, which is initially used over integrated service in network. Cruz [4] introduced the notion of service curves and proposed their use as a general framework called Network Calculus. A key feature of characterizing services with service curves is that the QoS guarantees can be expressed as simple functions of service curves and the input constraints. These functions are independent of the service curves and the input constraints of all other queries. Another key feature of the service curve specification is that it gives greater flexibility to a serve provider in allocating its resources to guarantee diverse QoS requirements. By specifying an appropriate service curve to a query, the query engine is dynamically informed and efficiently allocates resources to the query in order to meet its QoS specification. So if reasonably adapted to data stream processing, service curve based network calculus could consequentially help to provide a novel scheme for service specification and to improve resource (service) management of DSMS, which may lead to a brilliant performance guarantee for DSMS. In summary, we make the following contributions in this paper: – Based on the characteristics of data stream processing, deterministic quality of service is generalized and modelled based on the theory of network calculus. – An admission control mechanism is provided to determine the schedulability of several continuous queries with their QoS requirements satisfied simultaneously. Once admitted, queries are scheduled in accordance with our proposed QoS-Guaranteed scheduling algorithm. – QoS-guaranteed batch-processing scheme is extended to reduce the query-scheduling overhead. The rest of this paper is organized as follows. We establish service curve based QoS model of data stream processing in Section 2. Section 3 presents our QoS-Guaranteed mechanism, including QoS-Guaranteed scheduling algorithm and admission control. We extend our work to QoS-Guaranteed batch processing in Section 4. Experimental results are presented in Section 5. Section 6 discusses the related work. Finally, we end the paper with conclusions and future work in Section 7.

2 Service Curve Based QoS Model In this section, we model DSMS as a service system. With the knowledge of network calculus, quality of service for the continuous queries over data streams, such as response delay bound, memory requirement, throughput, etc. can be easily expressed as simple functions of the service curves and the characteristics of input at the entrance of the processing system.

Modelling and Guaranteeing Quality of Service over Data Streams

15

2.1 Preliminaries of Network Calculus Here we recall a few fundamental definitions and results proposed in network calculus as preliminary. Throughout this paper, we assume that time is divided into slots numbered 0,1,2...

Fig. 1. Properties of Service System

For a lossless service system S illustrated in Figure 1(a), which is viewed as a blackbox, S receives input data and delivers the data after a variable delay. Let cumulative input function R(t) denote the number of data seen on the input flow during the time interval [0, t]. Similarly, cumulative output function R∗ (t) is defined as the number of data that have received service from the service node during the interval [0, t]. By convention, we assume that there is no data stored in the service node at the end of slot zero, i.e. R(0) = 0. Therefore, the number of data that are stored in the service node at the end of slot t, called the backlog for the system at the end of slot t, is given by Equation 1: B(t) = R(t) − R∗ (t) (1) The virtual delay relative to t suffered by the flow, denoted by d(t), is defined in Equation 2: d(t) = inf{τ ≥ 0 : R(t) ≤ R∗ (t + τ )} (2) Both backlog and virtual delay are illustrated in Figure 1(b). Consider wide-sense increasing functions of time, with nonnegative, possibly infinite values. We introduce an operation called ”min-plus convolution”, which is the basis of min-plus algebra. Definition 1 (Convolution). Given wide-sense increasing functions f and g, the minplus convolution of f and g is defined as the function f ⊗ g : R → R+ ∪ {+∞}, as given in Equation 3: (f ⊗ g)(t) =

inf {f (t − s) + g(s)}

s:0≤s≤t

(3)

Definition 2 (Service Curve). Consider a system S and a flow through S with cumulative input function and cumulative output function R and R∗ , respectively. We say that S offers to the flow a service curve β if and only if β is wide sense increasing, β(0) = 0 and R∗ ≥ R ⊗ β.

16

S. Wu et al.

Service curve is defined as a measure for partially characterizing the service provided by a server. Roughly speaking, a service curve is a function that lower bounds the amount of traffic departing from the server within some specific interval. And an arrival curve defines the constraint on burstiness as follows: Definition 3 (Arrival Curve). Given a wide-sense increasing function α, we say that the flow is constrained by α if and only if R(t)−R(s) ≤ α(t−s) for all s ≤ t. Function α is called an arrival curve for the flow, and the flow is also called α-smooth. Given a service curve and arrival curve, Theorem1 provide the upper bounds on delay and backlog experienced by a flow as the maximum vertical and horizontal distance, which is illustrated by Figure 1(b) and (c). Theorem 1 (Backlog Bound and Virtual Delay Bound). Assume a flow constrained by arrival curve α traverses a service system that offers a service curve β. The backlog B(t) for all t is bounded, as shown in Equation 4: R(t) − R∗ (t) ≤ sup{α(t) − β(t)}

(4)

t≥0

The virtual delay d(t) is bounded by d(t) ≤ h(α, β), where h(α, β) is the horizontal deviation between the two functions, given by Equation 5: h(α, β) = sup{inf{τ : τ ≥ 0 and α(t) ≤ β(t + τ )}}

(5)

t≥0

2.2 Modelling QoS In the circumstance of data stream processing, each continuous query can be modelled as a service system as shown in Figure 2. Each query processes input stream as a service provider, and the input stream of the query can be regarded as service consumer. However, the output tuples of a continuous query are the results that satisfy certain query semantics. Taking a filter query as example, the output tuples of the filter are those that satisfy the filter predicate. In other words, the tuples in the output stream could not correspond to the tuples in the input stream one-to-one because of selectivity. As a result, when modelling a continuous query as a service system, the output should take the measure of the number of tuples that have been processed by the query rather than the number of results output by the query. Terminologically, R(t) denotes the number of tuples that have arrived in the input stream ready to be processed during the interval [0, t], and R∗ (t) denotes the number of tuples that have been served (processed) by the query. As for a deterministic service guarantee, a meaningful definition of the quality of service must include a description of the characteristics of the input to be served and an unambiguous definition of the performance requirement. When being provided with this set of information, the provider is capable of deriving the respective resource allocation in order to fulfill the QoS demand. DSMS being modelled as a service system, the characteristics of input stream and the service required can be flexibly described under the theory of network calculus as follows.

Modelling and Guaranteeing Quality of Service over Data Streams

17

Fig. 2. Modelling a DSMS

For continuous query Qi in a DSMS, both the arrival curve of input stream of Qi , αi , and the service curve of Qi , βi , determine the quality of service of Qi , such as response delay and buffer requirement. Therefore, for each continuous query Qi , a QoS model is defined as QoSi =< αi , βi >. The smoothness of input stream may be naturally induced at the source or can be imposed by the user. The service curve specification gives greater flexibility to a server in allocating its resources to meet diverse delay and throughput requirements. As an example, suppose a query guarantees the service curve β = δd , where  0, if 0 ≤ t ≤ d δd (t) = (6) ∞, if t > d In this case, it follows that for all t we have R∗ (t) ≥ (R ⊗ δd )(t) = R(t − d), and hence the response delay of tuples through this query is bounded by d.

3 QoS-Guaranteeing Mechanism Given QoS specification of continuous queries, measures should be taken to guarantee the admitted queries. Fig.3 presents the architecture of our QoS-Guaranteed DSMS. A user who wants to register a new continuous query to the DSMS has to explicitly specify the performance requirements that the system has to provide for the query in the form of QoS specification. Then admission controller determines whether the query can be supported without disrupting the service for existing queries in the system. Once the query is accepted, the system will dynamically allocate resources to various queries with a QoS-Guaranteed scheduling algorithm. QoS Specification

QoS M anager

Sc heduler

Data

Queries

Adm ission Controller

Query Engine

Results

QoS-Guaranteed DSM S

Fig. 3. Architecture of QoS-Guaranteed DSMS

18

S. Wu et al.

3.1 QoS-Guaranteed Scheduling Algorithm Without loss of generality, we assume that each stream is related to a query and each query has exactly one related stream, so that the processing of queries in a DSMS is independent of each other. Consider that there are N continuous queries in a DSMS sharing computation resources, and suppose query Qi requires that the service curve βi be guaranteed, where i = 1, ..., N . We design an SCED based scheduling algorithm that can guarantee the service curve for each query. SCED [5] is a non-preemptive task scheduling strategy in the theory of network calculus. It defines an output deadline allocation algorithm that guarantees, under some conditions, that flow i does have βi as a service curve. Suppose the ni -th input tuple of query Qi , arrives in the front of query Qi in slot u. As shown in Equation 7 and Equation 8, SCED algorithm tells the tuple must depart the system before the time slot di (n). Zi (t; u − 1) =

min

{Ri (s) + βi (t − s)}

τ (u−1)≤s≤u−1

di (n) = min{t : t ≥ u and Zi (t; u − 1) ≥ ni }

(7) (8)

where τ (t) is the index of the latest slot, no larger than t, at the end of which the query engine is idle, as shown in Equation 9: τ (t) = max{s : s ≤ t and Bi (s) = 0 f or i = 1, ..., N }

(9)

We call di (n) the departure deadline of the ni -th input tuple of query Qi . Since the processing cost of each tuple differs from one another, we should take processing delay into consideration when determine the scheduling priority. Suppose that per-tuple processing delay for query Qi is bounded by Δi (which will be referred in the next section), to ensure the satisfaction of departure deadline, tuples should be scheduled Δi time slots ahead of its departure deadline. Therefore, the scheduling deadline is defined in Equation 10: SDi (n) = min{t : t ≥ u and Zi (t − Δi ; u − 1) ≥ ni }

(10)

Based on the EDF strategy, the highest priority equals to the smallest scheduling deadline. If the tuple can be processed before its scheduling deadline, the output deadline can be satisfied, therefore the query could meet its service curve which corresponding to its QoS. The scheduling algorithm is given in Table 1. 3.2 Access Control for QoS Guaranteeing Since the capability of a certain query engine is limited, when a set of queries run in a single DSMS, they compete for computation resources with one another. So how to find the condition under which the shared query engine can simultaneously serve all the queries with QoS guarantees is a necessary problem to discuss.

Modelling and Guaranteeing Quality of Service over Data Streams

19

Table 1. QoS-Guaranteed Scheduling Algorithm Scheduling Algorithm 1: while (queues not empty) { 2: for i=1 to N { 3: if(SDi (n) of ready tuple not calcuated) 4: calculate SDi (n); 5: assign priorities based on SDi (n); 6: } //endfor 7: schedule tuple with the highest priority to execute; 8: } //endwhile

Because of different operation functions, processing costs of different queries differ from one another, so the service received by each query should be measured in a uniform comparable measurement rather than the number of tuples that have been served by each query. Therefore, the computation resource is standardized as follows when allocated to different queries. Assuming the query engine has the ability to perform C basic operations per time slot. And it takes Ci basic operations for Query Qi to serve a tuple. Therefore, for a tuple input to query Qi , we have Δi = CCi . We assume the statistic cost of queries and the capability of query engine are known in advance. This can be achieved by permanently monitoring the data stream processing during the warm-up stage. Theorem 3 (Feasible Allocation). Consider a query engine with capacity of C basic operations each time slot that serves N continuous queries. If the input stream to query Qi is αi -smooth, then the scheduling algorithm guarantees service curve βi to query Qi for i = 1, ..., N , if the following Equation 11 is satisfied. N 

((αi ⊗ βi )(t) × Ci ) ≤ C × t ∀ t ≥ 0

(11)

i=1

If without assumption on the characteristics of input stream, a simpler sufficient condition is as Equation 12: N 

(βi (t) × Ci ) ≤ C × t ∀ t ≥ 0

(12)

i=1

The proof of Theorem3 can refer to the proof of Theorem 2.3.1 in [6]. The above feasible allocation theorem gives us principles to introduce admission control policy when users register continuous queries. For generality, we could extend to a system with a variable capacity, meaning that the maximum number of basic operations that the system could perform during a slot N varies with time. If i=1 Bi (τ ) > 0 for all τ satisfying t1 ≤ τ ≤ t2 , the system is called continuouslybacklogged in the interval [t1 , t2 ]. Here we give the definition of service capacity as follows. Definition 4 (Capacity Curve). We say that a DSMS has a capacity curve C(t) if within any interval [t1 , t2 ] in which the system is continuously backlogged, the amount of basic operation that the system performs is at least C × (t2 − t1 ).

20

S. Wu et al.

With the definition of capacity curve, the right side of Equation 11 and Equation 12 in Feasible Allocation condition could be generalized to C × (t2 − t1 ). And the above fixed rate server, i.e., a system with a fixed capacity to perform C (a constant value) basic operations in each slot, is just a special case of a system with a capacity curve C(t) = C × t.

4 QoS-Guaranteed Batch Processing According to the scheduling algorithm proposed in Section 3, query engine performs scheduling in a-tuple-a-time (shorted as AT AT ) fashion, which has relatively low efficiency. This is because the high volume input tuples over data streams would lead to heavy scheduling overheads. Batch scheduling strategy, by grouping several tuples of a query as a scheduling unit, is the most efficient approach for real-time processing since it can lower down scheduling overheads effectively, compared with AT AT strategy. Many batch scheduling strategy have been proposed for data stream processing. However, under the circumstance of guaranteed service providing, batch processing should be reviewed carefully so that the required QoS is satisfied. Assuming that the batch size is b, we allocate each batch a priority equal to the priority of the last tuple in the batch, then the scheduler serves batches present in the system in the order of their priorities. Then the departure time of any tuple in the system is bounded by its departure time in the AT AT system plus b×CCmax where Cmax is the maximum per-tuple processing cost across all the queries and C is the system capability. In order to guarantee the pre-specified QoS requirements, each tuple in a batch should have its scheduling deadline intentionally b×CCmax ahead. In other words, because of the effect of batching processing, the service curve of each query should be modified as: βi (t + b×CCmax ) f or i = 1, ..., N . Considering the constraint of feasible allocation theorem, the size of batch, b, could be determined with the Equation 13 or Equation 14: N 

((αi (t) ⊗ βi (t +

i=1 N 

(βi (t +

i=1

b × Cmax )) × Ci ) ≤ C × t ∀ t ≥ 0 C

b × Cmax ) × Ci ) ≤ C × t ∀ t ≥ 0 C

(13)

(14)

5 Experiment Analysis In our experiment, we simulate three continuous queries with different QoS requirements. For simplification, the input rates of all the queries are constant. The input rates of Q2 and Q3 are both 200 tuples per second, and we vary the input rate of Q1 from 100 tuples per second to 700 tuples per second. And the QoS requirements of each query are listed as follows: – Q1 requires that the output rate be at least 300 tuples per second. – Q2 requires that the delay for any tuple be bounded by 4 ms.

Modelling and Guaranteeing Quality of Service over Data Streams

21

– Q3 asks for long-term output rate as 200 tuples per second, however, during the beginning of backlogged period tuples should has a response delay no more than 2.5ms.

(a) Servic e Curve of Q 1

(b) Servic e Curve of Q 2

(c ) Servic e Curve of Q 3

Fig. 4. Service Curves

(1) Modelling QoS The queries with QoS requirements can be modelled as in Table 2, and the service curves are shown in Figure 4. Table 2. QoS Specification of Queries

Arrival Curve Service Curve

Q1 α1 = r1 t (r1 = 0.1 ∼ 0.7) β1 = 0.3t

Q2

Q3

α2 = 0.2t β2 = δ4

 β3 =

α3 = 0.2t 0.4t 0≤t≤5 0.2t + 1 t>5

Noted that millisecond (ms) is used as time unit. (2) Admission Control Check It is known that the computation cost per tuple of all the queries is 1tuple/ms with response delay jitter 0.2 ms, so we know that Δi = CCi = 1 for i = 1, 2, 3.  ri t r1 ≤ 0.3 α1 (t) ⊗ β1 (t) = 0.3t r1 > 0.3 α2 (t) ⊗ β2 (t) = 0.2(t − 4) α3 (t) ⊗ β3 (t) = 0.2t We have:  3 (0.4 + ri )t − 0.8 r1 ≤ 0.3 (α (t) ⊗ β (t)) = i i i=1 0.7t − 0.8 r1 > 0.3 Even though the variation of input rate Q1 , it holds that: 3 C i=1 (αi (t) ⊗ βi (t)) < Ci × t ∀ t > 0 Therefore we conclude that all the three queries can be admitted in the system with their QoS requirements satisfied simultaneously, according to the feasible allocation condition.

22

S. Wu et al.

(3) QoS-Guaranteed Algorithm Analysis To evaluate the ability of our QoS-Guaranteed scheduling algorithm, we implement FIFO algorithm as well.

0.04

1

QoS-G FIFO QoS-Miss Ratio

QoS-Miss Ratio

0.05

0.03 0.02 0.01 0 100

0.8

QoS-G FIFO

0.6 0.4 0.2 0 100

300 500 Input rate of Q1 (tuple/s)

Fig. 5. QoS-Miss Ratio of Q1

300 500 Input rate of Q1 (tuple/s)

Fig. 6. QoS-Miss Ratio of Q2

QoS-Miss Ratio

0.5 The experimental results illustrated QoS-G FIFO by Figure 5-7 show that QoS require0.4 ments of all the admitted queries are 0.3 guaranteed under our QoS-Guaranteed Scheduling Algorithm. While for FIFO 0.2 scheduling, when the input rate of Q1 0.1 increases, more tuples appear on the input of Q1 with relative earlier arrival 0 100 300 500 time. Therefore, the query engine is Input rate of Q1 (tuple/s) over occupied with the processing of the tuples of Q1 . As a result, the input Fig. 7. QoS-Miss Ratio of Q3 tuples of Q2 and Q3 are less scheduled, which leads to the increase of QoSMiss ratio. The experiment above gives us a motivation that the service curve based approach is efficient for modelling and guaranteeing QoS requirements.

6 Related Work Recently, there has been considerable research activity pertaining to stream systems and data stream algorithms. Some systems that incorporate stream processing include Aurora [7][8], NiagaraCQ [9], STREAM [10], TelegraphCQ [11], and many others. QoS focuses on user-perceived qualities, and QoS-aware data management has been a hot topic in data management community [12][13]. In data stream research community, QoS is first proposed in [8]. The QoS requirements in Aurora are two-dimensional QoS graphs specified by application administrator telling the utility of the output in terms of several performance-related attributes. However, Aurora attempts to maximize the perceived QoS for the output it produces, in other words, this is a kind of posteriori QoS, and it can not provide deterministic performance guarantee. Moreover Aurora’s

Modelling and Guaranteeing Quality of Service over Data Streams

23

notion of QoS is general and is not restricted to the types of graphs. Qstream [14] suggests the idea of priori QoS for data stream processing, however the performance requirements are ensured by resource reservation, which incurs too much resource idleness, therefore less flexible. In addition, network calculus is a set of rules and results that apply min-plus algebra to packet networks. Fundamental work has been pioneered by Cruz [6][15][16], and it has been extended and simplified independently and simultaneously under equivalent forms by Sariowan [5] who gives a formal and general treatment of the concepts of arrival curves and service curves, two fundamental network calculus tools. The mathematics involved in network calculus uses min-plus algebra, as described in [16].

7 Conclusions and Future Work In this paper, we focus on modeling and guaranteeing quality of service for data stream processing based on the theory of network calculus. A QoS-Guaranteed DSMS architecture is proposed, which is supported by QoS modeling and QoS guarantee mechanisms. And a QoS-Guaranteed batch processing is mentioned here. The current work is based on query-level service providing, and we will try to push it into operator-level that might improve the system scheduling efficiently. Moreover, for some applications, it is desirable that a query be able to renegotiate its QoS requirements on the fly. We are going to give QoS guarantee when renegotiate arrival and service curves for a query on the fly. Moreover, since the input streams tend to be bursty and high-volume, we plan to perform arrival curve based load shedding which discards tuples from input streams to make it conform to the required burstiness constraints without breaking the negotiated QoS requirements.

References 1. D. Carney, U. Cetintemel, et al. Operator Scheduling in a Data Stream Systems. In Proc. of the 29th VLDB Conf., Berlin, Germany, Sep.2003, 838-849. 2. R. Avnur and J. M. Hellerstein. Eddies: Continuously Adaptive Query Processing. In Proc. of the ACM SIGMOD, Dallas, TX, May 2000, 261-272. 3. B. Babcock, S. Babu, M. Datar, and R. Motwani. Chain: Operator Scheduling for Memory Minimization in Data Stream Systems. In Proc. of the ACM SIGMOD Int.Conf. On Management of Data, San Diego, CA, 2003, 253-264. 4. R. L. Cruz. Quality of service guarantees in virtual circuit switched networks. IEEE J. Select. Aareas Commun., 1995(13): 1048-1056. 5. H. Sariowan. A service curve approach to performance guarantees in integrated service networks. Ph.D. dissertation, Univ. Calif. San Diego, 1996. 6. L. Boudec, J. Yves, P.Thiran. Network calculus. Springer Lecture Notes in Computer Science, Vol.2050, 2001. 7. D. J. Abadi, D. Carney, U. Cetintemel, et al. Aurora: A New Model and Architecture for Data Stream Management. VLDB Journal, 12(2), 2003. 8. D. Carney, U. Cetintemel, M. Cherniack, et al. Monitoring streamsCa new class of data management applications. In Proceeding of VLDB Conference, Hong Kong, China, August 2002, 215-226.

24

S. Wu et al.

9. J. Chen, D. DeWitt, F. Tian, and Y. Wang. NiagaraCQ: A scalable continuous query system for Internet databases. In Proc. of the 2000 ACM SIGMOD Intl. Conf. on Management of Data, May 2000, 379-390. 10. R. Motwani, J. Widom, A. Arasu, et al. Query Processing, Resource Management, and Approximation in a Data Stream Management System. In CIDR Conference, Asilomar, CA, January 2003, 245-256. 11. S. Chandrasekaran, O. Cooper, A. Deshpande, et al. TelegraphCQ: Continuous dataflow processing for an uncertain world. TelegraphCQ: Continuous Dataflow Processing for an Uncertain World. In CIDR Conference, Asilomar, CA, January 2003, 269-280. 12. K. Kang, S. H. Son, J. A. Stankovic, et al. A QoS-Sensitive Approach for Timeliness and Freshness Guarantees in Real-Time Databases. In Proc. of the 14th Euromicro Conference on RealTime Systems, 2002, 203-212. 13. Y. Liu, X. Liu, L. Xiao, et al. Location-Aware Topology Matching in P2P Systems. In Proc. of IEEE INFOCOM 2004, Hong Kong, Mar.2004, http://www.cse.msu. edu/ liuyunha/INFOCOM04-yunhao.pdf. 14. S. Schmidt, H. Berthold, and W. Lehner. Qstream: Deterministic querying of data streams (demo). In Proc. of the 30th VLDB, Toronto, Canada, August 30-September 3 2004, 1365-1368. 15. R. L. Cruz. A calculus for network delay, part I: Network elements in isolation. IEEE Trans. Inform. Theory, vol. 37, Jan.1991, 114-131. 16. R. L. Cruz. A calculus for network delay, part II: Network analysis. IEEE Trans. Inform. Theory, vol. 37, Jan. 1991, 132-141.

Research on Prediction Models over Distributed Data Streams Li Tian, AiPing Li, and Peng Zou National Laboratory for Parallel and Distributed Processing Changsha, Hunan, China 410073 [email protected]

Abstract. A framework is presented to provide a mechanism to maintain adaptive prediction models established both on the coordinator and remote nodes in distributed data stream processing for reducing communication consumption. The coordinator employs these models to answer registered queries, while the remote nodes check whether the prediction value is close to the actual value or not. Update messages are needed only when there’s a large deviation between prediction value and actual value. Three particular prediction models are given and compared with existent ones. Analytical and experimental evidence show that the proposed approach performs better both on overall communication cost reduction and prediction query processing. Keywords: Prediction model, Data stream, Network consumption.

1 Introduction Efficient resource management is critical to data stream processing due to characters such as massive data and rapid arriving, etc [1,2]. Considering distributed environments where remote nodes push continuous streams to a central coordinator [2], significant communication consumption is incurred due to rapid update steams. For example, network monitoring system requires frequently reporting the status of network elements in real time for applications such as traffic engineering, billing and security, etc. In these cases, the volumes of collected utilization and traffic data may be huge [3] and sometimes disruptive to communication infrastructure. Considering the fact that many applications need only approximate answers for their continuous queries [4,5,6], an effective method based on prediction models is offered to reduce communication cost. We believe that in many contexts the data stream is stable (or, predictable), and a proper prediction model can be established to estimate the values in the near future based on history information. We propose that every attribute measured by remote nodes be attached to a prediction model that will be used to predict future values of that attribute, and the same prediction model is shared with the coordinator. The coordinator employs these models to answer continuous queries, while the remote nodes check whether the prediction is close (with some precision) to the actual value or not. In this way, only significant values (when the prediction has a large deviation from the actual value) are needed to L. Feng et al. (Eds.): WISE 2006 Workshops, LNCS 4256, pp. 25 – 36, 2006. © Springer-Verlag Berlin Heidelberg 2006

26

L. Tian, A. Li, and P. Zou

transmit to the coordinator, saving a great amount of communication while still guaranteeing sufficient precision of query results. Moreover, prediction query processing over future data steams is needed in some situations[7]. However, recent works focused mainly on approximate queries over newly arriving data [1,2], and in this paper, prediction models are proposed to process prediction queries. The rest of this paper is as follows: Related works are concluded in Section 2. In section 3, prediction models are invited to distributed data stream processing architecture and a common framework is raised. There are three adaptive prediction models raised in section 4, comparative analyses among them are performed theoretically. In section 5, experimental evidence proves that our approach significantly reduces overall communication cost and performs well on prediction queries. And lastly in section 6, conclusions and future work are described.

2 Related Works Here we will just describe some works which, alike ours, proposing to consider the tradeoff between accuracy and communication for monitoring a limited class of continuous queries (at a coordinator site) over distributed streams (at remote sites). Other than prediction method, there are several approaches by which approximate answers of sufficient precision are computed from a small fraction of the input streams. Das et al. [8] discuss monitoring of approximate set-expression cardinalities over physically-distributed element streams. An adaptive filter adjustment algorithm is developed in [4], which adapt to changing conditions to minimize stream rates while guaranteeing that all continuous queries still receive the updates necessary to provide answers of adequate precision at all times. A similar idea is proposed by Ankur Jain, et al.[5], where they specifically choose a Kalman filter among the linear estimation methods. The most relevant works [6,9,11] propose to use predictors in data stream processing. Cormode et al [6] present algorithmic solutions for tracking a broad class of complex data-analysis queries over distributed streams setting to specified accuracy, which rely on a combination of general-purpose randomized sketches and concise sketchprediction models. Several adaptive prediction techniques are researched in [9], and all of them are based on linear functions. An approach with prediction functions is presented in [11] to process monitoring queries in a network of sensors. The authors consider sensors that communicate their values according to a threshold policy and prediction functions to compare tuples efficiently and generate answers even in the absence of new incoming tuples. Our work differs from all above mainly in proposing a general architecture, which provides a mechanism to maintain adaptive prediction models significantly reduce communication cost over the distributed environment while still guaranteeing sufficient precision of query results. Prediction models proposed in reference [6] is analyzed and ameliorated in this paper as per shortcomings; efficiency and veracity of different models are compared respectively both on theory and experiment.

Research on Prediction Models over Distributed Data Streams

27

3 Data Stream Processing with Prediction Models 3.1 Problem Formulation As illustrated in Fig. 1, a distributed data stream processing architecture comprises a collection of k remote sites node(j)( j {1,..,k}) and a designated coordinator site c. Generally, direct communication between node(j) are not allowed, instead, node(j) exchanges messages only with c. Object values f1,..,fs from corresponding domains Ui(i {1,..,s}) are monitored by the system. Assume that there is a global time in the system, fi,j(t) is used to denote the observed value of fi in node(j).

∈

∈

Fig. 1. Illustration of distributed data stream processing

Approach based on prediction models is offered in the above distributed environment to reduce bandwidth consumption in this paper, and the related definitions are as follows. *

Definition 1 Prediction Model. A prediction model PMi is a function from Ui to Ui, * where Ui is the domain of fi , and Ui is the set contains all the subsets of Ui. Definition 2 Prediction Value. Using Fi(t)={fi(x)|x
28

L. Tian, A. Li, and P. Zou Table 1. Model and algorithm symbols

Symbol node(j) Oi Ui fi,j(t) fi,jp(t) ti,jprev PMi .tbegin vi,j ai,j θi

Meaning Remote sites (j ∈ {1,..,k}) Data object((i ∈ {1,..,s}) Domain of fi Observed value of fi in node(j) at time t Prediction value of fi in node(j) at time t Time the last communication occurred Time from which PMi become effective Velocity parameter of PMi Acceleration parameter of PMi The upper bound on the deviation of observed value and prediction value

Symbol c fi t PMi Δdi,j Δt PMi .texp tp Q δQ

Meaning Coordinator site Concerned character of Oi The current system time Prediction model of fi Δdi,j=fi,j(t)-fi,jp(t) Δt=t-ti,jpre Expiry time of PMi Update tuples transmitted A continuous query Precision constraint of Q

3.2 Architecture In this section, we explain the architecture that we propose as shown in Fig. 2. Client Module Snapshots

Sampling

Stream Corrdinator Buffers of tuples

Prediction Model 1

----

fi

Remote nodes

p

Warnings Events

Prediction Manager

Trigger Processing

Alarms

. . .

Prediction Model Buffers

-------

Precision Manager

Approximate Answer

Register queries

Register queries (query + precision constraint)

Continuous Queries Evaluator

No Update the coordinator with new value

Is prediction value close (with some precision) to the actual observed value?

Precision control messages

Data sources f1 Updates

. . Yes Drop the data tuple . . . . PM s-1 Remote nodes

Is prediction value close to the fs-1 actual observed value? Updates Yes Drop the data tuple Significative update value PM s Is prediction value close to the actual observed value?

fs Updates

Yes Drop the data tuple

Fig. 2. System architecture

Remote Nodes. Remote nodes, on the right, each master values for one or more objects, and they generate streams of significant updates for those values according to the corresponding prediction model and local data stream from data sources. Since local data stream may change as time pass by, a prediction model representing the stream exactly at a given time may be invalidated after a period of time. PM.tbegin and PM.texp are used to indicate the beginning and expiry time of prediction model. We propose that remote nodes transmit update tuples to the stream coordinator whenever: 1) the difference between prediction value and observed value exceeds a certain precision threshold (correction update), or 2) the time elapsed since the last update has exceeded the effective period of PM, that is t>PM.texp (valid update). T=PM.texp-PM.tbegin indicates the amount of time during which a prediction model can be applied: beyond that period, the prediction model is not reliable and it can be assumed that the remote node is unable to communicate new updates (e.g., it is

Research on Prediction Models over Distributed Data Streams

29

not alive). A valid update indicates that the corresponding prediction model describes the stream character well and therefore the valid period of the model can be extended, while a correction update will adjust parameters of corresponding prediction model and shrink its valid period. Update date tuples transmitted from remote nodes to coordinator are logically composed of update-tuples: tp=<node(j), Oi, type, fi,j(t)>, where node(j) and Oi is the identifier of a remote node and the concerned object, respectively, type equals either to CORR or to VALI, which indicates tp is a correction update or a valid one, and finally, fi,j(t) means the observed value of Oi in node(j) at current time instant t. Stream Coordinator. It receives update-tuples, manages prediction model copies, controls precision issues, and provides answers to client modules. Prediction Manager. The main function of prediction manager is as follows: 1) Receiving update-tuples from remote nodes. 2) Maintaining the copies of prediction models in coordinator to be valid, adaptive and consistent with corresponding remote one. 3) Deciding which input tuples should be stored (i.e., they may be needed to answer queries with window-join constraints [11]). Precision Manager. A precision manager is invited to manage precision issues. We assume any number of arbitrary CQs with arbitrary individual precision constraints δQ, respectively. The challenge is to ensure that all times the approximate answer to every Q is of adequate precision, i.e., can be guaranteed within δQ, while drop local tuples as much as possible to minimize total communication cost. In this paper, we do not delve into the details of how precision constraints are specified, neither do we make any assumption about the way precision allocations are performed [4], which are remained as open problems and will be studied in future. Buffer. There are two kinds of buffer in the stream coordinator: buffers of tuples and prediction model buffers. The former store received update-tuples which will be needed in future (i.e., to rebuild the prediction models or to answer window-join constraints queries [11]), and the latter store copies of prediction models used by the Continuous Query Evaluator to answer user queries. Continuous Query Evaluator. A Continuous Query Evaluator in the stream coordinator receives users’ register requirements of CQs and provides continuous approximate answers to them according to the concerned prediction models. An example of continuous query specification is as shown below: SELECT AVG(D_s.c) FROM Data_Stream D_s WHERE (D_s.a < v1 and D_s.b>v2) BEGIN begin_time END end_time Current researches focus mainly on queries over current and historical data and pay few attentions to future data (where the begine_time is the current system time and the end_time is a future time instant), which we named as prediction queries.

30

L. Tian, A. Li, and P. Zou

The CQ Evaluator generates an output data stream of tuples that satisfy the required constraints (or predicted to satisfy in the future, depending on whether the query registered is a prediction query or not). For normal queries that end_time. However, for prediction queries, the format of an output tuple is < fip(t), δQ, VI >, where VI=MIN{PMi.texp| Oi is involve in the query’s WHERE clause} is the validity mark of the out predicted tuple, indicating the time interval during which the prediction value is available. The stream coordinator can process prediction queries in this way. Client Module. A module client will receive the approximate answer released by the CQ Evaluator for further processing as needed. Our approach fits naturally with different types of client modules, such as: (1) a sampling module that periodically transforms the data stream into relations that are shown to a user as snapshots at different time instants of the values that satisfy the constraints; (2) a trigger processing module that requires a certain action when an event is detected. (3) other users or applications that register queries and obtain continuous approximate answers for certain precision guaranteeing.

4 Prediction Models In this section, we propose three particular adaptive prediction models: the static model, the linear model and the acceleration model. Similar with [6], all these three models consider how the local distribution fi,j changes (as a function of time) between the time of the last communication to the coordinator ti,jprev and the current t; but models raised in this paper are improved version comparing with what in [6]. 4.1 Static Model Static model essentially assuming that fi,j remains static (fi,jp(t)=fi,j(ti,jprev)) over time. The following analysis indicates that the static model is useful in some situation. Theorem 1. Assume N is a random variable which denotes the number of update th tuples. Let the tuples are observed for r times, then the probability that the r observed value is larger/smaller than the first r-1 observed values is 1/r. Theorem 2. Assume N is a random variable which denotes the number of update tuples. Let the tuples are observed for r times, then r

∑N

lim x:=1 r →∞ r

x

= AVG( N )

where Nx means the xth observed value of variable N, and AVG(N) means the exact average value of N. Proof of these theorems is omitted due to space limitation [7]. Theorem 1 indicates that, the probability of the newly arrived tuple becomes the max/min value decreasing with the increasing of r. In other words, if we assume that max{N}=max{N1, N2, … ,Nr },

Research on Prediction Models over Distributed Data Streams

31

the assumption will be imprecise with probability of 1/r. When r is large, the assumption will almost be accurate. Similar analysis can be performed on AVG aggregation operation according to Theorem 2. 4.2 Linear Model The linear-growth model (LGM) proposed in [6] predicts the future behavior of the stream as a linear scaling of the entire history of the distribution. It imposes a linear, uniform rate of change over the entire frequency distribution vector, and thus, cannot capture or adapt to shifts and differing rates in the distribution of updates over the vector. However, in many real-life scenarios, only the recent history of the stream may be relevant for such predictions. Considering that fi,j(ti,jprev) is the exact value of fi,j when t=ti,jprev, we regard the deviation between observed value and prediction value (Δdi,j=fi,j(t)-fi,jp(t) ) as the cumulation from the last communication to NOW (Δt=t-ti,jpre), which is caused by the inaccurate change rate (vi,j). Thus we propose the linear model (LM) as fi,jp(t)= fi,j(ti,jprev)+vi,jΔti,j, and the corresponding update algorithm is shown in algorithm 1. Algorithm 1. UpdateLinearModel (tp) Input: an update tuple tp Output: the adjusted prediction model, and prediction tuples for each query, if needed PM:=PredictionManager.GetPM(tp.node(j),tp.Oi); If tp.type = CORR then // correction update Δdi,j:=tp.fi,j(t)-PM. fi,j(ti,jprev); Δti,j:=t-PM. ti,jprev; Δd PM. vi,j := PM.vi,j + i,j Δti,j ;

PM.ti,jprev:=t; PM.fi,j(ti,jprev):= tp.fi,j(t); PredictionManager.ExtendExpiry(PM) Else PredictionManager. ShrinkExpiry(PM) //valid update

4.3 Acceleration Model A richer prediction model named velocity/acceleration model (VAM) is raised in [6], which uses more parameters to better fit changing data distributions and can be described as fi,jp(t)= fi,j(ti,jprev)+vi,jΔti,j+(Δti,j)2ai,j. The author propose to compute the velocity component by maintaining a window of the W most recent updates to fi,j in remote node(j), scaling the difference between the newest and oldest updates stored in the window by the time difference, and finally transmitting the velocity parameter to coordinator [6]. This schema suffers from at least two significant shortcomings. Firstly, additional storage and CPU costs are needed for storing the W most recent updates and computing the velocity parameter, which aggravates the load of remote nodes. Secondly, the velocity parameter should be transmitted to coordinator c, which increases the communication cost.

32

L. Tian, A. Li, and P. Zou

Similar to the linear model, we regard the deviation Δdi,j as the cumulation result of the inaccurate of model parameters (vi,j and ai,j ) during the period of Δti,j,. The problem is how to describe this deviation by model parameters. Assume that the prediction function is fi,jp(t)= fi,j(ti,jprev)+vi,jΔti,j+(Δti,j)2ai,j, and the exact distribution function can be described by fi,j(t)= fi,j(ti,jprev)+vi,j*Δti,j+(Δti,j)2ai,j*. If vi,j=vi,j*, indicating that the deviation is caused only by the imprecision of acceleration parameter. Let Δai,j= ai,j*- ai,j, we have

Δai,j ( Δti,j )2 = Δdi,j ⇒ Δai,j =

Δdi,j ( Δti,j )2

Then we get

a*i,j = ai,j + Δai,j = ai,j +

Δdi,j ( Δti,j )2

v*i , j = vi,j +2a*i,j Δti,j = vi,j +2ai,j × Δti,j +

(1)

2Δdi,j

Δti,j

(2)

Similarly, If ai,j=ai,j*, indicating that the deviation is caused only by the imprecision of velocity parameter. we have

a*i,j = ai,j , v*i, j = vi,j +2ai,j × Δti,j +

Δdi,j Δti,j

(3)

In general, both the inaccurate of vi,j and ai,j have contribution to the deviation Δdi,j. We make an approximate assumption that the deviation caused by the above two parameters is equal to Δdi,j/2, respectively, then we get the update algorithm of our acceleration model (AM) according to formula (1)~(3), shown in algorithm 2. Algorithm 2. UpdateAccelerationModel (tp) Input: an update tuple tp Output: the adjusted prediction model, and prediction tuples for each query, if needed

PM=PredictionManager.GetPM(tp.node(j),tp.Oi); If tp.type = CORR then // correction update Δdi,j:=tp.fi,j(t)-PM. fi,j(ti,jprev); Δti,j:=t-PM. ti,jprev; 3 × Δd i,j ; PM. vi,j := PM.vi,j + 2PM.ai,j × Δti,j + 2 × Δti,j PM.ai,j := PM.ai,j +

Δd i,j

2 × ( Δti,j )2

;

PM.ti,jprev:=t; PM.fi,j(ti,jprev):= tp.fi,j(t); PredictionManager.ExtendExpiry(PM) Else PredictionManager. ShrinkExpiry(PM)

//valid update

4.4 Compare and Analysis The following Table 2 summarizes the key points of prediction models mentioned above.

Research on Prediction Models over Distributed Data Streams

33

Table 2. Compare of prediction models

fi , j (ti,jprev )

fi , j (ti,jprev )

Communication Cost None

t fi , j (ti,jprev ) tiprev ,j

fi , j (ti,jprev ) , ti,jprev

None

Name

Prediction Value

Static Model Linear-growth model(LGM)

Storage Cost

Velocity/Accelerati on Model(VAM)

fi , j (ti,jprev ) + Δti , j vi , j + (Δti , j )2 ai , j

Linear Model(LM) Acceleration Model(AM)

fi , j (ti,jprev ) + Δti , j vi , j prev i,j

fi , j (t

fi , j (ti,jprev ) , ti,jprev , vi,j , ai,j

W f i,j in node(j) fi , j (ti,jprev ) , ti,jprev , vi,j

) + Δti , j vi , j + (Δti , j ) ai , j 2

prev i,j

fi , j (t

prev i,j

) ,t

, vi,j , ai,j

vi,j

None None

Comparing with LGM [6], the LM proposed in this paper adds the storage cost of parameter vi,j to capture shifts and differing rates in the distribution of updates. Time complexity and space complexity of LM is O(s×k), where s and k is the number of objects concerned and remote nodes, respectively. Comparing with VAM [6], the AM proposed in this paper avoids the storage of W most recent fi,j in node(j) and changes the space complexity from O(W×s×k) to O(s×k). Model’s parameters can be computed from the deviation Δdi,j and no additional communication cost is needed, reducing O(s×k) network transmission. However, the assumption that the inaccurate of vi,j and ai,j has the same contribution to whole deviation will influence prediction veracity in some way.

5 Experiments A simulation system is implemented in Delphi 7 to test the prediction veracities and the effects on reducing communication cost of all our proposed models. Experiments were performed on an Intel Pentium 4, CPU 1.7GHZ, and RAM 512 Mb, with Windows XP. Two kinds of data sets were used during our experiments, just as shown in Table 3. Data stream 1 is synthetic where parameters 0 ≤ pi < 10 (i=1..5) are random generated every 100 seconds to simulate streams with different distributions. Data stream 2 is ocean air temperature data from 1996 to 2005 measured by TAO (tropical atmosphere ocean) [10]. Threshold policy is adopted in precision controlling, and update communication is needed when

f i , j (t)-f i,jp( t ) fi , j (t)

≥θ .

Table 3. Streams used during the experiments Streams 1 2

Description f(t)=p1 Δt 3 + p2 Δt 2 + p3 Δt + p4 + p5 Δt 1996~2005 ocean air temperature data measured by TAO [10]

34

L. Tian, A. Li, and P. Zou

5.1 Prediction Veracity Fig. 3 shows the effect of varying the parameter θ for prediction models on the prediction veracity. It can be seen that when θ<1%, the veracity increase rapidly with parameter’s growth, while when θ>1%, the increase trend slows down. Therefore, the following experiments are performed under situation of θ=1%.

Predicate veracity(%)

100

80

60

VAM AM LM LGM

40

20

0 0

1

2

θ (%)

3

4

5

Fig. 3. Relationship between θ and prediction veracity on data stream 1

We investigated the prediction veracity of different models on different data streams. 100

A

VAM

AM

LM

LGM

80

Predicate Veracity(%)

Predicate Veracity(%)

100

60 40 20 0

B

90

80 Static VAM LM LGM AM

70

60

50

0.0

3

5.0x10

1.0x10

4

t

1.5x10

4

2.0x10

4

2

7.0x10

3

1.4x10

3

2.1x10

3

2.8x10

3

3.5x10

3

4.2x10

t

Fig. 4. Prediction veracity of models (A) on data stream 1 (B) on data stream 2

As shown in Fig. 4 (A), due to the nonlinear character of data stream 1, the prediction veracities of acceleration models are higher than those of linear ones. Fig. 4 (B) indicates that linear models perform better than acceleration ones on data stream 2 because of its stable random distribution. The two illustrations indicate that comparing with LGM [6], the LM proposed in this paper adapts well to shifts and differing rates in the distribution of data stream, and therefore performs obviously well on prediction veracity. However, the AM performs a little worse on prediction veracity than VAM does because of the approximate processing mentioned above.

Research on Prediction Models over Distributed Data Streams

35

5.2 Communication Cost The following two factors play important roles in reducing communication cost: the prediction veracity and the update policy when prediction is failure. Symbol p is used to denote the veracity of prediction model PM, proportion between redundant and necessary communication during an update policy is denoted by m:n, then we can compute the total communication cost by the following formula: C_CostPM ( p,m,n ) =

( 1 − p )×( m + n ) × 100% n

(4)

54

A 100

80

Communication cost(%)

Communication cost(%)

Object values during the experiment streams are all float values. Recall that the update-tuple is tp=<node(j), Oi, type, fi,j(t)>, during the experiments, node(j) and Oi is stored in 16 bits, respectively; parameter type, which is the only additional communication cost introduced, is denoted by 1 bit, and fi,j(t) , the observed float value, is presented by 32 bits. For Static model, LGM, LM and AM, m:n=1:64, while for VAM, the value of m:n is equal to 17:64 because an extra parameter vi,j should be transmitted to coordinator when a correction update occur, which is stored in 16 bits. We investigated the communication cost of different models on different data streams according to the above analysis. Both of the two illustrations in Fig. 5 indicate that benefiting from the higher prediction veracity, LM performs quite better than LGM in reducing communication cost. Although AM is a little worse than VAM in veracity, it omits the additional communication of parameter vi,j, and therefore has similar (on data stream 1) and sometimes even better(on data stream 2) performance on reducing communication cost.

LGM LM AM VAM

60

40

LGM VAM AM LM STATIC

36

27

18

9

20 0.0

B

45

3

5.0x10

4

1.0x10

4

1.5x10

4

2.0x10

t

6.0x10

2

3

1.2x10

1.8x10

3

2.4x10

3

3.0x10

3

3

3.6x10

4.2x10

3

t

Fig. 5. Effect of models on reducing the communication cost (A) on data steam 1 (B) on data stream 2

6 Conclusions and Future Work In this paper we have described a framework for data stream processing with prediction models in typical distributed environment, which provides a mechanism to maintain adaptive prediction models that significantly reduce update stream rates and process prediction queries over future data streams. Three improved adaptive prediction models are proposed; theoretical analysis and experimental evidence

36

L. Tian, A. Li, and P. Zou

indicate that our approach significantly reduces overall communication cost and performs well over prediction queries. In future steps, we plan to conduct a more extensive experimentation and analyze the precision control and allocation issues. Research on effective prediction models for streams with different distribution character is an open problem. Acknowledgements. This work is supported by the National High-Tech Research and Development Plan of China ("863" plan) under Grant No.2004AA112020 and No. 2005AA112030, and the National Weapon Equipment Pre-research Fund under Grant No. 51415010304KG0175.

References 1. Jin, C.Q., Qian W.N., Zhou A.Y.: Analysis and Management of Streaming Data: A Survey. Journal of Software. 15 (2004) 1172-1181 2. Babcock, B., Babu, S., Datar, M., Motwani, R., Widom, J.: Models and issues in data stream systems. ACM SIGMOD. Madison, WI, USA (2002) 3. Cranor, C., Johnson, T., Spatscheck, O., Gigascop, V.S.: A Stream Database for Network Applications. ACM SIGMOD. San Diego. California (2003) 4. Olston, C., Jiang, J., Widom, J.: Adaptive Filters for Continuous Queries over Distributed Data Streams. ACM SIGMOD. San Diego, California (2003) 5. Jain, A., Chang, E.Y., Wang, Y.F.: Adaptive Stream Resource Management Using Kalman Filters. ACM SIGMOD. Canada (2004) 6. Cormode, G., Garofalakis, M.: Sketching Streams Through the Net: Distributed Approximate Query Tracking. VLDB. Trondheim, Norway (2005) 7. Li J.Z., Guo L.J., Zhang D.D., Wang W.P.: Processing Algorithms for Predictive Aggregate Queries over Data Streams. Journal of Software. 16 (2005) 1252-1261 8. Das. A., Ganguly, S., Garofalakis, M., Rastogi, R.: Distributed Set-Expression Cardinality Estimation. VLDB. Toronto, Canada (2004) 9. Kumar, V., Cooper, B.F., Navathe, S.B.: Predictive filtering: A learning-based approach to data stream filtering. International Workshop on Data Management for Sensor Networks, (2004) 10. Pacific Marine Environmental Laboratory. Tropical atmosphere ocean project. http://www.pmel.noaa.gov/tao (2005) 11. Sergio, I., Wolfson, O., Mena, E.:Processing of data streams with prediction functions. Proceedings of the 39th Hawaii International Conference on System Sciences (2006)

A Grid-Based Subspace Clustering Algorithm for High-Dimensional Data Streams Yufen Sun and Yansheng Lu College of Computer Science & Technology, Huazhong University of Science & Technology, Wuhan, 430074, China [email protected]

Abstract. Many applications require the clustering of high-dimensional data streams. We propose a subspace clustering algorithm that can find clusters in different subspaces through one pass over a data stream. The algorithm combines the bottom-up grid-based method and top-down grid-based method. A uniformly partitioned grid data structure is used to summarize the data stream online. The top-down grid partition method is used o find the subspaces in which clusters locate. The errors made by the top-down partition procedure are eliminated by a mergence step in our algorithm. Our performance study with real datasets and synthetic dataset demonstrates the efficiency and effectiveness of our proposed algorithm.

1 Introduction A data stream is a sequence of data items x1 , " , xi , " x n such that the items are read once in increasing order of the indices i [1]. It has a potentially infinite volume and it is either unnecessary or impractical to store the data in some form of memory [2]. Many applications require the clustering of high-dimensional data streams online, such as network monitoring, telecommunications data management, stock-market analysis, sensor networks, and so on. An algorithm for data streams should have the ability to process high dimensional data through one linear pass over the data. Clustering is a widely used technique for exploring the inherent structures of data. The aim of a clustering algorithm is to partition a data set into subsets (clusters) such that members of the same cluster are similar and members of distinct clusters are dissimilar, where the similarity of two data members is usually defined by a distance function [3]. Recently the clustering problem has been studied in data stream domain [2, 4-7]. The task of a clustering algorithm for data streams is to determine the clusters in data as new data flow in continuously. Most stream algorithms maintain a summarization of data in main memory to keep necessary information for computing. Histogram is a synopsis data structure that is often used to summarize data. A grid data structure can be thought as a multidimensional histogram. The distribution information of data stored by a grid data structure can be used to perform clustering. Grid based clustering algorithms have many ideal properties for clustering tasks. They can find clusters with arbitrary shapes and different sizes. They are insensitive to the order of input. But the curse of high L. Feng et al. (Eds.): WISE 2006 Workshops, LNCS 4256, pp. 37 – 48, 2006. © Springer-Verlag Berlin Heidelberg 2006

38

Y. Sun and Y. Lu

dimensionality also exists for grid based clustering algorithms, especially for those that use connected dense grid cells in original data space to represent clusters. Subspace algorithms have been proposed to deal with this problem [8, 9, 11]. In this paper, we propose an algorithm GSCDS (Grid-based Subspace Clustering algorithm for high-dimensional Data Streams) that can find clusters in different subspaces. The algorithm combines the advantages of the top-down grid-based method and bottom-up grid-based method. After summarizing the stream data into a uniformly partitioned grid data structure, the algorithm tries to find subspaces that contain clusters. For each dimension, if a cutting point on this dimension can best separate the projections of the data that belong to different clusters, this dimension is selected to span a subspace. The connected dense cells in these subspaces are identified as clusters. At last, these clusters are checked to see whether they can be merged. Thus the algorithm can find subspace efficiently and acquire accurate clusters. To deal with evolving data streams, the algorithm uses a fading parameter to eliminate the influence of history data. Our performance study with real datasets and synthetic dataset demonstrates the efficiency and effectiveness of our proposed algorithm. In the remainder of this paper, we first introduce related work in section 2. Then we discuss two kinds of grid-based methods in section 3. The method for subspaces identification and the algorithm GSCDS are described in section 4. Section 5 reports our performance study and last, section 6 gives our conclusion.

2 Related Work In a high-dimensional space, all pairs of points tend to be almost equidistant from one another [5]. This brings difficulties to clustering problems that define the similarity between data points by the distance between them. To solve this problem, subspace clustering algorithms try to find clusters in subspaces of the original data space [8, 9, 11]. CLIQUE is the first grid-based subspace clustering algorithm that identifies clusters in different subspaces [8]. The algorithm first finds dense units in all subspaces, and then it identifies connected dense units in these subspaces as clusters. These clusters may overlap, which makes the algorithm unfit for some applications. Moreover, the running time of CLIQUE is exponential in the highest dimensionality of any dense unit. MAFIA improves CLIQUE by adaptively partitioning the grid based on the distribution of data [9]. But its running time also grows exponentially with the number of dimensions in clusters. SURFING is a subspace clustering algorithm that tries to find interesting subspaces by checking whether the projections of data points in each subspace distribute uniformly [11]. If the distribution is not uniform, the algorithm tries to find clusters in the corresponding subspace. SURFING needs to compute k-nearest neighbors of every data point in every subspace, which is not a trivial task. OptiGrid is a grid-based clustering algorithm that separates clusters in highdimensional dataset based on the distribution of the projections of data points on each dimension [10]. But the accuracy of the clusters obtained by it is not very high. We will discuss it in detail in next section. Recently, several clustering algorithms for data streams have been proposed [2, 47]. The algorithm STREAM partitions the data stream into chunks that can be clustered in main memory [2]. The cluster centers of these chunks form higher level

A Grid-Based Subspace Clustering Algorithm

39

chunks and are clustered again. This algorithm satisfies the basic space and time restriction of a stream algorithm. The algorithm CluStream maintains online microclusters that are defined as a temporal extension of the clustering feature (CF) vectors [4]. The micro-clusters are stored at particular moments to support offline clustering over specific time horizons. HPStream is an algorithm that is proposed to perform incremental subspace clustering on high-dimensional data streams [5]. For each cluster, HPStream selects the dimensions over which the radii of this cluster are small. CluStream and HPStream have the problem of favoring clusters with spherical shape and they are sensitive to noise and the order of input. Park et al. propose a statistical grid-based clustering algorithm for data streams [6]. Based on an assumption of the distribution of data points in a dense cell, the algorithm divides the cell until it becomes a unit cell. A cluster is a group of adjacent dense unit cells. This algorithm does not consider the problem of high dimensionality and it needs to assume the distribution of data. GCHDS is a grid-based clustering algorithm for high-dimensional data streams [7]. It analyzes the distribution of data points on each dimension to select the dimensions that are useful for clustering. All clusters it finds lie in the same subspace. But for a real data set, clusters may lie in different subspaces. The algorithm GSCDS proposed in this paper is an on-line algorithm that can find clusters with arbitrary shapes in different subspaces. GSCDS first incrementally summarizes the data in a data stream into a uniformly partitioned grid in memory. Then a top-down grid-based method is used to find the subspaces that contain clusters. Finally the algorithm uses a bottom-up grid-based method to find clusters in each subspace.

3 The Grid-Based Clustering Algorithms Our procedure for subspaces identification is enlightened by OptiGrid, a grid-based clustering algorithm that aims at separating the clusters in a static data set. Before we introduce our algorithm, we first discuss the grid-based clustering algorithms. The grid based clustering algorithms can be categorized into two classes: the bottom-up method and the top-down method. The bottom-up method first uniformly partitions the data space into mutually exclusive equal-size cells, then tries to find connected dense cells as clusters. All data points in a cell are supposed to belong to the same cluster. Only the statistical information of these data points is stored with the cell. This method needs only one scan over the dataset and it can find clusters of arbitrary shapes. The accuracy of clusters is determined by the granularity of cells, which is determined by parameters that are given by users. A fine partitioned grid with small cells will produce more accurate clustering results, but at the same time cause higher computational complexity. The bottom-up method is unfit for high dimensional data sets because the sparsely distributed data in the high dimensional space will form too many unconnected dense cells. WaveCluster [12] and CLIQUE [8] are two representations of the bottom-up grid-based clustering algorithms. WaveCluster is designed for low-dimensional spatial data. It outperforms BIRCH, CLARANS, and DBSCAN in terms of both efficiency and clustering quality [3]. CLIQUE considers the problem of high dimensionality, but the time it needs to find the subspaces in which clusters locate is exponential in the highest dimensionality of the subspaces. MAFIA

40

Y. Sun and Y. Lu

adaptively partitions the grid by merging the adjacent intervals in a uniformly partitioned grid, and it proceeds much like CLIQUE [9]. So it is also considered as a bottom-up grid-based clustering algorithm. The top-down method does not partition the data space uniformly according to input parameters, but partitions the data space recursively according to the data distribution. This method adopts the idea of divide-and-conquer. The data space is first partitioned into several regions by cutting planes that can separate different clusters. For each region, the partition procedure is repeated until each region contains only one cluster. At last, the top-down method obtains an uneven partitioned grid in which each cell (region) contains at most one cluster. The highly populated cells in this grid are considered as clusters. By using the data distribution information on each dimension to separate the clusters, this method is insensitive to noise because noise is normally considered uniformly distributed.

(a) Clusters overlap on every dimension

(b) Clusters can be separated by axes aaaaaaaaaaaaaaaaaaaaaaaaaparallel cutting lines

Fig. 1. Errors caused by top-down partition procedure

OptiGrid is a typical top-down grid-based clustering algorithm that is designed specially to process high-dimensional data sets with noise. It partitions the data space recursively by cutting planes that can best separate the clusters. For each dimension, it chooses the points with local density minima of projections to determine the cutting planes. The results it produces are regions that are bounded by axes parallel planes. Each region contains at most one cluster. OptiGrid is easy to realize. But it has several drawbacks. First, it needs multiple scans over the database to perform the partition. Second, the algorithm only separates different clusters. It does not obtain an accurate description of the shapes of clusters. All the clusters it identified are represented by hyper-rectangles. Last, OptiGrid makes some errors during the partition procedure. Some clusters may be partitioned into two or more sub-clusters, and one region may contain several sub-clusters that belong to different clusters. As indicated in [10], this happens when two clusters overlap on every dimension. Fig. 1(a) shows a 2dimensional example. In this situation, the error cannot be avoided when cutting planes are axes parallel. But we find out that even when every pair of clusters can be separated by at least one axes parallel cutting plane (or cutting line in 2-dimensional space), a cluster is still possible to be partitioned into two regions under the effect of other clusters. Fig. 1(b) illustrates this situation. The bold line in the figure represents

A Grid-Based Subspace Clustering Algorithm

41

the cutting line that OptiGrid may choose. This kind of error is not considered by OptiGrid and it may decrease the accuracy of clustering results largely. When there are many clusters in the data space, this problem may be very serious. As has been mentioned above, the bottom-up grid-based method has a good clustering quality when the partition parameters are appropriately set, but it cannot deal with high-dimensional data. The top-down grid-based method can find clusters in a high-dimensional space efficiently, but the accuracy of the clustering result is not satisfiable. If we combine the advantages of these two methods, we will acquire an algorithm that can deal with high-dimensional data sets effectively and efficiently. This is the motivation of our algorithm. We use the top-down method to find subspaces that contain clusters. Then the connected dense cells in these subspaces are identified as clusters. Some of these clusters may be merged to improve the accuracy of the clustering result.

4 The Grid-Based Subspace Clustering Algorithm for HighDimensional Data Streams To formalize our problem, we expand the definition in CLIQUE algorithm [8] to data stream domain. Let A = A1 , A2 , " , Ad be a set of bounded, totally ordered domains and S = A1 × A2 × " × Ad be a d -dimensional data space. We will refer to A1 , A2 , " , Ad as the dimensions of S . The input stream data are d -dimensional points X = X 1 , X 2 , X 3 , " , where X i = ( x i1 , x i 2 , " , x id ) . The j -th attribute of X i is drawn from domain A j . The range of x i , j is [min j , max j ) . We partition the data space S into non-overlapping equal-size cells to get a grid data structure GS . The cells are obtained by partitioning every dimension into k intervals of equal length, which is an input parameter. Each cell C i is the intersection of one interval from each dimension. It has the form (c i1 , c i 2 , " , c id ) , where c ij = [ l mj , h mj ),1 ≤ m ≤ k is a right-open interval in the partitioning of A j . The number of data points contained in a cell is recorded by count of the cell, and we call it the density of the cell. There are k d cells in the grid. When d is large, this number will be very huge. To ensure that the whole grid can be kept in memory, we only store the cells (c i1 , c i 2 , " , c id , count i ) with counti > 0 in memory. 4.1 The Method for Subspaces Identification

The top-down grid-based method needs multiple scans over the data. That cannot be satisfied by an algorithm that processes data streams. To execute the top-down partition procedure without scanning the data multiple times, we first summarize the stream data into a uniformly partitioned grid GS that is built as described above. Then the top-down partition procedure is performed on this grid. The grid is partitioned into regions such that each region contains at most one cluster. The hyperplanes that form a region separate the cluster in this region from other clusters. Each result region Ri has the form ( ri1 , ri 2 ," , rid ) , where rij ⊆ [min j , max j ) is a right-open

42

Y. Sun and Y. Lu

interval. If rij equals the range of the grid on dimension j , dimension j of the region is not cut. This means that the cluster in the region can be separated from other clusters without using the values of data points on dimension j . For each region that contains a cluster, we can find the dimensions whose range is smaller than the range of the grid. These dimensions provide enough information needed to identify the cluster in the region. They span a subspace in which the cluster lies. Thus we can use top-down method to find the subspaces that contain clusters naturally through the grid partition procedure. In our algorithm, we partition the regions recursively until the partition procedure has been performed n times or none of the regions can be partitioned anymore, where n is an input parameter. Parameter nl represents the noise level in data. Algorithm Subspaces Identification Input: d -dimensional grid GS , parameter n , nl Output: the result region set RR , a set of dimension subset DI s 1 Let CR = {GS } represent the candidate region set. Let iteration _ num = 0 . 2 For each region Rl in CR , do: 2.1 For each dimension j , 1 ≤ j ≤ d , do: 2.1.1 Project the cells in Rl to dimension j . For an interval i on dimension j that satisfies [lij , hij ) ⊆ rlj , its density is:

∑ count

Dij = {

p

| C p ∈ Rl , c pj = [lij , hij )} .

p

2.1.2

Suppose

Di , j

is

a

local

max( D m j , j , D m j +1, j , " Di −1, j ) > N Rl /(nl × k j )

density and

minimum,

if

max( Di +1, j , Di + 2, j ,",

Dm j + k j −1, j ) > N Rl /(nl × k j ) , where N Rl represents the number of data

points in Rl , k j is the number of intervals of Rl on dimension j , interval m j and m j + k j − 1 are the leftmost and rightmost intervals of Rl on dimension j , then insert hij into the candidate cutting point i −1

set CCP . Dij and

∑D

p =m j

2.2

pj

−

m j + k j −1

∑D

pj

are also kept.

p =i +1

If CCP is nonempty, we choose the candidate cutting point in it with the smallest Dij . If several candidate cutting points have the same smallest i −1

density, we choose the one with the smallest value of

∑

p =m j

2.3

D pj −

m j + k j −1

∑D

pj

to

p =i +1

break the tie. If a cutting point hij has been selected from CCP , region Rl is partitioned into two regions by vertically cutting dimension j through the point hij . This partition produces two regions Rl′ and Rl ″ .

A Grid-Based Subspace Clustering Algorithm

43

″ ′ CR = CR + Rl + Rl − Rl . If CCP is empty, move Rl from CR into result

region set RR . 3 iteration _ num = iteration _ num + 1 . If iteration _ num < n and CR is not empty, go to step 2. 4 If CR is not empty, move the regions in CR to RR . 5 For each region Rl in RR , 5.1 For each dimension j , 1 ≤ j ≤ d , if rlj = [l , h) satisfying l > min j , or h < max j , insert j into dimension subset DI l that is corresponding

to Rl . In above algorithm, the dimensions in DI i construct a subspace in which the cluster contained in region Ri lies. One problem should be pointed out that if all data points are projected to a subspace corresponding to DI i , the cluster contained in Rl may not be identifiable. This is because the cutting hyperplanes may cut clusters. For example, the DI corresponding to the rightmost cluster in Fig. 1(b) only contains x axes, but the cluster cannot be identified if all data points are projected onto x axes. So the range of the region should be used together with the dimension subset. In next subsection, we will show how to merge the sub-clusters of a cluster that has been cut by cutting hyperplanes. In our experiments, the default value for parameter nl is 10 . That means that the noise level of the data does not exceed 10% of the data. That is reasonable for most data. If a data set contains more noise than 10% of the data, we can use a larger number for nl . The requirement for the density maxima on both sides of a candidate cutting point tries to ensure there really exist clusters on both sides of the data point. In step 2.2, if several candidate cutting points have the same smallest density, we choose the cutting point that can separate the data points most evenly to partition the region. That is because for a divide-and-conquer process, dividing the problem evenly is the most efficient way. 4.2 The Algorithm GSCDS

We maintain a uniformly partitioned grid data structure incrementally on a data stream to summarize the stream data in memory. When there is a request for clustering, the clustering procedure is performed on the grid to find clusters in the grid. As any other bottom-up grid-based clustering algorithms, the effectiveness of our algorithm is affected by the granularity of cells. In next section, we will discuss how to choose an appropriate grid partition parameter for a given dataset (data stream). Because a data stream is evolving, the clusters existing in history data may be different from the clusters in current data. For an application that only concerns the current data, the history data should be discarded. Thus we multiply the count of each cell in the grid by a fading parameter ε < 1 every time a new data item flows in. And only the cell with count > ξ will be stored, where ξ < 1 is a parameter used to control the number of cells in memory.

44

Y. Sun and Y. Lu

Algorithm GSCDS Input: the data stream DS , parameters k , ε , ξ Output: grid GS with cluster labels 1 Partition each dimension of the data space into k intervals to construct the grid GS . 2 For a new arrived data point X i = ( xi1 , xi 2 ," , xid ) of DS , find the cell C m that satisfies xij ∈ cmj for 1 ≤ j ≤ d , assign count m + 1 to count m .

3 For every cell stored, update its count , count = count × ε . Delete the cells with count < ξ . 4 If there is a request for clustering, go to step 5; else, go to step 2. 5 Run the algorithm for subspaces identification to obtain the region set RR and a set of dimension subset DI s. 6 For each region Rl in RR , 6.1 The dimensions in DI l construct a subspace SS l . Project every cell Ci ∈ Rl into SS l . 6.2 In SS l , label the connected cells as clusters. 6.3 The cells in the original data space get the cluster labels of their corresponding projections in SS l . 6.4 For each Clu i in Rl 6.4.1 For each dimension j in DI l 6.4.1.1 Suppose the range of Rl on dimension j is [l mj , hm′j ) , 1 ≤ m, m′ ≤ k . If l mj > min j , compute CLijm = {C p | C p ∈ Clui , c pj = [l mj , hmj )} ; if hm′j < max j , compute CRijm′ = {C p | C p ∈ Clu i , c pj = [lm′j , hm′j )}

6.4.1.2

If CLijm is not empty, find the span of CLijm on each dimension except j ; If CRijm′ is not empty, find the span of CRijm′ on each di-

mension except j . 7 For each pair of clusters Clu i and Clu l , if there exist nonempty set CLijm and CRljm′ satisfying m = m′ + 1 , and the spans of the sets on each dimension except j overlap, the clusters are merged. 8 Go to step 2.

In subspaces, the data points are much denser and we can identify the connected cells as clusters. Because the regions don’t overlap, a cell in the original data space will get at most one cluster label. As has been pointed out in section 3, the top-down grid partition procedure may cut one cluster into sub-clusters that lie in different regions. To check whether two result clusters belong to the same cluster, we put the clusters in the original data space. If a cluster has been cut by a hyperplane, step 6.4 will find out the cells in the cluster that are adjacent to the hyperplane. If two clusters meet the conditions stated in step 7, they are considered to belong to the same cluster.

A Grid-Based Subspace Clustering Algorithm

45

5 Experiment Results In this section, we empirically evaluate our GSCDS algorithm using two real data sets that have been used in [5] and one synthetic data set. We compare GSCDS with GCHDS to assess the accuracy and efficiency of GSCDS. GCHDS is our earlier algorithm that also utilizes the distribution information of data points on each dimension to select useful dimensions for clustering high-dimensional data streams [7]. All clusters the algorithm obtained lie in the same subspace. For the data set used in [7], GCHDS outperforms HPStream [5] both in effectiveness and efficiency. More details can be found in [7]. In this section, we also analyze the effect of the input parameters on GSCDS. All the experiments were performed on a PC with AMD 2500+ processor and 512 MB memory, which runs Windows XP operating system. We implemented our algorithm in Microsoft Visual C++. We use two real datasets with very different characters to evaluate our algorithm. The first real dataset we use is the KDD-CUP’99 Network Intrusion Detection stream dataset. There are 494020 records in this dataset, and each record has 34 continuous attributes. The second real dataset is the Forest CoverType dataset that is downloaded from the UCI machine learning repository website (http://www.ics.uci.edu/~mlearn). This dataset contains 581012 records. For each record, the 10 quantitative attributes are used to perform the clustering. In these two datasets, each record has a class label. We also generate a 2-dimensional synthetic dataset to illustrate the validity of our method for merging the sub-clusters of a cluster that has been cut by the partition procedure. We use the cluster purity that is defined as the average percentage of the dominant class label in each identified cluster to evaluate the clustering accuracy of GSCDS. Only the data points that arrive within a predefined window of time are used to calculate the cluster purity. The cluster purity has been used by GCHDS and HPStream to assess the clustering accuracy. As in [7], the stream speed is set at 100 points per time unit and one time window contains 1000 points. To avoid decaying the data too quickly, we multiply the count of every cell by ε every time 1000 new data points have arrived. In our experiments, the default value for ε is 0.9 , ξ is 0.8 . For the subspaces identification algorithm, the parameter n is set to 20, and nl is set to 10. The algorithm GCHDS chooses 20 dimensions for the Network Intrusion dataset and 8 dimensions for the Forest CoverType dataset. We compare the cluster purity of our results with GCHDS in Fig. 2 and Fig. 3. Fig. 2 shows the comparison for the Network Intrusion Detection dataset, and Fig. 3 shows the comparison for the Forest CoverType dataset. k is set to 20 for both datasets. We can see that the cluster purity of GSCDS is always higher than that of GCHDS. As illustrated in Fig. 3, GCHDS is unable to process dataset with complex data distribution because the dimension selection method it uses is too simple. Fig. 4 shows the clustering time of GSCDS and GCHDS. In GSCDS, the time needed for updating the grid is the same as that of GCHDS. So only the time needed for performing clustering on the grid is counted. GSCDS is slower than GCHDS because the procedure that it uses to select dimensions is more complicated. HTU

UTH

Y. Sun and Y. Lu

&OXVWHUSXULW\

46

*6&'6

*&+'6





      



6WUHDPLQWLPHXQLWV

Fig. 2. Quality comparison (Network Intrusion dataset)

*6&'6

*&+'6

&OXVWHUSXULW\

      









6WUHDPLQWLPHXQLWV

&OXVWHULQJWLPHLQ VHFRQGV

Fig. 3. Quality comparison (Forest CoverType dataset) 

*6&'6



*&+'6

   







6WUHDPLQWLPHXQLWV

Fig. 4. Stream clustering time (Network Intrusion dataset)

In our algorithm, the parameter n , nl , ε and ξ don't affect the quality of the algorithm much. But the effectiveness of the algorithm will decrease sharply much when the value for k is inappropriate. Fig. 5 shows the cluster purity of GSCDS for the Forest CoverType dataset with different settings of k . It is obvious that the

A Grid-Based Subspace Clustering Algorithm

47

&OXVWHUSXULW\

*6&'6      













N

Fig. 5. Cluster purity with different k (Forest CoverType dataset)

Fig. 6. Validation for mergence

accuracy of the algorithm is low when k is too small. From our experiments on several datasets, we find that the accuracy of our algorithm is high when k is no less than ten times of the number of clusters in the dataset. But this is not a general instruction for how to choose the number of intervals on each dimension for a bottomup grid-based clustering algorithm. We generate a simple 2-dimensional dataset to illustrate that the cluster cut by the top-down partition procedure can be identified by our algorithm. Fig. 6 shows the dataset with region borders and cluster labels. The cluster 3 has been cut into two regions, but out algorithm successfully identifies it.

6 Conclusion In this paper, we present a grid-based subspace clustering algorithm, GSCDS, for online clustering of high-dimensional data streams. We combine the top-down gridbased method and bottom-up grid-based method to design an algorithm that can find accurate clusters in different subspaces efficiently. The experiment results show that the clustering quality of the algorithm is better than GCHDS, a similar algorithm that find all clusters in the same subspace.

48

Y. Sun and Y. Lu

References 1. M. R. Henzinger, et al., Computing on data streams. SRC Technical Note 1998-011, Digital systems research center, Palo Alto, California, 1998 2. L. O'Callaghan, et al., Streaming-Data Algorithms for High-Quality Clustering. Proc. of the 18th International Conference on Data Engineering, 2002, 685-694 3. J. Han, M. Kamber, Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers, 2001 4. C. C. Aggarwal, et al., A Framework for Clustering Evolving Data Streams. Proc. of the 29th VLDB Conference, 2003, 81-92 5. C. C. Aggarwal, et al., A Framework for Projected Clustering of High Dimensional Data Streams. Proc. of the 30th VLDB Conference, 2004, 852-863 6. N. H. Park, W.S. Lee, Statistical Grid-Based Clustering over Data Streams. ACM SIGMOD Record, 2004, 33 (1): 32-37 7. Y. Lu, et al., A Grid-Based Clustering Algorithm for High-Dimensional Data Streams. Proc. of the 1st International Conference on Advanced Data Mining and Applications, 2005, 824-831 8. R. Agrawal, et al., Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications. Proc. ACM SIGMOD Int. Conf. On Management of Data (SIGMOD’98), 1998, 94-105 9. S. Goil, et al., MAFIA: Efficient and Scalable Subspace Clustering for Very Large Data Sets. Technical Report, No. CPDC-TR-9906-010, Center for Parallel and Distributed Computing, Department of Electrical & Computer Engineering, Northwestern University, 1999 10. A. Hinneburg, D. A. Keim, Optimal Grid-Clustring: Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering. Proc. of the 25th VLDB Conference, 1999, 506-517 11. C. Baumgartner, et al., Subspace Selection for Clustering High-Dimensional Data. Proc. 4th IEEE Int. Conf. On Data Mining (ICDM’04), 2004, 11-18 12. G. Sheikholeslami, S. Chatterjee, Aidong Zhang, WaveCluster: A Multi-Resolution Clustering Approach for Very Large Spatial Databases. Proc. of the 24th VLDB Conference, 1998, 428-439 P

P

P

P

P

P

P

P

P

P

P

P

P

P

Mining h-Dimensional Enhanced Semantic Association Rule Based on Immune-Based Gene Expression Programming* Tao Zeng1, Changjie Tang1, Yintian Liu1, Jiangtao Qiu1, Mingfang Zhu1,2 Shucheng Dai1, and Yong Xiang1,3 1.

School of Computer, Sichuan Univ., Chengdu, 610065, China {zengtao, tangchangjie}@cs.scu.edu.cn 2 Dept. of Computer Sci. & Tech., Shaanxi Univ. of Tech., Hanzhong, 723003 China 3 Chengdu Electromechanical college, Chengdu, 610031, China

Abstract. Rule mining is very important for data mining. However, traditional association rule is relatively weak in semantic representation. To address it, the main contributions of this paper included: (1) proposing formal concepts on hDimensional Enhanced Semantic Association Rule (h-DESAR) with selfcontained logic operator; (2) proposing the h-DESAR mining method based on Immune-based Gene Expression Programming (ERIG); (3) presenting some novel key techniques in ERIG. Experimental results showed that ERIG is feasible, effective and stable.

1 Introduction Rule mining is an important task of data mining because it is easy to understand rules better than other data mining model. Association rule (AR) mining has been a hot research theme in data mining due to its broad applications at mining association, correlation, causality, and many other important data mining tasks [1-4].Fruitful research results for AR mining can be found in [1-4]. However, complex data mining application requires refined and rich-semantic knowledge representation. Traditional association rule is relatively weak in semantic representation. Example 1 and 2 show that it is difficult for traditional concepts and methods to describe and discover rich-semantic rule. Example 1. Customers probably purchase “laptop” if age is “30-40”, title is “prof.”, and address is not at “campus”. To describe this fact, we need new association rule in the form of age ("30 − 40" ) ∧ title (" prof ." ) ∧ (¬ address (" campus " )) → purchase("laptop" )

(1)

Example 2. Customers probably purchase “PC” if age is “30-40”, either title is “ass.”, or address is at “campus”. To describe this fact, we need other new association rule in the form of * This paper was supported by the National Science Foundation of China under Grant Nos. 60473071 and 90409007. L. Feng et al. (Eds.): WISE 2006 Workshops, LNCS 4256, pp. 49 – 60, 2006. © Springer-Verlag Berlin Heidelberg 2006

50

T. Zeng et al. age ("30 − 40" ) ∧ (title (" ass ." ) ∨ address (" campus " )) → purchase("PC " )

(2)

On issues like Example 1 and 2, we can retrieve little related work except [5]. In 2002, Zuo proposed an effective approach based on Gene Expression Programming (GEP) to mine Predicate Association Rule (PAR), named PAGEP [5]. However, PAGEP’s main objective to mine is single-dimensional. And PAGEP can not always success in discovering strong PARs stably. To address it, focusing on multi-dimensional problem, we proposed algorithms based on Immune-based GEP to mine h-Dimensional Enhanced Semantic Association Rule (h-DESAR). These are distinguished from [5] and other related works. The main contributions of this work included that formal concepts and properties of h-DESAR were proposed, and the h-DESAR mining algorithm based on Immunebased GEP (ERIG) was proposed, implemented and tested. Main novel techniques in our ERIG include: − The distinctive structures of immune cell and antibody, which can carry 8 pieces of h-DESARs to decrease computing complexity 8 times; − The Dynamic Self-Tolerance Strategy where self set can change dynamically and both invalid and redundant immune cell can be eliminated. − The heuristic h-DESARs Reduction Criterion (EPC), that is, a strong rule is fine if and only if the contra-positive of it is strong too. The remaining of the paper is organized as follows. Section 2 describes the background of problem and our motivation. Section 3 formally introduces the problem. Section 4 proposes the ERIG algorithm, presents some distinctive methods or strategies and discusses the time complexity. Section 5 gives experimental results. Finally, Section 6 is conclusion and future work.

2 Background and Motivation 2.1 Background Gene Expression Programming (GEP) [5,6,7] is of genetic computing introduced by Candida in 2001 [6]. The philosophical strategy hidden in GEP is to solve complex problem with simple code. GEP is somewhat similar to, but not the same as Genetic

Expression Tree (ET) Gene

š››aab™cbcce

š

Decoding ›

Expression

(a›a)š(b›™c)

Equivalence

a

›

a

b

™

c Fig. 1. Decoding process in GEP

Mining h-Dimensional Enhanced Semantic Association Rule

51

Algorithms (GA) or Genetic Programming (GP). The chromosome of GP is treeformed structure directly, while that of GEP is linear string. So GP’s genetic operations are designed to manipulate the tree forms of chromosomes. However, GEP’s genetic operations are similar to but simpler than those in GA. Compared with its ancestors, GEP innovated in structure and method. It uses a very smart method to decode gene to a formula [5,6,7]. Fig. 1 demonstrates the decoding process in GEP. As an example, if let “a”, “b” and “c” represent atomic predicates “age(x)”, “title(x)” and “address(x)” respectively, then the expression in Fig. 1 can express the logic formula “(age(x) ∨ age(x)) ∧ (tile(x) ∨ ¬address(x))”. Like the example above, this paper will utilize GEP to express and discover the predicate formulas that can be used to construct enhanced semantic meta-rule. Please refer to [5, 6, 7] for the other detailed description on GEP due to the limited space. Artificial Immune System (AIS) [9-12] is a rapidly growing field of information processing based on immune inspired paradigms of nonlinear dynamics. It is expected that AIS, based on immunological principles, be good at modularity, autonomy, redundancy, adaptability, distribution, diversity and so on. As a member of natureinspired computing, AIS imitates biology immune system, aiming not only at a better understanding of the system, but also at solving engineering problems. There are various models or techniques for AIS based on different algorithms or representations. According to [10], the main representations used include binary strings, real-valued vectors, strings from a finite alphabet, java objects and so on. 2.2 Motivation of Proposing Immune-Based GEP GEP is strong in representing and discovering knowledge with simply linear strings. AIS has many advantages in evolution control. It is natural to assume that embedding GEP in AIS will inherit and enhance advantages of AIS and GEP.

3 Formal Statements for h-DESAR This section introduces some notations, presents the formal statement of problems, and discusses their properties. Basic relational algebra notations come from [8]. Let Sm denote a m-dimensional relation instance, Attr(Sm) denote attribute symbol set of Sm, Dom(Ai) denote the domain of attribute Ai, Sˆ m = ( A1 , A2 ,..., Am ) denote relation schema, and t = (V A ,VA ,...,V A ) denote a tuple of Sm, where Ai ⊆ Attr ( S m ) , 1 2 m VAi ∈ Dom( Ai ) for i=1,..,m.

Let H = {y | y is a well-formed predicate formula}, Ary(h) be arity of h, and PreSymbol(h) = {z | z is the symbol of an atomic formula in h, h∈H }. For instance, if q is A(x)∨A(x)∧(B(x)∨¬C(x)), then Ary(q) = 3 and PreSymbol(q) = {A, B, C}. Let W be a set, |W| denote the size of W that is the number of elements in W, and #(Sm) denote record number of Sm.

52

T. Zeng et al.

3.1 Enhanced Semantic Meta-rule The following formal statements on enhanced semantic meta-rule are different from those proposed by Fu in [4]. Definition 1. An enhaced semantic meta-rule ℜ on Sm can be described as a logic formula in the form of P→Q, where − Let X, Y ⊂ Atrr(Sm), X ≠ φ, Y ≠ φ, X ∩ Y = φ, and ΩM = {ψ | ψ is an atomic firstorder predicate whose symbol is in M, and ψ(x) means the value of attribute ψ is x} and F = {¬, ∧, ∨}. − P is a well-formed first-order logic formula composed of the atomic formulas in ΩX and logic operators in F. − Q is a well-formed first-order logic formula composed of the atomic formulas in ΩY and logic operators in F. Additionally, we call P antecedent, Q consequent and {P, Q} foundation set of it. □ T

T

Definition 2. We call an enhanced semantic meta-rule h-dimensional enhanced semantic meta-rule ℜh if and only if − 2 ≤ h ≤ m, and ary(P) + ary(Q) = h. − P and Q have been simplified.1 − The atomic predicates in P and Q can occur only once in P and Q respectively. Additionally, let {ℜh} denote the set of all h-dimensional enhanced semantic metarules on Sm. □ T

Remark 1. The logic operators we used include “AND”, “OR”, “NOT” which is selfcontained. 3.2 h-Dimensional Enhanced Semantic Association Rule Let M be an attribute set, M⊆Attr(Sm) and the sub-tuple GetFTuple (M, t) = M t where Ai ∈ M for i=1,…,|M|. ∏ A1M , A2M ,..., A|M M|

Definition 3. Given a tuple t = (VA ,VA ,...,VA ) ∈ Sm and ℜh, a h-Dimensional 1 2 n Enhanced Semantic Association Rule ℜh,ts can be described a logic formula in the form of Ps→Qs, where − Let P be antecedent and Q be consequent of ℜh. − Ps is the substitution formula of P, in which all variables were replaced by the corresponding value in GetFTuple (P, t) according to the meanings of atomic predicate in P. − Qs is the substitution formula of Q, in which all variables were replaced by the corresponding value in GetFTuple (Q, t) according to the meanings of atomic predicate in Q. Additionally, we call the tuple t feature tuple. Ps and Qs is antecedent and consequent of it respectively. { Ps, Qs } is foundation set of it. □ 1

Here simplified means that expression string is parsed to create an expression tree and both redundant brackets and “¬” are eliminated from expression string. For example, “(((a)∧b))” can be simplified to “a∧b”, “¬¬¬a” to “¬a”, and “¬¬¬¬a” to “a”.

Mining h-Dimensional Enhanced Semantic Association Rule

53

It is obvious that both Example 1 and Example 2 are sound 4-dimensional enhanced semantic association rules. Given two m-dimensional tuples t1=( Vc , Vc ,...,Vc ) and t2=( Vc ' ,Vc ' ,...,Vc ' ), let 1

2

m

1

2

m

t =( f c , f c ,..., f c ) denote match tuple between t1 and t2 where 1

2

fC j =

m

true

if VC = VC '

false

if VC ≠ VC '

j

j

(3)

j

j

j=1,…,m

Definition 4. Let U be one of Ps, Qs and Ps∧Qs of ℜh,ts, and t be feature tuple of ℜh,ts. For ∀t’∈Sm, we say that t’ support U if and only if − Let t be the match tuple between t and t’, and t P =GetFTuple(Attr(PSx), t ). − US is the boolean formula substituted for U, in which all atomic predicates were replaced by the corresponding boolean value in t P according to the mapping relationship between attributes in t P and atomic predicates in U. − Evaluate US and the result is true. − Otherwise, t’ does not support U. □ Let u∈{Ps, Qs, Ps∧Qs}, and σ(u | Sm) denote the number of records that support u. The support degree and confidence degree can be described as follows. − Support degree:

S S m sup(ℜh,ts, Sm)= σ ( P ∧ Q | S ) m # (S )

(4)

− Confidence degree:

S S m conf(ℜh,ts, Sm)= σ ( P ∧ Q | S ) S m σ (P | S )

(5)

Let min_conf, min_sup∈[0, 1]. ℜh,ts is strong if and only if sup(ℜh,ts, Sm)≥ min_sup and conf(ℜh,ts, Sm)≥ min_conf like [1,3]. 3.3 Example Example 3. 1) Let FA = age(x) ∧ (title(x) ∨ ¬address(x)), FA’ = (age(x) ∨age(x)) ∧ (title(x)∨¬address(x)) and FB = purchase(x) where “age, title, address, purchase”∈Attr(Sm). Then both FA→FB and FA’→FB are well-formed enhanced semantic meta-rule, but only FA→FB comply with h-dimensional enhanced semantic meta-rule according to Definition 2 where h = 4. 2) Given a tuple r(“30”, “male”, “campus”, “prof..”, “laptop”)∈Sm and Sˆ m = (age, gender, address, title, purchase), FAS → FBS is a ℜ4,rs where FAS = age(“30”) ∧ (title(“prof.”) ∨ ¬address(“campus”)) and FBS = purchase(“laptop”). 3) Suppose that there is another tuple r’(“30”, “male”, “not in campus”, “ass..”, “laptop”) ∈Sm, then match tuple r between r and r’ is (true, true, false, false, true). Because uSA = true∧(false∨ ¬ false) = true, uSB = true and uSA∧ uSB = true, r’ support FAS, FBS and FAS∧FBS. □ In this paper, we focus on mining h-DESAR, in which the atomic predicates in it occur only once, because it is more extractive and heuristic.

54

T. Zeng et al.

3.4 Some Properties of h-DESAR Lemma 1. If FS is a foundation set, then FS can be used to construct 8 pieces of hDESARs. They can be grouped into 4 pairs. Two h-DESARs in each pair are equivalent in logic each other. Proof. Suppose that there is a foundation set FS = {A, B}, and we can construct the following 8 h-DESARs: 1) A → B, 2) ¬B→¬A, 3) B → A, 4) ¬A→¬B, 5) ¬A→B, 6) ¬B→A, 7) A→¬B, and 8) B→¬A. In them, 1) and 2), 3) and 4), 5) and 6), 7) and 8) are the contra-positive each other respectively. Since the contra-positive is equivalent to the original statement, two statements in pair are equivalent each other. □ Theorem 1. Let FS={A, B} be a foundation set and Sm be a relation instance. If σ(A|Sm), σ(B|Sm), σ(A∧B|Sm) and #(Sm) were given, then all of support degree and confidence degree for 8 pieces of h-DESARs constructed by FS can be evaluated. Proof. Because in system, arbitrary tuple can either support h-DESAR or not, we can compute the following value: 1) σ(¬A|Sm) = #(Sm) - σ(A|Sm), 2) σ(¬B|Sm) = #(Sm) σ(B|Sm), 3) σ(A∧(¬B)|Sm)=σ(A|Sm)-σ(A∧B|Sm), 4) σ(¬A∧B|Sm) = σ(B|Sm) - σ(A∧B|Sm), 5) σ(¬A∧¬B|Sm)=#(Sm)-σ(A|Sm)-σ(B|Sm)+σ(A∧B|Sm). we can use these values to evaluate all support degree and confidence degree for these h-DESARs according to Equation (4) and (5). □ Lemma 2. Given a relation instance Sm and an enhanced semantic meta-rule ℜh, let EARSet be the set of enhanced semantic association rule complied with ℜh on Sm, then |EARSet| ≤ #(Sm). Proof. According to definition 3, let W = PreSymbol(PS) ∪ PreSymbol(QS), a subtuple GetFTuple (W, t) can be corresponding to a h-DESAR. Two cases arise: (a) If each of such sub-tuple in Sm is unique, then |EARSet| = #(Sm). (b) If there exist any □ duplicate sub-tuples in Sm, then |EARSet| < #(Sm). So |EARSet| ≤ #(Sm).

4 The ERIG Algorithm 4.1 Framework We call our algorithm ERIG (the h-DESAR mining based on Immune-based Gene Expression Programming). The AIS in ERIG is somewhat similar to the hybrid of the clonal selection principle [9-10] and the negative selection algorithm [11]. However, different from other models, the representation in our AIS is gene of GEP and mutation operators come from GEP. In addition, many new techniques were proposed in ERIG. The algorithm framework is as follows. Algorithm 1. (ERIG) The h-Dimensional Enhanced Semantic Association Rule mining based on Immune-based Gene Expression Programming. Input: A m-dimensional relation instance Sm, a minimum support, minsup, and a minimum confidence, minconf. Output: The set of strong h-Dimensional Enhanced Semantic Association Rules.

Mining h-Dimensional Enhanced Semantic Association Rule

55

BEGIN

1

Initialize and set control parameters; // The cellnum is the number of cells every generation. A outer loop is a generation. // The hfmt is the high frequent mutation threshold 2 WHILE stop condition is not satisfied BEGIN 3 BCSet := NULL; // BCSet is immune cells set count := 0; 4 WHILE BCSet.size < cellnum AND count < hfmt BEGIN 5 6 BCSet := GenBCSet(cellnum, Sˆ m , F, control parameters); //Call GenBCSet to generate BCSet via GEP BCSet := SelfTolerance(BCSet); // Self tolerance 7 count ++ ; 8 END WHILE 9 m 10 ABSet := MaturateCells(BCSet, S ); // Produce antibody set ABSet 11 Maturateaffinity(ABSet, BCSet, minsup, minconf); // Evaluate and eliminate those cells and antibodies which can not meet requirement. // Add cells in BCSet to elite gene pool for GEP 12 MemorizeCells(BCSet); // Output solution for problem; 13 Output(ABSet); 14 CloneMutation(BCSet); 15 END WHILE END.

□

The code is self-explanatory. But it is impossible to list all detail of ERIG. We will select some distinctive methods or strategies to show as follows. 4.2 Some Key Techniques in ERIG 4.2.1 Structures of Immune Cell and Antibody Immune cell and antibody are very important for AIS. In general, antigen is corresponding to the problem to be solved and antibody to the solution for it. For hDESAR problem, the record in relation instance can be antigen and h-DESAR can be antibody. Through comprehensive analysis on each aspect, we designed our antibody and immune cell (B cell). The formal definition is as follows. Definition 5. An immune cell, BCell, is a 3-tuple (G, E, δ) where − G = (gA, gB), called chromosome, is a 2-tuple, where both gA and gB are genes of GEP. − E = (eA, eB), called dual-expression, is a 2-tuple, which were decoded from genes in G according to GEP. − δ∈{-1, 0, 1, 2} is the state value of BCell, where –1, 0, 1 and 2 indicate cell is □ dead, immature, mature and memorized respectively. Definition 6. An antibody is a 3-tuple, (E, L, V), where − E comes from the immune cell that produces this antibody. − L = (lA, lB) is a 2-tuple, where lA and lB are the substitution formulas for those in E respectively by attribute values of record in relation instance. − The 4-tuple V = (pA, pB, pAB, ptotal) stores information about affinity where pA, pB, pAB and ptotal are the support number of lA, lB and lA ∧ lB and the total number □ of records who were tested respectively.

56

T. Zeng et al.

In Table 1 and Table 2, examples for BCell and Antibody were given respectively. Table 1. An example for BCell No. 1 2 3

Symbol G.gA

Value

E.eA

∧∨∨aab¬cbcce (a∨a)∧(b∨¬c)

δ

0

Symbol G.gB E.eB

Value da∧e∨a… d

Table 2. An example for Antibody No. 1 2

Symbol E.eA L.lA

Value

3 4

V.pA V.pAB

60 58

(a∨a)∧(b∨¬c) (age(“30”) ∨ age(“30”) ) ∧ ( title(“ass.”) ∨ ¬ address(“campus”))

Symbol E.eB L.lB

Value d purchase(“PC”)

V.pB V.ptotal

87 100

Theorem 2. An antibody can represent and evaluate 8 pieces of h-DESARs. Proof. Let Ab denote an antibody and by Lemma 1, use {Ab.L.lA, Ab.L.lB} to construct 8 pieces of h-DESARs. Then, after affinity maturation, there are σ(Ab.L.lA|Sm) = Ab.V.pA, σ(Ab.L.lB|Sm) = Ab.V.pB, σ(Ab.L.lA ∧ Ab.L.lB|Sm) = Ab.V.pAB, and #(Sm) = Ab.V.ptotal. Thus we can evaluate these 8 h-DESARs by Theorem 1. □ It shows our antibody is good at representation and discovery of h-DESARs. 4.2.2 Dynamic Self-tolerance Strategy The part of self-tolerance in ERIG develops from negative select algorithm [11] and looks like that in [12]. However there are many differences among them. Our selftolerance strategy is problem-oriented. Main strategy is as follows. − Treat those immune cells that have been generated or used as self dynamically. − Let Bc be an immune cell, and SS be self-set. For ∀Bc∈SS where Bc.E=(eA,eB ), those cells are self too, if their dual-expression is one of (eB, eA), (¬eA, eB ), (eB, ¬eA), (eA, ¬eB), (¬eB, eA), (¬eA, ¬eB ) and (¬eB, ¬eA). − Inject vaccine if it is needed. And treat those cells with certain pattern as self. The function of our self-tolerance strategy is as follows. − Avoid generating redundant cells that are equivalent to represent h-DESARs. − Avoid generating any fault cells that cannot represent valid h-DESARs. − Be able to inject vaccine too. 4.2.3 Affinity Computing In course of affinity maturation, for each antibody, its affinity information for all records (antigens) will be computed. After affinity maturation, there are σ(Ab.L.lA|Sm) = Ab.V.pA, σ(Ab.L.lB|Sm) = Ab.V.pB, σ(Ab.L.lA ∧ Ab.L.lB|Sm) = Ab.V.pAB, and #(Sm) = Ab.V.ptotal. According to Theorem 1 and Theorem 2, we can scan database once but evaluate 8 times more h-DESARs than antibodies.

Mining h-Dimensional Enhanced Semantic Association Rule

57

Additionally, because the statement and contra-positive is logically equivalent, we proposed a heuristic h-DESARs Reduction Criterion (EPC) to reduce result set, that is, a strong rule is fine if and only if the contra-positive of that is strong. 4.3 Algorithms Analysis In this section, we discuss the time complexity of ERIG. Theorem 3. Let h be a constant and #(Sm) = n, then the time complexity of each generation in ERIG depends on the number of antibodies, and it is lower than O(n2). Proof. Since operation on database is time-consuming, #(Sm) is the variable that has great impact on the time complexity. The number of cells, the high frequent mutation threshold, the size of pool and other control parameter all are limited constants. Hence, the time complexity from row 2 to 9 in ERIG is bounded above. It is O(C1). Similarly, MemorizeCells and CloneMutation are O(C2) and O(C3). Supposing the maximum number of cells of every generation is c, then the time complexity of MaturateCells is lower than O(c*n2). It is because, under worst-case condition, c cells can produce c*n antibodies with scanning database once and each of these c*n antibodies will match with n tuples to compute affinity. Finally, for Output, there are c*n antibodies to process at most. So it is O(c*n). To sum up, the total maximum time complexity is O(C1)+O(C2)+O(C3)+O(c*n2)+O(c*n) ≈ O(n2). □

5 Experiments To verify our algorithm, various cases were designed. The test platform is as follows: CPU: Intel C3 1.0GHz, memory: 320MB, hard disk: 80GB, OS: MS Windows XP Pro. SP2, compiler: JDK1.5.03. The data set we used in our experiments is cmc, with 10 dimensions and 1473 rows. It comes from UCI Machine Learning Repository2. Table 3 gives us symbol definitions for this section. 5.1 Case Test Because there has been little research on h-DESAR, the case 1 was designed to compare ERIG with traditional AR mining. Case 1. Let F = {∧}, minsup=0.5%, minconf=95%, cellnum = 20, and hfmt = 200. We run ERIG and Apriori algorithm to mine traditional multi-dimensional AR on data set “cmc” respectively to verify ERIG. Remark 2. If F = {∧} and the order of predicates not be considered, h-DESAR is equivalent to traditional multi-dimensional AR. In this case, in order to utilize Apriori algorithm to mine multi-dimensional AR, we preprocess cmc in the following way. For each value of attribute in cmc, we add a string of its attribute in front of it to construct a new value, whose type become string, then store it into a new data set cmc’. After preprocessing, in cmc’, original equal values of different dimensions in cmc became unequal. It will eliminate possible value-collision between dimensions when Apriori runs on cmc’. 2

http://www.ics.uci.edu/~mlearn/MLRepository.html

58

T. Zeng et al.

Some details of the result for case 1 were gives in Table 4. It showed the number and content of ARs mined by ERIG on cmc are the same as those by Apriori on cmc’. Table 3. Symbol Definitions for Section 5 Symbol TC TSAR EGN ACGE

ECN AREC CEE AEE

Definition Total number of independent cells Total number of strong h-DESARs The generation number when program ends Percentage of cell generation efficiency where ACGE = TC/(EGN*cellnum) * 100 % Number of cells eliminated by self tolerance Ratio of ECN and TC where AREC = ECN / TC (times) Number of cells generation by elite pool Percentage of usage of elite pool where AEE = CEE / TC * 100%

Table 4. Results for Case 1 minsup=0.5%, minconf=95% No. h EGN TC TSAR ACGE AREC AEE 1 2 3 45 35 75.0% 2289 8.9% 2 3 19 360 744 94.7% 291 30.6% 3 4 75 1470 3418 98.0% 34 25.6% 4 5 197 3780 6324 95.9% 23 21.0% 5 6 336 6510 5650 96.9% 18 13.7% 6 7 391 7560 2470 96.7% 25 5.1% 7 8 295 5715 478 96.9% 30 0.7% 8 9 132 2550 22 96.6% 52 0.0% 9 10 28 511 0 91.3% 221 0.0% Note: Sum of TSAR is 19141. The number and content are the same as those via Apriori on cmc’. Table 5. Results for Case 2 minsup = 5% minconf = 98.5% No. h EPC Convergence Vaccine EGN TC TSAR ACGE AREC AEE 1 3 no yes no 292 5760 316292 98.6% 19.26 50.0% 2 3 yes yes no 297 5760 980 97.0% 24.03 20.9% 3 4 no no no 500 10000 1334128 100.0% 0.00 49.8% 4 4 yes no no 500 10000 6796 100.0% 0.01 30.6% 5 5 yes no no 500 10000 18552 100.0% 0.00 30.6% 6 7 yes no no 500 10000 36984 100.0% 0.00 16.6% 7 2 to 6 yes no yes 500 10000 6431 100.0% 0.09 14.1% 8 7 yes no yes 500 10000 5434 100.0% 0.01 1.7% Notes  In No. 7, the dimensions were restricted to 2nd, 3rd, 4th, 6th, 7th and 8th.  In No. 8, the dual-expression template is (“#”, “(#›#)š (#›™#)š(™#›#)”).

Case 2. Let F = {¬, ∧, ∨}, cellnum = 20, hfmt = 200, and the order of predicates be considered. On data set “cmc”, mine general h-DESARs, restricted dimensional

Mining h-Dimensional Enhanced Semantic Association Rule

59

h-DESARs and the special h-DESARs generated by fixed dual-expression template, which test the function of vaccine respectively. The results for Case 2 are in Table 5. Extensional tests show that 1) our algorithm is stable, 2) the efficiency of EPC is notable by comparison, 3) the capability of generating new immune cells is strong, and 4) the function of vaccine is sound and effective. As an example, a 5-DESAR from results of No.7 in Tab 5 is as follows. D8(1)→D7(3) ∨ ¬ (D3(4) ∧D4(1) ∧D2(4))

sup = 8.7% conf = 99.22% (6)

¬(D7(3) ∨ ¬ (D3(4) ∧D4(1) ∧D2(4))) → ¬ D8(1) sup = 6.5% conf = 98.97% (7)

Relationship between TC and h (logarithm figure)

17 16 15 14 13 12 11 10 9 8 7 6 5

F={ F={

2

3

4

5

6

7

Running Time(s)

log2 (TC)

Since the 5-DESAR (6) and (7) are equivalent each other, they can be reduce to a 5-DESAR, where Di denote ith dimension.

∧} ￢,∧,∨} 8

9

10

h

Fig. 2. Relationship between TC and h in Case 1 and Case 2

6 5.5 5 4.5 4 3.5 3 2.5 2 1.5 1

Scalability Study on cmc incremental baseline

295

590 885 1180 Number of records

1473

Fig. 3. Relationship between average running time per generation and record number of data set in Case 3

5.2 Scalability Study In this section, we study the impact of relation instance scale on the performance of our algorithm. Case 3. Let F = {¬, ∧, ∨}, cellnum = 20, hfmt = 200, h = 4 and do the following. − Take a copy of records from row 1 to 295 in cmc as a new data set cmc1, similarly, records from row 1 to 590 as cmc2, records from row 1 to 885 as cmc3, and records from row 1 to 1180 as cmc4; − Merge 2 copies of cmc1 into a new data set cmc2’, similarly, 3 copies of cmc1 into cmc3’, 4 copies of cmc1 into cmc4’, and 5 copies of cmc1 into cmc5’; − Mine h-DESARs respectively on cmc1, cmc2, cmc3, cmc4, and cmc up to 100 generations several times. − Similarly, do it respectively on cmc1, cmc2’, cmc3’, cmc4’, and cmc5’ as baseline. Fig. 3 described the result. The number of distinct tuples from cmc2’, cmc3’, cmc4’ to cmc5’are the same as those in cmc1, besides different in the number of records, so that the number of antibodies does not change and average running time per generation increases very slowly in baseline. However, when we do step 3) in Case 3, the number of unique tuples from cmc1, cmc2, cmc3, cmc4 to cmc increases gradually

60

T. Zeng et al.

with the rise of rows. Thus for every generation, more antibodies are generated and the running time ascends. But it is not so steep. It testifies to Theorem 3. In Table 6, we bring a comparison between ERIG, PAGEP, and Apriori on available objective to mine. Table 6. Comparison between ERIG, PAGEP, and Apriori

Available objective to mine Traditional association rule Rule with connectives beyond “∧” Rule with constrained pattern Rule with constrained attributes

ERIG 9 9 9 9

PAGEP 9 9 8 8

Apriori 9 8 8 8

6 Conclusion and Future Work We have discussed h-DESAR problem, proposed ERIG algorithm, presented some key techniques in ERIG. Experimental results testified to our expectations and showed that the ERIG is feasible, effective and stable. Our future work includes: study on problem space, improvement of performance, discovery of h-DESAR on data streams, and application of web mining or firewall log mining.

References [1] Agrawal R, Imiclinski T, Swami A. Database mining: A performance perspective [J]. IEEE Trans Knowledge and Data Enginnering, 1993,5: 914-925. [2] Agrawal R, Srikant R. Fast algorithm for mining association rules [A]. Proceeding 1994 International conference Very Large Data Bases (VLDB’94). [3] Jiawei Han, Micheline Kambr. Data Mining-Concepts and Techniques [M]. Beijing: Higher Education Press, 2001 [4] Y Fu and J Han. Meta-rule-guided mining of association rules in relational databases[C]. KDOOD’95, 39-46, Singapore, Dec 1995 [5] Jie Zuo, Changjie Tang, Zhang Tianqing. Mining Predicate Association Rule by Gene Expression Programming[C]. WAIM, 2002 [6] C. Ferreira. Gene Expression Programming: A New Adaptive Algorithm for Solving Problems[J]. Complex Systems, 2001, 13(2): 87~129 [7] Jie Zuo. Research on the Key Techniques of Gene Expression Programming: [Ph. D. dissertation]. Sichuan: Sichuan University, 2004 [8] Silberschatz, Korth. Databse System Concepts, Fourth Edition, McGraw-Hill Computer Science Series, 2001 [9] DE CASTRO L N, VON ZUBEN F J .Artificial Immune Systems: Part I-Basic Theory and Applications[ J].Technical Report, TR- DCA Ol/99, 1999, 12. [10] Dasgupta D., Ji, Z., Gonzalez, F.. Artificial immune system (AIS) research in the last five years [J]. Evolutionary Computation, 2003. CEC '03. [11] S. Forrest, A. S. Perelson. et al. Self-Nonself Discrimination in a Computer. In Proceedings of IEEE Svmposiimi on Research in Secwitv and Privacy, 1994. [12] Tao Li, Xiaojie Liu, and Hongbin Li. A New Model for Dynamic Intrusion Detection [C]. CANS 2005, LNCS 3810, pp. 72–84, 2005.

An Efficient Algorithm for Distributed Incremental Updating of Frequent Item-Sets on Massive Database Jiangtao Qiu, Changjie Tang, Lei Duan, Chuan Li, Shaojie Qiao, Peng Chen, and Qihong Liu School of Computer Science, Sichuan University, Chengdu, China {qiujiangtao, tangchangjie}@cs.scu.edu.cn

Abstract. Incremental updating of frequent item-sets on a database includes three problems. In this paper, these problems are explored when database stores massive data. The main contributions include: (a) introduces the concept of Interesting Support Threshold; (b) proposes Frequent Item-sets Tree (FITr) with compact structure; (c) proposes and implements algorithm FIIU for frequent item-sets incremental updating; (d) in order to further improve performance, proposes the algorithm DFIIU for distributed incremental updating of frequent Item-sets on massive database; (e) gives extensive experiments to show that FIIU and DFIIU algorithms have better performance than traditional algorithm on massive database when the number of items is less.

1 Introduction Association Rules Mining (ARM) is an active research area on Data Mining. Since its introduction in [1], there have been extensive studies on efficient frequent item-set mining methods. The process of mining association rules consists of two main steps: (1) Find the frequent item-sets under support threshold; (2) Generate strong association rules from the frequent item-sets. Most studies focus on step 1 because step 1 is more difficult than step 2. However, finding frequent item-sets by simply re-executing mining on the whole database will be very low efficient when new data were inserted into database or support threshold changed, especially for database stored massive data. Although parallel algorithm and sampling algorithm have been proposed to find association rules on massive data, it is obvious that they are not suitable for the above problem. Therefore, using the prior knowledge to find out new item-sets on the updated database, so called Incremental Updating of Frequent Item-sets, has become a hot topic. It involves three problems:(1) Finds out frequent item-sets under new support threshold without database updating; (2) Finds out frequent item-sets when database was updated, but support threshold was unchanged; (3) Finds out frequent item-sets when database was updated and support threshold was changed. There have been many incremental mining algorithms being proposed, and they have been proved to be good at medium scale database. However, these algorithms showed one or several neglects: (1) only solved one of three problems; (2) Needed to scan database repeatedly; (3) Although some algorithm scanned database once, they didn’t prove good performance on the massive database. L. Feng et al. (Eds.): WISE 2006 Workshops, LNCS 4256, pp. 61 – 72, 2006. © Springer-Verlag Berlin Heidelberg 2006

62

J. Qiu et al.

In order to solve the three problems, our study makes following contributions based on idea of not scanning original database. 1) 2) 3) 4)

Introduces the concept of Interesting Support Threshold Supmin. Proposes a prefix tree with compact structure, called Frequent Item-sets Tree. Proposes an efficient algorithm FIIU (Frequent Item-sets Incremental Updating). In order to further improve performance, the algorithm DFIIU (Distributed Frequent Item-sets Incremental Updating) is proposed for incremental mining frequent Item-sets on massive databases with multiple computers.

The remaining of this paper is organized as follows. Section 2 gives a briefly introduction to related works. Section 3 revisits description of the problem. Section 4 proposes algorithm FIIU. Section 5 proposes algorithm DFIIU. Section 6 gives a thorough performance study in comparison with FP-Growth algorithm. Section 7 summarizes our study.

2 Related Works Some efficient algorithms have been proposed for finding frequent item-sets. Apriori[2] employs iterative approach known as level-wise search, where k-item-sets are used to explore k+1-item-sets. Apriori based DHP[3] uses hash table to improve performance on mining frequent item-sets. Partition[4] employs partition strategy to find frequent item-sets with only twice database scans. Han’s FP-Growth[5] may avoid candidates generation and utilizes compact data structure, called frequent pattern tree, to generate frequent item-sets with divide-and-conquer strategy. To address problem of incremental updating of frequent item-sets, Cheung and Li first propose FUP[4] and FUP2[5]. However, these algorithms only focus on second and third problems of incremental updating of frequent item-sets, and need to scan the entire database several times. In [6], a CAST tree is proposed. CAST may be employed to find frequent item-sets when support threshold changes. FIUA2[7] and IM[8] are FP-tree based algorithm. They incrementally mine frequent item-sets with strategy that use new data to extend old FP-tree. However, the two algorithms do not analysis performance on massive data. Main approaches of mining frequent item-sets on massive data include parallel-based approach and the sampling-based approach. CD[9] is an Apriori-like parallel algorithm. DD[9] and IDD[10] divide candidate set into several sub-sets, and then send each sub-set to one processor. Quick-Mining[11] is a sampling-based algorithm.

3 Problem Descriptions Let Ik be an item, and I={I1,I2,…, Im} be a complete collection of items. A transaction database DB={T1, T2,,…, Tn} is a collection of transactions, where Ti (i=1,…,n) is a transaction which contains items in I. Sup denotes support threshold. A item-set is called frequent item-set if its support count is not less than Sup × |DB| where |DB| is the number of transactions in database DB.

An Efficient Algorithm for Distributed Incremental Updating of Frequent Item-Sets

63

Given a transaction database DB and a threshold Sup, the problem of frequent item-set mining is to mine complete collection of frequent item-sets on DB with support threshold Sup. Let db be the collection of new transactions, and |db| be the numbers of new transactions, the updated database U=DB ∪ db. The problems of incremental updating of frequent item-sets include: (1) Find out frequent item-sets ISsup’ (DB) if support threshold Sup is changed to Sup’, but database is not updated, U=DB. (2) Find out frequent item-sets ISsup(U) if database is updated, U= DB ∪ db, but support threshold is not changed. (3) Find out frequent item-sets ISsup’ (U) when database was updated, U= DB ∪ db, and support threshold is changed to Sup’. The problem of Distributed Incremental Updating of Frequent Item-sets is to find out all frequent item-sets by utilizing distributed system when support threshold is changed and database is updated.

4 Incremental Updating of Frequent Item-Sets In order to not scan original database DB when incrementally mining frequent item-sets, in our study, all item-sets in DB will be stored. However the number of item-sets in DB may be large, especially when encountering long transactions in very large DB. Therefore, firstly, we introduce a concept, called Interesting Support Threshold Supmin in section 4.1. For each item-set A in DB, if A.count is not less than Supmin × |U|, A is a frequent item-set. Furthermore, all item-sets in DB may be divided into two categories: frequent item-sets and non-frequent item-sets. All frequent item-sets are stored in a prefix tree with compact structure, called FITr, which is defined in section 4.2. Then all reduced non-frequent item-sets are stored in two-level hash-indexed linked-lists, called THL, which is defined in section 4.3. Finally, FITr and THL are materialized on disk. For first problem of Incremental Updating of Frequent Item-sets, FITr is firstly read from disk when support threshold is changed to Sup(Sup>Supmin ). Then FITr is traveled to find out each item-set whose support count is not less than Sup × |U|. For the second and the third problems, firstly, all item-sets in db will be found out. Then store them into a data structure, called WITs, which is defined in section 4.3. Finally, utilizes Algorithm FIIU, described in 4.4, to realize incremental updating of frequent item-sets. 4.1 Interesting Support Threshold It is not necessary to find out item-sets under all support thresholds when apply mining association rules to industry. The smaller support threshold is, the larger the number of frequent item-sets is, and then the more difficult generating strong association rules is. Therefore, it can be concluded that generating significant strong association rules is impossible when support threshold is too small. Many criteria [12] are proposed to mine significant association rules. In this study, we defined Interesting Support Threshold according to these criteria. Definition 1(Interesting Support Threshold Supmin). Let DB be database and R be a set of criteria for mining association rules. Supmin is called interesting support threshold

64

J. Qiu et al.

if Supmin is minimal support threshold that satisfied R and may generate significant strong association rules on DB. 4.2 Frequent Item-Sets Tree To design a compact data structure to store frequent item-sets, let’s examine an example firstly. bN H

bN

I

I

I

I

I

cN I

I cN I

Fig. 1. Example of frequent item-set tree

Example 1. Let {I1,I2},{I1,I3,I4},{I2,I3},{I2,I4},{I3} be frequent item-sets. They are stored in frequent item-sets tree (or FITr in short). FITr is illustrated in Fig.1. Node Ij indicates that item Ij is stored in the node. A frequent item-sets tree may be designed as follows based on example 1. Definition 2(Frequent Item-sets Tree FITr). A Frequent Item-sets Tree (or FITr in short) is a tree structure defined below. 1) FITr consists of one root labeled as head. Each node in the FITr consists of four fields: item, count, cNode, bNode, where item registers item the node saved, count registers support count of an item-set, cNode is a pointer which point to first node in child level, bNode is also a pointer which point to brother node. 2) Let node1 and node2 be nodes in FITr. We call that node1 and node2 are in same level if node1.bNode=node2 or node1.bNode.….bNode=node2 . 3) Let node1 be a child node of root, we call that node1 is a node in first level in FITr. Starts off from node1, then goes to one of its children node, and go on by this way if noden may be reached at last, we call that there exists a path between node1 and noden. The set of items of all nodes in the path represents a frequent item-set, and count field of noden represents support count of the frequent item-set. Example 2. In our running example shown in Fig.1, I1 and its brother node I2, I3 are in same level. Path of node I1 to node I4 is I1 → I3 → I4. All nodes in the path represent an item-set A= {I1, I3, I4}. Value of count field of node I4 denotes support count of A. In our study, each item is given a unique integer number id. Property 1. Let id1 and id2 be integer number of node.item and node.bnode.item respectively. Then id1 is less than id2. Property 2. Let id1 and id3 be integer number of node.item and node.cnode.item respectively. Then id1 is less than id3. Property 1 ensures that nodes in same level will be sorted in ascending order by their integer number. Furthermore, cost of inserting operation and searching operation in

An Efficient Algorithm for Distributed Incremental Updating of Frequent Item-Sets

65

FITr will be reduced efficiently. Property 2 ensures that those frequent item-sets, which have same prefix, share same prefix sub-path in FITr. Furthermore, FITr may store frequent item-sets compactly. Algorithm 1 InsertFIT: inserting frequent item-sets to FITr Input: item-set A, FITr Symbols: A.count denotes support count of the item-set; item(i) denotes No.i item in item-set A; t denotes the number of items in item-set A. Method: (1) Sort(A); (2) for(int i=1, node=head; i<=t; i++){ (3) wNode=FindNode (node,item(i)); (4) if (wNode=null) wNode=Insert(item(i)); (5) node=wNode;} (6) node.count=node.count+A.count; For all item-sets in FITr, their items should be ranked in ascending order by id as shown in Property 2. Therefore, in step 1, items of the item-set are ranked before the item-set is inserted into FITr. The function FindNode(node,item(i)) search the node whose item field is same with item(i) in node’s child level. If the node is found, return the node, otherwise return null. If null is returned, in step 4, a new node, whose item field is set to item(1) and count is set to zero, will be generated, then inserted into node’s child level by Property 1. After the last node of item-set being inserted into FITr, in step 6, count of the node will be modify because the count of the last node should be support count of A. According to algorithm 1, support count of item-set A will be updated correctly when insert A to FITr and there exists A in FITr. Theorem 1. (Compactness of FITr) Let I be collection of items, I={I1,I2,…,Im}, ID(x) be unique integer number given ∈ to x(x ∈ I), A1 and A2 be item-set, and Path(A) be path of item-set A in FITr. We call that Path(A1) ⊂ Path(A2) if A1 ⊂ A2 and (∀x)(∀y )( x ∈ A2 ∧ x ∉ A1 ∧ y ∈ A1 ∧ ID( x) > ID( y )) . Proof. We assume that A1 has been inserted into FITr and the path of A1 is from node1 located in first level to node2. Let A2=A1 ∪ {Im} and ID(Im )>ID(x) (x ∈ A1). According to Property 2, the order of all items of A2 being inserted into FITr is items in A1 ∩ A2 at first, then item Im. According to step 3 and step 5 in Algorithm 1, the path of A1 will be found after all items in A1 ∩ A2 are inserted into FITr. A new node node3 (node3.item=Im) will be inserted at child level of node2. Name the path of node3 to node1 as the path of A2, denoted as Path(A2). It can be concluded that Path (A1) ⊂ Path (A2). 4.3 Storing of Non-frequent Item-Sets and Updating of FITr In our study, a two-level hash indexed linked-lists structure, called THL, is adopted to store non-frequent item-sets. Each linked-list is given a unique name, called class-name. Each node in linked-list consists of three fields: count, next, itNum, where

66

J. Qiu et al.

count registers support count of a item-set stored in linked-list, next points to next node, and itNum store the integer value gotten by reducing the item-set. Process of Item-set reduction includes follow steps. (1) Derive each item of an item-set and its integer number id. (2) Let an integer, called num, be zero, then set No. id bit of num to 1. By the reduction, different item-set may be represented by different integers. For example, let {I1, I4, I6} be an item-set, 1, 4, 6 be integer number of I1, I4 and I6 respectively. As a result, itNum=41. By summing up id of all items in item-set, we can get an integer, denoted as a. Then, denote a modulo 10 as key1. Let b be the base e logarithm of a. Denote value of second place after decimal point of b, as key2. Structure of THL is shown in Fig.2. T1 and T2 are class-name of linked-list. First level of two-level hash index uses key1 as hash key; another uses key2 as hash key. When an item-set is given, the class-name of linked-list the item-set belongs to can be gotten by two-level hash index. Second level First level

T1

…

…

…

6

12354

2

…

…

name head T2

… 7 …

…

…

8

488

…

…

Fig. 2. Two-level hash indexed linked-lists

…

T2

T2

…

… …

654

T100

…

Head list

T100 … 248 …

Fig. 3. Data structure of WITs

To insert the item-set to a linked-list, firstly, reduce item-set to an integer. Then generate a node of linked-list. Finally, insert the node to linked-list by itNum ascending order. The count of the node would be added if there exists node that has same itNum with the new node. According to the above data structure, all non-frequent item-sets may be saved to one hundred of linked-lists. Each linked-list will be materialized in disk by its class-name. In our study, a data structure, called WITs, is adopted to store temporary data during incremental updating of frequent item-sets. WITs includes a head list and linked-lists, whose structure is same with linked-lists in THL. The node in head list consists of two fields: name and head, where name registers class-name of a linked-list, head is pointer that points to a linked-list. Fig.3 shows structure of WITs. Before inserting a item-set to WITs, get class-name of the linked-list that the item-set belongs to by using the two-level hash index, then gets the linked-list by searching head list of WITs, and inserts item-set to the linked-list. Algorithm 2 GetFITr: Updating of FITr Input: FITr, WITs, THL, Supmin Output: Incremental updated FITr

An Efficient Algorithm for Distributed Incremental Updating of Frequent Item-Sets

67

Method: (1) While(traveling FITr){ (2) get item-set A from FITr; (3) InsertSI(A, WITs);} (4) FITr= ∅ ; (5) while(there exist unprocessed linked-lists in WITs and THL){ (6) wl=GetWL(WITs); (7) nl=GetNL(THL, wl); (8) nl=Merge(wl, nl, FITr); (9) WriteObject(nl);} (10) return FITr; From step 1 to 3, algorithm GetFITr travels FITr. Then inserts all item-sets stored in FITr to WITs. Function InsertSI(A, WITs) inserts item-set A to a linked-list in WITs. Function GetWL (WITs) gets an unprocessed linked-list in WITs, denoted as wl. Function GetNL (THL, wl) gets a linked-list of THL stored in disk, denoted as nl, which has same class-name with wl. Function Merge(wl, nl, FITr) merges wl to nl. Nodes having same itNum in both nl and wl sum up count of nodes. Then those nodes, whose counts are not less than Supmin, are inserted into a new FITr and deleted from nl. In step 9, stores nl to disk and free nl and wl from main memory. Lemma 1. Assume that a new FITr and a new THL can be derived after running algorithm GetFITr. There exists no same item-set in both the FITr and the THL, and the count of item-set is correct. Proof. i: The two-level hash index ensures that an item-set will be given a unique class-name. Therefore, it is impossible that an item-set may emerge on two linked-lists with different class-name in either THL or WITs. ii: Operation of inserting the item-set to linked-list ensures count of node in linked-list to be added when inserts same item-set to a linked-list. iii: According i and ii, the count of item-set may be added correctly when the item-set emerge in both THL and WITs because all same item-sets will be inserted into same linked-list in merging operation of Algorithm 2. iv: There will not be item-sets emerging in both FITr and THL after running algorithm 2 because an item-set will be inserted into FITr or THL by being or not being frequent. Lemma 1 means that algorithm GetFITr can create a new FITr that is incrementally updated correctly. 4.4 Algorithm of Frequent Item-Set Incremental Updating To find frequent item-sets under new support threshold Sup (Sup>Supmin), first step is to read FITr from disk. Then travels FITr to find item-sets whose support count is not less than Sup × |U|. Algorithm 3 is used to find frequent item-sets when database was updated and support threshold was changed. Algorithm 3 FIIU: Incremental updating of Frequent Item-sets Input: db Output: FITr, THL

68

J. Qiu et al.

Method: (1) WITs=General_FI(db); (2) FITr=ReadFIT(); // FITr is gotten from disk. (3) FITr=GetFITr(FITr, WITs, THL); In first step of algorithm 3, all item-sets of db are found, and then are inserted to WITs. General_FI is a general algorithm that mines frequent item-sets in dataset, such as Apriori[2] and FP-growth[5]. Step 3 uses algorithm 2 to generate the new FITr, which store all frequent item-sets of updated database. Lemma 2. Given Interesting Support threshold Supmin , database DB and new dataset db. A complete collection of frequent item-sets may be derived by algorithm FIIU. Proof. i: Complete collection of item-sets of db can be derived by using general frequent item-sets mining algorithm. ii: Because of THL and FITr storing all item-sets of DB, the new FITr and THL derived after running FIIU will include all frequent item-sets, according to i and Lemma 1.

5 FP-Tree Based Distributed Incremental Updating of Frequent Item-Sets Experiment in section 6 will show that time cost of FIIU increases dramatically when the number of items in dataset increases. As all known, building distributed systems is a good method to improve performance. Because of FP-tree and algorithm 2 being suitable for distributed architecture, we propose an algorithm DFIIU, based on FIIU and FP-tree, to incrementally mine frequent item-sets on multiple computers at the same time. FP-growth algorithm mines frequent item-sets on FP-tree as follows. First, build a head item table. Then, construct the condition FP-tree of each item in head item table and perform mining recursively on such a tree. Motivated by FP-growth, it should be feasible to hand out works of constructing condition FP-tree of each item and mining frequent item-sets on such a tree to different computers in a distributed system. Let NCi be No.i computer in the distributed system. Assume that there are k NC in the distributed system. The distributed incremental mining of frequent item-set proceeds as follows. First, one NC, called server, builds FP-tree of new dataset db and divides items in the head item table of the FP-tree to k parts. Then the server sends the FP-tree and the divide to other NC. NCi build conditional pattern trees of No.i part of items and mining frequent item-sets on such these trees. Item-sets derived from NCi are stored in WITsi . NCi divides all linked-lists in WITs to k parts, WITs(1),…., WITs(k). After merging No.i part of linked-lists in other computers (WITs1 (i), …, WITsk (i)), NCi reads FITr stored on server’s disk, and then searches frequent item-sets belonged to No.i part of linked-lists from FITr and inserts them to WITs(i). NCi reads No.i part of linked-lists in THL, THL(i), which is stored in server’s disk. After running algorithm GetFITr, The FITri may be built. Finally, server merges frequent item tree form FITr1 to FITrk, and a new FITr is derived.

An Efficient Algorithm for Distributed Incremental Updating of Frequent Item-Sets

69

Algorithm DFIIU includes client algorithm DFIIU-C and server algorithm DFIIU-S. Algorithm 4 DFIIT-C Input: fp-tree, item, class Symbol: Let itemi be an array save No.i part of items, class be an array record which part of WITs each linked-list belongs to; there are k computers in distributed system. Output: FITr Method: (1) IS=FP-Growth(itemi, fp-tree); (2) for each Item-set A in IS, InsertSI(A, WITsi); (3) Divide(class, WITsi); // divide WITsi to k parts according class (4) for(int j=0; j
6 Experiment and Performance Analysis 6.1 Test Environment and Test Datasets In this section, we evaluate FIIU and DFIIU in comparison with FP-growth. The three algorithms were implemented in java. Experiments were performed on a Intel C3 1.0G

70

J. Qiu et al.

PC with 512M main memory, running Windows 2000 sever and SQL Server 2000. There are two computers in the distributed system. Let total be the number of transactions, d be the number of new transactions. In the experiment, run time of FIIU and DFIIU were compared with run time of FP-growth when support threshold is Supmin and the number of transactions is total+d. In the experiment, Supmin is 0.1%. We use synthetic dataset in the experiment because real datasets are not enough large for the experiment. In addition, we will illustrate that experimental conclusion has nothing to do with datasets in section 6.2.The synthetic datasets were generated from algorithm 6. Algorithm 6 generating test datasets Input: Num is the number of items in dataset, Total is the number of transactions; Len is length of longest transaction in dataset. Output: dataset D Method: (1)I=CreateItems(Num); //build collection of items (2)For(int i=0;i
An Efficient Algorithm for Distributed Incremental Updating of Frequent Item-Sets

71

DFIIU may further reduces the time cost because it hands out parts of mining work to others computer in distributed system although I/O cost counteract some of effects, which is proved in the test 1, 2, 3. 6.3 Experiment Results In the test, we use N, L, T and d denotes Num, Len, Total and |db| respectively. In test 1, as shown in Fig.4, N=15, L=10, d=5k. We report experimental results on 8 different sizes of dataset. It can be observed that performance of DFIIU and FIIU is better than FP-growth When T>200K and T>350K respectively, and average time of DFIIU is less than FIIU. In test 2, as shown in Fig.5, N=17, L=17, d=10k. Experiments were performed on 5 different sizes of datasets. Performance of DFIIU and FIIU is better than FP-growth When T>700K and T>1200K respectively, In test 3, as shown in Fig.6, N=19, L=19, d=10k, experiments were performed on 6 different size of datasets. Performance of DFIIU and FIIU is better than FP-growth When T>800K and T>1.3M respectively.

 5XQ7LPH6

5XQWLPH6



 

),,8 '),,8



)3*URZWK

        

        

),,8

'),,8

)3*URZWK



'DWD6HW.



Fig. 5. N=17 L=17 d=10k



),,8'

)3*URZWK'



),,8'

)3*URZWK'





 

),,8



'),,8



)3*URZWK

5XQWLPH6

5XQ7LPH6

Fig. 4. N=15 L=10 d=5k

   'DWD6HW.



   











'DWD6HW.

Fig. 6. N=19 L=19 d=10k





   6XSSRUW



Fig.7. N=17 L=17

Fig.7 shows experiment result about first problem of incremental updating on two datasets. In first one, denotes as D1, N=17, L=17, T=100K. In D2, N=17, L=17,

72

J. Qiu et al.

T=200K. Time cost of FIIU was compared with FP-Growth on five different support thresholds. We can observe from Fig.7 that time cost of FIIU keep unchanged and that of FP-Growth increase when size of dataset increase. For each dataset, average time cost of FP-Growth is larger than FIIU on five thresholds. FIIU have obvious advantages on solving first problem of incremental updating than FP-Growth.

7 Conclusions In this paper, we have proposed efficient method for three problems of incremental updating of frequent item-sets. Experiments also have proved that FIIU and DFIIU have better performance than FP-Growth (or other size sensitive incremental updating algorithms) when size of datasets is large. Especially, FIIU has a great advantage on first problem of incremental updating. However, we must indicate that finding all item-sets, which FIIU and DFIIU based on, is a NP hard problem. It may be an impossible task to mine all item-sets when the number of items on dataset is great. Therefore, for second and third problem of incremental problems, FIIU and DFIIU can show better performance when the number of items on dataset is less.

References 1. R.Agrawal,T.Imielinski,and A.Swami. Mining assciation rules between sets of items in large database[A]. the ACM SIGMOD. Washington, 1993. 2. R.Agrawal and R.Srikant.Fast algorithms for mining association rules[A].In:Proc. the 20 th International Conference on VLDB Santago,1994.487-499. 3. J.S.Park, et al. An efficient hash-based algorithm for mining association rules[A]. In Proc.1995 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’95), San Jose, CA. 4. A. Savasere, et al. An efficient algorithm for mining association rules in large databases [A]. In Proc. 1995 Int. Conf. Very Large Data Bases (VLDB’95), Zurich, Switzerland. 5. Han, J., Pei, J., and Yin, Y. 2000. Mining frequent patterns without candidate generation [A]. In Proc. 2000 ACMSIGMOD Int. Conf. Management of Data (SIGMOD’00). 6. W. Cheung and O. R. Zaiane. Incremental Mining of Frequent Patterns Without Candidate Generation or Support Constraint[A]. In Proc. IDEAS 2003, Hong Kong. 7. Zhu Y.,Sun Z.,Ji X.. Incremental Updating Algorithm Based on Frequent Pattern Tree fof Mining Association Rules[J].Chinease Journal of Computers,2003,26(1):91-96. 8. Xiu-Li Ma,Yun-Hai Tong.Efficient Incremental Maintence of Frequent Patterns with FP-Tree[J].J.computer Science and Technology,2004,19(6),876-884. 9. R.Agrawal, and J.C.Shafer[A]. Parallel mining of association rules.IEEE Transaction on Knowledge and Data Engineering,1996,8(6),962-969. 10. E.H.Han, G.Karypis, and V.Kumar.Scalable parallel data minig for association rules[A].In Proc. ACM SIGMOD International Conference on Management of Data(SIGMOD’97). 11. Zhang Z.G. Study of Data Mining Algorithms on Massive Data[D].Harbin:Harbin Institute of Technology,2003. 12. S. Brin, R. Motwani, and C. Silverstein. Generalizing association rules to correlations[A]. In Proc. of the ACM SIGMOD Int'l Conf. on Management of Data (ACM SIGMOD '97).

Mining Maximum Frequent Access Patterns in Web Logs Based on Unique Labeled Tree Ling Zhang, Jian-ping Yin, and Yu-bin Zhan School of Computer, National University of Defense Technology, Changsha, Hunan, 410073, China [email protected]

Abstract. Discovering user’s Frequent Access Patterns is one of research hotspots in mining web logs. A novel apriori-based algorithm named s-Tree is proposed for mining maximum Frequent Access Patterns. The main contributions of s-Tree algorithm are the following. Firstly, a unique labeled tree is used to represent user session, which enables us to mine the maximum forward reference transaction and the users’ preferred access path. Secondly, an improved method of calculating support based on impact factor of content pages first, which helps us to discover some more important and interesting patterns than normal methods. Thirdly, two special strategies are adopted to reduce overheads of joining frequent patterns. Finally, experiments show that s-Tree algorithm is scalable, and is more efficient than previous graph-based structure pattern mining algorithms such as AGM and FSG.

1 Introduction The Web can be seen as the largest database and is a great challenge for data mining. Mining can be performed on the content, structure or logs of the Web. Mining Web logs, which is called Web usage mining[3,4,10] and has the vital significance in the field of new developing e-commerce, could find potential users, offer personal services to customer, and improve the performance and structure of the website by discovering the customer's access patterns. In Web logs, a Web server registers the IP address from which the request originates, the URL requested, the date and time of access, the page reference and the size of the requested data in each entry. To be analyzed Web log records are divided into user sessions. A user session is a set of page references of one source site during one logical period. Practically a session can be seen as a user starting visiting a Web site, performing work, and then leaving the Web sites. There are two main representations of user sessions at present. One is to use a set of pages visited by user in a session[2,5,8]. The advantage of this representation is that the mining algorithm is simple and intuitionistic, and all mining algorithms about normal transaction and frequent itemed which based on apriori[1] or FP-Growth[5] can be applied to it. However, this representation has neglected the visited order of visited pages, which will be a serious deficiency in respect to the purpose of predicting users’ visit behavior and websites’ periodic visit behavior through mining web logs. The other is to regard user session as a page sequence according to visited order. This representation records the visited order of visited pages. But it doesn’t take into L. Feng et al. (Eds.): WISE 2006 Workshops, LNCS 4256, pp. 73 – 82, 2006. © Springer-Verlag Berlin Heidelberg 2006

74

L. Zhang, J.-p. Yin, and Y.-b. Zhan

account the website topology structure. And multi-window browsers enable users to view many web pages simultaneously, whose visited order is unimportant and uninteresting, and so it is meaningless to sequence these visited pages. Therefore we propose a new representation of user session-unique labeled tree to solve the problems of the above two kinds of representations of user session. Normal algorithms for mining web logs adopt definition of support in definition 1 in Section 3[3,8,9]. This definition considers equally important every visited page. But actually functions and users’ interest of content page, navigation page and search page are different. Therefore some important and interested patterns cannot be discovered. In order to conquer the limitation of this definition, this paper defines the impact factor of content pages on support of pattern and proposes a new method to calculate support of pattern. Based on the unique labeled tree representation of user session, a novel algorithm named s-Tree is proposed to mine the maximum frequent patterns. It adopts a new method of calculating support of pattern. S-Tree algorithm improves two aspects of apriori algorithm: generating candidates by joining frequent patterns and frequent edges and reducing overhead by pre-pruning. Our experiments show that s-Tree algorithm is scalable, and is more efficient than previous graph-based structure pattern mining algorithm such as AGM[6],FSG[7],AGMG, and FSG[11]. The paper is organized as follows: in section 2, we propose the unique labeled tree representation of user sessions; then we analyze characteristics of interesting access patterns, define impact factor of content pages on support of pattern and propose a new method of calculating support of pattern in section 3; in section 4 we introduce sTree algorithm; in section 5 we conduct experiments and analyze the result of experiments; finally, we have a conclusion and point out our future research direction.

2 Representing User Session by Unique Labeled Tree Large amount of web logs data generated daily in Web servers are important data source for us to study the users’ visiting behaviors and interest. The data should be preprocessed because that they cannot be applicable directly to web mining. The procedure of normal preprocess can be divided into four steps [3,12]: data cleaning; user identification; session identification; path completion. After preprocess user sessions may be represented by sets or visited page sequence. However, the above two representations are unable to depict some user’s visiting behaviors. Users log in a website by clicking the hyperlink or typing the URL, then regard the page as a root and view other pages simultaneously by hyperlinks in the current page. Those pages’ visited order is unimportant and uninteresting. Users again can click the hyperlinks in those pages to visit other pages. Thus the visit procedure forms a tree, and it is actually one "width-first" traversal tree. Meanwhile we don’t care only the visited order of pages but also the hyperlinks by which the pages are visited, i.e., the users’ traversal path. So a labeled tree[13] is introduced to represent user session, which can not only depict the users’ visiting behavior but also describe the visit sequence of the pages and the users’ traversal path. However, in a user session users may visit one page several times and so there are a few nodes having the same label because of several times visit to a same page. This will make it hard to

Mining Maximum Frequent Access Patterns in Web Logs

75

distinguish isomorphism of sub-tree. We suppose that only the first visit to that page is normal and meaning. So we only consider the first visit to web pages, and then there are no nodes of a tree having the same label. We call it a unique labeled tree. In a session we neglect the second and deeper visit to the same page and take the successor of them as successor of the first visit instead. Take Fig.1 as an example where page C is visited twice, and H-I is the successor of the second visit. Thus we get Fig.2 by taking H-I as the successor of the first visit of page C. In this section, we use a unique labeled tree to represent user session. In Fig.2, the user session represented by the unique labeled tree is just the same as the one in the Fig. 1.

Fig. 1. The labeled tree representation of user session

Fig. 2. The unique labeled tree representation of user session

Definition 1 (unique labeled tree). Given a tree T , the node set N of the tree, a label set L, T is a unique labeled tree iff there exists a injection f : N → L , that v ∈ N , f ( v ) = l ∈ L . And the f ( v ) is called the node v ’s label. A unique labeled tree of user session is called session tree. The label of nodes represents web pages and edges represent hyperlinks. For example in Fig.1, path A-B-G, A-C-H-I, and A-D are three visited page sequences. On each path a child page node is visited using hyperlink on its parent page node. The visited order of some pages such as B, C, and D are uninterested, and yet the entry hyperlinks linking to them, which form the user’s traversal path, are important. Since the user session is represented by the unique labeled tree, the Frequent Access Patterns can be defined as following. Definition 2(Frequent Access Pattern). Let T = {T1 ,T2 ,",Tm } be database of session trees. S which is unique labeled tree is called a pattern, the support of S is defined by the formula sup(S)=

|{Ti |S ⊂Ti }| . Given the minimum support threshold min-sup, if |T |

sup(S)≥min-sup, then S is a frequent access pattern. S is called a Maximum Frequent Access Pattern, if there is no frequent access pattern S* satisfied that S⊂S*. Given the database of session trees and a user specified minimum support threshold, the problem we want to solve is to find all Frequent Access Patterns. According to Def. 2, the Frequent Access Patterns in s-Tree algorithm is represented by a unique labeled tree. It has two advantages as follows: (1)it is easy to identify a Maximum Forward Referenced transaction, which is simply a path from the root to a leaf node of a session tree; (2)it is easy to discover users’ preferred traversal paths. In every

76

L. Zhang, J.-p. Yin, and Y.-b. Zhan

pattern discovered, every path from the root to a leaf node is users’ preferred traversal path, which cannot be discovered in mining algorithms based on the set representation of user session. And algorithms based on sequence of visited pages can discover the frequent access sequence, but can not discover the traversal path based on the website topological structure.

3 An Improved Method of Calculating Support Based on Impact Factor of Content Pages There are lots of web pages, which contain many different topics information on a website. In order to facilitate users of different goals and interests to browse over the website these web pages are organized hierarchically according to subjects. Based on a hierarchy and functions of them web pages can be broadly divided into four classes: 1. Homepage - a page whose purpose is to be the first page that users visit. 2. Content Page - a page that contains a portion of the information content that the Web site is providing. 3. Navigation Page - a page whose purpose is to provide links to guide users on to content pages. 4. Look-up Page - a page used to provide a definition or acronym expansion. Homepage and navigation pages are visited most frequently , however, some content pages which user are really interested in are in the deep level of the website and not visited so frequently. So we concentrate on user’s visiting content pages and discovering association rules of content pages. These association rules become the basis of how to recommend interesting web pages to users. In order to mine the patterns which contain more content pages we should reduce their minimum support threshold or increase their support weight according to the number of content pages. This paper uses the latter method and qualifies content pages’ impaction on the support of patterns with impaction factor. Definition 3 (impact factor). Given a pattern T, let n be the total number of pages in T, and m be the number of content pages, then content pages’ impact factor δ to the

support of the pattern is 1−e− m n . So in our s-Tree algorithm we consider the content pages’ impact factor, and given a pattern T and the content page’s impact factor δ , then the pattern T’s support is sup (T )= supinit (T )⋅(1+δ ) , in this formula supinit (T ) is calculated as the way defined in definition 1.

4 s-Trees Algorithm s-Tree algorithm based on Apriori employs an iterative approach known as a levelwise search, where frequent k-trees(tree with k edges) and frequent edges are used to explore frequent (k+1)-patterns. There are two input parameters in s-Tree algorithm: the database D of session trees from the web logs and the minimum support threshold min-sup.

Mining Maximum Frequent Access Patterns in Web Logs

77

The pseudo-code for the s-Tree algorithm is as follows: Algorithm 1 s-Tree algorithm (D,min-sup) Input: the database D of session trees; the minimum support threshold min-sup. Output: the set of maximum frequent access patterns S. 1. Scan the database D, find set of the frequent edges Edge. 2. Scan the database D again, and prepruning operation is performed on every session tree in the database D, then get the new database D′ 3. i←1;F1← Edge;S←∅. 4. While (Fi ≠ ∅)

5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.

Do{Ci+1= Generation(Fi) // join and generate candidate frequent tree. If Ci+1= ∅, return S. For each candidate ti+1∈Ci+1

{ ti+1.Count←0 {for each T∈D′ if (sub-tree(ti+1,T)) //judge whether the ti+1 is a sub-tree of T. ti+1.Count ++} Fi+1←{ti+1∈ Ci+1|sup(ti+1) ≥ min- sup}} delete the patterns in S that are contained in a pattern that in Fi+1 S←S ∪ Fi+1 i←i+1} Return S

We don’t adopt the strategy of joining two frequent patterns in join step because judging whether two frequent patterns are joinable is a time-consuming operation. We generate candidates by adding a frequent edge to frequent pattern tree instead. At first the algorithm scans the database D and finds all frequent edges. Then it scans database D again, and prepruning is performed on the session trees. For each session tree in D, we remove the non-frequent edge and the child node from the tree if it has nonfrequent edges. And if the children node has children, we will take them as new children of the non-frequent edge’s father node, and no other change need to be done. Let’s take the session tree in the Fig.2 as an example, if edge (C,H) is non-frequent, then the algorithm gets rid of the edge (C,H) and the child node H, and the child of H is taken as the new child of node C, i.e., we adds an edge (C,I) to the tree. After pruning, the session is converted into session tree in Fig.3 and meanwhile the size of database is reduced significantly and this will not change the mining result. Finally, Edge is regarded as the set of frequent 1-patterns, denoted as F1, and it joined with itself is used to generate the candidate set C2, which after the pruning and deleting nonfrequent patterns is the F2, which is joined with Edge to find the C3, which after the pruning and deleting non-frequent patterns is F3 and so on, until no more frequent patterns with k edges can be found. In the join step, we generate candidate set Ci+1 by adding corresponding frequent edges to the frequent patterns in Fi. Generation of candidates is almost all overheads

78

L. Zhang, J.-p. Yin, and Y.-b. Zhan

of the algorithms based on apriori. In s-Tree algorithm, we adopt two strategies to reduce overheads of generation of candidate set. Firstly, the algorithm chooses an edge from Edge adding to the tree only at the nodes at level m-1 or m if the level of the pattern tree is m. For example in the Fig. 3, the algorithm adds an edge only at the nodes B,C, and D with the level number 2 and the nodes G,H with the level number 3. Let tn be a frequent n-tree, its level is m(m≥2) if tn+1 is a frequent n+1-tree generated by adding a frequent edge to it in the level neither m-1 nor m. So the tn+1’s level is also m. According to apriori property, it still be a frequent tree noted as tn* after tn+1 is gotten rid of an edge which links the nodes with the level m and m-1. So the level of tn* is m or m-1, and then the pattern tree tn+1 can be generated by adding the edge A to frequent pattern tn*. Therefore the algorithm doesn’t lose any frequent patterns. Thus the number of candidates and overheads of algorithm are reduced significantly by adding a frequent edge which chooses from the frequent edge set to the frequent patterns. Secondly, children of nodes in session tree are sorted in alphabetical order, so the algorithm adds frequent edges only at the nodes in the same level with and behind the father node of the right-bottom most edge or the nodes at the same level with the child node of that edge. For example in the Fig.3, arc(C,I) is the right-bottom most edge, so algorithm adds edges only at the node B, D, G and I which are labeled by a arrowhead. This doesn’t lose any frequent patterns, but can reduce the number of the candidate trees and the overhead of algorithm significantly.

Fig. 3. Illustrations of the incremental edges position

After generation of candidate set, s-Tree algorithm then deletes candidate patterns from candidate set that can not be frequent. In the prune step, the Apriori property is used as follows. For each candidate tree, the candidate is not frequent if any sub-tree of it is not frequent and so can be removed from the candidate set. Suppose that ci+1 is generated by adding a frequent edge A to the frequent tree tn. The algorithm verifies only the sub-trees which contain the edge A of ci+1 because all sub-tree of tn is frequent. ci+1 will be removed from the candidate if any one of them is not. Each candidate in Ci is frequent only if its support satisfies the user-specified minimum support threshold. In the procedure of calculating support, we first find out all the session trees with more than i edges. All candidates in Ci are not frequent if the number of all the sessions is less than min-sup·|D| and now the algorithm exits. Otherwise, the algorithm should judge a given candidate in Ci whether it is a sub-tree of a given session tree. After calculating the support of each candidate, we can find all

Mining Maximum Frequent Access Patterns in Web Logs

79

the frequent patterns in Fi+1.In algorithm 1 we use Boolean function sub-tree(ti+1,T) to describe this procedure. The pseudo-code for the function sub-tree(t,T) is as follows: Algorithm 2 sub-tree(t,T) function: it will output TRUE if tree t is a sub-tree of T, else it will output FALSE. parameter: the input argument t and T are trees, also they are the root nodes of the tree respectively. The symbol children(T) denote the set of T’s children nodes and the f(v) is the node v ’s label. { if f(t)=f(T) return Yessub-tree(t,T); else return Nosub-tree(t,T).} Nosub-tree(t,T) Yessub-tree(t,T) {if (∃M∈children(T), {if children(t)⊄ children(T) such that f(M)= f(t) ) return FALSE; return Yessub-tree(t,M); else {if children(t)=∅ return True; else if(children(T)= ∅) else for each m∈children(t) return FALSE; {find M∈ children(T) else {for each M∈children(T) such that f(m)=f(M); if (Nosub-tree(t,M)) if(!Yessub-tree(m,M)) return Nosub-tree(t,M); return FALSE} return FALSE; }} return TRUE;} } Distinguishing isomorphism of sub-tree is much time-consuming. But in algorithm 2, the time cost is o( n + N ) in the worst case ( n and N is the number of nodes of tree t and T respectively). Thus using the unique label tree to represent the user session improves significantly the efficiency of s-Tree algorithm and then makes it more efficient than AGM and FSG algorithm. This is the reason why we use a unique labeled tree but not labeled tree or label unordered tree[14] to represent the user session.

5 Experiment Results In this section we show the performance of s-Tree algorithm with experiments. The algorithm is implemented in c++ standard library and conducted using a machine with Intel Celeron 2.4GHz CPU, 256MB RAM, and XP OS. Test data set BMSWebView-1 and BMS-WebView-2 were downloaded from the homepage of KDDCUP 2000 (www.ecn.purdue.edu\KDDCUP). They contain several-months of click stream E-commerce data from several months. User sessions must be represented by unique labeled trees before experiments. Table 1 is a comparison between two test data sets using size, number of transactions, total occurrences of items, number of distinct items, maximal transaction size, and average transaction size. In experiments as follows the run time includes reading, computation and outputting the results to the disk.

80

L. Zhang, J.-p. Yin, and Y.-b. Zhan

5.1 Scalable Experiments We do scalable experiments on several session sets selected from above two datasets (the minimum support threshold is 0.3% on BMS-WebView-1 and 0.33% on BMSWebView-2). Fig.4 shows the relation between Run time and No. of sessions. The experiments show that s-Tree algorithm is scalable and more efficient than previous graph-based structure pattern mining algorithms such as AGM and FSG. Table 1. Characteristics of datasets Dataset

size

No. of Sess

BMS-WebView-1

2.07M

59602

497

267

2.51

BMS-WebView-2

5.01M

77512

3308

161

4.62

30 25 )20 s ( e15 m i t10 n5 u R 0

Total No. of page

Max No. of Sess.

Avg. Sess.size

BMS-WebView-1 BMS-WebView-2

1

1.5 2.5 3.5 4.5 5.5 No of sessions(×10000)

6

7.5

Fig. 4. Run time vs No. of sessions

5.2 Analysis of Run Time We conduct experiments on above two datasets respectively with different thresholds. For BMS-WebView-1, the run time decreases most sharply when the threshold is near to 0.3%, As Fig.5 show the run time is 113.1 seconds when the threshold is 0.24% and decreases sharply to 2.12 seconds when the threshold is 0.35%. The reason is that the number of frequent patterns decreases sharply at this threshold, and for BMSWebView-2, the run time decreases most sharply when the threshold is 0.35% )300 s250 ( e m200 i t150 n u100 R 50 0

BMS-WebView-1 BMS-WebView-2

0.2 0.24 0.29 0.35 0.4 Threshold（%） a.Run time vs Threshold

BMS-WebView-1 BMS-WebView-2

3.5 ) 3 s (2.5 e m 2 i t1.5 n 1 u R0.5 0

0.7 0.9 3 8 10 15 Threshold（%） b.Run time vs Threshold

Fig. 5. The relation between Run time and Threshold

Mining Maximum Frequent Access Patterns in Web Logs

81

5.3 Comparison of Mining Results S-Tree can mine some more frequent patterns ignored by normal algorithms because we increase the weight of important and interesting patterns containing more content pages. Table 2 compares the mining results of s-Tree algorithm with normal algorithms when the threshold is 0.3% on BMS-WebView-1. From the comparison, we conclude that our algorithm can discover more frequent patterns than normal algorithms. Table 2. Comparison of result of s-Tree algorithm and normal algorithm No of pattern

6

7

8

(8,10]

(10,20]

(20, ∞ )

Normal algrithms

8

5

5

4

0

0

s-Tree algorithm

13

7

9

7

2

0

6 Conclusion This paper proposes a unique labeled tree to represent user session. It conquers the limitation of the exiting representations and makes the frequent patterns to contain more useful information such as traversal path. A new improved method of calculating support is proposed in terms of four types of web pages. It can discover some more important and interesting patterns ignored by normal algorithms. S-Tree algorithm generates candidates by joining the frequent edges with the frequent patterns and reduces the overhead. However it is some rough to calculate the support and the interest of the patterns is hard to depict in s-Tree algorithm. In the future we will concentrate on how to quantify the impact of content page on the support of pattern more rationally and effectively.

References 1. Agrawal, Srikant.Fast algorithms for mining association rules in large database[C].VLDB1994,Santiago, Chile,1994.pp.487-499. 2. Pei, J., Han, J., et al.. Mining access patterns efficiently from Web logs[C]. PAKDD’00 ,Kyoto, Japan2000. 3. Srivastava, J., Cooley, R., et al. Web usage mining: Discovery and applications of usage patterns from Web data[J]. SIGKDD Explorations, 2000. Vol. 1. 4. R.Kosala,H.Blockeel. Web mining research: a survey[J]. In ACM SIGKDD Explorations, 2000. 5. J.Han,J.Pei,Y.Yin. Mining frequent patterns without candidate generation[C]. In SIGMOD 2000, 2000. 6. Inokuchi, T. Washio, H. Motoda. An apriori-based algorithm for mining frequent substructures from graph data[C].PKDD2000, Lyon, France, 2000. 7. M. Kuramochi and G. Karypis. Frequent subgraph discovery[C]. ICDM2001,San Jose,USA,2001.

82

L. Zhang, J.-p. Yin, and Y.-b. Zhan

8. Liping Sun ,Xiuzhen Zhang. Efficient Frequent Pattern Mining on Web Logs[C]. APWeb 2004. pp. 533-542. 9. Ezeife,Yi Lu. Mining Web Log Sequential Patterns with Position Coded Pre-Order Linked WAP-Tree[J]. Data Mining and Knowledge Discovery. 2005, 10, 5-38. 10. Han Jiawei,Meng Xiaofeng,Wang Jing, Li Shengen. Research on Web Ming: a Survey[J]. Journal of computer research & development. 2001,38(4):405-413. 11. Wang Wei, Zhou Haofeng,Yuan Qingqing,et al.. Mining Frequent Pattern Based Graph Theory[J]. Journal of computer research & develop-ment. 2005,38(4):230-235. 12. Robert Cooley. Bamshad Mobasher, et al. Data Preparation for Mining World Wide Web Browsing Patterns[J]. Knowledge and Information System.Vol.NO,1.1999 page 5-23. 13. Chen Wang, Mingsheng Hong, Wei Wang, et al.. Chopper: Efficient Algorithm for Tree Mining. Journal of computer science and technology[J]. 2004, Vol 19(4): 309-319. 14. Yun Chi, Yi Xia, Yirong Yang,and Richard R. Muntz. Mining Closed and Maximal Frequent Subtrees from Databases of Labeled Rooted Trees. IEEE Transactions on Knowledge and Data Engineering[J] 2005 27(2):190-202.

Short Documents Clustering in Very Large Text Databases* Yongheng Wang1, Yan Jia2, and Shuqiang Yang3 Computer School, National University of Defense Technology, Changsha, China 1 [email protected] 2 [email protected] 3 [email protected]

Abstract. With the rapid development of the internet and communication technology, huge data is accumulated. Short text such as paper abstract and email is common in such data. It is useful to cluster such short documents to get the data structure or to help build other data mining applications. But almost all the current clustering algorithms become very inefficient or even unusable when handle very large (hundreds of GB) and high-dimensional text data. It is also difficult to get acceptable clustering accuracy since key words appear only few times in short documents. In this paper, we propose a frequent term based parallel clustering algorithm which can be used to cluster short documents in very large text database. A novel semantic classification method is also used to improve the accuracy of clustering. Our experimental study shows that our algorithm is more accurate and efficient than other clustering algorithms when clustering large scale short documents. Furthermore, our algorithm has good scalability and can be used to process even huge data.

1 Introduction With the rapid development of the internet and communication technology, huge data is accumulated in many companies or organizations, most of which is text data. A vast amount of important scientific data and business data appears as documents. Many of such documents are short documents having no more than 50-100 words. For example, abstract of papers, most of the e-mails, conversations in chat room, etc. It is useful to cluster such short documents to get the data structure or to help building other data mining applications. In this paper, we provide the following task: clustering short documents in very large text databases efficiently and accurately. Document clustering has been studied intensively because of its wide applicability in areas such as web mining, search engines, information retrieval, and topological analysis. There are a large number of clustering algorithms that can be used in document clustering. J. Han and M. Kamber [1] categorized the major clustering methods into hierarchical methods, partition methods, density based methods, grid based methods and model based methods. Some clustering algorithms integrate the *

This project is sponsored by national 863 high technology development foundation (No.2004AA112020, No.2003AA115210 and No.2003AA111020).

L. Feng et al. (Eds.): WISE 2006 Workshops, LNCS 4256, pp. 83 – 93, 2006. © Springer-Verlag Berlin Heidelberg 2006

84

Y. Wang, Y. Jia, and S. Yang

ideas of several clustering methods. A recent study shows that a variant of k-means called bisecting k-means algorithm outperforms other algorithms in text clustering. When being used to cluster short documents in very large text databases, traditional clustering methods mainly encounter the following new challenges: (1) Text data is usually high dimensional and sparse. (2) Text databases can be very large. Some of the text databases contain more than 100 TB of documents. Most efficient clustering algorithms become inefficient or even unusable when the dataset is very large. (3) Getting understandable description of the clusters is difficult using common clustering methods. (4) It is difficult to get acceptable precision when clustering short documents with common methods based on vector space model since the key words appear several times or just one time in short documents. Frequent term-based text clustering [2,3] can be used to solve the problem 1 and 3. Problem 2 can be solved by using parallel clustering algorithms [4] or disk-based algorithms instead of memory-based algorithms. In order to improve the precision of document clustering, other methods such as semantic information based text clustering [5, 6] are developed. Based on the observation above, in this paper we propose a new algorithm named SDC (Short Documents Clustering) to cluster short documents in very large text databases. We make the following contributions in this paper. z

z

z

We use a novel semantic classification based method to eliminate clusters overlapping which is accurate for short document. The method is also efficient than other common semantic classification method for short documents. We take advantage of the function of text database to improve the performance. Logical data partition and text indexes are used in our algorithm which is efficient to process very large text data set. We develop a parallel clustering algorithm that has good scalability for very large text databases.

The remainder of this paper is organized as follows. In section 2, we give a general review of current related works, including frequent-term based clustering and semantic-based clustering. In section 3, we introduce the SDC algorithm. In section 4, we introduce our experiments on large and very large data sets. Then a discussion and conclusion is presented in section 5.

2 Related Work Frequent term based text clustering is a recently introduced text clustering method using frequent term sets, which are sets of terms co-occurring in more than a threshold percentage of all documents of a database [2] and can be efficiently discovered by algorithms of association rule mining, such as Apriori. The frequent term-based text clustering is based on the following ideas: (1) Frequent terms carry more information about the “cluster” they might belong to; (2) Highly co-related frequent terms probably belong to the same cluster. The FTC algorithm is a frequent term based text clustering algorithm developed by F. Beil [2]. FTC greedily picks up the next frequent term set (representing the next cluster) to minimize the overlapping of the documents that contain both the term set

Short Documents Clustering in Very Large Text Databases

85

and some remaining term sets. The clustering result depends on the order of picking up term sets, which in turn depends on the greedy heuristic used. FIHC is another frequent term-based text clustering approach developed by Benjamin [3]. There are two steps in FIHC. In the first step, for each frequent term set, an initial cluster is constructed to contain all the documents that contain this term set. Initial clusters are overlapped because one document may contain several frequent term sets. In the second step, overlapping between clusters is eliminated. A score function is defined to measure the goodness of a cluster for a document. The quality of the clusters detected by FIHC greatly depends on the score function which is not easy to define for short documents. And the score function is not easy to be calculated efficiently in very large text databases. The work of this paper is based on [3] but we provide parallel algorithm and use a semantic classification method to improve the accuracy. Traditional clustering methods treat document as a bag of words and don’t consider the semantic relationship between the words which reduce the quality of clustering. This is more important for short document since key words appear less times in short documents. Recently, some clustering approaches based on semantic information are developed to improve the clustering quality. Hotho [5] introduced an ontology based text clustering method named COSA. COSA uses a simple, core ontology for restricting the set of relevant document features and for automatically proposing good aggregations. B. Choudhary [6] used a new method for the creation of document vectors in his text clustering method. This approach uses the Universal Networking Language (UNL) representation of a document. The UNL (explained in detail in [Uchida, Zhu and Della 1995]) represents the document in the form of a semantic graph with universal words as nodes and the semantic relation between them as links. These methods get better clustering quality in some specific area but they depend on the domain ontologies.

3 Method Developments and SDC Algorithm In this section, we first introduce the basic ideas of the SDC algorithm and then provide the algorithm description. 3.1 Basic Clustering Method and Cluster Representation SDC is a frequent term based clustering method. We have developed an efficient algorithm for mining frequent term sets in very large text databases [9]. SDC detects clusters without overlapping. The basic clustering method contains two steps. In the first step, for each frequent term set, an initial cluster is constructed to contain all the documents that contain this term set. In the second step, a novel method based on semantic classification is used to eliminate overlapping of clusters. We take advantage of the function of text database to improve the performance in SDC. Most of the commercial database systems provide text index. For example, Oracle database 10g includes a text database named Oracle Text [8]. Oracle Text indexes documents by converting all words into tokens. The general structure of an Oracle Text index is an inverted index where each token contains the list of documents (rows) that contain that token. In Oracle text, it is efficient to get

86

Y. Wang, Y. Jia, and S. Yang

documents that contain specified words in very large database using SQL statement like the following: SELECT document FROM table WHERE CONTAINS (document, ‘Dog and Cat’) > 0; In a very large text database, a cluster may contain millions of documents. It is not feasible to provide all the documents to user as the result of the clustering. In this paper, we use the frequent term set as the label of the cluster. With the help of text index, we can easily get the documents that contain the frequent term set. But different clusters may be overlapped since one document may belong to more than one cluster. In order to represent the resulting clusters, we defined the document table structure like table 1. Table 1. Document table structure

Document ID Content … …

… …

Cluster ID Cluster Number .. …

If the document belongs to one cluster in the initial clusters, the cluster ID is not needed to be set. If the document belongs to more than one cluster in the initial step, the final cluster ID is filled into the cluster ID column of the document table after the overlapping is eliminated. Then for each cluster Ci labeled with frequent term set Fi, we can get all documents that contain Fi with a “SELECT” statement and then remove the documents that the cluster ID is not equal to Ci. 3.2 Parallel Method for SDC SDC is a parallel frequent term based short document clustering algorithm for very large text databases. It has one controlling node and n mining nodes. We can’t use traditional data partitioning method to support our parallel algorithm because one cluster may span many partitions. We use a logical data partitioning method in which there is no data really moved which is shown in Fig.1. We suppose the controlling node and the mining nodes are all in a cluster (cluster of computers) and the database is available for all nodes. Each mining server processes a part of the data but need not move the data to local machine. When eliminating cluster overlapping, documents in each logical partition can be processed parallel by taking advantage of the function of text database.

databases

logical partition

mining

Fig. 1. Logical partition for parallel processing

Short Documents Clustering in Very Large Text Databases

87

Mainly there are three steps in SDC. In the first step, the controlling node partitions the data logically and sends the frequent term sets to all mining nodes. In the second step, each mining node process all overlapping documents and eliminates the overlapping. In last step, the controlling node gathers local result from all mining node and merge them into global result. In step 2, each mining node first gets the documents in its logical partition that contain more than one frequent term set and then using the method described in 3.3 to decide which cluster it should be in. 3.3 Overlapping Elimination The cluster overlapping elimination method in this paper is based on semantic classification. As described in 3.1, after the first step of the clustering method, we get n clusters but they are overlapped. We consider the overlapping elimination problem as a classification problem: to classify the overlapped short documents into the n categories. We provide a novel kNN like classification method based on semantic text features graph. The semantic text feature graph is based on information inference [7,10]. An information inference mechanism has been proposed which automatically computes information flow through a high dimensional conceptual space. Each concept is represented as a vector of other concepts in the conceptual space. The information flow is a reflection of how strongly Y is informationally contained within X, which discovers the implicit associations between concepts.. Definition 1 (Concept representation in HAL). A concept c is a vector: c = <Wcp1,Wcp2,…,Wcpn> where p1,p2,…pn are called dimensions of c, n is the dimensionality of the HAL space, and Wcpi denotes the weight of pi in the vector representation of c. A dimension is termed a property if its weight is greater than zero. A property pi of a concept c is termed a quality property iff wcpi>∂, where ∂ is a nonzero threshold value. Let QP∂ (c) denote the set of quality properties of concept c. QPμ(c) will be used to denote the set of quality properties above mean value, and QP(c) is short for QP0(c). Definition 2 (HAL-based information flow). HAL-based information flow is defined as: i1,i2,…,ik |- j iff degree( ⊕ ci  cj ) > λ

(1)

Where ci denotes the conceptual representation of token i, and λ is a threshold value. ⊕ci refers to the combination of the HAL vectors c1,…,cK into a single vector representation representing the combined concept.

Wc p ∑ c c

i l

degree( ci  cj ) =

pl∈( QPμ (

i ) ∧ QP (

j ))

∑Wc p

(2)

i k

Pk ∈QPμ ( ci )

The degree of inclusion is computed in terms of the ratio of intersecting quality properties of ci and cj to the number of quality properties in the source ci as shown in equation 2.

88

Y. Wang, Y. Jia, and S. Yang

Based on the definition of information flow, we provide a new structure named semantic text features graph. There has been work where people tried to learn or create kernels (similarity measures) which would exploit semantic similarity between the terms. Attempts to incorporate some notion of term similarity also include the latent semantic indexing [12], semantic networks [13] and probabilistic methods [14]. In [15], a set of methods are presented for organizing a collection of documents into a graph and text feature similarity is defined based on the graph. In this paper, we proposed a semantic text features graph based classification method and used this method to eliminate the clusters overlapping. Definition 3 (Semantic text features graph). Given a set of documents D, semantic text features graph is a weighted graph G = where V is the set of vertexes and E is the set of edges. Each vertex denotes a document in D and also the set of words that the document contains. There is an edge iff v1 extends the vocabulary of v2. Here "extends" means that v1 (document 1) uses more specific terminology (on the same topic) than v2 (document 2). The weight of < v1, v2> is score(v1, v2) where score function is defined in definition 4. A special vertex that contains stop words acts as the root of the graph. For example, suppose we have a vertex with general “computer science” terms, which has among the others also the children “computer architecture” and “machine learning”. Each of the children extends the vocabulary of “computer science” vertex in their own way. Definition 4 (Score function for new vertex). Given a document Di which we are about to insert into the graph, the score function for is:

score(Vi,Vj ) =

| Join(Vi, (∪ p ∈ P ( j )Vp )) | | Union(Vi , (∪ p ∈ P ( j )Vp )) |

(3)

Where ∪ p ∈ P ( j )Vp denotes a set of words from vertexes on a path from Vj to the root. The Join and Union functions are defined as: Join(D1,D2) = {t| t ∈ D1, t ∈ D2} ∪ {t1, t2| t1 ∈ D1, t2 ∈ D2, degree(t1, t2) ≥ }

(4)

Union(D1, D2) = D1 + D2 – Join(D1, D2)

(5)

where is a threshold value. The semantic text features graph depends on the ordering of the documents. In order to create an optimized graph independent with the ordering of the documents, we define the total score function. Definition 5 (Total Score). The total score function for document di is:

totalscore(di ) =

∑ score(V ,V ) i

j

(6)

Vj∈V '

Where V’ means the set of vertex Vj that satisfies score(Vi, Vj) > ( is a threshold value). At each time the best document (the document which maximizes the totalscore given by equation 6) is selected to insert into the semantic text features graph. The basic idea for our classification method is that documents belonging to the same topic (category) are closed in the semantic text features graph. This assumption

Short Documents Clustering in Very Large Text Databases

89

Fig. 2. Semantic text features graph with labeled nodes

has been validated in our experiments. We use a kNN like method to build our short document classifier. Our method needs a set of labeled short documents as training samples. We can select the documents without overlapping in each cluster as training samples. The training samples are inserted into the semantic text features graph first. During the classifying process, each short document dc is inserted into the graph as vertex Vc and we find k labeled document vertexes that have the nearest path to Vc. An example of semantic text features graph with labeled vertexes and new vertexes to be classified is shown in fig. 2. We calculate the weight that document dc belonging to category Ci using the following equation:

weight (Ci ) =

∑ length(V ,V ) j

c

(7)

dj∈Ci , dj∈Dk

Where Dk means the set of k labeled documents and the length function calculates the weighted length between two vertexes in the semantic text features graph. Then document dc belongs to category Ci that maximizes weight(Ci). The key problem in our method is how to find the k nearest labeled neighbors for vertex Vc efficiently. This is a problem of fining k vertexes with shortest paths from a given source s to a set of vertexes in a weighted graph. The traditional Dijkstra 2 algorithm [16] can solve this problem with time O(n ) in a graph with n vertexes and m edges. To get satisfied accuracy, the number of unlabeled samples must be large enough 2 in our method. So it is very inefficient to find the k labeled neighbors with time O(n ) each time a new document is processed. Many other algorithms are developed to improve the performance of the shortest path problem. Since our semantic text features graph is static, we can improve the performance based on the following remark: Remark 1 (Weighted distance between vertexes in semantic text features graph). Let Vs and Vd be the source and destination vertexes in the semantic text features graph and Vs is linked to m vertexes V1,V2,…Vm. Suppose the weighted distance from Vi (i = 1,2,…m ) to Vd is D(Vi, Vd), then the distance from Vs to Vd is the maximum value of (weight(Vs, Vi) + D(Vi, Vd)).

■

The semantic text features graph is static when all labeled vertexes are inserted. When a new document to be classified is processed, we remove it from the graph to make the graph static. So the distance between vertexes is static and we calculate the distance from each vertex to all labeled vertexes once and store the distance value in a distance table. When a new vertex is added into the graph, we can easily get it distance to all labeled vertexes since D(Vi, Vd) is stored in the table.

90

Y. Wang, Y. Jia, and S. Yang

3.4 The SDC Algorithm Now we summarize the entire mining process and present the SDC algorithm. The frequent term set mining process and HAL semantic space building process is not included in this algorithm.

1 2 3

1 2 3

4

5

Algorithm 1. Short documents clustering in a very large text database Algorithm for controlling node: Input: (1) A very large text database D, (2) the frequent term set F. Output: Clusters with label, document count and documents (optional). Method: Partition the text database into n logical partitions named P1, P2, … Pn; Notify each mining node to run with input (Pi , F); Wait for the result of all mining server. When all result is returned, merge the result and return the resulting clusters. Algorithm for mining node Input: (1) A logical data partition Pi, (2) the frequent term set F. Output: The document count and label for all clusters. Method: Create an empty document table as shown in fig.1 and a cluster count table; Create the semantic text features graph; For each frequent term set Fi, get all documents in Pi that contain the terms in Fi and then: a) Use the documents as the initial cluster of Fi. Write the document number into the cluster count table; b) Increase the “cluster number” column of the document table as described in 3.2; Get the documents that are belong to more than one clusters by selecting the records with “cluster number” greater than 1. For each of such documents: a) Use the semantic classifier in 3.3 to classify the document into one of the clusters; b) Assign the document to the cluster by setting the “cluster ID” column in the document table; c) For all clusters that contain the document but the document does not belong to, decrease the cluster count in cluster count table; When the whole data partition is processed, send the cluster count table to the controlling node.

As we can see, SDC is communicating efficient since the mining nodes need not communicate with each other when clustering. With the help of text index, no database scan is needed. The semantic text features graph creating algorithm is not efficient but it runs only once and then the semantic text features graph is stored.

4 Experimental Evaluations A commonly used external measurement, the F-measure [11], is employed in this paper to evaluate the accuracy of the clustering algorithm. In order to evaluate the

Short Documents Clustering in Very Large Text Databases

91

semantic classification algorithm individually, we use interpolated 11-point average precision, initial precision and R-precision [17]. We use two types of data sets: (1) Reuters corpus which is commonly used for text clustering (Only the articles that are uniquely assigned to exactly one topic are used). (2) Short documents in our application. They are text data sets that are collected from public forums in the internet by robots. We use a small set of the short document (but the HAL semantic space is created from a large dataset) for accuracy experiment since it needs to cluster the documents by hand. To compare the performance of these algorithms, we used short documents that are about 400 MB in size. To evaluate the high scalability of SDC, we used short documents with 40 GB in size. Table 2. k=10, m=100,000 n

Average precision 50 0.575 100 0.728 200 0.753 300 0.782

initial Rprec- precision ision 0.729 0.833 0.895 0.901

0.614 0.691 0.718 0.712

Table 3. k=10, n=300 m

Average precision 10,000 0.470 50,000 0.753 100,000 0.782 500,000 0.788

Table 5. F-measures for Reuters data set # of clusters 5 15 30 60 Avg.

SDC 0.55 0.54 0.57 0.57 0.56

F-measures FIHC FTC 0.56 0.52 0.58 0.51 0.57 0.51 0.58 0.53 0.58 0.52

initial Rprécis- preciion sion 0.609 0.797 0.901 0.905

0.518 0.614 0.712 0.714

Table 4. n=300, m= 500, 000 k

Average precision 5 0.628 10 0.788 15 0.790 20 0.793

initial Rpreci- precision sion 0.741 0.905 0.897 0.908

0.644 0.714 0.722 0.725

Table 6. F-measures for short documents # of clusters 5 15 30 60 Avg.

SDC 0.49 0.51 0.55 0.52 0.52

F-measures FIHC FTC 0.41 0.35 0.41 0.35 0.42 0.35 0.41 0.36 0.41 0.35

We use 4 HP units connected with fast Ethernet. Each unit has 4 Itanium II 1.3G processors and 48 GB memory. The operating system is Red hat Advanced Linux 3.0. The text data is stored in an oracle 10g database (4 node cluster). The semantic classification method is important for the accuracy of the clustering algorithm. We first evaluate the parameters of the semantic classification method. Let m be the number of unlabeled documents used to create the semantic text features graph and n be the number of labeled documents. The result of our experiments is shown in table 2, 3 and 4. From the result we can find the increase of m, n and k will improve the precision of the classifier but the improvement becomes not obvious when a certain value is reached. The reason is that when the new vertex has enough neighbors to decide its category, the precision can’t be improved further. In the following experiments, we set n = 300, m = 500,000 and k = 10. We compare the accuracy of SDC with FTC and FIHC on the Reuters dataset. The result is shown in table 5. As we can see from the result, the accuracy of SDC is a little better than FTC and is comparable with FIHC. The reason is that SDC is designed for

92

Y. Wang, Y. Jia, and S. Yang

160 140 120 100 80 60

run time (minute)

run time (minute)

short documents and it has no superiority when processing normal long documents. The accuracy experiment result on short documents is shown in table 6. The number of clusters is controlled by setting different support value for frequent term set. SDC outperforms other methods for our real data which are short documents. As we described before, the reason is that key words appears less times in short document which affects the accuracy of FTC and FIHC but SDC uses the semantic information based classification method to improve the accuracy. In the next experiment, we compare the performance of the three algorithms on large data set as shown in fig. 3 (the HAL semantic space building time and semantic text features graph building time is not included). As we can see, the performance of SDC exceeds other algorithms especially when data set becomes even larger. The reason is that SDC is a parallel algorithm and it takes advantage of the function of text database. When data set is not very large, FTC and FIHC have better performance than SDC because they are simpler than SDC. The result of the scalability experiment in very large data set is shown in Fig. 4. We can see SDC has good scalability for very large data set while other algorithms can’t handle such data set.

FT C FIHC SDC

40 20 0 50

100

200

300

400

documents (thousand)

Fig. 3. Performance on large data set

450 400 350 300 250 200 150 100 50 0 0.5

1

2

3

4

documents (million)

Fig. 4. Scalability on very large data set

From these experiments we can conclude that SDC is more efficient and accurate than other algorithms when clustering short documents in very large text databases. Unlike FTC and HIFC whose performance deteriorates seriously as documents number becomes large, SDC's running time is almost linear. In addition, SDC has better accuracy for short document since it uses semantic information to eliminate the cluster overlapping.

5 Discussions and Conclusion In this paper, we have proposed a simple but efficient novel parallel algorithm SDC which is used to cluster short documents in very large text databases. As shown in our experimental results, SDC has better accuracy and good scalability than other algorithms when clustering short documents in very large text databases. SDC is designed for very large text databases. It can be easily scaled-up to even huge databases by applying more mining nodes since it is a parallel and distributed algorithm. Using semantic information is a reasonable way to improve the clustering accuracy for short documents. Parallel and distributed mining is a reasonable way to cluster

Short Documents Clustering in Very Large Text Databases

93

documents in very large databases. More detailed study along this direction is needed, including further improvement of the semantic space model to improve the accuracy of clustering and modifying this algorithm to build hierarchal clusters.

References 1. Jiawei Han and Micheline Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers, 2001. 2. Beil F., Ester M., Xu X. Frequent Term-Based Text Clustering, Proc. 8th Int. Conf. on Knowledge Discovery and Data Mining (KDD ‘2002), Edmonton, Alberta, Canada, 2002. 3. Benjamin C. M. Fung, Ke Wang, Martin Ester: Hierarchical Document Clustering using Frequent Itemsets. SDM 2003. 4. E. Jensen, S. Beitzel, A. Pilotto, N. Goharian, O. Frieder “Parallelizing the Buckshot Algorithm for Efficient Document Clustering”, ACM 11th Conference on Information and Knowledge Management (CIKM), November 2002. 5. A. Hotho, A. Mädche, A., S. Staab. Ontology-based Text Clustering. Workshop Text Learning: Beyond Supervision, 2001. 6. Bhoopesh Choudhary and P. Bhattacharyya. Text Clustering Using Semantics. World Wide Web Conference (WWW2002), Hawai, USA, May 2002. 7. Song, D., Bruza P.D. (2001) Discovering Information Flow Using a High Dimensional Conceptual Space. In Proceedings of ACM SIGIR 2001, pp. 327-333. 8. Oracle Text 10g Technical Overview. http://www.oracle.com/technology/products/text/x/ 10g_tech_overview.html. 9. Wang Yongheng, Jia Yan and Yang Shuqiang. Parallel Mining of Top-K Frequent Itemsets in Very Large Text Database. WAIM 2005. 10. Lund, K. and Burgess C. (1996) Producing High-dimensional Semantic Spaces from Lexical Co-occurrence. Behavior Research Methods, Instruments, & Computers, 28(2), 203-208. 11. M. Steinbach, G. Karypis, and V. Kumar. A comparison of document clustering techniques. KDD Workshop on Text Mining’00, 2000. 12. T. A. Letsche and M.W. Berry. Large-scale information retrieval with latent semantic indexing. Information Sciences 100, 1997. 13. G. Siolas and F. d'Alch e-Buc. Support vector machines based on a semantic kernel for text categorization. In IEEE-IJCNN, 2000. 14. T. Hofmann. Probabilistic latent semantic indexing. In Research and Development in Information Retrieval, 1999. 15. Jure Leskovec, John Shawe-Taylor. Semantic Text Features from Small World Graphs. In Subspace, Latent Structure and Feature Selection techniques: Statistical and Optimization perspectives Workshop, Bohinj, Slovenia, 2005. 16. E. Dijkstra. "Two Problems in Connexion with Graphs," Numerische Mathematik, 1(1959), 269-271. 17. Song, D. and Bruza, P.D., Huang, Z., and Lau. Classifying Document Titles Based on Information Inference. Foundations of Intelligent Systems (Lecture Notes in Artificial Intelligence 2871) -Proceedings of ISMIS'03 conference. pp. 297-306.

A Simple Yet Efficient Approach for Maximal Frequent Subtrees Extraction from a Collection of XML Documents Juryon Paik and Ung Mo Kim Department of Computer Engineering, Sungkyunkwan University, 300 Chunchun-dong, Jangan-gu, Suwon, Gyeonggi-do 440-746, Republic of Korea [email protected], [email protected]

Abstract. Recently, XML is penetrating virtually all areas of computer science and information technology, and is bringing about an unprecedented level of data exchange among heterogeneous data storage systems. With the continuous growth of online information stored, presented and exchanged using XML, the discovery of useful information from a collection of XML documents is currently one of the main research areas occupying the data mining community. The mostly used approach to this task is to extract frequently occurring subtree patterns in trees. However, the number of frequent subtrees usually grows exponentially with the size of trees, and therefore, mining all frequent subtrees becomes infeasible for a large tree size. A more practical and scalable approach is to use maximal frequent subtrees, the number of which is much smaller than that of frequent subtrees. Handling the maximal frequent subtrees is an interesting challenge, and represents the core of this paper. We present a novel, conceptually simple, yet effective approach that discovers maximal frequent subtrees without generation of candidate subtrees from a database of XML trees. The beneficial effect of our approach is that it not only reduces significantly the number of rounds for infrequent tree pruning, but also eliminates totally each round for candidate generation by avoiding time consuming tree join operations or tree enumerations.

1

Introduction

In recent years, XML has become a popular way of storing many datasets because the semi-structured nature of XML allows the modeling of a wide variety of databases as XML documents. With the ever-increasing amount of available XML data, the ability to extract valuable knowledge from them becomes increasingly important and desirable. The data mining community has been challenged 

This work was supported in part by the Ubiquitous Autonomic Computing and Network Project, 21st Century Frontier R&D Program and by the university IT Research Center project (ITRC), funded by the Korean Ministry of Information and Communication.

L. Feng et al. (Eds.): WISE 2006 Workshops, LNCS 4256, pp. 94–103, 2006. c Springer-Verlag Berlin Heidelberg 2006 

A Simple Yet Efficient Approach for Maximal Frequent Subtrees Extraction

95

to come up with an efficient and scalable method for uncovering useful information from large collections of XML data. The first step toward mining information from XML documents is to find subtrees frequently occurring in a large collection of XML trees. Frequent subtrees in a database of trees provide useful knowledge in many cases. However, the discovery of frequent subtrees appearing in a large-scaled tree-structured dataset is not an easy task to do. Due to combinatorial explosion, the number of frequent subtrees usually grows exponentially with the size of a tree. Therefore mining all frequent subtrees becomes infeasible for a large number of trees. A more practical and scalable approach is to use maximal frequent subtrees. Handling the maximal frequent subtrees is an interesting challenge, and represents the core of this paper. The rest of this paper is organized as follows. We begin by reviewing some related works in Section 2. We continue in Section 3 with a description of some terminologies used throughout the paper, and problem definitions considered in this paper. Then, the details of the proposed algorithm are given in Section 4. Finally, in Section 5 we sum up the main contributions made in this paper and discuss some of our future works.

2

Related Works

The various works for mining frequent subtrees are described in [3,14,15,17]. Wang and Liu [15] considered mining of paths in ordered trees by using Apriori [2] technique. They propose the mining of wider class of substructures which are subtrees called schemas. Asai et al. [3] proposed FREQT for mining labeled ordered trees. FREQT uses rightmost expansion notion to generate candidate trees by attaching new nodes to the rightmost edge of a tree. Zaki [17] proposes two algorithms, TreeMiner and PatternMatcher, for mining embedded subtrees from ordered labeled trees. PatternMatcher is a level-wise algorithm similar to Apriori for mining association rules. TreeMiner performs a depth-first search for frequent subtrees and uses the scope list for fast support counting. Termier et al. [14] developed TreeFinder which uses a combination of relational descriptions for labeled trees and θ-subsumption notion to extract frequent subtrees. Other recent works describe how to mine frequent graph patterns [9,10]. Such graph mining algorithms are likely to be too general for tree mining as pointed out in [17]. Frequent subtrees in a database of trees provide useful knowledge in many cases, such as gaining general information of data sources, mining of association rules, classification as well as clustering, and helping standard database indexing. However, as observed in Chi et al’s papers [7,8], due to combinatorial explosion, the number of frequent subtrees usually grows exponentially with the size (number of nodes) of a tree. This causes severe problems with the completion time of mining algorithm and the huge amount of potentially uninteresting patterns. Therefore mining all frequent subtrees becomes infeasible for a large number of trees. A more practical and scalable approach is to use maximal frequent

96

J. Paik and U.M. Kim

subtrees. Informally, a maximal frequent subtree is a frequent subtree such that none of its proper supertrees is frequently occurred in a database of XML trees, and the number of which is much smaller than that of frequent subtrees. The algorithms presented by Xiao et al. [16] and Chi et al. [6] attempt to alleviate the huge amount of frequent subtrees by finding and presenting to end-users only the maximal frequent subtrees. The PathJoin algorithm proposed by Xiao et al. uses a new compact data structure, FST-Forest, to store compressed trees, representing the trees in the database. The structure itself obtains maximal frequent subtrees by pruning the frequent subtrees which are not maximal. Note that all frequent subtrees are found by joining the maximal frequent paths contained in the FST-Forest. Nevertheless, the algorithm uses post-processing techniques that prune away non-maximal frequent subtrees after discovering all the frequent subtrees. Therefore, the problem of the exponential number of frequent subtrees still remains. The CMTreeMiner presented in [6] instead looks for all frequent subtrees in a database of trees, directly aims at closed and maximal frequent subtrees only. The algorithm uses several pruning and heuristic techniques to reduce the search space that does not correspond to closed and maximal frequent subtrees and to improve the computational efficiency on the generation of closed and maximal frequent subtrees. However, CMTreeMiner algorithm bases on the enumeration trees. In this approach, a candidate subtree is generated by extending its unique parent, which is a frequent subtree with smaller size in the enumeration tree. In this paper, we present a novel approach for efficiently finding maximal frequent subtrees from a set of rooted and ordered trees. The major idea of the proposed technique is to construct special data structures that preserve all necessary information for establishing our goal, and to extract maximal frequent subtrees without either joining two frequent subtrees or extending the unique parent frequent subtree, for candidate subtrees generation. The rest of this paper is organized as follows. In Section 3, we begin by describing some terminologies used throughout the paper, and problem definitions considered in this paper. Then, the details of the proposed approach are given in Section 4. Finally, we conclude in Section 5 with discussion of our future works and goals.

3 3.1

Preliminaries XML Data Model

With no rigid structure, XML documents are often called semi-structured data, traditionally modeled as an Object Exchange Model (OEM) graph [1]. The OEM offers a highly flexible data structure that may be used to capture most kinds of data, and provides a substrate in which almost any other data structure may be represented [4]. However, graph structures in general have undesirable properties with regard to algorithmic complexity; no efficient algorithm is known to perform systematic enumeration of the subgraphs of a given graph, which is a common facet of a semi-structured data mining algorithm. But fortunately, it suffices to

A Simple Yet Efficient Approach for Maximal Frequent Subtrees Extraction

97

use trees, a special class of graphs, to represent XML data; there exists no cycles in tree structures [11,5,17]. XML represents data as trees, and makes no requirement that the trees be balanced. Indeed, XML is remarkably free-form, with the only requirements being that (i) the root is the unique node denoting a whole document, (ii) the other internal nodes are labeled by tags, and (iii) the leaves are labeled by contents or attributes of tags. A rooted tree is a directed acyclic graph satisfying there is a special node called the root that has no entering edges, every other node has exactly one entering edge, and there is a unique path from the root to each node. Thus, any XML tree is a rooted tree. Another characteristics of an XML tree is the labels. The labels in a tree could be unique, or duplicate labels are allowed for different nodes. In addition, because edge labels can be subsumed without loss of generality by the labels of corresponding nodes, we ignore all edge labels in this paper. Let T = (N, E) be a tree, where N is a set of nodes and E is a set of edges. We say that the tree T is a labeled tree if there exists a labeling function that assigns a label to each node in N . Therefore, the tree of XML document is often called labeled rooted tree. A path in a tree is a sequence of edges, i.e, p = (v1 , v2 ), (v2 , v3 ), . . . , (vn−1 , vn ), where vi ∈ N (1 ≤ i ≤ n), and n is the number of nodes on the path; p is called a path from v1 to vn and its length is n − 1. For short, the path is usually represented just by the nodes on the path, i.e, p = v1 , v2 , v3 , . . . , vn−1 , vn . In a tree there is a unique path from the root to each node. The length of the path from the root r to a node v is the depth of v in T . Also, a height of a tree T , denoted by height(T), is the largest depth any node in the T . The XML model we are describing here is based on ordered collections. An ordered tree is one in which the children of each node are ordered. That is, if a node has k children, then there is a first child, a second child,. . . , and a kth child. An unordered tree is one in which parent-child relationships are important, but there is no sibling order. The emphasis on order in XML stems from its origin as a document markup language. In documents, order is crucial; while in data applications, unordered data is widespread. For brevity, in the remaining of this paper, unless otherwise specified, we call a labeled rooted ordered tree as simply a tree. 3.2

Tree Mining Problem

The primary goal of mining some set of data is to provide the information often occurred in the dataset. Roughly speaking, often occurred information means some data patterns frequently used by various users or applications. However, it is not straightforward in the case for trees unlike the case for traditional recordoriented data. In this subsection we briefly describe the basics of the occurrence of a pattern in a collection of trees before addressing the issue of the tree mining algorithm. Definition 1 (Subtree). Let T = (N, E) be a labeled tree where N is a set of labeled nodes and E is a set of edges. We say that a tree S = (NS , ES ) is a subtree of T , denoted as S  T , iff NS ⊆ N and for all edges (u, v) ∈ ES , u is an ancestor of v in T .

98

J. Paik and U.M. Kim

Intuitively, as a subtree defined in this paper, a subtree S must not break the ancestor-descendant relationship among the nodes in a tree T . Let D = {T1 , T2 , . . . , Ti } be a set of trees and |D| be the number of trees in D, where 0 < i ≤ |D|. Definition 2 (Support). Given a set of trees D and a tree S, the frequency of S with respect to D, f reqD (S), is defined as ΣTi ∈D f reqTi (S), where f reqTi (S) is 1 if S is a subtree of Ti and 0 otherwise. The support of S w.r.t D, supD (S), is the D (S) fraction of the trees in D that have S as a subtree. That is, supD (S) = f req|D| . A subtree is called frequent if its support is greater than or equal to a minimum value of support specified by a user. This user specified minimum value of support is usually called the minimum support (minsup), denoted σ. A subtree S is σfrequent if its support is greater than or equal to σ. As mentioned in earlier sections, obtaining frequent subtrees causes severe problems with the completion time of mining algorithm and the huge amount of potentially uninteresting patterns. Therefore mining all frequent subtrees becomes infeasible for a large number of trees. In addition, even though frequent subtrees are mined through an algorithm, users have to put a lot of effort into finding interesting results from huge number of potentially useless results. Definition 3 (Maximal Frequent Subtree). Given some minimum support σ, a subtree S is called maximal frequent w.r.t D iff: i) the support of S is not less than σ, i.e., supD (S) ≥ σ. ii) there exists no any other σ-frequent subtree S  w.r.t. D such that S is a subtree of S  . Usually, the number of maximal frequent subtrees is much smaller than the number of frequent subtrees, and we can obtain all frequent subtrees from the set of maximal frequent subtrees. Example 1. An example of a set of XML trees D with various tags is shown in Fig. 1(a). At a glance, contents of three documents are different from each other and it seems that there is no similarity among them. However, when a minimum H

A C

B

D …

a

…

…

E

F

G

b

d

e

N

K

J L

b

…

M

… … … D

D

…

I

…

V = 2/3,

O

G

b

e

D b

D G

G

D

e

G

D b

G

…

e

G

T2

(a) Input: A set of XML trees D

T3

G e

Maximal Frequent Subtree

Frequent Subtrees

(b) Output: Maximal

b

e

e

T1

D

2 -frequent 3

Fig. 1. Maximal frequent subtrees of XML dataset

subtree

A Simple Yet Efficient Approach for Maximal Frequent Subtrees Extraction

99

support value is given as 23 , the interesting hidden information is discovered, as illustrated in Fig. 1(b). With a sufficient reliability more than 60%, we can get to know the commonly-occurring information. Also with the same reliability, we find the implicit relations between tags; tag D is obtained always together with tag G.

4

Overview of the Proposed Approach

In this section, we describe key features of our method to extract maximal frequent subtrees without any candidate subtree generation. The proposed method is inspired by the mining algorithm EXiT-B presented in the recent works of Paik et al. [12,13]. We modify their data structure PairSets because it can fail to store all frequent nodes. A large part of this problem is caused by the structure of PairSets. It keeps only current node(actually an n-bit binary code)’s information and a list of tree indexes. It is possible to establish a relationship with a wrong parent or ancestor since the current node has no information for either of them. In the PairSets, the relationship is only decided by the minimum support. Thus, we devise a new compact structure, LL-Tree (Linked List-Tree) to make up for the weak point of the PairSets. 4.1

Outline

Fig. 2 shows a brief outline of the proposed approach. As stated in the figure, the algorithm has three main functions: construcutLLL, buildLLTree, and findMaximals. The constructLLL function constructs a set of linked lists of tree indexes for node labels, named LLL (Linked List for Label). Each element, except Head, consisting of a single LLL holds the following information; locations of parent nodes, tree index placing a current node within itself, and a pointer for a next element. The function takes as inputs a database of trees, and returns a collection of LLLs, denoted as LLLD , for every unique node label in a database D. Afterwards, the set LLLD is divided into two groups F and N F , which are frequent LLLs and non-frequent LLLs in LLLD , respectively, by using a threshold value. Usually, this threshold value is minimum support σ × |D|. The frequent group F contains all LLLs in which the number of element of a single LLL is greater or equal to the threshold. Otherwise, into the non-frequent group N F . The second function buildLLTrees configures relations of every LLL in the set F . To this end, it builds a compressed tree, which is named LL-Tree. The LLLs in N F are referred because of ancestor-descendant relationships between nodes. We look a little more deeply the compressed tree in the later subsection. The last function findMaximal extracts maximal frequent subtrees from the LL-Tree produced by the function buildLLTree. Note that we do not perform any candidate subtree generation, which has been usually required to derive (maximal) frequent subtrees in previous researches. The LLLs and a LL-Tree make us avoid that complicate, time-consuming candidate generation phase.

100

J. Paik and U.M. Kim Algorithm Input: D: database of trees σ: minimum support Output: MFT: all maximal frequent subtrees Method: // scan the database to construct LLLD (1) LLLD = constructLLL(D) // scan LLLD to divide into two groups (2) threshold = |D| × σ (3) F = ∅, N F = ∅ (4) for each Linked List for Label LLL ∈ LLLD do begin (5) LLL.size≥ threshold then (6) F = F LLL (7) else  (8) N F = N F LLL // build a LL-Tree (9) LLT = buildLLTree(F, N F, threshold) // extract maximal frequent subtrees (10) MFT = findMaximals(LLT ) (11) return MFT

Fig. 2. Outline of the proposed algorithm

4.2

LL-Tree Construction

The compressed structure LL-Tree is initially built with the LLLs in F . The work for constructing LL-Tree is actually two step processes; first step is to identify each parent node of elements of every LLL in F , and second step is to replace the parent node in N F with an ancestor node in F or null(/). Prior to explaining the LL-Tree building process, first we define the data structures. Definition 4 (Head). Given a database D, a Head is defined as a unique node label which must have a single Linked List for Label for itself. Definition 5 (LLL). A single LLL (Linked List for Label) is a linked list structure for a head. It usually has several elements. Each element holds the (p, tid , ne ) information, where p indicates locations of parent nodes of a current head, tid is a tree index placing a current head within itself, and Ne is a pointer for a next element. A set of all LLLs for a database D is denoted by LLLD . According to a specified threshold calculated with the minimum support and the size of D, the LLLD is divided into two groups. Definition 6 (F and N F ). Given the threshold, a LLL ∈ LLLD is called frequent and classified as a member of a group F if LLL.size 1 ≥ threshold value. Otherwise, called non-frequent and as a member of a group N F . 1

Here LLL.size means a number of elements consisting of the single LLL.

A Simple Yet Efficient Approach for Maximal Frequent Subtrees Extraction

101

Price Compare Computer Shop

Desktop Desktop

Laptop

Desktop

Information

Company Brand

Model

Price

Model

OS

Brand Name Model

Price Brand

T1

Price

Model

T2

T3

(a) Original database D /LQNHG/LVWRI/DEHO/// ORFDWLRQ 

'HVNWRS

















%UDQG

















0RGHO

 















3ULFH

 







Head

DQHOHPHQW





&RPSDQ\









&RPSXWHU6KRS









1DPH









,QIRUPDWLRQ









/DSWRS









26







3ULFHFRPSDUH









)

(b) F and N F derived from LLLD by σ =

1) 2 3

Fig. 3. Database of trees and classified LLLD

Fig. 3 shows a database of three XML trees and its LLLD already classified into two groups, F and N F , by minimum support σ = 23 . We build a LL-Tree over the data depicted in the Fig. 3(b). Definition 7 (LL-Tree). Given the F and N F , a compressed data structure, LL-Tree (Linked List Tree), is constructed to reflect the original database compactly. To build an LL-Tree, indicators for parent nodes in each element and threshold are required. The LL-Tree is built by applying the following rules, illustrated in Fig. 3(b) and Fig. 4; first, identify whether each parent node (this is also Head of other LLL) in elements is included in F or N F by tracing the location indicators ps of a current Head. If the parent is not in F (see the second element of Brand Head, the 9 indicates the LLL of Information Head ), 1) trace every location indicator (actually the current Head’s grandparent) of elements for the LLL of parent node (in the figure, the Information Head has only one element. Therefore, trace the indicator 2), 2) check if the node indicated by the location indicator is a member of F or null (the LLL of Desktop Head is a member of F ), 3) if not, continue the step 1) and 2), 4) if so, the location indicator of the original current is replaced by the indicator for the frequent ancestor or null (the indicator 9 is replaced by the indicator 2). Second, consider the multi-location indicators in an element. To resolve this problem, the threshold value is applied. The indicator for a parent which is not a member of F is removed.

102

J. Paik and U.M. Kim

#2

Desktop

/

1

/

2

/

3

/

#4

Brand

#2

1

#2

2

#2

3

/

#5

Model

#2

1

#2

2

#4

3

/

#6

Price

#2

1

#2

2

Desktop

Brand

Model

Price

/

LL-Tree

Maximal frequent subtree

Fig. 4. LL-Tree and its maximal frequent subtree

After completion of a LL-Tree, maximal frequent subtrees are derived topdown construction of each LLL in the LL-Tree.

5

Conclusion and Future Work

We presented a new, simple yet effective approach for extracting maximal frequent subtrees from a database of trees. Unlike the traditional approaches, the proposed method does not perform any candidate subtree generation. To this end, we modified the recently suggested algorithm and its data structure by Paik et al. because there is a weak point in their proposal such that it can fail to store all frequent nodes. Thus, we complemented the problem by devising LLL structure and LL-Tree. We scan the original database only once to build LLLs for each unique node label. Afterwards, just LLLs are used to construct a LL-Tree which has all information to extract maximal frequent subtrees. The beneficial effect of our methodology is that it not only reduces significantly the number of rounds for non-frequent tree pruning, but also eliminates totally each round for candidate subtrees generation by avoiding time consuming tree join operations or tree enumerations. Currently, we are working on the analysis of the proposed algorithm as well as an evaluation of its performance compared to EXiT-B, especially focusing on how much the accuracy of maximal frequent subtree is increased.

References 1. Abiteboul, S., Buneman, P., Suciu, D.: Data on the Web: From Relations to Semistructured Data and XML, 1st edition, Morgan Kaufmann (1999) 2. Agrawal, R., Srikant, R.: Fast algorithms for mining association rules in large databases. Proceedings of the 12th International Conference on Very Large Databases (1994) 487–499 3. Asai, T., Abe, K., Kawasoe, S., Arimura, H., Sakamoto, H., Arikawa, S.: Efficient substructure discovery from large semi-structured data. Proceedings of the 2nd SIAM International Conference on Data Mining (2002) 158–174 4. Buneman, P.: Semistructured data. Proceedings of the 16th ACM SIGACTSIGMOD-SIGART symposium on Principles of databases systems (1997) 117–121 5. Chi, Y., Nijssen, S., Muntz, R. R., Kok, J. N.: Frequent subtree mining — an overview. Fundamenta Informaticae 66(1–2) (2005) 161–198

A Simple Yet Efficient Approach for Maximal Frequent Subtrees Extraction

103

6. Chi, Y., Xia, Y., Yang, Y., Muntz, R.R.: Mining closed and maximal frequent subtrees from databases of labeled rooted trees. IEEE Trans. Knowledge and Data Engineering 17(3) (2005) 190–202 7. Chi, Y., Yang, Y., Muntz, R. R.: HybridTreeMiner: An efficient algorithm for mining frequent rooted trees and free trees using canonical forms. The 16th International Conference on Scientific and Statistical Database Management (2004) 11–20 8. Chi, Y., Yang, Y., Muntz, R. R.: Canonical forms for labelled trees and their applications in frequent subtree mining. Knowledge and Information Systems 8(2) (2005) 203–234 9. Inokuchi, A., Washio, T., Motoda, H.: An Apriori-based algorithm for mining frequent substructures from graph data. Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery (2000) 13–23 10. Kuramochi, M., Karypis, G.: Frequent subgraph discovery. Proceedings of IEEE International Conference on Data Mining (2001) 313–320 11. Kilpe¨ ainen, P.: Tree matching problems with applications to structured text databases. PhD thesis in University of Helsinki (1992) 12. Paik, J., Shin, D. R., Kim, U. M.: EFoX: a Scalable Method for Extracting Frequent Subtrees. Proceedings of the 5th International Conference on Computational Science. Lecture Notes in Computer Science, Vol. 3516. Springer-Verlag, Berlin Heidelberg New York (2005) 813–817 13. Paik, J., Won, D., Fotouhi, F., Kim, U. M.: EXiT-B: A New Approch for Extracting Maximal Frequent Subtrees from XML Data. Proceedings of the 6th International Conference on Intelligent Data Engineering and Automated Learning. Lecture Notes in Computer Science, Vol. 3578. Springer-Verlag, Berlin Heidelberg New York (2005) 1–8 14. Termier, A., Rousset, M-C., Sebag, M.: TreeFinder: a First step towards XML data mining. Proceedings of IEEE International Conference on Data Mining (2002) 450– 457 15. Wang, K., Liu, H.: Schema discovery for semistructured data. Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining (1997) 271–274 16. Xiao, Y., Yao, J-F., Li, Z., Dunham, M. H.: Efficient data mining for maximal frequent subtrees. Proceedings of IEEE Internation Conference on Data Mining (2003) 379–386 17. Zaki, M. J.: Efficiently mining frequent trees in a forest. Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data mining (2002) 71–80

A Web-Based Transformation System for Massive Scientific Data∗ Shi Feng, Jie Song, Xuhui Bai, Daling Wang, and Ge Yu College of Information Science and Engineering, Northeastern University, Shenyang 110004, P.R. China [email protected], [email protected], [email protected], {dlwang, yuge}@mail.neu.edu.cn

Abstract. In the domain of science research, a mass of data obtained and generated by instruments are in the form of text. How to make the best use of these data has become one of the issues for both nature science researchers and computer professions. Many of these data contain their logic structure inside, but they are different from the self-describing semi-structured data, for these data are separate from the schema. Because of the great increase of the data amount, the traditional way of studying on these data can not meet the needs of high performance and flexible access. Relational DBMS is a good technique for organizing and managing data. In this paper, a mapping model—STRIPE— between scientific text and relational database is proposed. Using STRIPE, we design and implement a Web-based massive scientific data transformation system, which gives a good solution to the problem of the massive scientific data management, query and exchange. The evaluation to the system shows that it can greatly improve the efficiency of scientific data transformation, and offer scientists a novel platform for studying the data.

1 Introduction Scientific instruments and computer simulations are obtaining and generating vast data stores in the domains of astronomy, oceanography, geognosy, meteorology and so on. Furthermore, the data volumes are approximately doubling each year [7]. These data require new scientific methods to analyze and organize. As the foundation of scientific research, many of these data are in form of ASCII text. However, there are some drawbacks in the text data as follows. • Low readability: without special explanation files, the text data is ambiguous or meaningless. • Hard to integrate: many data are stored in different locations or even in different countries. It’s difficult to integrate all the data into one place. • High query cost: it’s difficult to find certain contents in massive datasets, for the contents may distribute in thousands of files. With the development of information technology, relational DBMS provides scientists an efficient way to manage scientific data. Using DBMS, scientists can get ∗

This work is supported by National Natural Science Foundation of China (No. 60573090).

L. Feng et al. (Eds.): WISE 2006 Workshops, LNCS 4256, pp. 104 – 114, 2006. © Springer-Verlag Berlin Heidelberg 2006

A Web-Based Transformation System for Massive Scientific Data

105

benefit from the non-procedural query analysis, automatic parallelism, and sophisticated tools for associative, temporal, and spatial search. However, it is still necessary to store scientific data in text form for the reasons as follows. Firstly, ASCII text is the only form supported by the scientific instruments and devices. Secondly, text data are platform independent, so they can be analyzed in different operation systems. Thirdly, ASCII text is the international standard for data exchange. Thus, in the area of scientific research, text data and databases will coexist for quite a long time. Recently, how to provide an efficient way to implement massive data transformation between texts and databases has become a common concern problem for both computer science researchers and natural science researchers. In this paper, we analyze the scientific text data structure, and model the data using a mathematics method. The main contribution of our research is that we present a mapping model for scientific data transformation (STRIPE-Scientific Text RelatIonal maPping modEl). Using this model, we design and implement a system based on Web for transformation between massive scientific text data and relational databases and also provide a platform for advanced applications. The evaluation to the system shows that our system provides a good solution to the problem of massive scientific data management in a distributed environment. The rest of this paper is organized as follows. Section 2 gives some basic concepts about scientific data, and then introduces the related work regarding the scientific data management and several data mapping models proposed. Section 3 analyzes the nonself-describing scientific text data structure, and presents a relational mapping model for the data, then describes an implementation for this model under the oceanography background. Section 4 proposes the Web-based framework for scientific data transformation and its applications. Section 5 gives the performance and evaluation of the system. Section 6 finally gives the conclusion and the future work of this research.

2 Theoretical Backgrounds 2.1 Non-Self-Describing Semi-structured Scientific Text Data Most scientific text data do not have the property of self-describing, for the describing tags waste plenty of space and may make the data file too big to be analyzed. In this section, we will describe the non-self-describing semi-structured scientific text data and how it is used in science research. 2.1.1 Semi-structured Data In semi-structured data, the information that is normally associated with a schema is contained within the data, which is called “self-describing” [3]. The meaning and logic structure of semi-structured data can be expressed and identified by semantic tags. For example, XML is a standardized extended markup semi-structured data. 2.1.2 Non-Self-Describing Semi-structured Scientific Text Data Non-self-describing semi-structured scientific text data (scientific text for short below) is a kind of semi-structured data produced by scientific devices or recorded by researchers. Every year, huge amount of Scientific Text are collected, exchanged and

106

S. Feng et al.

analyzed. Different from normal self-describing semi-structured data such as XML [6] and BibTex [15], scientific texts have not semantic tags to constrain inner structure and express meaning. The meaning of scientific texts usually hides in the hiberarchy structure and position relationship between characters. There are many international organizations to specify the norms for the scientific texts. 2.2 Related Work How to give an efficient way of managing scientific data has become a hot topic for both nature science researchers and computer professions. Jim Gray discusses several problems to be solved [7], and Peter Buneman et al design a biological data transformation system [2] and propose a way to archive scientific data in relation database [4]. There is a rich literature addressing the issue of managing semi-structured data in relational backends, and several mapping strategies have been proposed. Lorel [14] and Tsimmis [13] define the self-describing semi-structure data using graph theory. Semistructure data are represented as graph-like or tree-like forms, and data schema is defined by labeling the edges of the tree-like graph. Using this model, Jason McHugh et al design a query and management system Lore for the semi-structure data [9]. Lore provides a method to manage semi-structure data in DBMS. A self-describing semi-structured data relational mapping strategy STORED is proposed in [5]. When a semi-structured data instance is given, a STORED mapping can be generated automatically using data mining techniques, and then data can be transformed between relational database [1] and XML documents. Prior work on semi-structured data mostly focuses on self-describing documents. However, scientific devices and instruments are obtaining and generating massive non-self-describing scientific data every year and moreover, these devices and instruments may be placed in different location. Richard et al provide several frameworks for Web development [16] but none of those is suitable for scientific data. So the purpose of this research is to develop a Web-based system for massive scientific data collection, transformation and management.

3 Modeling Scientific Text Data 3.1 Scientific Text Modeling Scientific text data have hiberarchy structure. Sometimes there are object identifiers, which can identify different kind of data. Character is the minimum physical unit, and minimum logical unit is the string that contained underlying meanings. The meanings of scientific text data are defined in international scientific data format standards. For example, an integer in the text may represent the longitude of a certain position. Therefore, scientific text is a kind of semi-structure data with separate schema. Actually, these text data contain many kinds of data types, such as integer, decimal, timestamp, date, string and so on. In scientific text, objects are distinguished by object types, which are identified by object identifiers or inner text position structures. Having the same type means that these data have the same object identifier or they have close internal logic. For

A Web-Based Transformation System for Massive Scientific Data

107

example, if the data of longitude and the data of latitude together describe a certain position, we consider the two data have the same type. As we discussed above, in scientific text, there are four kinds of relation between minimum logic units: (1) Join with the same type inner row. (2) Join with the different type inner row. (3) Join with the same type between rows. (4) Join with the different type between rows. The four kinds of relation are reflexive, symmetric and transitive, so they are equivalence relations. Assuming that a scientific text data file is set D, R represents logic units relation (1) and (3) (the same type join inner and between rows). For any minimum logic unit d∈D, according to the set theory, the set [d]R={x|x∈D, xRd} is the equivalence class for the relation R on set D. By the same token, for equivalence class set Q on set D, Q is the quotient set of R on D. Therefore, there may be many equivalence classes consisting of the same object identifier in quotient set Q, and the relations between the equivalence classes in Q meet the definition of relational database theory. 3.2 STRIPE STRIPE (Scientific Text RelatIonal maPping modEl) is a kind of mapping model between scientific texts and relational databases, including text model, relation model and the mapping strategy between them. The mapping between text and relational database has two directions: the mapping from text to database (T/R mapping) and the mapping from database to text (R/T mapping). As a kind of forward engineering, in the T/R mapping procedure, the database structure is generated by the mapping model automatically and the text is parsed, relationalized, and at last saved into the database. R/T mapping is a kind of reversed mapping, in which scientific text data are generated from the relational database automatically by the mapping model. According to quotient set and relational database theory, there is relational schema lying in the equivalence classes of quotient set Q. In STRIPE, each equivalence class is mapped to relation entity, and the meaning of the minimum logic unit is mapped to the attribute of the entity. Because of the scientific text’s hiberarchy structure and the relationship between the rows, there are one-to-one or one-to-many relations between the entities mapped. In each equivalence class, the data that is divided by rows correspond to the tuples in the relational database. Since elements in the equivalence class have no order, the primary key of the tuples can be generated automatically or specify manually. 3.3 Building STRIPE with Oceanographic Data In this section, we will take oceanographic data as an example for explaining how to model the data and build up the STRIPE. Oceanography is really important branch of scientific research. As the scientists pay more attention to Green House and El Nino phenomenon and the observation technology develops fast, massive marine information is recorded in text form every year all around the world [12]. At last, these data will be stored in relational database for higher efficiency of query and

108

S. Feng et al.

management. At the meantime, text files are also the standards for international marine data exchange. STRIPE provides an efficient method to transform massive data between oceanographic texts and relational databases. Oceanographic raw text data take the international ASCII character coding scheme. This kind of text uses “row identifier” form, which means that the first character of each row identify this row’s object type. So the first character of each row is an object identifier, which divides the data into three types: Header, Data and Description. The data of the three types are in international marine gridded data format, which are constituted by a rectangular matrix of rows and columns. One example of marine Header data is showed in Table 1. For each oceanographic data file, there may be hundreds of columns in it, and a data file that an instrument creates can accumulate to several megabytes one day. There are dozens of this kind instruments in one data collect station, therefore, massive marine data are created per day. Table 1. Oceanographic Station Header Grid Data Format (excerpt) Parameter name This row identifier Next row identifier Country code Latitude Degree Latitude Minute Longitude Degree Longitude Minute

Start column 1 2 3 5 7 9 10

Length 1 1 2 2 3 2 3

Description Always 1 Always 2 or 3 According to IOC Latitude(degree) Latitude(minute) Longitude(degree) Latitude(minute)

From what we have discussed above, we can give the following definitions of oceanographic data. Definition 1. Given the marine data file OceanData, the three types of oceanographic data are represented by Header, DataSection and Description, respectively. DataSection i stands for one kind of DataSection. The operator ∨ denotes the relationship of join with different type between rows. m• denotes m lines of the data with the same identifier type, which means that the data are the relationship of join with the same type. The symbol n represents the max number of each component. So the record unit can be defined as follows: n DataBlock = Header (1... n ) ∨ ∪ m • DataSectio n i ∨ DataBlock' (0... n ) ∨ Descriptio n (0...1) i =1

(1)

The subscripts of each part represent the minimum and maximum occurrence of this part in the same DataBlock. By the same token, a marine data file OceanData is defined as follows: OceanData = m•DataBlock

(2)

In the DataSection, because of different ways of data collecting, each row can be divided into two parts: firstly, data appears in the fixed position; secondly,

A Web-Based Transformation System for Massive Scientific Data

109

transactional data with fixed length but unlimited numbers, which is attached to the first kind of data, as the depicting extra information under the first kind of data. So we have the definition as follows: Definition 2. CertainSection denotes the fixed data in DataSection; UncertainSection denotes the transactional data in DataSection. The operator + means the relationship of join with different type inner the row; p∗ means several transactional data with the same type in one row. According to definition 2, we can get: (3)

DataSection = CertainSection + p∗UncertainSection

By the definition 1 and 2, we can give the framework of STRIPE with oceanographic data in Fig.1. As showed in Fig.1, the left part shows a section of marine data which can be depicted as follows, where m, n, p represents the number of each component respectively: DataBlock = Header ∨ m•(CertainSection1 ∨ n•(DataBlock’))

(4)

DataBlock’ = CertainSection2 + p∗UncertainSection

(5)

According to relational database theory, there is relational schema in the oceanographic data. Different type of the oceanographic data can be mapped to the different relational entity in a database. For example, Header is mapped to entity Header in the relation model of Fig.1. Pay attention to the arrows in the Fig.1, we can find that they are bidirectional, which means our STRIPE is bidirectional. The data can be transformed not only from oceanographic files into databases, but also from database to oceanographic files. Scientific Text Model

Relational Model <<Entity>> Header

Header CertainSection1 CertainSection2

UncertainSection

CertainSection2

UncertainSection

1 *

<<Entity>> CertainSection1

CertainSection1 CertainSection2 CertainSection2

UncertainSection UncertainSection

1 *

<<Entity>> CertainSection2

1

Fig. 1. Oceanographic data STRIPE framework

*

<<Entity>> UncertainSection

110

S. Feng et al.

4 Design and Implementation of Web-Based Massive Scientific Data Transformation System In this section, we will discuss how to design and implement a Web-based massive scientific data transformation system. This system provides an efficient solution to the problem of massive scientific data management, query and exchange. 4.1 The Implementation of STRIPE XML [6] (eXtensible Markup Language) is a kind of markup language, which allows users to define their own tags. In our system, we give an implementation of STRIPE based on XML shown in Fig.2.

Fig. 2. STRIPE XML schema (excerpt)

Fig.2 is an excerpt from the XML STRIPE schema file, which describes the mapping model between scientific text data and relational databases. The STRIPE XML configuration file (short for STRIPE below) has three parts: scientific text model, relational database model and mapping strategy. The “Table” part of STRIPE reflects the schema of tables in the relational database, whose nodes include the attribute of table name tableName, and child elements primary key Pk, foreign key Fk. The “DataBlock” part of STRIPE depicts the physical structure of scientific text data. DataBlock may have four child elements: Header, DataSection, recursive DataBlock and Description. In each element, there are attributes describing the mapping strategy between scientific text data and relation database, such as the element and its database counterpart table name tableName, the start position startPosition and end position endPosition of data files and their mapped column name columnName in the database.

A Web-Based Transformation System for Massive Scientific Data

111

Building the scientific data under the STRIPE can reduce the coupling degree between data files and databases, and STRIPE provides a standard method of explaining massive scientific text data, therefore, it raises the readability of the scientific data. STRIPE offers computer scientists a standard of manipulating scientific data using programming language, and helps science researchers to understand the relational database more easily. Because of XML’s powerful ability of Web development, it is easy to take STRIPE into Web information system. In next section, we will design a Web-based massive scientific data transformation system, using STRIPE as transforming criterion. 4.2 Designing Web-Based Massive Scientific Data Transformation System Web-based massive scientific data transformation system is a kind of Web information system for managing, querying and exchanging scientific data. The architecture of it is shown in Fig.3. Every kind of scientific text data has its corresponding STRIPE configuration XML file. The system architecture includes the components of STRIPE Config Files, Import Engine, Export Engine, Relational Database and User Applications, and the STRIPE config files play an important role in the architecture. We will discuss each component of the architecture as follows. • Import Engine Through paring the STRIPE config XML files, Import Engine gets the physical structure of scientific data and the schema of the relational database. Then the SQL Generator creates the insert SQL script with regard to the database. After that, the Data Loader subcomponent gets the data from file system by the physical structure, and imports them into the database using the SQL script created before. • Relational Database Relational Database provides a high performance and high security solution to the management and query of massive scientific data. In our architecture, because of the platform independence of SQL, the Relational Database can be any commercial database or open source database. • Web Server Web Server provides a high efficiency container for the distributed scientific data management environment. The scientific researchers and data collector are usually not in the same location. So it is very useful for scientists to deliver and transform the data through Web. • User Applications Scientists used to search and analyze the scientific data through files. However, it’s really a tough work because there may be several gigabytes of data in one application. Relational database and Web server provide a much more efficient way to query and analyze the data. Furthermore, most application can be easily migrated to Web-based systems. As we can see from Fig.3, data visualizing, data mining, data statistics and data query can be easily deployed on our Web-based system. • Export Engine In reverse of the Import Engine, the purpose of Export Engine is to export scientific text data from databases. Firstly, Export Engine gets the query conditions from user’s

112

S. Feng et al.

requests, and then the SQL Generator creates the query SQL script from the relational schema and conditions. At last, File Writer executes the query script, and writes the data into files using the result set.

Fig. 3. Web-based massive scientific data transformation system architecture

5 The System Performance and Evaluation 5.1 System Performance The java technology provides a mature framework and toolkit for Web development. The whole system is developed under the struts of framework which is based on MVC model [10]. We use SAX for XML parsing which has the advantage of low memory cost and high parsing speed. JDBC is our choice for database accesses. As all of the technology we used is under standard API, our system is platform independence and can be deployed on any commercial or open source databases. For massive data is processed through our system, we design some accelerating algorithms to accelerate the speed of import and export. As insert and query are the most costly action in our system, the main idea of the two algorithms is reducing the

A Web-Based Transformation System for Massive Scientific Data

113

number of I/O of the database. In the import procedure, every data file is divided into several files according to object types inside. So the same type data can be inserted into the database at one time, which can greatly increase import efficiency. Using our import strategy, the data have the order that when the foreign key increases, the primary key will certainly increase. In the export procedure, we use this property to lower the number of database query. In the best condition, there will be only two times of query for the relational schema with two tables. 5.2 System Evaluation A Web-based scientific text transformation and application system has been successful deployed for the China Nation Marine Data and Information Service (NMDIS) [11]. The traditional way of store oceanographic data in NMDIS is text files, whose disadvantages have been discussed in Section 1. There are many data collecting station around the China's coastal areas, which collect huge amount of data every year. Using our system, it becomes really easy for oceanographer to integrate the data into data center in NMDIS, and exchange the appropriate data with foreign research institutes, as shown is Fig.4. Many these data centers and collectors all over the world may constitute a kind of network for scientific data integrating and exchanging. For reducing unnecessary traffic, this network may have some P2P attributes as described in [8]. Location A Data Collector 1

Location D Internet

Internet Data Collector 2

Location B

Data Center 1

Data Exchange Internet

Data Center 2

Internet

Data Collector 4

Internet

Internet

Data Collector 3

Data Collector 5

Data Collector 6

Location C

Location E

Location F

Internet

Fig. 4. The data collect and exchange in distribute environment

As massive data is transformed every day, our accelerating algorithms demonstrate good performance. After statistics, the speed of import can be about ten times faster than the normal import program, with export about thirty times faster. Our system provides flexible and fast accesses to the scientific databases. The applications based on Web offer good visualization and plotting tools, standard data mining API and mature data analyze algorithms. After a period time of trial running, our system runs stably and turns to play a great role in China’s oceanographic research.

114

S. Feng et al.

6 Conclusions and Future Work In this paper, a transformation model STRIPE that describing scientific text data and its mapping strategy to relational databases has been proposed. Using STRIPE, a Web-based massive scientific data transformation system has been designed and implemented, which offers a solution to the problem of the management, query and exchange of massive scientific data. Several approaches for further improving and extending the work are required. Firstly, more kinds of applications should be developed on our system. Secondly, the accelerating algorithms should be improved to meet the needs of more and more data. Thirdly, the text is only one kind of many forms of scientific data in the research, so more attention will be paid to find an efficient way to manage image or binary scientific data based on Web information system.

References 1. P. Atzeni, S. Ceri, S. Paraboschi, R. Torlone: Database System Concents,Languages and Architecture. McGraw-Hill (1999) 2. P. Buneman, S.B. Davidson, K. Hart, G.C. Overton, L. Wong: A Data Transformation System for Biological Data Sources. VLDB (1995) 158-169 3. P. Buneman, S.B. Davidson, M.F. Fernandez, D. Suciu: Adding Structure to Unstructured Data. ICDT (1997) 336-350 4. P. Buneman, S. Khanna, K. Tajima, W.C. Tan: Archiving scientific data. ACM Trans. Database Syst. 29 (2004) 2-42 5. A. Deutsch, M.F. Fernandez, D. Suciu: Storing Semistructured Data with STORED. SIGMOD (1999) 431-442 6. Extensible Markup Language: http://www.w3.org/XML/ 7. J. Gray, D.T. Liu, M.A. Nieto-Santisteban, A. Szalay, D.J. DeWitt, G. Heber: Scientific data management in the coming decade. SIGMOD Record 34(4) (2005) 34-41 8. Y. Liu, X. Liu, L. Xiao, L.M. Ni, X. Zhang: Location-Aware Topology Matching in P2P Systems. Proc. of the IEEE INFOCOM (2004) 9. J. McHugh, S. Abiteboul, R. Goldman, D. Quass, J. Widom: Lore: A Database Management System for Semistructured Data. SIGMOD Record 26(3) (1997) 54-66 10. Model-View-Controller. http://java.sun.com/blueprints/patterns/MVC.html 11. National Marine Data Information and Service. http://www.nmdis.gov.cn/ 12. National Oceanographic Data Center. http://www.nodc.noaa.gov/ 13. Y. Papakonstantinou, H. Garcia-Molina, J. Widom: Object exchange across heterogeneous information sources. ICDE (1995). 251-260 14. D. Quass, A. Rajaraman, J.D. Ullman, J. Widom, Y. Sagiv: Querying Semistructured Heterogeneous Information. Journal of Systems Integration 7(3/4) (1997) 381-407 15. The BibTeX Format. http://www.ecst.csuchico.edu/~jacobsd/bib/formats/bibtex.html 16. R.T. Vidgen: Constructing a web information system development methodology. Inf. Syst. J. 12(3) (2002) 247-261

Supporting Complex Query with Structured Overlays in Schema-Based P2P System* Min Yu, Zhanhuai Li, and Longbo Zhang School of Computer, Northwestern Polytechnical University, 710072 Xi’an, P.R. China {yum, zhanglb}@mail.nwpu.edu.cn, [email protected]

Abstract. Despite of their advantages in scalability and routing efficiency, structured peer-to-peer(P2P) overlay networks fail to support complex queries in a network of peers with heterogeneous schemas, which limits their use in schema-based P2P systems. By using relation keywords as index key for schema info and partitioning tuples vertically, a method of indexing both schema and data with structured overlay is designed. And an algorithm based on these two levels of indices to support complex queries on multiple attributes is proposed. Qualitative analysis and comparison show that this work is closer to the goal of P2P data management than other projects. Keywords: Peer-to-Peer, Schema-Based, Complex Query.

1 Introduction Enabling query processing is a natural extension of key and keyword based search in existing P2P systems. It is quite challenging because P2P query processing must be effective and efficient for handling peers with heterogeneous schema in a large scale dynamic and distributed network. We are interested in the problem of relational query processing in P2P systems. This is an important research area with applications to e-learning, P2P databases, monitoring and stream processing. Structured overlay is a good foundation for the creation of indices because it allows very efficient access for known keys. However it can not support complex queries such as join and aggregation on relational data directly. PIER[1] has tried to tackle the problem by partitioning the relations horizontally and indexing the tuples on certain attribute. But it assumes that every node knows and adopts the same schema which is impossible in large scale P2P systems and it can not support multiattributes queries effectively. Therefore, we try to support complex query over relational data with heterogeneous schemas based on structured overlays. The rest of the paper is organized as follows: Section 2 introduces our indexing scheme, based on which an algorithm of complex query is proposed and analyzed in section 3. In section 4, related work is discussed and compared with ours. Section 5 is devoted for concluding remarks. *

Supported by the National Natural Science Foundation of China (No.60573096).

L. Feng et al. (Eds.): WISE 2006 Workshops, LNCS 4256, pp. 115 – 121, 2006. © Springer-Verlag Berlin Heidelberg 2006

116

M. Yu, Z. Li, and L. Zhang

2 Schema and Instance Indices In this paper, each peer shares its data with its own schema. It is required that the creator of each relation appending some keywords to the relation and its attributes as thesaurus to describe their meaning[2]. Each peer consists of local database (LDB), vertically partition component (VP), index partitioning buffer(IPB), metadata extractor(ME), local schema buffer(LSB), and indexing schema buffer(ISB).Firstly the ME extracts schema from LDB and puts it with the thesaurus into LSB, which is the schema for the peer to share data with others. Meanwhile, ME indexes the schema in the schema index. ISB is used to store the schema information assigned to this peer by the schema index. Secondly, VP extracts the data for sharing from LDB according to the shared schema and partitions them vertically into triples in form of (tid, relation name: attribute name, attribute value)[3] to be published into the structured instance index. IPB is used to store the triples assigned to this peer to maintain by the instance index. We borrow the concept of soft-state from PIER[1] to ensure that the data and schema published by the failed and leaving data source can be discarded finally. 2.1 Schema Index The schema index is mainly used to find schemas similar to that used by the original query. As schema index only requires efficient exact query on strings, any structured overlay can be used as schema index. Each keyword of a relation is used as the key to publish the corresponding schema info to the structured overlay in the form of (relation keyword, relation name, attribute1, attribute2,…, attribute n) and attaches metadata file with it:(1) so that each attribute is attached its thesaurus, (2) and the information about the relation which has foreign key reference with the relation is attached. The schema index only includes the list of schemas in the network without the information about the data source. So the data sources publish their own schema info to the schema index periodically. 2.2 Instance Indices Each tuple of relation is partitioned into triples of form (tid, relation name: attribute name, attribute value), in which tid(consisting of data source name, table name, primary key etc.) is used to identify a tuple uniquely. For a relation R with schema (A1,A2, …,An), each tuple (tid, v1, v2,…,vn) is partitioned vertically into n triples, i.e. (tid,R:A1,v1),(tid, R:A2, v2),…,(tid, R:An,vn)[3].Each triple is published to BATON[4] three times using tid, R:Ai:vi and vi as index key respectively. Using R:Ai:vi as index key is to support selection on attribute Ai. Using tid as index key is to get the complete tuple from the vertical partitions. Using vi as index key is for the join operator. BATON[4] is a P2P structured overlay which is the extension of B-tree in database to the field of P2P. For a network of n peers, it guarantees answering exact match query and range query in O(log N) hops, which is efficient. So it is an ideal choice for instance indices, which can support selection algorithm Selection(R,θ,p) naturally:

Supporting Complex Query with Structured Overlays in Schema-Based P2P System

117

(1)If the selection condition θ is in the form of Ci1 ≤ Ai ≤ Ci 2 , p searches BATON with range [R:Ai:Ci1, R:Ai:Ci2], which gets to the first overlay range in O(logN) hops. Searching the left range only needs constant hops before all the answers are found. (2)If the selection condition θ is in the form of Ai = Ci , p searches BATON with R:Ai:Ci as the search key which will be answered in O(logN) hops. After arriving at the peer satisfying the selection condition, the triples that satisfy the selection condition on (tid, R:Ai,vi) are found. To get the complete tuple of the triple, it needs to search BATON with tid as search key, which finds the match peer in O(log N) hops. As tid uses the data source name and relation name as the prefix, and BATON does not destroy the sequence of data, the tuples of the same relation often reside on the nearby nodes in the index. Thus, finding all the complete tuples satisfying the selection condition will not cost too much more hops than finding one of the complete tuples.

3 Answering Complex Query Based on the Indices Queries are routed by messages in the network. Each query message consists of the query itself, the identifier of peer issuing the query, the number of attributes in the query, a bitmap which indicates whether each attribute is translated. We only focus on selection and join operator in this paper, and defer aggregation operators to our future work. According to the experience of database theory, it’s better to put selection operator down before join operator. Furthermore, the original relation is usually quite large, and only parts of them are needed by the user, so queries often have both selection and join. After user issues the query according to the schemas in LSB and ISB of peer p, p receives the query and does the two tasks at the same time: (1) using the original query to search instance indices directly. (2) translating the query: First, it searches schema index with the keywords of R. Each match is located in O(log N) hops if it does exist. Then the query is sent to that peer, and it is translated as far as possible on that peer. It’s possible that there are many matched relations on that peer and thus there may be many rewritten queries and join operator may be introduced to the rewritten queries. Whenever an attribute is translated, the corresponding bit in the query message is set to ready. If the original query refers to more than one relation, the next relation in the query is translated using the schema index similar to the above steps. If there are attributes which can not be translated when all the relations are dealt, the unfinished rewritten query is discarded. When all the attributes are translated successfully, the rewritten query is sent back to the peer who issues the original one and is processed in the same manner as the original one. Algorithm 1 shows the steps to answer a complex query consists of selection and join, in which t.JR means the value of tuple t on attribute JR. As join is exchangeable operator, without loss of generality we assume R is more selective than S, which means R will filter out more tuples. Our partition and indexing strategy make our join algorithm able to implement the Fetch Matches join with semi-join optimization[1] easily.

118

M. Yu, Z. Li, and L. Zhang Table 1. Pseudo-code for the Algorithm1

Algorithm 1. ComplexQuery(R,S,θR,θS, JR,JS,p) Input: R, S: two relations to be joined; θR, θS: selection on R and S respectively; JR, JS: the join attribute of R and S respectively; p: the peer issuing the query. Output: Results of {t | t σ θ R(R) R.JR = S.JSσ θ S(S)}. Steps: 1. O={}; 2. if θR not null, then ResultR= Selection(R,θR,p);//section 2.2 3. else ResultR= R; 4. for t Result R do 5. { p searches BATON with t.JR to find node q; 6. Resultsemi= GetSemiJoin(t.JR,JS,S,q,p); } 7. for o Result semi do 8. { p search BATON with o.tid to get complete tuple of S; 9. get the complete joined tuple tjoin; 10. O= {t join } O ;} 11.Return (O);

∈

∀∈

∀∈

∪

Table 2. Pseudo-code for the procedure GetSemiJoin Procedure GetSemiJoin(vR,attS,S,θS,p,poriginal) Input: vR:the value on join attribute of R; attS: the join attribute of S; S: a join relation; θS: selection on S; p: the peer performing the query; poriginal: the peer receiving the outputs. Output: Returns the set of triples whose values on S.attrS equal to vR. Steps: 1.Resultjoin= {o | o = (tid, S : attrs, v) v = vR o Datap} ; 2.if θS applys to attrS,then 3. Resultsel= {o | o satisfies θ S o Resultjoin} ; 4.else 5. {ResultS=Selection(S,θS,p); //section 2.2 6. Resultsel = {o | ( t O' (o.tid = t.tid)) ( t' Results(o.tid = t'.tid))} ;} 7.Return Resultsel to poriginal;

∧ ∧∈ ∧∈

∃∈

∧∃∈

As query with multiple operators is handled in pipeline manner with the results of one operator flowing into the next, we only consider the delay of generating the first result tuple for each operator when calculating the delay of the query. First, ComplexQuery takes O(logN) hops to find the tuples of R which satisfy θR no matter it is

Supporting Complex Query with Structured Overlays in Schema-Based P2P System

119

exact match condition or range condition. For each tuple of R, it takes O(logN) to find the matching triple of S on join attribute. Filtering it with θS can be finished directly in the best case and needs O(log N) steps in the worst case. GetSemiJoin can send the results back to the issuing peer of the query using IP address directly without routing through the network. The issuing peer pays O(log N) hops to get the complete tuple of the result. In summary, the complex query can be answered in O(logN) hops. The logarithmic relationship between the hops and the number of peers shows the good scalability of our strategy and guarantee of efficiency.

4 Related Work and Comparison Like us, many projects focus on relational data management in P2P systems. Hyperion[5] focuses on the semantic coordination between peers instead of query processing. Our work is similar to PeerDB[2] in the method of attaching keywords to relation and attributes. PeerDB is based on unstructured overlay network and uses flooding query strategy limited by TTL. Different from it, we adopt structured overlay to index both schema and data, which provides theoretical guarantee on efficiency of query translation and query evaluation avoiding the shortcomings of unstructured overlays. PIER[1] supports range selection by applying PHT(prefix hash tree) on distributed Hash table(i.e. DHT) which can only get approximate results and is inefficient. PIER proposed Fetch-Matches join and symmetric hash join algorithms and provided two optimization strategies, Bloom join and semi-join. Superior to it, our work can get exact result of range selection and need not construct temporary hash index as PIER when join attribute is not the primary key attribute while implementing semi-join naturally. [3] also partitions relations vertically but it publishes each triple using qgrams of attribute name and attribute value as keys to support similar queries on attribute name and attribute value. It assumes similar name means the same thing so it does not specify relation name in query. But storing huge number of q-grams is costly and it can not express the situation that different attribute names mean similar things. Let’s use PeerDB’s example, Protein is a similar or related attribute to Kinases but they are not in common in q-gram. Our method can solve this problem and avoid the complex decomposition of string to q-grams to save attribute matching time. The similar join in [3] is just the approximate of natural join while we can also support equi-join with exact answers. CON-QuerP[6], based on unstructured overlay network, uses structured coordination overlay network (CON) to index views and data sources. Different from ours, CON is not used for schema translation and does not use keywords of relation as index key. Piazza[7] focuses on XML data and the transformation between RDF and XML data. Its index is centralized and poor in scalability and robustness. Edutella[8], GridVine[9], et.al focus on queries on RDF data which are much simpler than relational data in processing due to the fixed dimension. Now, we show the advantages of our work by qualitative analysis: First, in dealing with heterogeneity, we use keywords as thesaurus which is simpler than creating schema mapping for the user who is not expert in computer science. Second, processing of original query is in parallel with query translation which both ensures the initial response time and improves the recall by retrieving more results. Third, keywords of

120

M. Yu, Z. Li, and L. Zhang

relation name instead of the relation name itself are used to publish the schema information to schema index. Thus the relations with the same keywords which are considered similar in semantics will be indexed to the same or nearby peer. Moreover, when a single relation can not provide all the attributes in the query but along with those having foreign-key reference with it can provide all, the query can still be rewritten correctly. Finally, adopting of soft-state in creating schema index simplifies the maintenance, where the failed or departed peer need not inform the index and the data source need not be checked for connection. Table 3 shows our work is closer to the goals of P2P data management than others. Table 3. Comparison of related work Projects

Semantic coordination Hyperion excellent PeerDB good PIER no [3] good CON-QuerP no Piazza excellent Edutella good GridVine good Our work good Ideal state excellent

Expressiveness of query medium strong strong medium strong strong medium medium strong strong

Scalability medium medium strong medium medium poor medium strong strong strong

Need it reconstruct index for multi-attribute query? no no yes no no no no no no no

5 Conclusion By trading off between the semantic coordination and query processing in P2P data management systems, we attach keywords to schema elements and partition tuples vertically to make it possible to index both schema and data with structured overlay. Based on these indices, an algorithm of supporting complex query on multiple attributes is proposed. Qualitative analysis and comparison show that our approach is closer to the goals of P2P data management than other work. Quantitative analysis of it is our ongoing work and supporting aggregation operators on these indices is our future work.

References 1. R.Heubsch, B.Chun, J.Hellerstein, B.T.Loo, P.Maniatis, T.Roscoe, S. Shenker, I.Stoica, A.R.Yumerefendi.: The Architecture of PIER: an Internet-Scale Query Processor. In: Proc. of the 2005 Conference on Innovative Data Systems Research(2005) 28–43. 2. W.S.Ng, B.C.Ooi, K-L. Tan, AY Zhou: PeerDB:A P2P-Based System for Distributed Data Sharing. In: Proc. of the 19th International Conference on Data Engineering(2003) 633–644. 3. M.Karnstedt, K-U.Sattler, M.Hauswirth, R.Schemidt: Similarity Queries on Structured Data in Structured Overlays. In: Proc. of NetDB06 (2006) 32.

Supporting Complex Query with Structured Overlays in Schema-Based P2P System

121

4. H.V.Jagadish, B.C.Ooi, Q.H.Vu: BATON: A Balanced Tree Structure for Peer-to-Peer Networks. In: Proc. of the 31st VLDB Conference(2005) 661-672. 5. A..Kementsietsidis, M.Arenas: Data Sharing through Query Translation in Autonomous Sources. In: Proc. of the 30th VLDB Conference(2004) 468-479. 6. WN. Qian: Data Management in Peer-to-Peer Systems. PhD thesis, Fudan University(2003). 7. I.Tatarinov, A.Halevy: Efficient Query Reformulation in Peer Data Management Systems. In: Proc. of the ACM SIGMOD International Conference on the Management of Data(2004) 539-550. 8. W.Nejdl, W.Siberski, M.Sintek: Desigh Issues and Challenges for RDF- and Schema-Based Peer-to-Peer Systems. ACM SIGMOD Record Vol32(3). (2003) 41-46. 9. K.Aberer, P.Cudré-Mauroux, M.Hauswirth, T.V.Pelt: GridVine: Building Internet-Scale Semantic Overlay Networks. In: Proc. of the third International Semantic Web Conference(2004) 107-121.

DRO+: A Systemic and Economical Approach to Improve Availability of Massive Database Systems* Kai Du, Huaimin Wang, Bo Deng, Yongheng Wang, and Shuqiang Yang National Laboratory for Parallel and Distributed Processing, Changsha, China [email protected] [email protected] [email protected] [email protected] [email protected]

Abstract. Because of the huge scale and numerous components, a massive database system’s availability has become a serious challenge. Many database replication technologies are used to increase the MTTF, but few are provided to decrease MTTR in massive database systems where the traditional backup methods are not feasible for expensive human cost. Based on analyzing the characteristics of the data in massive databases, we propose a novel approach called Detaching Read-Only (DRO) mechanism and its variation DRO+. It decreases MTTR through reducing the size of physically changing data in every database by detaching data on node granularity. The analysis and experiment results show that our approach can not only reduce MTTR by an order of magnitude, but also reduce the expensive human cost without extra hardware cost.

1 Introduction The requirements to store and query massive data in scientific and commercial applications have appeared. Alexander Szalay and Jim Gray address that the amount of scientific data is doubling every year and scientific methods are evolving from paper notebooks to huge online databases [1]. Until 2000, disk capacity has improved 1,000 fold in the last 15 years, consistent with Moore’s law, so storage volume is not the primary challenge as before [2]. System maintenance, automation and availability have become the new great challenges [3]. It is a good idea to build a massive database system with federated databases [4]. Because of the complexity of management and maintenance of a single PB(PetaByte)scale massive database system, partitioning it into many small federated databases is a feasible way. However maintaining such a huge system is expensive due to its low availability caused by its large scale. There are at least two challenges in gaining the high availability in massive database systems: the short MTTF (Mean Time To Failure) and long MTTR (Mean Time To Recovery) [5] for storage failures. The former is caused by the number of *

Supported by the National High Technology Development 863 Program of China under Grant No.2004AA112020, and the National Grand Fundamental Research 973 Program of China under Grant No.2005CB321804.

L. Feng et al. (Eds.): WISE 2006 Workshops, LNCS 4256, pp. 122 – 132, 2006. © Springer-Verlag Berlin Heidelberg 2006

DRO+: A Systemic and Economical Approach

123

hardware components. For example, if the availability of a database of 1TB is 99.99%, the availability of a database system of 100TB constituted of 100 such databases will only be 99%. The latter is caused by single database’s size. There are two reasons: 1) Recovering the data of 1TB needs a long time even if with fine backup solutions like archived and timely backup [6]. 2) Finely backuping 100 databases is a huge DBAs’ cost. The efficient way to increase the overall MTTF is to increase the MTTF of single database in a massive federated system since the number of databases can’t be decreased. How to increase MTTF has been researched by those who mainly focus on how to provide efficient synchronization mechanism between the replicas of a cluster [8] and care little about the recovery time. Decreasing the MTTR for storage failure is a great challenge for the database’s size. Little attention has been paid to this problem in previous research because it is a new problem which only comes forth in a massive system. The idea of reducing MTTR rather than increasing MTTF has been proposed in the ROC [9] project. How to decrease the MTTR and human cost will be researched in this paper. From the analysis above, we will achieve two objectives in a massive system: z

To improve the massive database system’s availability by reducing the MTTR. z To decrease the MTTR without extra expensive human cost. Currently the massive storage system is usually filled by the high-rate streaming log data, such as science experiment data [10,11], call detail records, RFID-based free way tracking [12], network packet traces. All these data basically have the same features: z

The data are generated high-rate and continuously (otherwise the information will not be cumulated into a massive system of TB or PB-scale). z The data are just appended into the system and the old data will not be updated. We call these features as “insert-once-no-update”. Leveraging these features, we design a novel mechanism DRO and its variation DRO+ to separate the insert-onceno-update “read-only” data from the online loading data. We compare the novel mechanism to the double replication used in an existed massive system in MTTR, TCO (Total Cost of Ownership) and performance. The results show that DRO+ excels others in most cases. The organization of this paper is as follows: Section 2 describes a massive database system CDRMDB. Section 3 describes our novel replication mechanisms. Section 4 and Section 5 analyze the MTTR and cost of the novel mechanism; Section 6 is the experiment; Section 7 is the related work and Section 8 is the conclusion and future work.

2 A Massive Database System: CDRMDB In this section, we will illustrate a massive database system CDRMDB (Call Detail Records Massive DataBase) which stores high-rate and massive call detail records. It is built up with 86 database nodes and every node’s volume is 500GB. CDRMDB has

124

K. Du et al.

the following features which are classic to many massive streaming data storage systems: 1) Store high-rate and massive streaming data. 2) Provide query access interface to the massive data. 3) The scalability and availability are two key system features. In CDRMDB, the simple Primary Backup mechanism [13] is adopted in terms of efficient loading performance. One primary and backup replica constitute one cluster. So it is constituted by 43 database clusters. The cause of too long MTTR is database size and recovery mechanism. In CDRMDB, one database’ size is 500GB. During the recovery period, all the 500GB data must be loaded into the recovered database from the correct database through logical export and import mechanism. The size and logical recovery mechanism lead to the long MTTR. In addition, double replication may cause the failure cluster to be the bottleneck of the query process when the recovery is being done because the exporting data operation will dramatically decrease the system’s performance. In order to eliminate the query bottleneck in Double Replication, Treble Replication is a better choice with more half cost of the former. When a cluster has three replicas and one of them fails, one normal database is used to recover the data and the other can process the query as before. Another benefit of the treble replication is that the cluster’s availability is higher because the probability of three databases failing is lower by an order of magnitude than two.

3 Novel Replication Mechanisms: DRO and DRO+ In this section, firstly we uncover the inherent reasons of too long recovery time in massive database systems in Section 3.1. Then we propose a novel replication mechanism DRO and its variation DRO+ in Section 3.2 and 3.3. 3.1 Why so Long Recovery Time In Section 2 we show the conflict of decreasing the MTTR and decreasing the maintenance cost. The essential reason of the conflict is that the system’s scale is so large that the traditional backup can’t be done because the DBAs’ cost is high. The main idea of shortening the recovery time stems from the feature of insertonce-no-update which is described in section 1. We can explain this idea clearly in Fig.1. In Fig.1 (a) and (a1), it shows the current state of CDRMDB --all data is in an online changing database. The databases’ data is always changing and all loading and query requests are issued to the total database. If a database fails for storage failures, it needs to recover all data whose size can reach 500GB in CDRMDB. It will take several days. However this can be avoided by leveraging the insert-once-no-update feature. We can periodically detach the history data which will not be updated. This idea is shown in Fig.1 (b) and (b1). Fig.1 (b) means to logically detach the history data from a database. Fig.1 (b1) means to divide the system into two parts from the system’s view. One part processes loading and query requests as an OLTP database. The other stores history data and it is consolidated as an OLAP database. In addition, in order to eliminate the IO contention between detaching and loading, it is sound to detach data based on node.

DRO+: A Systemic and Economical Approach

125

y Query Loading (a) All data on changing state

OLTP

(a1) All data in OLTP Query

Loading (b) Detaching history data to consolidated state

OLTP

OLAP

(b1) Detaching history data dynamically to OLAP

Fig. 1. Online detaching history data

3.2 Detaching Read-Only Data Replication To detach history data based on node granularity can be implemented by dynamically deploy nodes to different usages. We call this as “Detaching Read-Only (DRO) Replication”. The idea stems from three basic facts: 1) a read-only database can have an extremely short recovery time comparing to a changing database. 2) The smaller the scale of a write-read database, the shorter the recovery time.3) some research about read-only compressed database [14] has proved that compressed databases will likely do better. 3.2.1 Tasks in DRO Now let’s illustrate the DRO mechanism in Fig. 2. In Fig.2, the system’s running time is divided by cycles. In every cycle, two works will be done parallelly: loading data into the write-read database clusters and compressing read-only database clusters. In cycle 1, three database clusters which are called as Loading Database Cluster (LDC) (marked as “Loading”) provide query and data loading functions. In cycle 2, the three database clusters become read-only, and at the same time another three clusters are added into the system as LDCs. The three read-only database clusters are compressed and all the data is collected into one database cluster which is called Query Database Cluster (QDC) marked as “Compressed & Query” with black color. The two free database clusters which are released after data compressing (boxes with dashed frame in Fig.2) will be added into the third cycle for next cycle’s data loading task. In cycle 3, one fresh database cluster which is newly added into the system (boxes with solid frame in Fig.2) and two free database clusters from cycle 2 make up the new data LDCs. Just like in cycle 2, two free database clusters come out after compressed and are added into cycle 4. In cycle 4, the procedure is continued and the rest may be deduced by analogy.

126

K. Du et al. Task N1

Loading

N2

N3

N4

N5

N6

N2

N3

N7

N5

N6

N8

N1

N2

N3

N4

N5

N6

N2

N3

N7

n

Compress & Query

Cycle 1

Cycle 2

fresh database cluster

Time

Cycle 4

Cycle 3

compressed & read-only database cluster

free database cluster

Fig. 2. Detaching Read-Only Data Replication Mechanism

3.2.2 Two Types of Database Clusters In a LDC, all the database nodes save the same data but the data are not stored in the absolutely same physical files. For example, when a tuple R is loaded into the three databases d1, d2, d3 in a cluster, it may be saved in file1 in d1, file2 in d2, file3 in d3 while it is saved logically in the completely same way. So when one database node breaks down for a media failure, the database needs to be built from the blank and imports the data which are exported from another normal node. However, in a QDC, all database nodes save absolutely the same physical data. When a compressed database node has been created, it can be copied into another node through a disk copy: copying all the files with the same directories and files. This mechanism profits from the data’s no-update-after-insert property. Its advantage is that when a database node breaks down for media failures, only the fault files need to be copied from the normal node. It shortens the recovery time and tinily affects the normal node. 3.3 DRO+: Improved DRO Task N1

Loading

N2

N4

N3

N5

n

N6

N1

N2

N3

N4

N5

N6

n

Compress & Query

Cycle 1 fresh database cluster

R1

R2

R3

Cycle 2

Cycle 3

Cycle 4

Time

compressed & read-only large database cluster

Fig. 3. DRO+: improved DRO

DRO+: A Systemic and Economical Approach

127

DRO has decreased the MTTR without increasing DBAs’ backup and recovery work. However it loses much loading performance because too few nodes are used to load data in every cycle. In DRO, all database nodes have the same storage volume and the storage resources are wasted since its volume is designed for all online time which is larger than one cycle. So we can save the budget for storage to buy more Loading Database nodes. The procedure of DRO+ in Fig. 4 is like DRO except that one compressed and read-only database cluster is added in every cycle whose storage size is larger than LDCs and in every cycle the number of LDCs is equal to the treble replication. What is the economical benefit of DRO+ over DRO will be illustrated in Section 4.

4 MTTR Analysis In Section 3, we have illustrated four database replication mechanisms. In this section, we will analyze MTTR, performance, economic cost of the four mechanisms. 4.1 MTTR in DRO In order to analyze the system’s MTTR in DRO, we define the following variables: The number of database clusters is NS. The data’s online time is T. The time of every cycle is C. The number of LDC in every cycle is NL. The storage volume of one LDC is S. The requested average data loading rate is V. The overall performance of the data loading is PL. The compression ratio is R1. The space utilization ratio of every database node is R2 after it becomes a query-only database and before it is compressed. In Table 1, the number of various types of database clusters in every cycle is shown. The value of every column in Table 1 is calculated based on the volume usage. The number of fresh database clusters should be an integer which is not less than the float value NL *R1 * R2, and the number of free database clusters should be an integer which is not greater than NL * (1 - R1 * R2). Table 1. Number of various types of database clusters in every cycle

Cycle No. 1 2 3 4 …

# of fresh database clusters NL NL NL *R1 * R2 NL *R1 * R2 NL *R1 * R2

# of free database clusters 0 NL * (1 - R1 * R2) NL * (1 - R1 * R2) NL * (1 - R1 * R2) NL * (1 - R1 * R2)

For example, in Fig.2, the value of every variable is like the following: NL = 3, R1 * R2 = 1/3, NL *R1 * R2 = 1, NL * (1 - R1 * R2) = 2. In every cycle one or more QDC is created after the database clusters in the previous cycle are compressed. Because a QDC can only be written once with the compressed data and will not allow to be updated, the following two points should be guaranteed:

128

K. Du et al.

1) To make the best of the storage space, a QDC should be filled up as much as possible since the QDC can only be written once. 2) The cycle should be long enough that the volume of the data which is loaded in this cycle in the NL LDCs is large enough to fill up the storage space of one or more QDCs after the data is compressed. According to the above analysis and Table 2, we can educe the following equations: NS = NL + NL + (T/C - 2)*NL *R1 * R2 = (2 + (T/C - 2) *R1 * R2) NL.

(1)

The data loading performance is generally thought as relative to the number of the data loading clusters, so we have this: (f1, f2 is a constant factor.) PL= f1* NL. V= f2*PL.

(2) (3)

The system’s MTTR is classified as two types: MTTRQ, the MTTR of one QDC; MTTRL, the MTTR of one LDC. Since the recovery operation of a QDC is only to copy one or more data file, the recovery time is a constant time t0. So the system’s MTTR is determined by the MTTRL. In order to simplify the discussion about the MTTRL, we assume that it is linear to the data size of one node of the LDC: (f3 is a constant factor.) MTTRL = f3*V*C/NL. Referring to (2), (3), we can get: MTTRL = f1* f2* f3* NL *C/NL = f1* f2* f3 *C. From (1), (4), we can find the relation between MTTRL, C and NL: MTTRL = f1* f2* f3 * T *R1 * R2 /(2* R1 * R2 -2 + NS / NL).

(4) (5)

Theorem 1. In DRO and DRO+, assuming that the data loading performance is proportional to the number of data loading clusters and the MTTR of one database is proportional to its size, the MTTR is proportional to the cycle C. Proof. As discussed above.

□

Theorem 1 indicates that C determines the MTTR. 4.2 MTTR and Performance Comparison Theorem 2. In Treble, DRO and DRO+, assuming that the data loading performance is proportional to the number of LDCs and the MTTR of one database is proportional to its size, the MTTR of DRO+ is smallest and the loading performance of DRO+ is best. Proof. We mark the MTTR of treble, DRO and DRO+ as MTTRT, MTTRD and MTTR+. In fact, the double and treble replication mechanisms are a special case of DRO from (4). In (4), the treble replication means R1=R2 = 1, T = C, so the NS = NL, MTTRT = f1* f2* f3 *C= f1* f2* f3 *T. From (4), we also get that MTTRD = MTTR+= f1* f2* f3 *C. So MTTRD:MTTR+:MTTRT =C:C:T (6). If we assume the loading performance is linear to the number of Loading Clusters, obviously we can get the comparison of Performance of Treble, DRO and DRO+: PT: PD: P+= NS : NL:NS. (7) From (6) and (7), we can infer that DRO+ has the smallest MTTR and the best performance. □

DRO+: A Systemic and Economical Approach

129

5 Cost Analysis In Section 4.2 we have concluded that DRO+ has the smallest MTTR and the best performance. The cost may be higher than the other two. In this section we will show that the total cost of DRO+ is not always more than the other two. 5.1 Original Cost Analysis The original hardware cost includes CPU, memory, storage, network switch, and so on. In order to simplify analyzing the cost of the three replication mechanisms, we assume that every node has the same number of CPU and memory and the storage’s cost is proportional to its volume. Theorem 3. If the ratio of the storage cost to the computation cost is more than some value, the original cost of DRO+ is not more than Treble and DRO. Proof. The original hardware cost of Treble, DRO and DRO+, CT, CD, C+ is: CT = CD =3*NS *(CPU+S)

(8)

C+ = 3*(2* NS *(CPU+SW) + (T/C - 1)*(CPU+SR))

(9)

CPU is one node’s cost except its storage cost. The other variables are defined in Section 4.1. In (9), one loading node’s storage size is SW= (C/T)*S, one read-only node’s storage size is SR= NS * SW * R1. So if we expect the cost of DRO+ is not more than the other two, that is C+ <=CT = CD, we should keep the following inequality: S/CPU >= (NS + T/C - 1))/( NS *(1- R1+(C/T)*( R1-2)))

(10)

From (10), we can conclude that if the ratio of storage to CPU cost is larger than f(C)= (NS + T/C - 1))/( NS *(1- R1+(C/T)*( R1-2))), the original cost of DRO+ will not overspend the other two. □ Through simple analysis of f(C), we can find that it has a min value when R1>0.1 and T/C>3 are true which is really true in most cases. In Section 6.2 we can find it really true. 5.2 TCO Analysis The total cost of ownership (TCO) [15] of an information system can be divided into two parts: original hardware cost and management cost. The former is discussed in Section 5.1 and the latter mainly is human cost. As G. Weikum points out, TOC in a mission- critical system becomes more and more dominated by the money spent on human staff [16]. The human cost in recovery can be calculated as the total recovery time: failure count*MTTR. Since the system storage scale is the same, the failure count is the same. So the ratio of the human cost of DRO+ to Treble is CH+:CHT= MTTR+: MTTRT = C:T. The cost of transforming online data to offline is difficult to analyze in quantity, but at least it is clear that it is zero cost in DRO+ or DRO discussed in Section 3.2.2. In Treble, it is expensive for it needs huge extra human operation such as exporting and deleting old online data and it will sharply degrade the performance of a 24*7 running system.

130

K. Du et al.

6 Simulation and Cases Analysis In this section, we will show the differences of MTTR and cost in the four mechanisms which are described in section 5 through simulating several massive systems. 6.1 MTTR and Performance In this section we pay attention to MTTR and NL. Fig.4 shows the value of NL with different cycle. NS = 30, T = 150 days, R1 =0.4, R2 =0.5, f1= f2 =1. For treble and double replication, C=T=150 days; for DRO, C=10,15,30,50 days, NL is calculated from (1). In Fig.5, MTTR is calculated from (4) in Section 4.1. For Treble and DRO, f3 = 0.1 and for Double, f3 = 0.13. For Double and Treble, C=T=150 days. For DRO, MTTR varies with the cycle. From Fig.4 and 5, we can conclude that the shorter the cycle is, the shorter the MTTR is, but the data-loading performance the worse may be. MTTR can be decreased to one-tenth when the cycle is 15 days. 6.2 Cost Analysis

MTTR(day)

25 20

Double

15

T reble

10

DRO

5

DRO+

0 0

20

40

60

NL(Number of Clusters)

Fig.6 is the curves of the right expression of (10). Fig.7 is the human cost ratio of DRO+ to Treble in recovery calculated from Section 5.2. In Fig.6, T=150 days, the curves show that the larger NS is and the smaller R1 is, the smaller the ratio is. That is to say the larger the system is and the higher the compression ratio is, the more possibly the hardware cost in DRO+ is not more than the others. When C=15, NS =30 and R1=0.1, the minimum ratio reaches 1.8 and the human cost in recovery is only one-tenth in DRO+. The value of 1.8 can be easily reached in

35 30 25 20 15 10 5 0

Double T reble DRO DRO+

0

20

Cycle(day)

Fig. 4. Performance and Cycle

6 o i5 t4 a R e3 c2 i r P1 0

40

60

Cycle(day)

NS=15,R1=0.4 NS=30,R1=0.4 NS=15,R1=0.1 NS=30,R1=0.1 0 5 10 15 20 25 30 35 Cycle(day)

Fig. 6. Ratio of S/CPU in DRO+

Fig. 5. MTTR and Cycle

o 0.25 i t a 0.2 R t s 0.15 o C 0.1 n a 0.05 m u 0 H

0

5

10

15

20

25

30

35

Cycle(day)

Fig. 7. Human Cost Ratio of DRO+ to Treble

DRO+: A Systemic and Economical Approach

131

data-intensive applications like TPCC. The NO.1 in TPCC’s Price/Performance column until 27-May-2006 is Dell’s PowerEdge 2800 whose S/CPU is 1.95 [17]. This is evidence that the original cost of DRO+ is quite probable to be not more than Treble or DRO.

7 Related Work In the research community of database availability, database replication is a primary technology. The eager approach may easily lead to deadlocks and be hard to scale for its block mode [18]. So many lazy approaches are proposed to improve the overall performance and scalability [19]. However, all of them discuss little about the recovery of a replica from other replicas in a massive scale background. Another novel research point is to build a high availability system based on sharenothing database clusters. RAIDb [7] aims to build a high available system like the commercial system based on multiple open-source databases. It implements the high availability and load schedule through building the middleware tier, caches all the sql operations in the management node and redoes them on the fault database replica. This recovery way is not feasible when the data arrives at a high rate because the cache size is too large and the traditional backup mechanism is not useful to each replica. Oracle RAC [20] adopts another way to gain high availability on massive systems. It provides high availability through a multiple instances fault-tolerance mechanism in the query processing tier and can’t continue working when encountering media failures. So it can’t easily provide high availability for the high media fault ratio in a massive system. Google is a successful massive system. It is constituted by about ten thousand nodes. About one hundred nodes break down every day [21]. Its data scale is 4080TB. The method to gain high availability is data replication. All data and metadata is replicated double or treble. It focuses on the high availability of a massive file system and its recovery granularity is physical files. Thus the difficult problem of data consistency in database recovery doesn’t exist. The replication mechanisms proposed in this article focus on quick recovery from the media failure node which is not covered enough in the above research work. Especially the view of taking the total cost of recovery into account is not addressed earlier.

8 Conclusions The development of computing technology in several decades has made it possible to store massive data like web-log, call detail records, sensor data. However, the short MTTF and long MTTR of massive systems caused by the massive scale becomes a new challenge. Much work has been done to increase MTTF but little attention has been paid to decrease MTTR which is a severe problem in running product systems. Based on the experiences of our product system CDRMDB, we propose a novel mechanism DRO and its variation DRO+ from a systemic and economical view. The simulation shows that our approach can sharply decrease the MTTR by an order of magnitude without any performance loss and need no extra hardware or human cost.

132

K. Du et al.

References 1. 2. 3. 4. 5.

6. 7. 8. 9.

10. 11. 12. 13. 14. 15. 16.

17. 18. 19.

20. 21.

Jim Gray, Alex Szalay. Science in an exponential world. Nature,V.440.23, 2006. Jim Gray, Prashant Shenoy. Rules of Thumb in Data Engineering. ICDE2000. Jacek Becla, Daniel Wang. Lessons Learned from Managing a Petabyte. CIDR2005. Boris Gelman. V2LDB. CIDR2005. K. Nagaraja , X. Li and B. Zhang, R. Bianchini, R. Martin and T. Nguyen. Using Fault Injection and Modeling to Evaluate the Performability of Cluster-Based Services. In Proceedings of the Usenix Symposium on Internet Technologies and Systems, Mar. 2003. Abraham Silberschatz, Henry F. Korth, S. Sudarshan. Database System Concepts. 4th edition. China Machine Press. P461-470. Emmanuel Cecchet. C-JDBC: a Middleware Framework for Database Clustering. IEEE Computer Society Technical Committee on Data Engineering 2004. Yuri Breitbart, Raghavan Komondoor, Rajeev Rastogi, S. Seshadri, Avi Silberschatz.Update Propagation Protocols For Replicated Databases. SIGMOD 1999. Patterson D. A., A. Brown, P. Broadwell, G. Candea, M. Chen, J. Cutler, P. Enriquez, A. Fox, E. Kiciman, M. Merzbacher, D. Oppenheimer, N. Sastry, W. Tetzlaff, J. Traupman, N. Treuhaft. Recovery-Oriented Computing (ROC): Motivation, Definition, Techniques, and Case Studies. UC Berkeley Computer Science Technical Report UCB//CSD-02-1175, March 15, 2002. Y. Dora Cai, Ruth Aydt, Robert J. Brunner. Optimized Data Loading for a Multi-Terabyte Sky Survey Repository. In Proc.Supuer Computing 2005. A. Szalay, P. Kunszt, A. Thakar, J. Gray, R. Brunner. Designing and Mining MultiTerabyte Astronomy Archives: The Sloan Digital Sky Survey. In Proc. SIGMOD2000. http://www.511.org/fastrak Matthias Wiesmann, Fernando Pedone, Andr´e Schiper, Bettina Kemme,Gustavo Alonso. Transaction Replication Techniques: a Three Parameter Classification. SRDS 2000. Daniel J. Abadi, Samuel R. Madden, and Miguel C. Ferreira. Integrating Compression and Execution in Column-Oriented Database Systems. Proceedings of SIGMOD 2006. Hitt, Ellis F. Total ownership cost use in management. Digital Avionics Systems Conference 1998. Gerhard Weikum, Axel Moenkeberg, Christof Hasse, Peter Zabback. Self-tuning Database Technology and Information Services: from Wishful Thinking to Viable Engineering. VLDB2002. http://www.tpc.org/tpcc/results/tpcc_result_detail.asp?id=105092601 Jim Gray, Pat Helland, Patrick O’Neil and Dennis Shasha - The Dangers of Replication and a Solution.ACM SIGMOD 1996. A. Sousa,J. Pereira, L. Soares, A. Correia Jr., L. Rocha, R. Oliveira, F. Moura.Testing the Dependability and Performance of Group Communication Based Database Replication Protocols. Dependable Systems and Networks (DSN) 2005. Building Highly Available Database Servers Using Oracle Real Application Clusters. An Oracle White Paper May, 2001. Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. The Google File System. The ACM Symposium on Operating Systems Principles (SOSP) 2003.

Research and Implement of Real-Time Data Loading System IMIL* Han WeiHong, Jia Yan, and Yang ShuQiang Computer School, National University of Defense Technology, Changsha, China [email protected], [email protected], [email protected]

Abstract. With rapid development of the Internet and communication technology, massive data has been accumulated in many web-based applications such as deep web applications and web search engines. Increasing data volumes pose enormous challenges to data-loading techniques. This paper presents a data loading system in real time, the IMIL (Internet Monitoring Information Loader) that is used in RT-IMIS (Real-time Internet Monitoring Information System), which monitors real-time internet flux, manages network security, and collects a mass of Internet real-time information. IMIL consists of an extensible fault-tolerant hardware architecture, an efficient algorithm for bulk data loading using SQL*Loader and exchange partition mechanism, optimized parallelism, and guidelines for system tuning. Performance studies show the positive effects of these techniques with loading speed of every Cluster, increasing from 220 million records per day to 1.2 billion per day, and achieving the top loading speed of 6TB data when 10 Clusters are in parallel. This framework offers a promising approach for loading other large and complex databases.

1 Introduction With the enhancement of the degree of social information, people have placed more demands on on-line multi-terabyte information transactions. For example, Internet Information Security Management, storage and transaction of large scale scientific compute middle result (nuclear simulation, meteorology analysis), real-time monitoring system information(sensor network, astronomy meteorology monitoring system, secondary planet monitoring system), and analyses and research based on Internet information. The requirement of these application fields is as follow: the scale of overall data would reach hundreds of TB even PB; the rate of real-time data loading and storage has to keep up with the speed of data real-time acquisition, and the record number of real-time loading would reach several billions strips per day; real-time data analyses and transaction requirements is dealing together with real-time * This project is sponsored by national 863 high technology development foundation (No. 2004AA112020) and the National Grand Fundamental Research 973 Program of China (No. 2005CB321804). L. Feng et al. (Eds.): WISE 2006 Workshops, LNCS 4256, pp. 133 – 144, 2006. © Springer-Verlag Berlin Heidelberg 2006

134

W. Han, Y. Jia, and S. Yang

loading process. The on-line multi-terabyte data transaction system stated above, poses new challenge to the traditional database technology and the speed of real-time data loading. This paper is based on RT-IMIS (Real-time Internet Monitoring Information System), which monitors real-time internet flux, manages network security, and collects a mass of Internet real-time information, including package tracing data, such as IP package or TCP package, user session information, network flow data, SNMP data, data package, flow data. The characteristics of these data are listed as follows: 1. Varieties of data source: including package tracing data, flow tracing data, route table, configuration data, SNMP data, package transmission delay by active survey, the utilized rate of link, and so on. 2. Sustaining a generation of data: the network works 24 hours and 7 days a week, so monitoring data of the network is continuous. 3. Large amounts of data and continual increase of data will form multi-terabyte data. RT-IMIS not only records these monitoring data into the database, but also provides analyses and query function for on-line data, including network abnormal monitoring, network attack and virus origin query, and on-line data query for one year with analyses and inquire about them. The storage of RT-IMIS annual information is about 400TB, the arrival rate of the average monitoring information is about 1TB per day with its peak rate reaching 6TB. The same data scale system like RT-IMIS has not been found until now. According to 2005 Top Ten Award Winners, the max scale data system in 2005 is Max Planck Institute for Meteorology, which is about 223TB, and the data scale of yahoo is about 100TB, AT&T about 94TB. These characteristics of RT-IMIS bring great challenges to data loading. First, the large scale of data requires the base hardware architecture extensible. Second, the large data-collection rates and continuous data processing require real time and faulttolerant data loading. Finally, data loading and data query are working together in RTIMIS, which requires that data loading can not affect the usability of the database. Based on the requirements of Internet Monitoring Information System, this paper presents real-time data loading part—IMIL (Internet Monitoring Information Loader) in RT-IMIS. IMIL uses Oracle 10g database, and adopts multi-node, multitask parallelism technology and a range of optimized data loading technology, making it possible for the speed of data loading to reach GB degree per second and satisfying real-time multi-terabyte data loading request of RT-IMIS.

2 Related Research In recent years, the research of data loading mostly centralized on improving the efficiency of data loading in a single database, especially in the performance of [5][6][7][8] . The related researches included: J. Bercken’s research on constructing indexes a currency data loading algorithm.; P. Ciaccia’s research on how to construct indexes in multimedia database while data bulk loading; Christian’s research on how to construct indexes while loading multi-dimension data, and so on. These researches are very useful in single database data loading, but their performance can not satisfy the requirement of Multi-terabyte data real-time loading.

Research and Implement of Real-Time Data Loading System IMIL

135

Each major relational database management system (RDBMS) vendor provides a utility to load data from a flat file into a table. The Oracle system supports SQL*Loader, the MS/SQLServer system supports Data Transformation Services (DTS), and IBM DB2 supports a LOAD utility. However, these are proprietary tools that can only work with the vendor’s own databases. Furthermore, they are primarily designed to quickly load data into a single database table without performing any data transformation. These data-loading services can be used as the local database support for multi-terabyte data loading, but they can not complete the multi-terabyte data loading themselves. The research according to multi-terabyte data loading is just beginning. The National Center for Supercomputing Applications (NCSA) and Department of Astronomy in University of Illinois are researching on data loading that is being used to populate a multi-table, multi-terabyte database repository for the Palomar-Quest [1] sky survey . They brought out a data loading framework named SkyLoader, which improves the performance of data loading. But their research aimed at sky survey data, depending on the application and the structure of table, and the rate of data loading is not enough for real time data stream loading. The research of Sloan Digital Sky Survey (SDSS) is similar, they use a SQL SERVER Cluster for storing data. [2][3][4] . SDSS uses a temporary database, but it does not perform as well as SkyLoader

3 IMIL System Framework 3.1 Extensible Fault-Tolerant Hardware Architecture RT-IMIS is based on RAC architecture of Oracle 10g. Oracle RAC architecture is a Multi-Instance, single database. All of the Oracle Instances share one Storage Resource. Oracle RAC technology is a high-availability, high-performance, and lowprice database architecture. If one of the Oracle Instances in the cluster breaks down, the others will automatically take over its tasks and try to repair it. All of these actions are transparent to the users. The cluster database has the Automatic Load Balanced Function, and all the Instances can share a database case, so the database may parallel complete the visit requests, making it highly effective. Moreover, Oracle RAC structure is one kind of expandable platform, the RAC cluster, may facilitate increase or deletion server pitch point and oracle example according to the service demand. The best processor number that Oracle RAC recommends is 6-8, (too many processors will cause an internal communication overload, and the performance would be unable to grow linearly with the number of processors.) Therefore, the IMIL system uses many Oracle RACs interconnected with each other; each Oracle RAC is composed of 6-8 processors and installed on an Oracle 10g database, as figure1 shows. This hardware architecture is high-extensible, it could increase the processor number in a RAC interior, and it could also increase the RAC number in the system. The structure is highly fault-tolerant, if one of the processor breaks down, the RAC will continue to function normally. If one of the RAC breaks down, then another RAC can take over its tasks, and the entire system will continue to function normally.

136

W. Han, Y. Jia, and S. Yang

Fig. 1. IMIL hardware architecture

3.2 IMIL System Software Framework The IMIL system is composed by the Data Dispatch module, the preprocessing module and the bulk loading module, as figure2 shows. Data Dispatch module: According to the data distribution strategy (users may choose for themselves), it accepts real-time data on the Internet and dispatches them to the preprocessing module corresponding to the different databases. Preprocessing module: Each preprocessing module corresponds with a local database. First, because there are too many varieties of data monitored on the Internet (their form is also different with each other), there should be a transformation of the received data to a unified expression data. Second, statistics and on-line analysis module are responsible for real-time analysis, discovering the threatsl in the network (like the network attack and the virus and so on) in real time, handling the statistical data, updating the statistical table promptly, keeping the statistical data consistent with real-time data. Last, according to the different data format, the data buffer manage module is responsible for writing the data to the corresponding buffer files and managing the buffer files. Bulk Loading Module: It is divided into three sub-modules: Data Loading Module, Index Constructing Module and Partition Exchanging Module. Data Loading Module is responsible to load data files to temporary tables. Index Constructing Module is responsible for creating all kinds of indexes on temporary tables. Partition Exchanging Module is responsible for exchanging temporary tables with a partition of monitoring information table. All these modules finally make the new data available in the database. These operations may execute in-order or out-order or in parallel. The parallel manager module manages parallel processing among all these sub-modules, it dispatches the different operations to computing resources used in data loading, controlling parallel data loading, and maintaining the relationship between each operation.

Research and Implement of Real-Time Data Loading System IMIL

137

Internet Monitoring data

Fig. 2. IMIL software architecture

3.2.1 Bulk Data Loading The traditional way to load data was by writing INSERT in the sentence, but this did not satisfy the demand of the mass data increase like IMIL. So we use the Oracle bulk data load tool SQL*Loader, which could directly load the data from a formed external data file to an Oracle database table. The flow of data loading by SQL*Loader is shown as figure3.

Oracle RDBMS

Input Data File

Log File SQL *Loader

Control File

Bad File abandoned file

Fig. 3. Data loading flow of SQL*Loader

1. Control file: It controls how to map data in external data file into the Oracle table. 2. Data-input file: It is a data file which is organized according to the attribute of the Oracle table by preprocessing module. 3. Output of SQL*Loader: The loaded Oracle table and index. The bad file composed by the data whose format is inconsistent with the request. The abandoned file composed by records, which can not satisfy the condition request in the control file. The log file of SQL*Loader executing. SQL*Loader has provided two kinds of data loading: The usual path and the direct path, as the following Figure shows. The usual path of data loading is the default set on the Oracle database, its merit is the space saved, but there are defects. The first defect is its speed in data loading is not as fast as direct data loading, the second is the loading operation will compete with other processes running in the database. Because there is little data update and delete operations in IMIL, the waste in database space is

138

W. Han, Y. Jia, and S. Yang

not very big when using the direct path data loading. The request of data loading speed in IMIL is very strong, therefore, we choose the direct path data loading in the IMIL system.

Fig. 4. Usual path data loading and direct path data loading

Although SQL*Loader has provided high performance data loading, it is still unable to meet the performance needs of the application environment. The main problem is that many indexes have been created on data tables to satisfy high performance demand of system query and analysis, including B-tree index and text index. This may cause two problems, first, when data is inserted into a table, the database needs to detect conflicts between recent data and old data in the index while at the same time it must update all indexes of the table. The repetitive update will consume a lot of time, especially when there is text index on the table, the time of update index could be far more than the time of loading. The second is that the table index can not be used while data loading by SQL*Loader, it will cause a delay when users visit this table at this time. Therefore, we add an index management mechanism and exchange partition mechanism to data loading using SQL*Loader. 3.2.2 Indexes Management and Exchange Partition There is a restriction in the usual data loading method, which requires that accessing the data can not be permitted until the data base has been imported completely. But RT-IMIS will import data continuously while other operations like query and analysis will been done at the same time. If the query of data base can not be permitted while importing the data, then the availability of the system will be affected. So the indexes management and exchange partition mechanism will be used while the data is loading. Oracle 10g supply a function to partition the table, this function is suitable for very large databases like IMIL. First, partitioning the table can reduce the affection to data query while loading the data. The operation is the same as changing mobile hard disk, but replacing the disk with a Partition. Second, considering the performance, the table in IMIL is very large, because of the great capacity of data stored on it; by using a Partition, we can improve the query performance by adopting the mechanism, such as ignoring some of the Partitions. Third, it makes the table administrable. It makes operations such as deleting data and backing up data easier. It partitions the large table, and divides and rules them one by one. Last, the technique of partition upgrades the availability of the system. It localizes the fault in the partition, and decreases the time for recovery.

Research and Implement of Real-Time Data Loading System IMIL

139

To the user, a partitioned table is a set of segments. Segments can be added and deleted if necessary. A partitioned table can exchange data with a table in the database if their structure, type, and key are consistent. The partitioned table owns the data of the table after exchanging data. The exchanging of data runs only in the data dictionary of the database, and the data is not moved. So the exchanging of data is so fast that it will not affect other operations executed by Data Manipulation Language (DML). Based on SQL Loader and exchanging partition and taking the user session table, which records the communication session message as an example, the process of data loading is shown as figure5.

Fig. 5. The process of data loading

The process of data loading for Session table includes steps as follow: 1. SQL*Loader loads the data to a temporary table of Session from data buffer file. 2. Creating indexes for the temporary table of Session. 3. Creating a new partition of Session table and Exchanging the temporary table with the new partition. 3.2.3 Parallel Execution of Data Loading In order to meet real-time loading of the Internet monitor information system, it will need high parallel execution of data loading. The parallelism not only exists between every Oracle 10g database (each RAC has an Oracle 10g database, corresponding to the hardware), but also exists in the loading task itself. So as to fully parallel the loading tasks of every Oracle 10g databases, the data independence between each database should be pledged as possible as it could when IMIL system dispatch the data. There are 10 RACs in IMIL system, and 10 Oracle 10g databases installed correspondingly to RACs. There are more than 100 tables in IMIL system. Through the correlation analyses of the tables, we sort them into 10 classes, and each database stores one class. This way, the parallel degree of loading tasks achieves almost 10, and the data transformation between 10 databases has greatly been reduced in data query and analyses. Inside every RAC, which is composed of 6 nodes, there also exists parallelism between nodes. The ideal parallel degree is 6, but because the 6 nodes are connected to a RAID through SAN, and they face one database storage system at the bottom, there are resources competition and lock waiting. If 6 nodes are loading at the same time, as found in the system monitoring displayed by Oracle in the test process, the system will have problems such as lock wait that will affect the performance. The test

140

W. Han, Y. Jia, and S. Yang

shows that the optimized quantity of parallel nodes is 4 (detailed test data and analyses is in figure 8). In each loading task, there are two level parallelisms: One is the parallelism of data loading among different tables; the other is the parallelism of sub tasks loaded by each table through a pipeline. So in the IMIL system, after data transform module has transformed the data format to the database table required format, it puts each format data corresponding to one database table into a different data file, and each database table corresponds to a SQL*Loader process, accessing it’s own data file, which assures the parallelism of data loading between different tables. Every loading task of the database table is divided into three sub tasks: Data loading module responses creating temporal table for data file, and loading the data into this temporal table. Index constructing module creates the index for the temporal table; exchanging partition module first creates a partition corresponding to a database table, and then exchanging the temporal table into the database. All of these sub tasks are through a pipeline. A process is created for each sub task, and each sub task hands over the data to the next sub task after finishing its own work, and then it can deal with next data file. Parallel task management module assort with the parallel execution of sub tasks. Through the multi-level parallel dispatch: Database level, node level, database table level, loading sub tasks level. The loading performance of IMIL system can be greatly improved. The loading speed of every Cluster can increase from 220 million records per day to 1.2 billion per day, and it can achieve the top loading speed of 6TB data when 10 Clusters are in parallel. 3.3 Optimization of IMIL System IMIL is a huge quantity database system, every database stores ten TB data, and each database table in the database is also huge. This can make many common operations, such as recording logs, database statistical optimizing, to be long-time operations, even greatly affecting the system performance. So there is a need to optimize the system according to the factual situation. 3.3.1 Online Log Oracle Instance will store the operations in the database into Redo Log Buffer in SGA, and background process LGWR will timely write the content of Redo Log Buffer into Redo Log File. When the Oracle database is created, it automatically assigns two Redo Log Files for each Instance, each of which is 50MB. For IMIL system, bulk loading will lead to frequently using Redo Log File. When a Redo Log File works out, the system will do Redo Log File switch, and then the system will automatically do a checkpoint operation to synchronize cache and storage. Through monitoring the background log and the trace file, (under the default setting), when loading speed is 50 million records per hour, the system will do checkpoint every 8 minutes. Frequent checkpoints bring on large I/O, which badly affects the system’s performance. So we increase the Redo Log Files number to eight and the volume to 512M for each Database Instance, every two of which are in a group. This effectively controls the interval time of two checkpoints to 30 minutes, and therefore reduce the effects of database recording log operation.

Research and Implement of Real-Time Data Loading System IMIL

141

3.3.2 Statistic Optimization Oracle10g database in default uses CBO to build and choose the query plan with the CBO choosing the query plan according to the statistic of using an index. The statistic will record the using of CPU and I/O resources by table and index, thereby helping the CBO make a choice. There are quantity of text indexes and other indexes in the data table of the IMIL system, which makes the statistical cost to be obvious. For example, like ‘ANALYZE TABLE COMPUTE STATISTICS’, it needs one day to analyze a big table with text index (10 billion records). This is unacceptable for such a real-time system like IMIL. Therefore, we use the strategy of doing the statistic of the table or index by Partition, and along with DBMS_JOB, Oracle RAC, we can timely choose a comparative idle node to execute database statistical task. This can maintain the optimal indexing performance, and also decrease the effects to the online data management due to the database statistic optimization.

4 Performance Analyses of IMIL System In this section, we present various aspects of our performance tests on IMIL system, all tests were implemented based on RT-IMIS application system, using a hardware equipment as a Cluster of system structure Figure 1 shows, six Nodes are jointed to a RAID through SAN Switch, Node is HP4640 server (ItaniumII CPU, 1.6GHz/6MB; Memory: 48G), SAN Switch is Brocade Silkworm 3850, RAID is StorageTek FLX240, overall capacity is 60TB, and adopted method is 1000M Switch Connection among the Nodes as well as among the Clusters; in addition, OS is RedHat AS4 in which Oracle 10g release2 database is built. All tests were performed using the same data, which is the real monitoring data of RT-IMIS. The adopted data table is TalkingContent table used for recording user interactive information, average record length of it is 784B, and there are 5 indexes, one of which is a text index. The characteristic of text index is that it takes a long time to create. In order to avoid impacting on test results, during the test process, RTIMIS will not need to do other work, like query and analyses. There are already two month worth of data stored in database when testing. 4.1 Bulk Data Loading and Exchange Partition In this test, we contrast the difference of performance among three modes, general data-loading mode (inserting record by strip), bulk data loading mode and bulk data loading with exchange partition mode. In order to gain a good comparability, we only use one Node to do data loading, and don’t do parallel task scheduling. Respectively testing for empty TalkingContent table, where there is existing data of 10 days, 20 days, 30 days, 40 days, 50 days, 60 days, and record the loading time of 2 million records, the following Figure shows the results.

W. Han, Y. Jia, and S. Yang Runtime(minutes)

142

400 300

general data loading

200 bulk data loading

100 0 0

10

20

30

40

50

60

bulk data loading + exchange partition

data in table(days)

Fig. 6. General Data loading, bulk data loading and exchange partition

From this test, we can see that the performance of bulk data loading with exchange partition mode is better than general data-loading mode and only bulk-data-loading mode. In addition, there is a very important problem as loading performance becomes decrease as data increases in general data-loading mode and bulk-data-loading mode. The reason is because under these two ways, it is required to scan existed data indexes when creating index for new data loading, consequently, the performance of loading descends as data increase. But the problem doesn’t exist while adopting exchange partition mode, so the performance of loading has nothing to do with the scale of data in the database. 4.2 Performance of Parallelism Scheduling In IMIL system, there exists multilevel parallelism of database level, Node level, database table level, loading subtask level (as presented in Section 3.2.3). Next, we do experiments for the performance of all levels parallelism scheduling respectively.

Runtime(minutes)

4.2.1 Parallelism Among Loading Subtasks To test the performance of parallel and serial mode among loading subtasks, we use a Node Engine, and test the loading time of different scale of data, following Figure shows the results. Viewing from Figure 7, we can recognize that the parallelism among subtasks can enhance the speed of loading, in the case of loading large scale data. 60 40

serial data loading

20

parallel among subtasks

0 0.5

1

1.5

2

2.5

3

number of records for loading (million)

Fig. 7. Performance Test of Loading Subtask Parallelism

4.2.2 Parallelism Among Nodes Now, we test the impact of parallelism of Nodes in RAC with respect to the loading performance of the system. Respectively, to load 2 million pieces of records by using

Research and Implement of Real-Time Data Loading System IMIL

143

Runtime(minutes)

1, 2, 3, 4, 5, 6 Nodes, and writing the loading time down. The following Figure shows the results. We can see from the result, the system reaches its best data loading performance when the data loading nodes number is 5, but the cost requires more resources. If loading nodes number is 6, the performance decreases because of overfull network communication and database lock waiting. Besause the performance improvement is not evident from 4 nodes to 5 nodes, but the using of resource increases evidence, we use 4 nodes to load data parallel in IMIL. 25 20 15 10 5 0 1

2

3

4

5

6

number of nodes

Fig. 8. Performance Test of Node Parallelism

5 Conclusions Real-time Internet Mon