Digital Library[ Search Result ]
Graph Structure Learning: Reflecting Types of Relationships between Sensors in Multivariate Time Series Anomaly Detection
http://doi.org/10.5626/JOK.2024.51.3.236
Sensors are used to monitor systems in various fields, such as water treatment systems and smart factories. Anomalies in the system can be detected by analyzing multivariate time series consisting of sensor data. To efficiently detect anomalies, information about the relationships between sensors is required, but this information is generally difficult to obtain. To solve this problem, the previous work used sensor data to identify relationships between sensors, which were then represented using a graph structure. However, in this process, the graph structure only reflects the presence of relationships between sensors, not the types of relationships between sensors. In this pap er, we considered the types of relationships between sensors in graph structure learning and analyzed multivariate time series to detect anomalies in the system. Experiments show that improving detection accuracy in graph structure learning for multivariate time series anomaly detection involves taking into account the different kinds of relationships among sensors.
Algorithms for the k-Scaled Order-Preserving Pattern Matching Problem
Kyung Bin Park, Youngho Kim, Joong Cha Na, Jeong Seop Sim
http://doi.org/10.5626/JOK.2022.49.8.585
Two strings of the same length are order-isomorphic if the relative orders of their characters are the same. Given text T of length n and pattern P of length m, the order-preserving pattern matching problem is to find all substrings of T that are order-isomorphic to P. Order-preserving pattern matching can be used to analyze time-series data such as stock indices and melodies. In this paper, we defined the k-scaled order-preserving pattern matching problem and proposed an O(n+mlogm)-time algorithm for the problem. We also proposed a parallel algorithm for the problem, which runs in O(m+k) time using O(n+m) threads.
Knowledge Graph Embedding for Link Prediction using Node-Link Interaction-based Graph Attention Networks
http://doi.org/10.5626/JOK.2022.49.7.555
Knowledge graphs are structures that express knowledge in the real world in the form of nodes and links-based triple form. These knowledge graphs are incomplete and many embedding techniques have been studied to effectively represent nodes and links in low-dimensional vector spaces to find other missing relationships. Recently, many neural network-based knowledge graph link prediction methods have been studied. However existing models consider nodes and links independently when determining the importance of a triple to a node which makes it difficult to reflect the interaction between nodes and links. In this paper, we propose an embedding method that will be used to analyze the importance of triple units by simultaneously considering nodes and links using composition operators, and at the same time prove that the model outperforms other methods in knowledge graph link prediction.
Parallel Implementation of the Order-Preserving Multiple Pattern Matching Algorithm using the Karp-Rabin Algorithm
Kyung Bin Park, Youngho Kim, Jeong Seop Sim
http://doi.org/10.5626/JOK.2021.48.3.249
When two strings of the same length have the same relative orders, they are called order-isomorphic. Given a text T(｜T｜=n)and a set of patterns P̃={P₁,P₂,...,Pk}, the order-preserving multiple pattern matching problem is to find all substrings of T that are order-isomorphic to any pattern in P̃ . Let m be the length of the shortest pattern, m̅ be the length of the longest pattern, and M be the sum of lengths of all the patterns in P̃. When M is polynomial with respect to m, an order-preserving multiple pattern matching algorithm using the Karp-Rabin algorithm was presented whose searching step runs in O(n) time on average. In this paper, we implemented an order-preserving multiple pattern matching algorithm using the Karp-Rabin algorithm in parallel. It runs in O(m̅) time on average using O(M) threads in the preprocessing step and runs in O(m) time on average using O(n) threads in the searching step. The experimental results for random strings as input showed that our parallel implementation performed approximately 201.5 times faster than the existing sequential algorithm when n=1,000,000, k=1,000, m=5.
Parallel Computation of Order-Preserving Periods and Order-Preserving Borders of a Set of Strings
http://doi.org/10.5626/JOK.2019.46.12.1232
Given two strings of the same length over an integer alphabet, those two strings are order-isomorphic when they have the same relative ranks. When strings order-isomorphic to T[1..p](1 ≤ p ≤ n) are periodically repeated in T, a representation of the order relations of T[1..p] is referred to as an order-preserving period of T. When a prefix T[1..q] (1 ≤ q ≤ n) of T is order-isomorphic to a suffix T[n-q+1..n] of T, a representation of the order relations of T[1..q] is called an order-preserving border of T. The lengths of all order-preserving periods (resp. all order-preserving borders) of T can be computed in O(n logn) time using the Z-function. Given a set Ŝ=｛S₁, S₂,..., Sr｝of strings of length n over an integer alphabet, we propose parallel algorithms computing the lengths of all order-preserving periods and all order-preserving borders of Ŝ using O(rn) threads in O(n) time by the Z-function. When compared to each sequential algorithm for Dow Jones Industrial Average, the experimental results show that our parallel algorithm for computing the lengths of all order-preserving periods (resp. all order-preserving borders) of Ŝ runs approximately 3.47 (resp. 3.41) times faster when r =1,000, n =10,000.
Partial Movement Authoring for a Reconfigurable Motion Capture
Seonghun Kim, Yangkyu Lim, Youngho Kim, Youngho Chai
http://doi.org/10.5626/JOK.2019.46.10.989
Research on human motion perception has progressed along with the development of technology. The demand for the gesture recognition is increasing daily. In motion capture, data on each part of the body are acquired by using a sensor or camera in order to realize a natural movement as an actual motion. However, it is inefficient to use the sensor every time motion data must be obtained or to make repeat measures because of slight differences in motion. In addition, various problems must be solved in order to transfer the stored data to another person or modify it use for another action.
In this paper, we studied the trends of motion recognition research and analyzed characteristics of the motion reproduction method using keyframe animation and the Labanotation motion recording method. In addition, we proposed an action authoring method which addresses the disadvantages of the existing methods. By visualizing and recording the pattern of partial motions in the units of the images, it is possible to reconstruct other motions, including the meaning of the motion.
Parallel Algorithms for the Boxed-Mesh Permutation Pattern Matching Problem
Jihyo Choi, Youngho Kim, Joong Chae Na, Jeong Seop Sim
http://doi.org/10.5626/JOK.2019.46.4.299
Given a text T(|T|= n) and a pattern P(|P|= m), the boxed-mesh permutation pattern matching problem asks to find all boxed subsequences of T that are order-isomorphic to P. In this paper we present two parallel algorithms for the problem. We first propose an O(nm) -time parallel algorithm using O(n) threads and then propose an O(n)-time algorithm using O(nm) threads. The experimental results for Daw Jones Industrial Average show that our first and second algorithms run approximately 7.2 times and 20.6 times, respectively, faster compared to the sequential algorithm using order-statistics trees when n = 36,364 and m = 30.
An Order-Preserving Pattern Matching Algorithm using Fingerprints of Two q-grams
Gwangmo Yoo, Youngho Kim, Jeong Seop Sim
http://doi.org/10.5626/JOK.2018.45.11.1111
Given a text T of length n and a pattern P of length m, the order-preserving pattern matching problem is to find all substrings in T that have the same relative orders as P. Recently, an O(nm+nqlogq+q!)-time order-preserving pattern matching algorithm was proposed that uses fingerprints of q-grams. In this paper, we propose an order-preserving pattern matching algorithm using the fingerprints of two q-grams to improve execution times. The experimental results for randomly generated T (n = 5,000,000) and P (m = 5,10,15) show that our algorithm runs up to approximately 12% faster than the previous algorithm. Also, for T using Dow Jones Industrial Average (n = 34,658) and P (m = 5,10,15) randomly extracted from T, our algorithm runs up to approximately 10% faster than the previous algorithm.
Parallel Computation of Z-Function for Order-Preserving Pattern Matching and Order-Preserving Multiple Pattern Matching
Youkun Shin, Youngho Kim, Jeong Seop Sim
http://doi.org/10.5626/JOK.2018.45.8.778
Given a text T of length n and a pattern P of length m, the order-preserving pattern matching problem is to find all substrings in T which are order-isomorphic to P. Given a text T of length n and a set of patterns W={P₁, P₂,…, Pb}, the order-preserving multiple pattern matching problem is to find all substrings in T which are order-isomorphic to patterns of W. In this paper, we present two parallel algorithms based on the Z-function. The first algorithm for the order-preserving pattern matching problem runs in O(m) time using O(n+hm) threads and the second algorithm for the order-preserving multiple pattern matching problem runs in O(n+M) time using O(b(n+M)) threads, where h is the number of blocks and M is the length of the longest pattern in W. Experimental results show that our parallel algorithm for the order-preserving pattern matching problem is approximately 71.2 times faster than the sequential algorithm when m=10 and n=1,000,000, and that our parallel algorithm for the order-preserving multiple pattern matching problem is approximately 12.2 times faster than the sequential algorithm when b=1,000, m=10, and n=1,000.
Parallel Algorithms for Finding δ-approximate Periods and γ-approximate Periods of Strings over Integer Alphabets
http://doi.org/10.5626/JOK.2017.44.8.760
Repetitive strings have been studied in diverse fields such as data compression, bioinformatics and so on. Recently, two problems of approximate periods of strings over integer alphabets were introduced, finding minimum δ-approximate periods and finding minimum γ-approximate periods. Both problems can be solved in O(n²) time when n is the length of the string. In this paper, we present two parallel algorithms for solving the above two problems in O(n²) time using O(n²) threads, respectively. The experimental results show that our parallel algorithms for finding minimum δ-approximate (resp. γ-approximate) periods run approximately 19.7 (resp. 40.08) times faster than the sequential algorithms when n = 10,000.
Search
Journal of KIISE
- ISSN : 2383-630X(Print)
- ISSN : 2383-6296(Electronic)
- KCI Accredited Journal
Editorial Office
- Tel. +82-2-588-9240
- Fax. +82-2-521-1352
- E-mail. chwoo@kiise.or.kr