조건이 있는 k-최근접 객체 질의 처리 방법

김준성,권혁윤,윤태섭,이재길 한국정보과학회 2016 데이타베이스 연구 Vol.32 No.2

Recent applications of geographical information system(GIS) need queries with attribute conditions, keyword conditions, and spatial conditions(simply, DB-spatial-keyword queries). k-Nearest neighbor queries with attribute and keyword conditions are a kind of the DB-spatial-keyword queries whose spatial condition is a k-nearest neighbor condition. A k-nearest neighbor query finds top-k spatial objects nearest to a given query point that satisfy attribute and keyword conditions. Major commercial/open-source systems that support k-nearest neighbor queries with attribute and keyword conditions can not process those queries efficiently since they do not take advantage of spatial locality of the results. In this paper, we propose three methods for efficient processing of k-nearest neighbor queries with attribute and keyword conditions. We then compare the performance of the proposed methods by the extensive experiments and show the advantages and disadvantages of performance of the proposed methods while varying the parameters. The results are the basis of the optimization of k-nearest neighbor query processing. 최근 속성 조건, 키워드 조건 및 공간 조건을 모두 가지고 있는 질의(간단히, DB-공간-키워드 질의)를 필요로 하는 지리 정보 시스템 응용들이 나타나고 있다. 조건이 있는 k-최근접 객체 질의는 k-최근접 객체 질의라는 특수한 형태의 공간 조건이 있는 DB-공간-키워드 질의이며, 지리 공간상에서 질의점에 가장 가까우면서 주어진 속성 및 키워드 조건을 만족하는 k개의 공간 객체를 찾는다. 주요 상용/공개 소스 시스템에서는조건이 있는 k-최근접 객체 질의 처리를 처리할 때 공간적 지역성을 질의 처리에 활용하지 않아 이를 항상최적으로 처리할 수 없다. 본 논문에서는 조건이 있는 k-최근접 객체 질의를 처리하는 세 가지 방법을 제안하고 이들의 성능을 분석한다. 또한 광범위한 실험을 통해 제안한 세 가지 방법의 성능을 비교하고, 이를 통하여파라메터에 따라 세 가지 방법의 장·단점을 보임으로써 조건이 있는 k-최근접 객체 질의 최적화를 위한 근거를 제시한다.

공간 네트워크 데이타베이스에서 시간제약을 고려한 경로 내 최근접 질의처리 알고리즘

김용기(Yong-Ki Kim),김상미(Sang-Mi Kim),장재우(Jae-Woo Chang) 한국정보과학회 2008 정보과학회 컴퓨팅의 실제 논문지 Vol.14 No.2

최근 공간 네트워크 데이타베이스를 위한 질의처리 알고리즘에 관한 연구가 많이 진행되어 왔으나, 경로기반 질의에 대한 연구는 매우 미흡한 실정이다. 공간 네트워크 데이타베이스에서는 이동객체가 공간 네트워크상에서만 이동하기 때문에 LBS(Location-Based Services) 및 Telematic와 같은 응용에서는 경로-기반 질의가 매우 유용하게 사용된다. 따라서 본 논문에서는 경로-기반 질의의 대표적인 방법인 경로 내 최근접(In-Route Nearest Neighbor, IRNN) 질의처리 알고리즘을 분석하고, 시간 제약을 지닌 새로운 경로 내 최근접 질의처리 알고리즘을 제안한다. 아울러, 성능 분석을 통하여 시간 제약을 지닌 제안하는 질의처리 알고리즘이 기존 경로 내 최근접 질의처리 알고리즘에 비하여 검색 성능이 우수함을 보인다. Recently, the query processing algorithm in spatial network database (SNDB) has attracted many interests. However, there is little research on route-based query processing algorithm in SNDB. Since the moving objects moves only in spatial networks, the route-based algorithm is very useful for LBS and Telematics applications. In this paper, we analyze In-Route Nearest Neighbor (IRNN) query, which is an typical one of route-based queries, and propose a new IRNN query processing algorithm with time constraint. In addition, we show from our performance analysis that our IRNN query processing algorithm with time constraint is better on retrieval performance than the existing IRNN query processing one.

위치 기반 서비스에서 연속 범위 질의와 k-최근접 질의 처리에 대한 조사

이성민(Sungmin Yi),정하림(HaRim Jung),정연돈(Yon Dohn Chung),이기용(Ki Yong Lee) 한국정보과학회 2011 정보과학회논문지 : 데이타베이스 Vol.38 No.1

최근 위치기반 정보 서비스는 GPS를 탑재한 스마트폰의 대중화 및 다양한 무선통신 기술의 발달에 힘입어 새로운 성장 국면을 맞이하고 있다. 본 논문에서는 효과적인 위치기반 정보 서비스 제공의 초석이 될 수 있는 위치 기반 질의 처리 기법 동향을 소개·분석한다 (본 논문에서 소개하는 연속 공간 범위 질의 기법들은 VCI, Q-Indexing, MQM, MobiEyes, P2P-MQM, 연속 k-최근접 질의 기법들은 Yu-CNN, SEA-CNN, CPM, iSEE, disMKNN, P2P-MQM이다). 특히, 질의 및 데이터의 위치 변화에 따라 지속적으로 질의 결과의 유효성을 검증하고 새로운 결과를 신속하고 에너지 효율적으로 제공하기 위한 연속 위치기반 질의 처리 기법에 초점을 맞추어 진행한다. 또한, 기존의 위치기반 질의의 한계점과 향후 연구 방향을 제시한다. With the wide spread of smart phones and the development of wireless communication technologies, the popularity of location-based information services has recently gained momentum. In this paper, we study on the methods of processing location-based queries, which are one of the core building blocks for supporting location based information services (This paper covers the following methods - VCI, Q-Indexing, MQM, MobiEyes, and P2P-MQM for continuous spatial range queries, and Yu-CNN, SEA-CNN, CPM, iSEE, disMKNN, and P2P-MQM for continuous k-NN queries). In particular, we focus on the methods for fast and energy-efficient processing of continuous location-based queries, which require continual re-evaluation as their results become easily invalid due to the movement of queries and/or data. In addition, we present a new research direction inspired by the limitations of existing work.

효율적인 최근접 질의 처리를 위한 Voronoi 다이어그램 기반 그리드 검색 구조

권동섭(Dongseop Kwon) 한국컴퓨터정보학회 2008 韓國컴퓨터情報學會論文誌 Vol.13 No.1

최근접 질의(nearest-neighbor query)는 멀티미디어 시스템이나 GIS 시스템과 같은 여러 가지 응용 분야에서 사용되는 중요한 질의 처리 기법 중 하나이다. 최근접 검색 기법들을 위한 다양한 연구가 제안되었으나 이러한 기법들은 질의 수행 시 데이터를 검색하여 최근접 질의를 처리하므로 성능의 한계가 있었다. 본 논문에서는 정적인 데이터에 대하여 Voronoi 다이어그램을 이용한 전처리를 통하여 최근접 질의의 결과를 미리 계산하고 이 결과를 그리드 기반 검색 구조를 이용하여 저장하는 기법을 제안한다. 이 기법은 데이터 자체를 색인하는 기존의 기법과는 달리, 질의의 결과를 미리 색인하므로 대량의 데이터에 대해서도 기존의 기법보다 빠르게 최근접 질의를 처리할 수 있다. Nearest-neighbor searches are essential operations in various applications such as multimedia systems and GIS systems. Although numbers of research works for nearest-neighbor search have been proposed, they have a limitation on the performance since they process queries on the fly with indexes on data. This paper proposes a new nearest-neighbor search algorithm based on a grid-based data structure, which preprocesses and stores the result of nearest-neighbor queries using Voronoi diagrams over static data. While traditional techniques try to index data itself, the proposed technique attempts to index the result of the queries. Therefore, it performs nearest-neighbor queries more efficiently.

질의 결과를 이용한 거리 브라우징 질의의 처리

박동주,박상원,정태선,이상원,Park Dong-Joo,Park Sangwon,Chung Tae-Sun,Lee Sang-Won 한국정보처리학회 2005 정보처리학회논문지D Vol.12 No.5

k-최근접 질의와 같은 거리 브라우징 질의는 지리정보시스템(GIS)과 같은 공간 데이터베이스 응용에서 아주 중요한 질의이다. 최근 GIS 응용은 웹과 같은 다중 사용자 환경으로 확장되고 있는 추세이다. 이러한 질의를 처리하기 위한 많은 기법들 중에서 Hjaltason과 Samet이 제안한 알고리즘이 가장 우수하지만, 하나의 질의 처리에 대해서만 최적화가 이루어졌다. 따라서 다중 사용자 환경에 적합하도록 이러한 기법들을 보완할 필요성이 있다. 이전에 처리된 질의 결과를 캐쉬에 저장해 두고(즉, 질의 결과 캐슁 기법) 후속 질의를 처리할 때 질의 결과를 이용하는 (즉, 질의 결과 매칭 기법) 것은 하나의 좋은 접근 방법이라 할 수 있다. 본 논문은 다중 사용자 GIS 환경에서 거리 브라우징 질의를 효율적으로 처리하기 위해서 캐쉬된 이전 질의 결과를 재사용할 수 있도록 보완된 Hjaltason & Samet의 알고리즘을 제안한다. 실험 결과를 통해 우리의 접근 방법이 효율적임을 보인다. Distance browsing queries, namely k-nearest neighbor queries, are the most important queries in spatial database applications, e.g., Geographic Information Systems(GISs). Recently, GIS applications trends to extend themselves toward wide multi-user environments such as the Web. Since many techniques for such queries, where Hjaltason and Samet's algorithm is the most efficient one, were optimized for only one query, we need to complement them suitable for multi-user environments. It can be a good approach that we store many individual query results in a cache, i.e., query result caching and reuse them in evaluating incoming queries, j.e., query result matching. In this paper, we propose a complementary Hjaltason and Samet's algerian capable of reusing previous query results in a cache for answering distance browsing queries in multi-user GIS environments. Our experimental results conform the efficiency of our approach.

시야각으로 한정된 최근접 질의

이성민(Sungmin Yi),정연돈(Yon Dohn Chung),박준표(Jun Pyo Park),정하림(HaRim Jung) 한국정보과학회 2012 정보과학회 컴퓨팅의 실제 논문지 Vol.18 No.1

In many location based services with augmented reality, it is critical to provide valuable data to users of diverse interests based on their locations as well as their view-fields. This paper introduces a novel type of spatial queries, which we call the View Field Nearest Neighbor (VFNN) query. Given a user's view-field, VFNN finds the nearest data object that falls within the users' view-field. In this paper, we utilize the R*-tree, one of the most representative index structures, to index spatial data objects and search VFNN in an efficient manner. In particular, we employ (i) MINDIST to compute the minimum possible distance from a query point (i.e., user's location) to each data object and (ii) min_angle (max_angle), which is the starting (ending) angle in the user's view-field boundary, for pruning unnecessary search paths in the R*-tree. Finally, we conduct the simulation experiments to investigate the performance of the proposed VFNN search algorithm. 최근 많은 관심을 받고 있는 증강현실 위치기반 서비스와 같이 사용자의 한정된 시야각이 존재하는 상황에서 사용자가 원하는 데이터를 효과적으로 제공하기 위하여 본 논문에서는 새로운 위치기반 질의인 시야 최근접 질의 (VFNN: View Field Nearest Neighbor Query)를 소개한다. VFNN 질의는 사용자의 시야각 또는 한정된 각내에 위치하는 가장 가까운 데이터를 검색한다. 본 논문에서 제안하는 VFNN 질의 처리 알고리즘은 가장 널리 활용되고 있는 공간 데이터 색인 구조인 R*-tree를 사용한다. 특히, 질의 점과 MBR 사이의 최소거리인 MINDIST뿐만 아니라, 질의 점과 MBR 사이의 최대 각, 최소 각을 정의한다. 이를 활용하여 R*-tree 탐색 시 질의 결과 값을 포함하지 않는 노드들을 연산에서 제외하여 질의 처리의 효율성을 향상시킨다. 마지막으로 실험을 통하여 VFNN 질의 처리 알고리즘의 성능을 평가한다.

도로 네트워크에서 사용자 정보 보호를 지원하는 질의영역에 대한 k-최근접 질의 처리 알고리즘

김형일(Hyeongil Kim),유혜겸(Hyekyeom Yoo),장재우(Jaewoo Chang) 한국정보과학회 2012 정보과학회논문지 : 데이타베이스 Vol.39 No.1

최근 무선 통신 기술의 발달 및 모바일 기기의 발달로 인하여 위치 기반 서비스가 주목을 받고 있다. 그러나 사용자의 정확한 위치정보를 통해 위치 기반 서비스 서버에 질의를 요청하는 것은 심각한 개인 정보 누출의 위협이 될 수 있기 때문에, 사용자 정보 보호를 위해 도로 네트워크를 고려하여 질의영역을 생성하는 연구가 활발히 진행되어 왔다. 따라서 질의영역에 대한 효율적인 질의 처리 방법이 요구된다. 이를 위해, 본 논문에서는 도로 네트워크에서 사용자 정보 보호를 지원하는 질의영역에 대한 k-최근접 질의 처리 알고리즘을 제안한다. 제안하는 기법은 POI(Point Of Interest)를 효율적으로 검색하기 위하여 Island 인덱스를 사용한다. 또한, 본 논문은 질의 처리 성능을 향상시키기 위해 적응적 Island 인덱스를 생성하는 방법을 제안한다. 마지막으로, 성능평가를 통해 제안하는 기법이 기존 기법들에 비해 네트워크 확장 비용 및 서비스 시간 측면에서 우수함을 보인다. Recent development in wireless communication technologies and mobile equipments are making location-based services (LBSs) popular. However, since requesting queries to LBS servers by using users' exact locations could make the privacy of the users in danger, many researches have been studied on generating query region for the user privacy protection, specially in road networks. Therefore, an efficient query processing mechanism for the query region is required. In this paper, we propose a k-nearest neighbor query processing algorithm for a query region supporting user privacy protection in road networks. The proposed scheme uses the Island index to efficiently retrieve POIs. This paper also proposes the method that generate the Adaptive Island index which could improve the performance of the query processing. Finally, we show from our performance analysis that our query processing schemes outperform the existing schemes in terms of network expansion cost and service time.

모바일 객체의 방향성을 고려한 최근접 질의 처리

이응재,정영진,최현미,류근호,이성호,Lee, Eung-Jae,Jung, Young-Jin,Choi, Hyon-Mi,Ryu, Keun-Ho,Lee, Seong-Ho 한국공간정보학회 2004 개방형지리정보시스템학회 논문지 = Journal of the Korea Open Geogr Vol.6 No.1

최근접 질의 (NN: Nearest Neighbor Query)는 질의요청자와 가상 가까운 곳에 위치한 대상 객체를 검색하기 위한 질의로서, 모바일 환경에서 빈번하게 사용되는 질의 유형이다. 이 논문에서는 모바일 환경에서 방향 성분을 가지며 연속적으로 이동하는 질의 요청자가 요구하는 최근접 대상 객체를 검색하기 위한 질의 처리 방법을 제안한다. 제안된 방법은 모바일 환경에서 특정 방향 성분을 갖고 위치를 이동하는 질의요청자의 방향 속성을 반영하여 최근접 객체를 검색할 수 있도록 유클리디안 거리 정보뿐만 아니라 사용자의 진행 방향을 고려하여 최근섭 대상 객체를 검색한다. 제안된 방법은 모바일 환경에서 최근섭 객체의 검색 기능을 요구하는 교통 정보 시스템, 관광정보 시스템, 위치 기반 추천 시스템과 같은 응용 분야에 적용할 수 있다. Nearest neighbor query retrieves nearest located target objects, and is very frequently used in mobile environment. In this paper we propose a novel neatest neighbor query processing technique that is able to retrieve nearest located target object from the user who is continuously moving with a direction. The proposed method retrieves objects using the direction property of moving object as well as euclidean distance to target object. The proposed method is applicable to traffic information system, travel information system, and location-based recommendation system which require retrieving nearest located object.

단일방송채널환경에서 k-최근접질의 처리를 위한 힐버트 곡선과 최소영역 사각형 기반의 분산 공간 인덱싱 기법

이정형(Junghyung Yi),정성원(Sungwon Jung) 한국정보과학회 2010 정보과학회논문지 : 데이타베이스 Vol.37 No.4

본 논문은 단일무선방송채널환경에서 힐버트곡선과 최소영역사각형을 이용하여 공간데이터를 방송하고 이를 가지고 k-최근접질의 처리를 효과적으로 처리하는 기법에 관한 논문이다. 기존 방식은 k-최근 접질의 처리시 백트랙킹문제가 발생하여 질의처리에 오랜 시간이 걸리거나 검색범위를 빠르게 줄이지 못하여 많은 정보를 수신해야 하는 단점이 존재하였다. 제안하는 방법은 공간데이터를 힐버트 곡선 순서대로 방송하되 방송중인 공간데이터를 제외한 나머지 공간데이터를 최소영역사각형으로 그룹화하고 이를 인덱스 테이블로 구성하는 방법이다. 그리고 이를 이용하여 클라이언트가 알려지지 않은 데이터의 위치를 예측하여 빠르게 검색범위를 줄여나가 불필요한 정보를 제거하여 적은 튜닝시간과 접근지연시간을 갖도록 하는 것이다. This paper deals with an efficient index scheduling technique based on Hilbert curve and MBR for k-NN query in a single wireless broadcast channel environment. Previous works have two major problems. One is that they need a long time to process queries due to the back-tracking problem. The other is that they have to download too many spatial data since they can not reduce search space rapidly. Our proposed method broadcasts spatial data based on Hilbert curve order where a distributed index table is also broadcast with each spatial data. Each entry of index table represents the MBR which groups spatial data. By predicting the unknown location of spatial data, our proposed index scheme allows mobile clients to remove unnecessary data and to reduce search space rapidly. As a result, our method gives the decreased tuning time and access latency.

공간 네트워크 데이터베이스에서 공간 제약을 고려한 경로 내 최근접 질의처리 알고리즘

김용기,김아름,장재우,Kim, Yong-Ki,Kim, Ah-Reum,Chang, Jae-Woo 한국공간정보학회 2008 한국공간정보시스템학회 논문지 Vol.10 No.3

최근 공간 네트워크 데이터베이스를 위한 질의처리 알고리즘에 관한 연구가 많은 관심을 받고 있으나, 경로-기반 질의에 대한 연구는 매우 미흡한 실정이다. 공간 네트워크 데이터베이스에서는 이동객체가 공간 네트워크상에서만 이동하기 때문에, 위치기반 서비스 및 텔레매틱스의 응용을 지원하기 위해 경로 내 최근접(In-Route Nearest Neighbor : IRNN) 질의와 같은 경로-기반 질의에 대한 효율적인 질의처리 알고리즘 연구가 필수적이다. 그러나 기존 경로 내 최근접 질의처리 알고리즘은 도로내의 병목현상을 반영하지 못하는 문제점이 존재한다. 따라서 본 논문에서는 공간제약을 고려한 경로 내 최근접 질의처리 알고리즘을 제안한다. 마지막으로, 기존 알고리즘과의 성능 비교를 통하여 제안하는 알고리즘이 우수함을 보인다. Recently, the query processing algorithm in the field of spatial network database(SNDB) has been attracted by many Interests. But, there is little research on route-based queries. Since the moving objects move only in spatial networks, the efficient route-based query processing algorithms, like in-route nearest neighbor(IRNN), are essential for Location-based Service(LBS) and Telematics application. However, the existing IRNN query processing algorithm has a problem that it does not consider traffic jams in the road network. In this thesis, we propose an IRNN query processing algorithm which considers space restriction. Finally, we show that space-constrained IRNN query processing algorithm is efficient compared with the existing IRNN algorithm.