Digital Library[ Search Result ]
An Approximate k-Nearest Neighbor Query Processing Method Based on a Dynamic Partitioning Grid Index in Distributed Processing Environments
Dojin Choi, Jongtae Lim, Kyoungsoo Bok, Jaesoo Yoo
http://doi.org/10.5626/JOK.2018.45.8.838
As smart devices continue to grow in popularity, various location-based services are increasingly provided to users. Some location-based social applications that combine social services and location-based services have a large number of users. The demands of a k-nearest neighbors (k-NN) query, which finds the k closest locations from a user location, are increased in services such as these. In this paper, we propose an approximate k-NN query processing method for real time response requirements for a dynamic partition based grid index. The proposed approximate k-NN query processing method first retrieves the related cells by considering a user movement. Then, we optimize cell searches in the dynamic partitioning method and grid index for the improvement of the accuracy of the proposed approximate k-NN query. The proposed method is implemented in Storm to perform efficient distributed processing in stream environments. In order to show the superiority of this method, we conduct various performance evaluations.
An Efficient Algorithm for Monitoring Continuous Top-k Queries
JaeHee Jang, HaRim Jung, YougHee Kim, Ung-Mo Kim
In this study, we propose an efficient method for monitoring continuous top-k queries. In contrast to the conventional top-k queries, the presented top-k query considers both spatial and non-spatial attributes. We proposed a novel main-memory based grid access method, called Bit-Vector Grid Index (BVGI). The proposed method quickly identifies whether the moving objects are included in some of the grid cell by encoding a non-spatial attribute value of the moving object to bit-vector. Experimental simulations demonstrate that the proposed method is several times faster than the previous method and uses considerably less memory.
Grid-based Index Generation and k-nearest-neighbor Join Query-processing Algorithm using MapReduce
MapReduce provides high levels of system scalability and fault tolerance for large-size data processing. A MapReduce-based k-nearest-neighbor(k-NN) join algorithm seeks to produce the k nearest-neighbors of each point of a dataset from another dataset. The algorithm has been considered important in bigdata analysis. However, the existing k-NN join query-processing algorithm suffers from a high index-construction cost that makes it unsuitable for the processing of bigdata. To solve the corresponding problems, we propose a new grid-based, k-NN join query-processing algorithm. Our algorithm retrieves only the neighboring data from a query cell and sends them to each MapReduce task, making it possible to improve the overhead data transmission and computation. Our performance analysis shows that our algorithm outperforms the existing scheme by up to seven-fold in terms of the query-processing time, while also achieving high extent of query-result accuracy.
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