데이타와 질의의 이원성을 이용한 데이타스트림에서의 연속질의 처리

임효상(Hyo-Sang Lim),이재길(Jae-Gil Lee),이민재(Min-Jae Lee),황규영(Kyu-Young Whang) 한국정보과학회 2006 정보과학회논문지 : 데이타베이스 Vol.33 No.3

본 논문은 데이타스트림 환경에서 연속질의를 효율적으로 처리하는 방법을 다룬다. 먼저, 기존의 질의 처리 방법을 데이타 엘리먼트와 질의 중에서 어느 것을 먼저 선택하고 수행을 시작하느냐에 따라서, 서로 이원적인 두 가지 방법인 데이타-이니셔티브(data-initiative)와 질의-이니셔티브(query-initiative)로 분류한다. 이러한 분류는 기존의 질의 처리 연구에서 데이타와 질의를 서로 다르게(asymmetrically) 취급하였다는 것에 기인한다. 기존의 연속질의 처리에서는 이원적인 질의 처리 방법 중에서 데이타-이니셔티브 방법만이 사용되었기 때문에, 질의-이니셔티브 방법에서 얻을 수 있는 성능 상의 이점이 간과되었다. 이러한 문제를 해결하기 위해, 데이타와 질의를 동등하게(symmetrically) 볼 수 있다는 점에 착안한다. 본 논문에서는 데이타와 질의의 이원성 모델(Duality Model of Data and Queries)을 제안하고 이 모델에 기반하여 연속질의 처리 문제를 다차원 공간에서의 공간조인 문제로 변환하는 새로운 관점을 제시한다. 그리고, 공간조인 기반 연속질의 처리 알고리즘인 Spatial Join CQ를 제안한다. Spatial Join CQ는 다차원 공간상에 영역으로 표현된 데이타 엘리먼트들의 집합과 질의들의 집합으로부터 서로 겹치는 쌍을 찾음으로써 연속질의를 처리한다. 제안하는 알고리즘은 대칭적인(symmetric) 연산인 공간조인으로 겹치는 영역들을 찾아냄으로써 서로 이원적인 두 가지 질의 처리 방법의 효과를 동시에 얻는다. 성능 평가 결과, 제시하는 알고리즘은 기존의 방법에 비해서 단순 선택 연속질의는 최대 36배, 슬라이딩 윈도우 조인 연속질의는 최대 7배의 성능 향상을 보였다. In this paper, we deal with a method of efficiently processing continuous queries in a data stream environment. We classify previous query processing methods into two dual categories ? data-initiative and query-initiative ? depending on whether query processing is initiated by selecting a data element or a query. This classification stems from the fact that data and queries have been treated asymmetrically. For processing continuous queries, only data-initiative methods have traditionally been employed, and thus, the performance gain that could be obtained by query-initiative methods has been overlooked. To solve this problem, we focus on an observation that data and queries can be treated symmetrically. In this paper, we propose the duality model of data and queries and, based on this model, present a new viewpoint of transforming the continuous query processing problem to a multi-dimensional spatial join problem. We also present a continuous query processing algorithm based on spatial join, named Spatial Join CQ. Spatial Join CQ processes continuous queries by finding the pairs of overlapping regions from a set of data elements and a set of queries defined as regions in the multi-dimensional space. The algorithm achieves the effects of both of the two dual methods by using the spatial join, which is a symmetric operation. Experimental results show that the proposed algorithm outperforms earlier methods by up to 36 times for simple selection continuous queries and by up to 7 times for sliding window join continuous queries.

주식 데이타베이스에서 질의간 따름 관계를 이용한 연속 질의의 처리

하유민(You-min Ha),김상욱(Sang-Wook Kim),박상현(Sanghyun Park) 한국정보과학회 2006 정보과학회논문지 : 데이타베이스 Vol.33 No.6

본 논문에서는 주식 데이타베이스로부터 탐사된 다수의 규칙들을 이용하여 주식 투자 추천을 요구하는 대량의 연속 질의들을 효과적으로 처리하는 방안에 관하여 논의한다. 먼저, 본 논문에서는 주식투자 추천을 위한 사용자 질의의 특성을 분석함으로써 질의간에 존재하는 새로운 관계인 ‘따름 관계’를 정의한다. 두 질의 Q₁, Q₂간의 추천값 X에 대한 따름 관계는 ‘만일 선행 질의 Q₁의 추천값이 X이면, 추종질의 Q₂의 추천값은 항상 X인 관계’를 의미한다. 이러한 따름 관계가 존재하는 경우, 추종 질의 Q₂의 추천값은 선행 질의 Q₁의 추천값을 이용하여 바로 결정할 수 있으므로 Q₂를 위한 질의 처리 과정을 제거할 수 있다. 본 논문에서는 전체 사용자 질의들간의 따름 관계들을 파악하여 그래프 형태로 표현하는 방법을 제안한다. 또한, 처리 과정이 제거되는 질의들의 수가 최대가 되도록 이러한 그래프를 탐색하여 질의 처리순서를 결정하는 방법을 제안한다. 따름 관계를 기반으로 하는 제안된 방식을 이용하는 경우, 많은 사용자 질의들은 실제 질의 처리 과정이 불필요하게 되므로 전체 시스템의 처리 성능을 크게 개선할 수 있다. 실제 주가 데이타를 이용한 실험을 통하여 제안한 질의 처리 방식의 우수성을 규명한다. 실험 결과에 의하면, 제안된 방식에 의한 전체 질의 처리 시간은 기존 방식에 의한 시간의 10%이하로 줄어드는 것으로 나타났다. This paper analyzes the properties of user query for stock investment recommendation, and defines the ‘following relation’, which is a new relation between two queries. A following relation between two queries Q₁, Q₂ and a recommendation value X means ‘If the recommendation value of a preceding query Q₁ is X, then a following query Q₂ always has X as its recommendation value’. If there exists a following relation between Q₁ and Q₂, the recommendation value of Q₂ is decided immediately by that of Q₁, therefore we can eliminate the running process for Q₂. We suggest two methods in this paper. The former method analyzes all the following relations among user queries and represents them as a graph. The latter searches the graph and decides the order of queries to be processed, in order to make the number of eliminated query-running process maximized. When we apply the suggested procedures that use the following relation, most of user queries do not need to be processed directly, hence the performance of running overall queries is greatly improved. We examined the superiority of the suggested methods through experiments using real stock market data. According to the results of our experiments, overall query processing time has reduced less than 10% with our proposed methods, compared to the traditional procedure.

RFID 스트리밍 데이터 처리를 위한 연속 질의의 변환 기법

박재관,홍봉희,반재훈,Park, Jae-Kwan,Hong, Bong-Hee,Ban, Chae-Hoon 한국정보처리학회 2007 정보처리학회논문지D Vol.14 No.3

RFID 미들웨어 시스템은 애플리케이션의 질의를 처리하기 위해서 다수의 RFID 판독기에 의해 지속적으로 인식되는 RFID 스트리밍 데이터를 수집 및 정제한다. 이러한 질의들은 미들웨어에서 일정기간 동안 수행되기 때문에 연속 질의라고 불린다. 미들웨어의 성능을 개선하기 위해서는, 이러한 연속 질의를 효과적으로 처리하기 위한 색인이 필수적이다. 최근, 데이터가 아닌 질의를 기반으로 색인을 구축하는 질의 색인 기법들이 제안되었으며 이러한 기법들은 이동체 위치 스트리밍 데이터 혹은 센서 스트리밍 데이터에 대하여 연속 질의를 처리하는 환경에서 향상된 성능을 보여준다. EPCglobal은 RFID 애플리케이션을 위한 표준 질의 인터페이스인 Event Cycle Specification (ECSpec)을 제안하였다. ECSpec 기반의 연속 질의는 질의의 조건을 대상 도메인 공간에 표현하면 다수의 세그먼트로 표현되는 특징이 있다. 이러한 RFID 질의 색인의 데이터에 대하여 기존의 질의 색인을 사용하면 다수의 데이터를 삽입해야 하기 때문에 색인을 구축 및 유지하기 위한 비용이 커지게 된다. 이러한 문제를 해결하기 위해서, 이 논문에서는 다수의 세그먼트를 새로운 변환공간으로 표현하고 이것을 결집하여 단일 데이터로써 표현하는 결집 변환(Aggregate Transformation) 기법을 제안한다. 또한, 기존 질의 색인과 변환 기법을 적용한 색인의 성능을 비교한다. RFID middleware systems collect and filter the RFID streaming data gathered continuously by numerous readers in order to process requests from applications. These requests are called continuous queries because they are kept on executing during certain periods. To enhance the performance of the middleware, it is required to build an index to process the continuous queries efficiently. Several approaches of building an index on not data records but queries, called Query Index, are proposed and widely used for evaluating continuous queries over streaming data. The EPCglobal proposed an Event Cycle Specification (ECSpec) model, which is a standard query interface for RFID applications. Continuous queries based on ECSpec consist of a large number of segments for representing the query conditions. The problem with using any of the existing query indexes on these continuous queries is that it takes a long time to build the index because it is necessary to insert a large number of segments into the index. To solve this problem, we propose an Aggregate Transformation that converts a group of segments into a compressed data which is representative of the segments. We compare the performance of a transformed index with the existing query indexes.

모바일 P2P 네트워크에서 효율적인 스카이라인 질의 처리 기법

복경수(Kyoung-Soo Bok),박선용(Sun-Yong Park),김대윤(Dae-Yeon Kim),임종태(Jong-Tae Lim),신재룡(Jae-Ryong Shin),유재수(Jae-Soo Yoo) 한국콘텐츠학회 2015 한국콘텐츠학회논문지 Vol.15 No.7

본 논문에서는 모바일 P2P 환경에서 질의 처리 정확성 및 통신 비용을 향상시키기 위한 새로운 스카이라인 질의 처리 기법을 제안한다. 제안하는 기법은 사전 스카이라인 구축, 질의 배포 범위 확장 정책과 연속 스카이라인 질의 처리 과정으로 구성된다. 사전 스카이라인에서는 질의 처리 이전에 필터링 객체로 선정될 가능성을 가지고 있는 후보 객체 집합을 선정하여 질의 처리에서의 필터링 비용을 감소시킨다. 질의 배포 범위 확장 정책에서 질의 배포 범위를 확장함으로써 정확성을 향상시킨다. 또한, 최초 스카이라인 질의 처리한 후 모니터링을 수행하여 연속 스카이라인 질의를 처리한다. 제안하는 기법의 우수성을 입증하기 위해 기존 기법과 성능 평가를 수행한 결과 제안하는 기법이 기존 기법보다 우수한 성능을 보였다. In this paper, we propose a new skyline query processing scheme to enhance accuracy of query processing and communication cost in mobile P2P environments. The proposed scheme consists of three stages such as the pre-skyline processing, the query transmission range extension policy, and the continuous skyline query processing. In the pre-skyline processing, a peer selects the candidate filtering objects who have the potential to be selected. By doing so, the proposed scheme reduces the filtering cost when processing the query. In the query transmission range extension policy, we have improved the accuracy by extending the query transmission range. In addition, it can handle continuous skyline query by performing the monitoring after the first skyline query processing. In order to show the superiority of the proposed method, we compare it with the existing schemes through performance evaluation. As a result, it was shown that the proposed scheme outperforms the existing schemes.

도로망에서 연속적인 스카이라인 질의처리를 위한 효율적인 전처리기법

장수민(Sumin Jang),유재수(Jaesoo Yoo) 한국정보과학회 2009 정보과학회논문지 : 데이타베이스 Vol.36 No.4

최근에 검색서비스에서 스카이라인 질의 처리는 상당한 주목을 받고 있다. 스카이라인은 모든 속성들 측면에서 다른 객체에 지배되지 않는 관심 있는 객체들을 포함한다. 이에 관련된 기존 많은 연구들은 정적 데이터에 대한 스카이라인이거나 유클리디언 공간상에서 움직이는 대상에 대한 스카이라인 처리이다. 그러나 본 논문은 스카이라인 질의를 요청한 객체가 도로망에서 연속적으로 이동하는 것을 가정한다. 본 논문은 전처리된 객체들의 최단영역을 통하여 도로망에서 효과적인 연속적 스카이라인 질의처리를 위한 새로운 처리 기법을 제안한다. 제안하는 기법은 검색 대상에 대한 미리 연산된 최단거리 범위 데이터를 통하여 연속 스카이라인을 처리한다. 성능평가는 질의처리속도 측면에서 제안하는 기법이 기존방법보다 약 100배 정도 빠르다는 것을 보여준다. Skyline queries have recently received considerable attention in the searching services. The skyline contains interesting objects that are not dominated by any other objects on all dimensions. Many related works have processed a skyline on static data or on moving objects in Euclidean space. However, this paper assumes that the point of a skyline query continuously moves in road networks. We propose a new method that efficiently processes continuous skyline queries in road networks through pre-computed shortest range data of objects. Our experiments show that the proposed method is about 100 times faster than previous methods in terms of query processing time.

XML 스트림 데이터에 대한 연속 질의 처리 시스템

한승철,강현철,Han Seungchul,Kang Hyunchul 한국정보처리학회 2004 정보처리학회논문지D Vol.11 No.7

Streaming data processing is an area of interest with much research under way. There has been increasing attention on the demands for efficient processing of streaming data produced in the application areas such as monitoring and sensor network. We have developed a continuous query processing system for streaming data and evaluated its performance in this paper. XML, the standard for data exchange on the web, is used as the model for the streaming data and the XQuery appended with a time interval is adopted as the query language for expressing con-tinuous queries. In the proposed system, the result is produced through background processing and materialized for reute in subsequent query processing. Through a detailed set of performance experiments, we shoed the effectiveness of the proposed system. 스트림 데이터 처리는 여러 응용 분야에서 많은 관심을 가지고 활발한 연구가 수행되고 있다. 특히 모니터링, 센서 네트워크 등의 응용 분야에서 끊임없이 생성되는 대량의 스트림 데이터에 대한 효율적인 처리 요구가 높아지고 있다. 본 논문에서는 스트림 데이터에 대한 연속 질의처리 시스템 모델을 개발하고 성능을 평가한다. 스트림 데이터 모델로 웹상의 데이터 교환 표준으로 자리잡은 XML을 사용하였고 연속 질의는 XQuery에 시구간을 추가한 형태로 표현하였다. 제시된 시스템에서는 질의 처리의 성능 향상을 기하기 위해 질의 결과 값을 백그라운드 처리를 통해 생성하고 결과 값을 실체화하여 후속 질의의 결과 계산에 이용하는 기법을 제공한다. 성능 평가 실험을 통해서 XML 스트림 데이터 처리를 위한 제시한 시스템의 타당성을 보였다.

대용량 위치 데이터에서 효율적인 k-최근접 질의 처리 기법

최도진(Dojin Choi),임종태(Jongtae Lim),유승훈(Seunghun Yoo),복경수(Kyoungsoo Bok),유재수(Jaesoo Yoo) 한국콘텐츠학회 2017 한국콘텐츠학회논문지 Vol.17 No.8

스마트 기기의 대중화로 다양한 위치 기반 서비스가 제공되고 있다. 최근에는 소셜 서비스와 결합한 위치 기반 소셜 서비스들이 생겨나고 있다. 이러한 위치 기반 소셜 네트워크 서비스에서는 사용자 중심의 가장 가까운 위치를 검색하는 k-최근접 질의 처리의 요구가 증가된다. 본 논문에서는 대규모 사용자 환경에서 질의를 효율적으로 처리하기 위한 근사 k-최근접 질의 처리 기법을 제안한다. 제안하는 기법은 빅데이터 분산 처리기술을 활용하여 효율적인 스트림 처리를 수행한다. 본 논문에서는 대량의 위치 데이터에 대한 색인을 위해 전통적인 그리드 색인 기법을 변형한 색인 기법을 제안한다. 제안하는 질의 처리기법은 사용자의 진행방향을 고려하여 해당 셀을 우선적으로 탐색한다. 이를 통해 k개의 근사 결과 집합을 생성할 수 있다. 제안하는 기법의 우수성을 입증하기 위해 기존 기법과 다양한 성능 평가를 수행한다. With the growing popularity of smart devices, various location based services have been providing to users. Recently, some location based social applications that combine social services and location based services have been emerged. The demands of a k-nearest neighbors(k-NN) query which finds k closest locations from a user location are increased in the location based social network services. In this paper, we propose an approximate k-NN query processing method for fast response time in a large number of users environments. The proposed method performs efficient stream processing using big data distributed processing technologies. In this paper, we also propose a modified grid index method for indexing a large amount of location data. The proposed query processing method first retrieves the related cells by considering a user movement. By doing so, it can make an approximate k results set. In order to show the superiority of the proposed method, we conduct various performance evaluations with the existing method.

빅데이터 환경에서 연속 질의 처리를 위한 리버스 k-최근접 질의 처리 기법

임종태(Jongtae Lim),박선용(Sunyong Park),서기원(Kiwon Seo),이민호(Minho Lee),복경수(Kyoungsoo Bok),유재수(Jaesoo Yoo) 한국콘텐츠학회 2014 한국콘텐츠학회논문지 Vol.14 No.10

최근 위치 측정 기술과 모바일 기기들의 발달과 함께 위치 기반 서비스가 중요하게 연구되고 있다. 위치 기반서비스를 제공하기 위해 많은 연구자들이 맵리듀스를 활용한 다양한 질의 처리 기법을 제안하였다. 그 중에 하나가 맵리듀스를 활용한 리버스 k-최근접 질의 처리 기법이다. 하지만 기존 기법들은 연속 리버스 k-최근접 질의 처리를 수행하기 위해 많은 처리 비용이 요구된다. 본 논문에서는 맵리듀스를 활용한 효율적인 연속 리버스 k-최근접 질의 처리 기법을 제안한다. 제안하는 기법은 60도 가지치기 기법을 이용한다. 제안하는 기법은 60도 가지치기 기법을 활용하여 모니터링 영역을 생성하고 모니터링을 수행하여 결과 업데이트을 수행하기 때문에 효율적으로 결과 업데이트를 수행한다. 또한, 본 논문에서는 제안하는 기법의 우수성을 보이기 위해 기존 기법과의 성능평가를 수행한다. With the development of location aware technologies and mobile devices, location-based services have been studied. To provide location-based services, many researchers proposed methods for processing various query types with Mapreduce(MR). One of the proposed methods, is a Reverse k-nearest neighbor(RkNN) query processing method with MR. However, the existing methods spend too much cost to process the continuous RkNN query. In this paper, we propose an efficient continuous RkNN query processing method with MR to resolve the problems of the existing methods. The proposed method uses the 60-degree-pruning method. The proposed method does not need to reprocess the query for continuous query processing because the proposed method draws and monitors the monitoring area including the candidate objects of a RkNN query. In order to show the superiority of the proposed method, we compare it with the query processing performance of the existing method.

도로 네트워크에서 연속질의 처리를 지원하는 사용자 위치 정보 보호 기법

나소라(So Ra Na),유혜겸(Hye Kyeom Yoo),장재우(Jae Woo Chang) 한국정보과학회 2011 정보과학회 컴퓨팅의 실제 논문지 Vol.17 No.1

사용자에게 안전하게 위치기반 서비스를 제공하기 위해, 사용자 위치 정보 보호 방법이 요구된다. 하지만 기존 연구는 연속 질의 처리 시, 사용자의 위치 정보가 노출될 수 있는 문제점을 지닌다. 이러한 문제를 해결하기 위하여 본 논문에서는 도로 네트워크에서 연속적인 질의 처리를 지원하는 새로운 위치 정보 보호 기법을 제안한다. 제안하는 기법은 연속 질의 처리 시, 사용자의 노출 확률을 감소시키기 위해 프라이버시 보호 수준을 정의한다. 이를 통해, 기준점 이상의 사용자 개인정보 보호를 지원할 수 있다. 마지막으로 성능평가를 통해 제안하는 기법이 cloaking 영역 설정시간 및 성공 횟수 측면에서 기존 연구보다 우수함을 보인다. To provide users location-based services in a safe way, a scheme for user location protection is required But existing work has a problem of disclosing users’ locations in case of continuous query processing. To solve the problem, we, in this paper, propose a new location anonymization scheme to support continuous query processing in road network. For this, we define the level of privacy protection in order to reduce the probability of user location disclosure for continuous query processing. By using it, we can support privacy protection to a higher level than threshold. Finally, we show from a performance analysis that our scheme outperforms existing work in terms of cloaking area creation time and the number of its successes.

시공간 연속질의 처리 규칙의 고속 실행을 위한 RETE 노드의 해시 인덱싱

무하마드 하비부르 라만,홍봉희,김우찬 한국정보과학회 2021 데이타베이스 연구 Vol.37 No.2

This paper proposes a hash index for spatiotemporal continuous query processing rules for filtering, classifying, analyzing, and responding to consecutively collected target objects. The RETE technique for improving the performance of rule-based complex event processing shows better performance than the rule interpretation method because it creates a compiled data structure for the rule. When the number of rules increases, the RETE technique has a disadvantage in that the performance is degraded due to the overhead of searching for the corresponding rule for the input stream data. This paper proposes a performance improvement method that eliminates rule search overhead by creating a spatiotemporal index for RETE nodes expressing spatiotemporal continuity query rules and stabbing the RETE node of the rule by hash indexing on stream data. Through the comparison performance experiment with Drool of the RETE method, it is shown that the performance of the spatiotemporal index processing method of the RETE node outperforms the existing Drool by at least 18%. 이 논문은 연속적으로 수집되는 표적객체들의 여과, 분류, 분석, 대응을 위한 시공간 연속질의 처리 규칙에 대한 해시 인덱스를 제안한다. 규칙 기반 복합 이벤트 처리의 성능 개선을 위한 RETE 기법은 규칙에 대한 컴파일된 데이터 구조를 생성하기 때문에 규칙의 해석 방식보다 우수한 성능을 보여준다. 규칙들의 개수가 증가할 때 RETE 기법은 입력되는 스트림 데이터에 대하여 해당 규칙을 탐색해야 오버헤드 때문에 성능이 떨어지는 단점이 있다. 이 논문은 시공간 연속질의 규칙들을 표현한 RETE 노드들에 대하여 시공간 색인을 만들고, 스트림 데이터에 대한 해시 인덱싱으로 해당 규칙의 RETE 노드를 스태빙하는 방법으로 규칙의 탐색 오버헤드를 없애는 성능 개선 방법을 제안한다. RETE 기법의 Drool과 비교 성능 실험을 통하여 RETE 노드의 시공간 색인 처리 방법의 성능이 최소 18% 이상 우수함을 보인다.