Protocols for group key exchange (GKE) are cryptographic algorithms that describe how a group of ... more Protocols for group key exchange (GKE) are cryptographic algorithms that describe how a group of parties communicating over a public network can come up with a common secret key. Due to their critical role in building secure multicast channels, a number of GKE protocols have been proposed over the years in a variety of settings. However despite many impressive achievements, it still remains a challenging problem to design a secure GKE protocol which scales very well for large groups. Our observation is that all constant-round authenticated GKE protocols providing forward secrecy thus far are not fully scalable, but have a computation complexity that scales only linearly in group size. Motivated by this observation, we propose a new and the first forward-secure authenticated GKE protocol that achieves both constant round complexity and logarithmic computation complexity. In particular, our GKE protocol is fully scalable in all key metrics when considered in the context of a broadcast network. The scalability of the protocol is achieved by using a complete binary tree structure combined with a so-called “nonce-chained authentication technique”. Besides its scalability, our protocol features provable security against active adversaries under the decisional Diffie-Hellman assumption. We provide a rigorous proof of security for the protocol in a well-defined formal model of communication and adversary capabilities. The result of the current work means that forward-secure generation of session keys even for very large groups can be now done both securely and efficiently.
An Improved Protocol for Server-Aided Authenticated Group Key Establishment
Protocols for group key establishment enable a group of parties to build a secure multicast chann... more Protocols for group key establishment enable a group of parties to build a secure multicast channel over insecure public networks. In this paper, we present a group key transfer protocol designed for use in the model where a trusted key generation center shares a long-term secret with each of its registered users. Our protocol is an improved version of the group key transfer protocol proposed recently by Harn and Lin. Improvement is made in three different aspects: security, efficiency and correctness. Our main contribution is in showing that Harn and Lin’s protocol does not achieve implicit key authentication but can be fixed without causing any efficiency degradation.
EXiT-B: A New Approach for Extracting Maximal Frequent Subtrees from XML Data
Along with the increasing amounts of XML data available, the data mining community has been motiv... more Along with the increasing amounts of XML data available, the data mining community has been motivated to discover the useful information from the collections of XML documents. One of the most popular approaches to find the information is to extract frequent subtrees from a set of XML trees. In this paper, we propose a novel algorithm, EXiT-B, for efficiently extracting maximal frequent subtrees from a set of XML documents. The main contribution of our algorithm is that there is no need to perform tree join operation during the phase of generating maximal frequent subtrees. Thus, the task of finding maximal frequent subtrees can be significantly simplified comparing to the previous approaches.
Mining Association Rules from a Collection of XML Documents using Cross Filtering Algorithm
Since numerous data have been represented and exchanged by XML, the ability to extract useful kno... more Since numerous data have been represented and exchanged by XML, the ability to extract useful knowledge from XML data is needed. There are several attempts to mine association rules from XML data. However, they mostly rely on legacy relational database with an XML interface so that efficiency and simplicity are challenging issue. In this paper, HILoP (hierarchical layered structure of PairSet) is introduced. The use of this data structure prevent from multiple XML data scans to mine association rules from a collection of XML documents. Also, cross filtering algorithm is introduced to mine frequent patterns, the algorithm reduces the number of candidate set. The performance evaluation result shows that this mechanism is powerful enough to represent both simple and complex structured association relationships inherent in XML data
Mining Maximally Common Substructures from XML Trees with Lists-Based Pattern-Growth Method
With the continuous growth in XML data sources over the Internet, the discovery of useful informa... more With the continuous growth in XML data sources over the Internet, the discovery of useful information from a col- lection of XML documents is currently one of the main re- search areas occupying the data mining community. The mostly used approach to this task is to extract frequently oc- curred subtrees in XML trees. But, because the number of frequent
EFoX: A Scalable Method for Extracting Frequent Subtrees
The more web data sources provide XML data, the greater information flood problem has been caused... more The more web data sources provide XML data, the greater information flood problem has been caused. Hence, there have been increasing demands for efficient methods of discovering desirable patterns from a large collection of XML data. In this paper, we propose a new and scalable algorithm, EFoX, to mine frequently occurring tree patterns from a set of labeled trees. The main contribution made by our algorithm is that there is no need to perform any tree join operation to generate candidate sets.
Journal of Information Science and Engineering, 2009
With the continuous growth in XML data sources over the Internet, the discovery of useful informa... more With the continuous growth in XML data sources over the Internet, 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 most commonly adopted approach to this task is to extract frequently occurring subtree patterns from XML trees. But, the number of frequent subtrees usually grows exponentially with the size of trees, and therefore, mining all frequent subtrees becomes infeasible for large size trees. A more practical and scalable alternative 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, though, and represents the core of this paper. We present a novel, conceptually simple, yet effective algorithm, called EXiT-B, that significantly simplifies the process of mining maximal frequent subtrees. This is achieved by two distinct features. First, EXiT-B represents all of string node labels of trees by some specified length of bits. Through fast bitwise operations, the process of deciding on which paths of trees contain a given node is accelerated. Second, EXiT-B avoids time-consuming tree join operations by using a specially devised data structure called PairSet. To the best of our knowledge, EXiT-B is the first algorithm that discovers maximal frequent subtrees adopting bits representation. We also demonstrate the performance of our algorithm through extensive experiments using synthetic datasets which were generated artificially by a randomized tree-structure generator.
A Simple Yet Efficient Approach for Maximal Frequent Subtrees Extraction from a Collection of XML Documents
Recently, XML is penetrating virtually all areas of computer science and information technology, ... more 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.
Mining Maximal Frequent Subtrees with Lists-Based Pattern-Growth Method
Mining maximal frequent subtrees remains at a preliminary state compared to the fruitful achievem... more Mining maximal frequent subtrees remains at a preliminary state compared to the fruitful achievements in mining frequent subtrees. Thus, most of them are fundamentally complicated and this causes computational problems. In this paper, we present a conceptually simple, yet effective approach based on lists structures. The beneficial effect of the proposed approach is that it not only gets rid of the process for infrequent tree pruning, but also eliminates totally the problem of candidate subtrees generation. As far as we know, this is the first algorithm that discovers maximal frequent subtrees without any subtree generation.
Protocols for group key exchange (GKE) are cryptographic algorithms that describe how a group of ... more Protocols for group key exchange (GKE) are cryptographic algorithms that describe how a group of parties communicating over a public network can come up with a common secret key. Due to their critical role in building secure multicast channels, a number of GKE protocols have been proposed over the years in a variety of settings. However despite many impressive achievements, it still remains a challenging problem to design a secure GKE protocol which scales very well for large groups. Our observation is that all constant-round authenticated GKE protocols providing forward secrecy thus far are not fully scalable, but have a computation complexity that scales only linearly in group size. Motivated by this observation, we propose a new and the first forward-secure authenticated GKE protocol that achieves both constant round complexity and logarithmic computation complexity. In particular, our GKE protocol is fully scalable in all key metrics when considered in the context of a broadcast network. The scalability of the protocol is achieved by using a complete binary tree structure combined with a so-called “nonce-chained authentication technique”. Besides its scalability, our protocol features provable security against active adversaries under the decisional Diffie-Hellman assumption. We provide a rigorous proof of security for the protocol in a well-defined formal model of communication and adversary capabilities. The result of the current work means that forward-secure generation of session keys even for very large groups can be now done both securely and efficiently.
An Improved Protocol for Server-Aided Authenticated Group Key Establishment
Protocols for group key establishment enable a group of parties to build a secure multicast chann... more Protocols for group key establishment enable a group of parties to build a secure multicast channel over insecure public networks. In this paper, we present a group key transfer protocol designed for use in the model where a trusted key generation center shares a long-term secret with each of its registered users. Our protocol is an improved version of the group key transfer protocol proposed recently by Harn and Lin. Improvement is made in three different aspects: security, efficiency and correctness. Our main contribution is in showing that Harn and Lin’s protocol does not achieve implicit key authentication but can be fixed without causing any efficiency degradation.
EXiT-B: A New Approach for Extracting Maximal Frequent Subtrees from XML Data
Along with the increasing amounts of XML data available, the data mining community has been motiv... more Along with the increasing amounts of XML data available, the data mining community has been motivated to discover the useful information from the collections of XML documents. One of the most popular approaches to find the information is to extract frequent subtrees from a set of XML trees. In this paper, we propose a novel algorithm, EXiT-B, for efficiently extracting maximal frequent subtrees from a set of XML documents. The main contribution of our algorithm is that there is no need to perform tree join operation during the phase of generating maximal frequent subtrees. Thus, the task of finding maximal frequent subtrees can be significantly simplified comparing to the previous approaches.
Mining Association Rules from a Collection of XML Documents using Cross Filtering Algorithm
Since numerous data have been represented and exchanged by XML, the ability to extract useful kno... more Since numerous data have been represented and exchanged by XML, the ability to extract useful knowledge from XML data is needed. There are several attempts to mine association rules from XML data. However, they mostly rely on legacy relational database with an XML interface so that efficiency and simplicity are challenging issue. In this paper, HILoP (hierarchical layered structure of PairSet) is introduced. The use of this data structure prevent from multiple XML data scans to mine association rules from a collection of XML documents. Also, cross filtering algorithm is introduced to mine frequent patterns, the algorithm reduces the number of candidate set. The performance evaluation result shows that this mechanism is powerful enough to represent both simple and complex structured association relationships inherent in XML data
Mining Maximally Common Substructures from XML Trees with Lists-Based Pattern-Growth Method
With the continuous growth in XML data sources over the Internet, the discovery of useful informa... more With the continuous growth in XML data sources over the Internet, the discovery of useful information from a col- lection of XML documents is currently one of the main re- search areas occupying the data mining community. The mostly used approach to this task is to extract frequently oc- curred subtrees in XML trees. But, because the number of frequent
EFoX: A Scalable Method for Extracting Frequent Subtrees
The more web data sources provide XML data, the greater information flood problem has been caused... more The more web data sources provide XML data, the greater information flood problem has been caused. Hence, there have been increasing demands for efficient methods of discovering desirable patterns from a large collection of XML data. In this paper, we propose a new and scalable algorithm, EFoX, to mine frequently occurring tree patterns from a set of labeled trees. The main contribution made by our algorithm is that there is no need to perform any tree join operation to generate candidate sets.
Journal of Information Science and Engineering, 2009
With the continuous growth in XML data sources over the Internet, the discovery of useful informa... more With the continuous growth in XML data sources over the Internet, 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 most commonly adopted approach to this task is to extract frequently occurring subtree patterns from XML trees. But, the number of frequent subtrees usually grows exponentially with the size of trees, and therefore, mining all frequent subtrees becomes infeasible for large size trees. A more practical and scalable alternative 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, though, and represents the core of this paper. We present a novel, conceptually simple, yet effective algorithm, called EXiT-B, that significantly simplifies the process of mining maximal frequent subtrees. This is achieved by two distinct features. First, EXiT-B represents all of string node labels of trees by some specified length of bits. Through fast bitwise operations, the process of deciding on which paths of trees contain a given node is accelerated. Second, EXiT-B avoids time-consuming tree join operations by using a specially devised data structure called PairSet. To the best of our knowledge, EXiT-B is the first algorithm that discovers maximal frequent subtrees adopting bits representation. We also demonstrate the performance of our algorithm through extensive experiments using synthetic datasets which were generated artificially by a randomized tree-structure generator.
A Simple Yet Efficient Approach for Maximal Frequent Subtrees Extraction from a Collection of XML Documents
Recently, XML is penetrating virtually all areas of computer science and information technology, ... more 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.
Mining Maximal Frequent Subtrees with Lists-Based Pattern-Growth Method
Mining maximal frequent subtrees remains at a preliminary state compared to the fruitful achievem... more Mining maximal frequent subtrees remains at a preliminary state compared to the fruitful achievements in mining frequent subtrees. Thus, most of them are fundamentally complicated and this causes computational problems. In this paper, we present a conceptually simple, yet effective approach based on lists structures. The beneficial effect of the proposed approach is that it not only gets rid of the process for infrequent tree pruning, but also eliminates totally the problem of candidate subtrees generation. As far as we know, this is the first algorithm that discovers maximal frequent subtrees without any subtree generation.
Uploads
Papers by Juryon Paik