Digital Library[ Search Result ]
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.
Graph-based Wi-Fi Radio Map Construction and Update Method
http://doi.org/10.5626/JOK.2017.44.6.643
Among Wi-Fi based indoor positioning systems, fingerprinting localization is the most common technique with high precision. However, construction of the initial radio map and the update process require considerable labor and time effort. To address this problem, we propose an efficient method that constructs the initial radio map at each vertex based on a graph. In addition, we introduce a method to update the radio map automatically by mapping signal data acquired from users to the reference point created on each edge. Since the proposed method collects signal data manually only at the vertex of the graph to build the initial radio map and updates it automatically, our proposed method can dramatically reduce labor and time effort, which are the disadvantages of the conventional fingerprinting method. In our experimental study, we show validity of our radio map update method by comparing with the actual reference point data. We also show that our proposed method is able to construct the radio map with an accuracy of about 3.5m by automatically updating the radio map.
A Fingerprint Verification System Based on Fuzzy Vault and Steganography for Smartphone
Han-Sol Nam, Ae-Young Kim, Sang-Ho Lee
This paper proposes a fingerprint verification system on a fuzzy vault with steganography for a smartphone. While biometric-based authentication can provide strong security, the biometric data must be handled carefully as it cannot be re-enrolled when it is revealed to other people. When the transformed data is used for authentication, the original biometric data can be protected. In this paper, we combine a fingerprint verification system with a fuzzy vault scheme to protect the fingerprint data of a smartphone user. In addition, the transformed data using a fuzzy vault scheme increases the security as it is concealed by the steganography scheme. The result of the experiment using fingerprint databases shows that the proposed scheme provides a high level of convenience and security for authentication of a smartphone having with a fingerprint sensor.
Multi-Level Sequence Alignment : An Adaptive Control Method Between Speed and Accuracy for Document Comparison
Jong-kyu Seo, Haesung Tak, Hwan-Gue Cho
Finger printing and sequence alignment are well-known approaches for document similarity comparison. A fingerprinting method is simple and fast, but it can not find particular similar regions. A string alignment method is used for identifying regions of similarity by arranging the sequences of a string. It has an advantage of finding particular similar regions, but it also has a disadvantage of taking more computing time. The Multi-Level Alignment (MLA) is a new method designed for taking the advantages of both methods. The MLA divides input documents into uniform length blocks, and then extracts fingerprints from each block and calculates similarity of block pairs by comparing the fingerprints. A similarity table is created in this process. Finally, sequence alignment is used for specifying longest similar regions in the similarity table. The MLA allows users to change block’s size to control proportion of the fingerprint algorithm and the sequence alignment. As a document is divided into several blocks, similar regions are also fragmented into two or more blocks. To solve this fragmentation problem, we proposed a united block method. Experimentally, we show that computing document’s similarity with the united block is more accurate than the original MLA method, with minor time loss.
Parallel Rabin Fingerprinting on GPGPU for Efficient Data Deduplication
Jeonghyeon Ma, Sejin Park, Chanik Park
Rabin fingerprinting used for chunking requires the largest amount computation time in data deduplication, In this paper, therefore, we proposed parallel Rabin fingerprinting on GPGPU for efficient data deduplication. In addition, for efficient parallelism in Rabin fingerprinting, four issues are considered. Firstly, when dividing input data stream into data sections, we consider the data located near the boundaries between data sections to calculate Rabin fingerprint continuously. Secondly, we consider exploiting the characteristics of Rabin fingerprinting for efficient operation. Thirdly, we consider the chunk boundaries which can be changed compared to sequential Rabin fingerprinting when adapting parallel Rabin fingerprinting. Finally, we consider optimizing GPGPU memory access. Parallel Rabin fingerprinting on GPGPU shows 16 times and 5.3 times better performance compared to sequential Rabin fingerprinting on CPU and compared to parallel Rabin fingerprinting on CPU, respectively. These throughput improvement of Rabin fingerprinting can lead to total performance improvement of data deduplication.
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