짧은 구간을 갖는 범위 질의의 효율적인 질의 색인 기법

김재인,송명진,한대영,김대인,황부현,Kim, Jae-In,Song, Myung-Jin,Han, Dae-Young,Kim, Dae-In,Hwang, Bu-Hyun 한국정보처리학회 2009 정보처리학회논문지D Vol.16 No.4

데이터 스트림 환경에서는 지속적으로 입력되는 데이터에 대한 실시간 처리를 수행하기 위하여 범위를 갖는 다수의 질의를 시스템에 미리 등록한다. 등록된 질의를 입력 스트림에 따라 빠르게 검색하기 위해 질의 색인 기법을 사용하는데, 질의 색인은 메인 메모리 기반에서 동작하기 위해 색인 정보의 저장 비용이 낮아야 하고 빠른 질의 탐색을 실시해야 한다. 본 논문에서는 다수의 범위 질의에 대하여 색인 정보의 저장 비용이 낮고 빠른 질의 탐색을 실시하는 질의 색인 기법으로 LVC-based(Limited Virtual Construct-based) 기법을 제안한다. 해시기반으로 동작하는 LVC-based 색인 기법은 입력 스트림의 범위를 가상의 분할 구조로 나눈 LVC를 이용한다. 각 LVC는 식별자가 할당되고 각 LVC에 구간에 해당하는 범위 질의를 저장하며 색인을 실시한다. LVC-based 기법은 입력 스트림의 범위가 길고 범위가 짧은 다수의 질의를 색인할 때 저장비용과 탐색 비용에서 좋은 효율을 보이며 이는 기 제안된 CEI-based 색인 기법과의 비교를 통하여 입증하였다. In stream data processing system, generally the interval queries are in advance registered in the system. When a data is input to the system continuously, for realtime processing, a query indexing method is used to quickly search queries. Thus, a main memory-based query index with a small storage cost and a fast search time is needed for searching queries. In this paper, we propose a LVC-based(Limited Virtual Construct-based) query index method using a hashing to meet the both needs. In LVC-based query index, we divide the range of a stream into limited virtual construct, or LVC. We map each interval query to its corresponding LVC and the query ID is stored on each LVC. We have compared with the CEI-based query indexing method through the simulation experiment. When the range of values of input stream is broad and there are many short interval queries, the LVC-based indexing method have shown the performance enhancement for the storage cost and search time.

위치 기반 서비스에서 연속 범위 질의와 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.

고차원 공간 데이타를 위한 연속 범위 질의의 효율적인 처리 (pp.397-401)

장수민(Sumin Jang),유재수(Jaesoo Yoo) 한국정보과학회 2007 정보과학회 컴퓨팅의 실제 논문지 Vol.13 No.6

이동객체에 대한 연속 범위 질의(Continuous Range Query)의 응용프로그램이 급속도로 확장되면서 이차원정보를 넘어서 고차원 공간 데이타에 대한 처리를 요구하고 있다. 만약 고차원 데이타에 대한 중첩되어지는 연속 범위 질의의 정보를 기존의 색인으로 구성한다면 객체의 수와 질의의 수가 증가함에 따라 질의처리성능이 저하된다. 본 논문은 이러한 문제점을 해결하기 위하여 PAB (Projected Attribute Bit)-기반의 질의색인방법을 제안한다. 제안하는 기법은 성능향상을 위하여 질의의 정보를 각 속성 축에 투영이라는 작업을 통하여 고차원의 데이타를 1차원 정보들로 변환하고 이러한 정보를 비트단위로 구성하였다. 또한 제안하는 질의색인은 보다 효율적인 질의의 처리를 위하여 점진적인 갱신(Incremental Update)을 지원한다. 다양한 성능평가 및 분석을 통하여 제안하는 방법이 최근에 연구된 CES-기반의 질의색인 기법보다 더 나은 확장성(Scalability)을 가짐을 입증한다. Recent applications on continuous queries on moving objects are extended quickly to various parts. These applications need not only 2-dimensional space data but also high-dimensional space data. If we use previous index for overlapped continuous range queries on high-dimensional space data, as the number of continuous range queries on a large number of moving objects becomes larger, their performance degrades significantly. We focus on stationary queries, non-exponential increase of storage cost and efficient processing time for large data sets. In this paper, to solve these problems, we present a novel query indexing method, denoted as PAB (Projected Attribute Bit)-based query index. We transfer information of high-dimensional continuous range query on each axis into one-dimensional bit lists by projecting technique. Also proposed query index supports incremental update for efficient query processing. Through various experiments, we show that our method outperforms the CES(containment-encoded squares)-based indexing method which is one of the most recent research.

SPQI: 이동 환경에서 연속 범위 질의에 대한 효율적인 색인 구조

이종혁(JongHyeok Lee),정하림(HaRim Jung),윤희용(Hee Yong Youn),김응모(Ung-Mo Kim) 한국정보과학회 2015 정보과학회 컴퓨팅의 실제 논문지 Vol.21 No.1

본 논문에서는 이동객체 수의 급증에 따른 연속 범위 질의의 효율적인 처리 방법을 논한다. 각질의들은 관심 있는 (지리적)질의 영역 내의 이동객체들을 지속적으로 검색한다. 연속 범위 질의 결과를 최신으로 유지하기 위해, 이동객체들은 현재 위치를 보고하고자 서버와 지속적으로 통신해야한다. 그러나 연속 범위 질의 및 이동객체 수가 많아지면. 서버 작업량은 증가하고 막대한 통신비용 발생을 초래한다. 본 논문에서는 가용성 메모리와 연산 자원을 바탕으로 다음과 같은 문제를 해결하고자 한다. 이를 위해 Space Partitioning Query Index(SPQI)라는 질의 색인 구조를 제안한다. 이 색인 구조는 연속 범위 질의 처리에 대해, 서버가 이동객체와 효율적으로 협력하여 처리할 수 있게 함으로써 서버 작업량과 통신비용면에서 시스템 성능을 향상시킨다. 시뮬레이션을 통해 SPQI의 우수성을 검증한다. In this paper, we explore the efficient processing of continuous range queries over a huge number of moving objects, each of which retrieves the moving objects that are currently located within a geographic query region of interest. The moving objects should continually communicate with the server to report their current locations, so as to keep the results of the continuous range queries up-to-date. However, this increases the server workload and involves a enormous amount of communication as the number of continuous range queries and the moving objects becomes enormous. In this paper, we adopt an approach where we leverage available memory and computational resources of the moving objects in order to resolve these problems. To this end, we propose a query indexing structure, referred to as the Space Partitioning Query Index(SPQI), which enables the server to efficiently cooperate with the moving objects for processing continuous range queries. SPQI improves system performance in terms of server workload and communication cost. Through simulations, we show the superiority of SPQI.

이동 P2P 네트워크 환경에서 효율적인 연속 범위 질의 처리 기법

임종태(Jongtae Lim),박용훈(Yonghun Park),복경수(Kyoungsoo Bok),유재수(Jaesoo Yoo) 한국정보과학회 2012 정보과학회 컴퓨팅의 실제 논문지 Vol.18 No.4

최근 모바일 기기의 보급이 확산되면서 서버-클라이언트의 문제점을 해결하기 위해 P2P 기반 서비스가 연구되기 시작하였다. 본 논문에서는 이동 P2P 기반의 서비스를 위한 효율적인 연속 범위 질의 처리 기법을 제안한다. 제안하는 기법은 질의 배포 과정과 실제 질의를 처리하거나 변경된 질의 결과를 반영하는 과정으로 이루어진다. 질의 배포는 질의 결과에 영향을 미칠 가능성이 있는 모든 피어들에게 배포한다. 질의를 수신한 피어들은 스스로 어떤 질의에 영향을 미치는지를 계산하고 모니터링을 수행한다. 제안하는 기법에서는 질의 피어와 질의를 수신한 피어의 벡터 값을 이용하여 결과가 갱신되는 시점을 미리 계산하기 때문에 효율적으로 질의 결과를 갱신한다. 제안하는 기법의 우수성을 증명하기 위해 기본 기법과의 성능평가를 수행한다. With the development of mobile devices, P2P services have been studied to solve the problems of client-server architectures. In this paper, we propose an efficient continuous range query processing method for mobile P2P network environments. The proposed method consists of two phases. The first phase is a query distribution in which the query peer distributes the query to neighbor peers. The second phase is a result update. The peers receiving the query compute and monitor the results of range queries. Because the proposed method computes the update time in advance, it updates the result of a range query efficiently. In order to show the efficiency of the proposed method, it is compared with the existing method.

유형 속성을 포함하는 연속 범위 질의 처리

권영모,정하림,정연돈,김용성 한국정보과학회 2010 데이타베이스 연구 Vol.26 No.3

This paper addresses efficient processing of a continuous range query with type attributes, which continually monitors only the specific types of moving objects falling within a given query region. We follow a distributed continuous range query processing strategy with the notion of resident domain, where the server pushes some query processing tasks to the moving objects’ side to achieve significant savings in terms of server load as well as communication costs. We propose a novel BP-tree (Binary Partitioning tree) variant index structure called the B2P-tree (Bit-vector Binary Partitioning tree) to facilitate determining the type attributed resident domain for each moving object. The search algorithm on the B2P-tree is also discussed. Through simulation experiments, we demonstrate the superiority of our B2P-tree based method for determination of the type attributed resident domain. 본 논문은 다양한 유형의 이동 객체들 중 주어진 범위 내에 존재하는 특정 유형의 이동 객체들을 지속적으로 찾고 관리 하는 유형 속성을 포함하는 연속 범위 질의의 효율적인 처리에 대해 논한다. 특히, 서버 중심의 연산 환경에서 발생할 수 있는 서버의 병목현상 극복과 주기적인 위치 보고로 인한 이동 객체의 에너지 소비절감을 위해 이동 객체들의 연산 능력을 활용한 분산화 된 질의 처리 전략을 활용하기 위해 각각의 이동 객체가 직접 처리해야 하는 질의를 포함하는 영역인 상주 영역 (resident domain) 개념을 도입한다. 또한, 유형 속성을 고려한 상주 영역 결정 및 할당을 위해 BP-tree (Binary Partitioning tree)의 확장 변형인 B2P-tree (Bit-vector Binary Partitioning tree)를 제안하고 B2P-tree 탐색 알고리즘을 소개한다. 성능 평가를 통해 제안하는 B2P-tree를 통한 상주 영역 결정 및 할당 기법의 우수함을 보인다.

점진적인 스카이라인 영역 결정 기법

김진호(Jin-Ho Kim),박영배(Young-Bae Park) 한국정보과학회 2007 정보과학회논문지 : 데이타베이스 Vol.34 No.1

대부분의 스카이라인 질의에 대한 연구는 정적인 데이타에 관하여 이루어지고 있다. 하지만, 모바일 응용환경의 발전에 따라 이동객체에 대한 연속적인 스카이라인 질의에 대한 필요성이 증대되고 있다. 연속적인 스카이라인 질의를 처리하기 위하여 4단계 스카이라인 영역 결정 기법이 최근 제안되었지만, 이 기법은 스카이라인 영역 계산 비용이 크므로 대량의 데이타 객체에 대해서는 사용되기 힘든 문제점이 있다. 이 논문은 이러한 문제를 해결하기 위하여 먼저 4단계 영역 결정 기법에 대해서 이론적으로 분석하고, 이를 바탕으로 4 단계 영역 결정 기법을 위한 점진적인 스카이라인 영역 결정 기법을 제안한다. 제안하는 기법은 거리 기반 가지치기와 영역 결정 선분의 범위 축소 기법을 이용하여 기존 기법의 스카이라인 영역 결정 비용을 효율적으로 감소시킨다. 본 논문은 다양한 성능 시험을 통하여 제안된 기법의 효율성을 증명한다. Most of works for skyline queries have focused on static data objects. With the advance in mobile applications, however, the need of continuous skyline queries for moving objects has been increasing. To process continuous skyline queries, the 4-phased decision method of skyline regions has been proposed recently. However, it is not feasible for a large number of data because of the high cost of computing skyline regions. To solve this problem, this paper first provides a theoretical analysis of the 4-phased decision method. Then we propose a progressive decision method of skyline regions for the 4-phased decision method, which consists of a distance-based pruning and an extent shrinking of region decision lines. The proposed method can efficiently reduce the cost of the decision of skyline region in the 4-phased decision method. This paper also presents the experimental results to show the effectiveness of the proposed method.

K-최근접 질의와 비공간 속성을 결합한 효율적인 안전 영역 할당 기법

정재우(Jae-Wool Chung),김응모(Ung-Mo Kim) 한국컴퓨터정보학회 2016 한국컴퓨터정보학회 학술발표논문집 Vol.24 No.2