Digital Library[ Search Result ]
An Efficient Continuous Subgraph Matching Technique for Graph Stream Processing in a Memory-constrained Environment
Somin Lee, Sanghyeuk Kim, Hyeonbyeong Lee, Dojin Choi, Jongtae Lim, Kyoungsoo Bok, Jaesoo Yoo
http://doi.org/10.5626/JOK.2022.49.12.1154
Recently, with the proliferation of social network services, the size of graph data has been becoming increasingly vast and graph data are changed in real-time. Therefore, it is necessary to perform continuous query processing on real-time graph streams. Moreover, it is difficult keep the entire large graph data in the main memory since its size is constrained in real-world application environments. Consequently, continuous subgraph matching techniques are required by considering memory-constrained environments. In this paper, we propose a continuous subgraph matching technique for graph streams in a memory-constrained environment. The proposed technique consists of modules such as index manager, query processor, and cache manager for efficient continuous subgraph matching. We conduct performance evaluations to demonstrate the superiority of the proposed technique.
Partially Collective Spatial Keyword Query Processing Based on Spatial Keyword Similarity
Ah Hyun Lee, Sehwa Park, Seog Park
http://doi.org/10.5626/JOK.2021.48.10.1142
Collective spatial keyword queries return Points of Interest (POI), which are close to the query location and contain all the presented set of keywords. However, existing studies only consider a fixed number of query keywords, which is not adequate to satisfy the user. They do not care about the preference of a partial keyword set, and a flexible keyword set needs to be selected for the preference of each POI. We thus propose a new query, called Partially Collective Spatial Keyword Query, which flexibly considers keywords that fit the preference for each POI. Since this query is a combinatorial optimization problem, the query processing time increases rapidly as the number of POIs increases. Therefore, to address these problems, we propose a keyword-based search technique that reduces the overall search space. Furthermore, we propose heuristic techniques, which include the linear search-based terminal node pruning technique, approximation algorithm, and threshold-based pruning technique.
An Efficient Continuous Subgraph Matching Scheme Considering Data Reuse
Dojin Choi, Kyoungsoo Bok, Jaesoo Yoo
http://doi.org/10.5626/JOK.2019.46.8.842
With an increase in the utilization of graph streams in various applications, a continuous subgraph matching scheme is required to search the subgraphs that undergo changes in real time. In this paper, we propose an efficient continuous subgraph matching scheme that reuses indexing and performs distributed processing in graph stream environments. In order to perform distributed processing, we propose a query decomposition method based on the degree and subsequently manage the decomposed subqueries as an index. The proposed scheme reuses indexing information to reduce the load on the index caused by the environment in which multiple queries are entered. We also conduct query allocation through a cost model that calculates the indexing load of each server. For efficient performance of distributed processing in stream environments, the proposed scheme was implemented in Storm. Various performance evaluations were conducted to demonstrate the superiority of the proposed scheme.
Route Recommendation based on Dynamic User Preference on Road Networks
http://doi.org/10.5626/JOK.2019.46.1.77
The current location based services provide maps and nearby information, or provide a route to a specific destination. A route recommendation system recommends the best route that suits the evaluation criteria for each user. The existing personalized path recommendation system recommends the route under the assumption that the user’s preference is constant regardless of the change of the time zone. However, there is a problem in that it does not reflect requirements that important factors to users can be different for each time zone, such as importance of moving distance in morning time and importance of risk in late time. In this paper, we propose a Dijkstra algorithm considering time attributes to overcome this limitation. In addition, we suggest an efficient algorithm that can search the path reflecting the change of the weight of the preference factor according to the time zone using the G-tree index structure that effectively expresses the road network.
kNN Query Processing Algorithm based on the Encrypted Index for Hiding Data Access Patterns
Hyeong-Il Kim, Hyeong-Jin Kim, Youngsung Shin, Jae-woo Chang
In outsourced databases, the cloud provides an authorized user with querying services on the outsourced database. However, sensitive data, such as financial or medical records, should be encrypted before being outsourced to the cloud. Meanwhile, k-Nearest Neighbor (kNN) query is the typical query type which is widely used in many fields and the result of the kNN query is closely related to the interest and preference of the user. Therefore, studies on secure kNN query processing algorithms that preserve both the data privacy and the query privacy have been proposed. However, existing algorithms either suffer from high computation cost or leak data access patterns because retrieved index nodes and query results are disclosed. To solve these problems, in this paper we propose a new kNN query processing algorithm on the encrypted database. Our algorithm preserves both data privacy and query privacy. It also hides data access patterns while supporting efficient query processing. To achieve this, we devise an encrypted index search scheme which can perform data filtering without revealing data access patterns. Through the performance analysis, we verify that our proposed algorithm shows better performance than the existing algorithms in terms of query processing times.
A MapReduce-based kNN Join Query Processing Algorithm for Analyzing Large-scale Data
HyunJo Lee, TaeHoon Kim, JaeWoo Chang
Recently, the amount of data is rapidly increasing with the popularity of the SNS and the development of mobile technology. So, it has been actively studied for the effective data analysis schemes of the large amounts of data. One of the typical schemes is a Voronoi diagram based on kNN join algorithm (VkNN-join) using MapReduce. For two datasets R and S, VkNN-join can reduce the time of the join query processing involving big data because it selects the corresponding subset Sj for each Ri and processes the query with them. However, VkNN-join requires a high computational cost for constructing the Voronoi diagram. Moreover, the computational overhead of the VkNN-join is high because the number of the candidate cells increases as the value of the k increases. In order to solve these problems, we propose a MapReduce-based kNN-join query processing algorithm for analyzing the large amounts of data. Using the seed-based dynamic partitioning, our algorithm can reduce the overhead for constructing the index structure. Also, it can reduce the computational overhead to find the candidate partitions by selecting corresponding partitions with the average distance between two seeds. We show that our algorithm has better performance than the existing scheme in terms of the query processing time.
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