+

KR100828404B1 - 경계관찰질의를 이용한 데이터 스트림 처리 방법 - Google Patents

경계관찰질의를 이용한 데이터 스트림 처리 방법 Download PDF

Info

Publication number
KR100828404B1
KR100828404B1 KR1020060040879A KR20060040879A KR100828404B1 KR 100828404 B1 KR100828404 B1 KR 100828404B1 KR 1020060040879 A KR1020060040879 A KR 1020060040879A KR 20060040879 A KR20060040879 A KR 20060040879A KR 100828404 B1 KR100828404 B1 KR 100828404B1
Authority
KR
South Korea
Prior art keywords
query
data stream
node
bmq
index
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
KR1020060040879A
Other languages
English (en)
Other versions
KR20070108616A (ko
Inventor
이진원
이영기
강승우
이상정
진현주
김병집
송준화
Original Assignee
한국과학기술원
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 한국과학기술원 filed Critical 한국과학기술원
Priority to KR1020060040879A priority Critical patent/KR100828404B1/ko
Priority to US11/741,923 priority patent/US7895188B2/en
Publication of KR20070108616A publication Critical patent/KR20070108616A/ko
Application granted granted Critical
Publication of KR100828404B1 publication Critical patent/KR100828404B1/ko
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F16/33—Querying
    • G06F16/3331—Query processing
    • G06F16/334—Query execution

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Computational Linguistics (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Computer Hardware Design (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

본 발명은 경계관찰질의(BMQ : Border Monitoring Query)를 이용한 데이터 스트림 처리 방법에 관한 것이다. 더 구체적으로는 특정의 데이터 스트림이 특정의 질의영역 경계를 가로 지나는 경우에 대하여 정보처리를 함으로써 복수의 데이터 스트림과 복수의 질의들에 대하여 효율적으로 정보 처리를 하는 방법에 관한 것이다.
종래의 기술은 영역관찰질의(RMQ : Region Monitoring Query)에 관한 것이었다.
본 발명에서는 경계관찰질의를 이용한 데이터 스트림 처리를 위한 기술적 사상으로서,
중앙처리장치, BMQ-색인을 저장하고 있는 데이터 베이스 및 데이터 스트림 센서를 포함하는 시스템에서,
상기 센서에서 특정 데이터 스트림을 인식하는 단계; 상기 중앙처리장치에서 상기 데이터 스트림에 대한 ID를 확인한 후, 이를 상기 BMQ-색인에 등록되어 있는 데이터 스트림인지를 검사하고 등록된 것임을 확인하는 단계; 상기 중앙처리장치에서 상기 데이터 스트림에 대한 새로운 노드 포인터를 설정하는 단계; 상기 중앙처리장치에서 상기 BMQ-색인을 이용하여 상기 데이터 스트림에 대한 새로운 정보를 처리하는 단계; 및 상기 중앙처리장치에서 상기 설정된 새로운 노드 포인터를 데이터베이스화하여 상기 데이터 스트림에 대한 기존의 BMQ-색인을 갱신하는 단계를 포 함하는 경계관찰질의를 이용한 데이터 스트림 처리 방법을 제시한다.
영역관찰질의, 경계관찰질의, 데이터 스트림

Description

경계관찰질의를 이용한 데이터 스트림 처리 방법 { Processing method of data stream using Border Monitoring Query }
도 1은 본 발명의 실시예가 적용되는 지역기반광고의 예시도이다.
도 2는 본 발명의 실시예에 따른 일차원 BMQ-색인의 구성도이다.
도 3은 본 발명의 실시예에 따른 일차원 BMQ-색인의 점진식 검색 알고리즘을 보여주는 그림이다.
도 4는 본 발명의 실시예에 따른 이차원 BMQ-색인의 구성도이다.
도 5는 본 발명의 실시예에 따른 이차원 BMQ-색인의 검색 알고리즘의 흐름도이다.
도 6은 본 발명의 실시예에 따른 교차검사 알고리즘을 나타내는 그림이다.
도 7은 본 발명의 실시예에 따른 시스템의 개략적인 구성도이다.
도 8은 본 발명의 실시예에 따른 질의의 변동에 의한 BMQ-색인을 갱신하기 위한 흐름도이다.
도 9는 본 발명의 실시예에 따른 경계관찰질의를 이용한 데이터 스트림을 처리하기 위한 흐름을 설명하는 흐름도이다.
＜도면의 주요 부분에 대한 부호의 설명＞
100 : 일차원 BMQ- 색인 101 : 스트림 테이블
102 : 영역조각 리스트 103 : 등록된 BMQ들
200 : 이차원 BMQ-색인 201 : 스트림 테이블
202 : 영역조각-X리스트 203 : 영역조각-Y리스트
204 : 질의 테이블 701 : 중앙처리장치
702 : 데이터베이스 703 : 데이터 스트림 센서
704 : 입력장치 705 : 출력장치
본 발명은 경계관찰질의를 이용한 데이터 스트림 처리 방법에 관한 것이다. 좀 더 자세하게는 특정의 데이터 스트림이 특정의 질의영역 경계를 가로 지나는 경우에 대하여 정보처리를 함으로써 복수의 데이터 스트림과 복수의 질의들에 대하여 효율적으로 정보 처리를 하는 방법에 관한 것이다.
미래 정보통신환경의 한 가지 중요한 특징은 대부분의 응용분야에서 엄청난 양의 데이터들이 연속적으로 생성된다는 것이다. 예를 들면, 수많은 모바일 사용자나 자동차로부터 위치정보가 연속적으로 생성되고 이외에도 센서, RFID등의 다양한 종류의 장치들로부터 데이터들이 연속적으로 생성된다. 이를 가리켜 데이터 스트림(Data Stream)이라고 한다. 이때 사용자들은 이러한 데이터 스트림을 관찰하고 필요할 경우 적절한 행동을 취하기 위해서 다수의 구간질의나 필터를 시스템에 등록한다. 시스템에서 데이터 스트림에 대해 연속적으로 실행되는 이러한 질의를 연 속질의(Continuos Query)라 한다.
데이터 스트림 관찰에 있어 주요한 관심 중에 하나는 데이터 스트림이 연속구간질의를 언제 만족하기 시작하고 끝나느냐이다. 많은 경우에 사용자들은 데이터 스트림이 구간 안에 들어갔는지 아닌지에 대해서 관심이 많다. 그래서 시스템은 구간조건을 만족하는 모든 데이터들을 보고하는 것보다는 구간조건을 만족하기 시작할 때와 끝날 때만을 보고하는 것으로 충분하다. 또한, 시작과 끝 정보는 자동으로 적절한 행동을 시동하거나 끝내기를 원하는 사용자에게 있어서 매우 중요하다. 우리는 이러한 새로운 종류의 연속구간질의(Continuos Range Query)를 경계관찰질의(BMQ: Border Monitoring Query)라고 부른다.
종래의 데이터 스트림에 대한 연속구간질의는 영역관찰질의(RMQ: Region Monitoring Query)에 관한 것이다. RMQ는 질의 영역안에 매칭되는 모든 데이터를 보고한다. 이에 따라 데이터 처리에 많은 메모리 공간이 필요하였다. 반면, BMQ는 질의 영역에 들어오거나 나갈 때만 사용자에게 보고한다.
또한 종래의 기술은 효율적인 RMQ처리를 위한 방법만을 제시했을 뿐 다수의 BMQ처리를 위한 특별한 방법은 전혀 제안하지 않았다.
본 발명은 상술한 문제점을 해결하기 위한 것으로서, 본 발명의 목적은 특정 질의 영역 경계를 지나갈 때의 정보만을 처리함으로써 복수의 데이터 스트림을 효율적으로 처리함과 동시에 복수의 질의에 대하여도 효율적으로 처리할 수 있는 방법을 제공함에 있다.
상술한 목적을 달성하기 위하여 본 발명에 대한 이론적 접근을 설명하면 다음과 같다.
본 발명에 대한 이론적 목적은 BMQ의 의미정의와 확장을 제안하고 다수의 BMQ를 효율적으로 처리하는 질의색인을 제공하는 데 있다. 본 발명은 첫째, BMQ의 의미를 정의하고 확장을 제안한다. 둘째, 다수의 BMQ를 공유식 및 점진식으로 처리하는 일차원 BMQ-색인을 제안한다. BMQ-색인은 다수의 BMQ를 공유식 처리를 통해 높은 수준의 확장성을 지원한다. 또한, 연속적인 BMQ처리를 점진식으로 함으로써 상당히 가속화시킨다. 이러한 주 아이디어를 기반으로 일차원 BMQ-색인구조(100)와 검색알고리즘(도 3)을 제안한다. 일차원 색인은 질의경계들로 가능한 데이터 영역(Domain Space)을 영역조각(Region Segment)들로 나눈다. 이때 질의는 질의 구간이 시작하고 끝나는 영역조각에만 저장한다. 데이터가 들어올 때, 데이터가 질의경계를 가로지른 질의들만을 점진적으로 찾는다. 이때 검색은 이전에 들어온 데이터에 매칭된 영역조각에서부터 현재 들어온 데이터에 매칭된 영역조각으로 선형횡단을 통해 이루어진다. 셋째, 우리는 일차원 BMQ-색인을 확장하여 다차원 BMQ-색인(200)을 제안한다. 이때 다차원 검색처리(도 5)를 위해서 교차검사 알고리즘(cross-check algorithm)(도 6)을 제안한다.
이와 같은 이론적 접근을 기반으로 하여 상술한 본 발명의 목적을 달성하기 위한 본 발명의 기술적 사상으로서,
본 발명에서는 중앙처리장치, BMQ-색인을 저장하고 있는 데이터 베이스 및 데이터 스트림 센서를 포함하는 시스템에서,
상기 센서에서 특정 데이터 스트림을 인식하는 단계; 상기 중앙처리장치에서 상기 데이터 스트림에 대한 ID를 확인한 후, 이를 상기 BMQ-색인에 등록되어 있는 데이터 스트림인지를 검사하고 등록된 것임을 확인하는 단계; 상기 중앙처리장치에서 상기 데이터 스트림에 대한 새로운 노드 포인터를 설정하는 단계; 상기 중앙처리장치에서 상기 BMQ-색인을 이용하여 상기 데이터 스트림에 대한 새로운 정보를 처리하는 단계; 및 상기 중앙처리장치에서 상기 설정된 새로운 노드 포인터를 데이터베이스화하여 상기 데이터 스트림에 대한 기존의 BMQ-색인을 갱신하는 단계를 포함하는 경계관찰질의를 이용한 데이터 스트림 처리 방법을 제시한다.
이하에서는 본 발명의 실시예에 대하여 첨부한 도면을 참조하면서 그 구성 및 작용에 대하여 상세히 설명하기로 한다.
우선, 본 발명의 구체적인 실시예를 설명하기에 앞서 본 발명의 이론적 기반에 대하여 설명하면 다음과 같다.
첫 번째로, 경계관찰질의(BMQ)에 대한 의미 정의 및 그 확장에 대하여 알아본다.
많은 스트림 기반 응용프로그램에서는 매우 많은 수의 스트림들을 구간질의로 연속적으로 관찰한다. 이 경우에 어떤 스트림이 구간조건을 만족하기 시작하거나 끝났는지를 아는 것은 매우 중요하다. 이는 사용자가 대게 연속적인 데이터 스트림이 구간조건을 만족했는지 아닌지에 관심 있기 때문이다. 그래서 사용자들은 만족하는 모든 이벤트를 알기보다는 구간조건만족의 시작과 끝만을 아는 것만으로 충분하다(시나리오 2 참조). 또한, 구간조건만족의 시작과 끝은 자동으로 필요한 행동을 시동하거나 끝내거나 하는데 매우 유용하다(시나리오 1, 2 참조). 이뿐만 아니라 시작과 끝을 연계해 구간조건을 만족하는 시간을 쉽게 알아내어 활용할 수 있다(시나리오 3 참조). 마지막으로, 처리 관점에서는 만족하는 모든 이벤트 대신에 시작과 끝만을 알리는 것은 네트워크 대역폭을 크게 절약해 준다.
먼저 경계관찰의 예제 시나리오를 제시한다.
<시나리오1: 금융거래>
NASDAQ의 경우를 생각해보자. 수천의 회사들에서 주식가격과 같은 데이터 스트림이 생성된다. 또한, 수백만의 주식투자가들은 각자의 질의를 통해 그것들을 관찰할 수 있다. 어떤 주식투자자가 IBM 주식을 40달러 이하로 떨어지면 사고 50달러 이상이 되면 파는 과정을 자동으로 하기를 원한다고 가정해보자. 이때 그 투자자에게는 지정한 경계값을 넘어가거나 내려갈 때 알려주는 것이 매우 유용하다.
<시나리오 2: 지역기반 광고>
도 1에서처럼 많은 식당과 카페 및 주유소들은 각 가게근처의 사람들에게 점심메뉴를 광고하거나 할인쿠폰을 보내려고 한다. 이러한 지역기반 서비스를 위해서는 사람들의 위치정보 스트림을 관찰해서 지정한 영역을 들어오거나 나가는 사람들을 빨리 찾아내는 것이 필요하다. 이때, 사람들은 같은 광고를 한번이상 받는 것을 싫어하기 때문에 이미 지정한 영역 안에 있는 사람들을 찾을 필요는 없다.
<시나리오 3: 주차관리>
도시의 길가 및 건물에는 많은 수의 주차금지지역과 유료주차장이 존재한다. 이를 관리하는 지역정부는 차들의 위치정보 스트림을 모니터링하여 주차위반을 감시하거나 자동으로 주차장영역에 있는 동안만을 과금하려고 한다. 이러한 주차관리시스템을 위해서는 차들이 언제 주차영역에 들어오고 나갔는지를 경계관찰로 확인해야 한다. 이를 통해 각각의 자동차가 특정 주차영역에 얼마나 머물렀는지를 쉽게 알아내어 각 주차영역별 규칙을 적용해 주차위반을 판단하거나 주차시간에 따라 자동으로 과금한다.
다음으로 BMQ의 의미를 정의한다. 위의 경계관찰 시나리오에서 구간질의의 의미는 일반적인 데이터 스트림 처리에서 구간질의의 의미와는 다르다. 이러한 질의를 구분하기 위해서 우리는 연속구간질의를 두 가지 형식으로 구분한다. 즉, 경계관찰질의 (BMQ:Border Monitoring Queries)와 영역관찰질의 (RMQ:Region Monitoring Queries)로 구분한다. 기존의 데이터 스트림 처리에서의 연속구간질의는 RMQ에 속한다. 즉, 질의 영역 안에 있는 모든 데이터를 보고하는 질의이다. BMQ는 질의 영역의 경계를 가로지르는 데이터만을 보고하는 질의이다. 데이터 집합에 대한 형식적인 BMQ의 정의는 다음과 같다. RSet(t-1)는 바로 전 갱신시간 t-1에서의 질의 영역 안에 포함된 데이터를 의미한다. RSet(t)는 현재 갱신시간 t에서의 그것이다. 이때 BMQ의 결과로 두개의 데이터 집합이 정의된다.
< 정의 1. 경계관찰질의 >
RSetBMQ+(t) = RSet(t) - RSet(t-1)
RSetBMQ-(t) = RSet(t-1) - RSet(t)
마지막으로 BMQ의 확장을 제안한다. 기본적으로 BMQ의 확장은 BMQ결과에 대 한 집계를 제공하는 것이다. 이때, BMQ결과는 윈도우로 제한되는 것으로 가정한다(예: 지난 24시간의 BMQ결과 또는 지난 100개의 BMQ결과). 이렇게 윈도우로 BMQ결과의 크기를 제한한 후 집계를 하는 이유는 시간에 따라서 BMQ결과가 계속 생성되기 때문에 이를 한정하기 위해서이다.
집계하는 방식으로 크게 두 가지를 제안한다. 첫째는 COUNT이다. 이는 BMQ 결과로 나오는 데이터 스트림들의 개수를 세는 것이다. BMQ 결과에 대한 COUNT는 네 가지 방식이 가능하고 각각의 고유의미는 다음과 같다.
Figure 112006031977210-pat00001
위의 BMQ 기반의 COUNT는 구간조건을 만족하는 데이터 스트림들이 어떻게 변해 가는지를 집계 관찰하는데 있어 매우 유용하다. 예를 들어 KAIST 캠퍼스영역을 오고가는 차들을 집계 관찰한다고 가정해보자. 이때 차들은 자신의 위치를 데이터 스트림 형태로 시스템에 업데이트한다. (1) COUNT(RSetBMQ+(t))을 통해 KAIST로 얼마나 차들이 들어오는지를 쉽게 알 수 있다. (2) COUNT(RSetBMQ-(t))을 통해 KAIST에서 얼마나 차들이 나가는지도 쉽게 알 수 있다. (3) COUNT(RSetBMQ+(t)) - COUNT(RSetBMQ-(t))을 통해 KAIST내의 차가 늘어나는지 줄어드는지를 쉽게 알 수 있다. 이 값이 양수이면 차가 늘어나고 있다는 것을 의미하고 반대로 음수이면 차가 줄어들고 있다는 것을 의미한다. (4) COUNT(RSetBMQ+(t)) + COUNT(RSetBMQ-(t))을 통해 KAIST에 얼마나 많은 차가 오고 가는지를 알 수 있다. 이 값이 크면 클수록 많은 차들이 KAIST로 오고간다는 것을 의미한다.
BMQ 결과에 대해 집계하는 두 번째 방식은 시간기반 집계이다. BMQ 결과에는 세 가지의 중요한 시간정보가 내포되어 있다. 즉, 데이터 스트림이 구간조건을 만족하기 시작한 시각(begin time), 끝난 시각(end time), 그리고 시작과 끝을 연계해 구간조건을 만족한 시간(time interval)을 내포한다. 이들을 집계하면 매우 유용한 정보를 얻어낼 수 있다. 특히, 각각의 시간정보에 대해 MIN(최소값), MAX(최대값), AVG(평균값), Bottom-k(하위 k개), Top-k(상위 k개)의 다섯 가지 집계 방식이 가능하다. 다음 표는 각각의 경우 고유의미를 정리한 것이다.
Figure 112006031977210-pat00002
예를 들어 하루 동안 KAIST 캠퍼스영역을 오고가는 교직원들의 위치들을 시간적 집계 관찰한다고 가정해보자. 이때 교직원들은 자신의 위치를 데이터 스트림 형태로 시스템에 업데이트한다. (1)begin time을 통해 KAIST로 가장 빨리 출근한 시각(MIN), 가장 늦게 출근한 시각(MAX), 평균출근시각(AVG), 가장 일찍 출근한 k명(Bottom-k), 가장 늦게 출근한 k명(Top-k)을 찾아낼 수 있다. (2)end time을 통해 KAIST에서 가장 빨리 퇴근한 시각(MIN), 가장 늦게 퇴근한 시각(MAX), 평균 퇴근시각(AVG), 가장 일찍 퇴근한 k명(Bottom-k), 가장 늦게 퇴근한 k명(Top-k)을 찾아낼 수 있다. (3)time interval을 통해 KAIST에 가장 짧게 근무한 시간(MIN), 가장 오래 근무한 시간(MAX), 평균근무시간(AVG), 가장 짧게 근무한 k명(Bottom-k), 가장 오래 근무한 k명(Top-k)을 찾아낼 수 있다.
두 번째로, 일차원 BMQ-색인의 구조와 그 처리에 대하여 알아본다.
< 색인 구조 >
일차원 BMQ-색인(100)은 스트림 테이블(101)과 영역조각 리스트 (RS 리스트: 102)의 두 개의 데이터 구조로 구성된다. 스트림 테이블은 각 데이터 스트림에 대해 가장 최근 데이터가 위치했던 RS노드를 가리키는 노드 포인터를 가지고 있다. 데이터 스트림이 여러 개의 소스에서 동시에 입력되는 경우 각 데이터 스트림은 Stream_ID로 구별된다. 스트림 테이블 항목들은 Stream_ID에 대해 해시되어 있기 때문에 데이터 스트림 구별 작업은 Ο(1)으로 빨리 처리된다.
RS 리스트는 다음 같이 정의된다. Q =
Figure 112006031977210-pat00003
를 연속구간질의의 집합이라고 하 자. 질의
Figure 112006031977210-pat00004
는 (
Figure 112006031977210-pat00005
,
Figure 112006031977210-pat00006
) 구간을 가진다. B를 집합 Q 에 있는 질의
Figure 112006031977210-pat00007
구간의 하단(Lower Bound)과 상단(Upper Bound)의 집합이라고 하자. 즉, B = { b | b는 임의의
Figure 112006031977210-pat00008
의
Figure 112006031977210-pat00009
또는
Figure 112006031977210-pat00010
이다. 단
Figure 112006031977210-pat00011
∈ Q } ∪ { ∞ }. 집합 B의 원소는 원소 값의 오름차순으로 아래 첨자가 할당된다. 즉,
Figure 112006031977210-pat00012
<
Figure 112006031977210-pat00013
< … <
Figure 112006031977210-pat00014
<
Figure 112006031977210-pat00015
.
RS 리스트는 RS 노드들의 리스트이다 - <
Figure 112006031977210-pat00016
,
Figure 112006031977210-pat00017
, …,
Figure 112006031977210-pat00018
,
Figure 112006031977210-pat00019
>. RS노드
Figure 112006031977210-pat00020
는 (
Figure 112006031977210-pat00021
,
Figure 112006031977210-pat00022
,
Figure 112006031977210-pat00023
)를 갖는다.
*
Figure 112006031977210-pat00024
는 영역조각의 구간 (
Figure 112006031977210-pat00025
,
Figure 112006031977210-pat00026
)이다.
Figure 112006031977210-pat00027
∈ B
*
Figure 112006031977210-pat00028
는 질의
Figure 112006031977210-pat00029
의 구간 (
Figure 112006031977210-pat00030
,
Figure 112006031977210-pat00031
)에 대해
Figure 112006031977210-pat00032
=
Figure 112006031977210-pat00033
를 만족하는 질의들의 집합이다.
*
Figure 112006031977210-pat00034
는 질의
Figure 112006031977210-pat00035
의 구간 (
Figure 112006031977210-pat00036
,
Figure 112006031977210-pat00037
)에 대해
Figure 112006031977210-pat00038
=
Figure 112006031977210-pat00039
를 만족하는 질의들의 집합이다.
RS 노드는 두 개의 델타질의집합인
Figure 112006031977210-pat00040
과
Figure 112006031977210-pat00041
을 갖는다.
Figure 112006031977210-pat00042
는
Figure 112006031977210-pat00043
의 하단과 동일한 하단을 갖는 질의들의 집합이다. 즉,
Figure 112006031977210-pat00044
=
Figure 112006031977210-pat00045
이면
Figure 112006031977210-pat00046
∈
Figure 112006031977210-pat00047
. 마찬가지로, 질의
Figure 112006031977210-pat00048
의 상단과
Figure 112006031977210-pat00049
의 하단과 동일할 때 질의
Figure 112006031977210-pat00050
는 집합
Figure 112006031977210-pat00051
의 원소가 된다. 즉,
Figure 112006031977210-pat00052
=
Figure 112006031977210-pat00053
이면
Figure 112006031977210-pat00054
∈
Figure 112006031977210-pat00055
.
도 2에는 5개의 BMQ에 대해 RS 리스트가 만들어져 있다. 그리고 9개의 RS 노드가 생성되었다. 각 노드는 구간과 집합
Figure 112006031977210-pat00056
를 가진다. 예를 들어,
Figure 112006031977210-pat00057
는 구간 (
Figure 112006031977210-pat00058
,
Figure 112006031977210-pat00059
)와 { }인
Figure 112006031977210-pat00060
, { Q₃}인
Figure 112006031977210-pat00061
를 가진다.
< 질의 등록과 해지 >
질의는 동적으로 BMQ-색인에 등록되거나 해지될 수 있다. 구간이 (
Figure 112006031977210-pat00062
,
Figure 112006031977210-pat00063
)인 질의
Figure 112006031977210-pat00064
는 다음 같은 절차로 등록된다. 첫째, BMQ-색인은 질의의 하단
Figure 112006031977210-pat00065
을 포함하는 구간 (
Figure 112006031977210-pat00066
,
Figure 112006031977210-pat00067
)를 갖는 RS노드
Figure 112006031977210-pat00068
를 찾는다. 즉,
Figure 112006031977210-pat00069
≤
Figure 112006031977210-pat00070
<
Figure 112006031977210-pat00071
.
Figure 112006031977210-pat00072
이
Figure 112006031977210-pat00073
과 동일하면
Figure 112006031977210-pat00074
을
Figure 112006031977210-pat00075
의
Figure 112006031977210-pat00076
에 넣는다. 그렇지 않으면,
Figure 112006031977210-pat00077
는 RS노드 두 개로 나뉘어 진다. 왼쪽 노드의 구간은 (
Figure 112006031977210-pat00078
,
Figure 112006031977210-pat00079
)가 되고
Figure 112006031977210-pat00080
와 동일한 ± DQSet을 가진다. 오른쪽 노드의 구간은 (
Figure 112006031977210-pat00081
,
Figure 112006031977210-pat00082
)가 되고 +DQSet에
Figure 112006031977210-pat00083
을 포함한다. 둘째, BMQ-색인은 질의의 상단
Figure 112006031977210-pat00084
을 포함하는 구간(
Figure 112006031977210-pat00085
,
Figure 112006031977210-pat00086
)을 갖는 RS노드
Figure 112006031977210-pat00087
를 찾는다. 즉,
Figure 112006031977210-pat00088
≤
Figure 112006031977210-pat00089
<
Figure 112006031977210-pat00090
.
Figure 112006031977210-pat00091
이
Figure 112006031977210-pat00092
과 동일하면
Figure 112006031977210-pat00093
을
Figure 112006031977210-pat00094
의
Figure 112006031977210-pat00095
에 넣는다. 그렇지 않으면,
Figure 112006031977210-pat00096
는 RS노드 두 개로 나뉘어 진다. 왼쪽 노드의 구간은 (
Figure 112006031977210-pat00097
,
Figure 112006031977210-pat00098
)가 되고
Figure 112006031977210-pat00099
와 동일한 ± DQSet을 가진다. 오른쪽 노드의 구간은 (
Figure 112006031977210-pat00100
,
Figure 112006031977210-pat00101
)가 되고 -DQSet에
Figure 112006031977210-pat00102
을 넣는다.
구간이 (
Figure 112006031977210-pat00103
,
Figure 112006031977210-pat00104
)인 질의
Figure 112006031977210-pat00105
는 다음 같은 절차로 해지된다. 첫째, 질의 구간의 하단
Figure 112006031977210-pat00106
과 동일한 하단을 갖는 RS노드
Figure 112006031977210-pat00107
를 찾아서 그 노드의
Figure 112006031977210-pat00108
에서
Figure 112006031977210-pat00109
을 삭제한다. 만약
Figure 112006031977210-pat00110
과
Figure 112006031977210-pat00111
이 공집합이 되면 노드
Figure 112006031977210-pat00112
를 노드
Figure 112006031977210-pat00113
와 합친다. 둘째, 질의 구간의 상단
Figure 112006031977210-pat00114
과 동일한 하단을 갖는 RS노드
Figure 112006031977210-pat00115
를 찾아서 그 노드의
Figure 112006031977210-pat00116
에서
Figure 112006031977210-pat00117
을 삭제한다. 만약 +DQSetj과 -DQSetj이 공집합이 되면 노드
Figure 112006031977210-pat00118
를 노드
Figure 112006031977210-pat00119
와 합친다.
< 공유식 처리 >
경계관찰 시나리오에서 사용자들이 많은 수의 BMQ를 요청할 수 있다. 이때, 높은 수준의 확장성을 달성하기 위해서는 BMQ의 공유식 처리가 필수적이다. 이를 위해 BMQ-색인은 질의색인방법을 채택하였다. 등록된 BMQ들을 바탕으로 BMQ색인이 생성되면 결과와 관련 없는 질의는 접근하지 않고 관련 있는 질의만을 빨리 찾을 수 있다.
데이터 스트림의 튜플( 스트림 ID, 스트림 소스에서 측정된 값인 value, 값이 측정된 시간을 갖는다고 가정한다)이 들어오면 BMQ-색인은 두개의 질의집합을 추출한다. 즉, 한 데이터 스트림의 연속적인 두 튜플의 value를
Figure 112006031977210-pat00120
과
Figure 112006031977210-pat00121
라 하면 (1) QSet+(t): 현재 데이터 값
Figure 112006031977210-pat00122
에는 매칭 되지만 이전 데이터 값
Figure 112006031977210-pat00123
에는 매칭 안되는 질의들의 집합 (2) QSet-(t): 현재 데이터 값
Figure 112006031977210-pat00124
에는 매칭 안되지만 이전 데이터 값
Figure 112006031977210-pat00125
에는 매칭되는 질의들의 집합. 우리는 이 두개의 질의 집합을 차이질의집합(Differential Query Set)이라고 부른다.
< 점진식 처리 >
연속적인 데이터 스트림에 대해 BMQ처리를 하기 위해서는 연속적으로 차이질의집합을 추출하는 과정이 필요하다. 이러한 연속적인 연산은 대량의 데이터 스트림이 빠르게 들어오는 상황에서 매우 큰 처리 비용을 유발한다.
이러한 연속적인 연산을 가속화하기 위해 BMQ-색인은 점진식 처리방식을 채택한다. 첫째, BMQ-색인은 델타질의정보만을 저장한다. BMQ-색인은 가능한 데이터 값의 범위인 데이터 영역(Domain Space)을 영역조각(Region Segment)들로 나눈다. 그리고 질의 구간이 시작하고 끝나는 영역조각에만 질의 ID를 저장한다. 각 영역조각에 저장된 질의는 델타질의(Delta Query)라고 부른다. 둘째, BMQ-색인은 이전 데이터에 매칭된 영역조각으로부터 현재 데이터에 매칭된 영역조각까지 선형횡단을 통해 차이질의집합을 점진적으로 추출한다. 차이질의는 방문하는 영역조각에 저장되어 있는 델타질의로부터 쉽게 얻을 수 있다.
점진식 처리방식을 기반으로 연속적인 BMQ처리는 상당히 가속화된다. 데이터 스트림의 지역성 때문에 새로 들어온 데이터 튜플은 이전과 동일한 영역조각에 매칭될 가능성이 높다. 이렇게 되면 간단한 비교 연산만이 필요하다. 그렇지 않은 경우에도 새로 들어온 데이터 튜플은 이전 영역조각 근처의 영역조각에 매칭될 가능성이 높다. 따라서 적은 수의 영역조각 방문만으로도 차이질의들을 빨리 찾아낼 수 있다.
< 점진식 검색 알고리즘 >
BMQ-색인에서 차이질의집합은 각 노드가 가지는 델타질의집합에서 효율적으로 검색할 수 있다. 연속적인 두 데이터 값
Figure 112006031977210-pat00126
과
Figure 112006031977210-pat00127
가 있을 때,
Figure 112006031977210-pat00128
는 RS노드,
Figure 112006031977210-pat00129
의 구간에 속하고
Figure 112006031977210-pat00130
는 RS노드,
Figure 112006031977210-pat00131
의 구간에 속한다고 하자. 즉,
Figure 112006031977210-pat00132
≤
Figure 112006031977210-pat00133
<
Figure 112006031977210-pat00134
그리고
Figure 112006031977210-pat00135
≤
Figure 112006031977210-pat00136
<
Figure 112006031977210-pat00137
. 노드
Figure 112006031977210-pat00138
에서 노드
Figure 112006031977210-pat00139
까지 이동하는 과정에서 두 차이질의집합인
Figure 112006031977210-pat00140
과
Figure 112006031977210-pat00141
은 도 3과 같이 계산된다.
도 3과 같이
Figure 112006031977210-pat00142
과
Figure 112006031977210-pat00143
계산법은 노드
Figure 112006031977210-pat00144
와 노드
Figure 112006031977210-pat00145
간의 상대적 순서에 따라서 달라진다. 만약 j < h이면
Figure 112006031977210-pat00146
는 노드
Figure 112006031977210-pat00147
에서 노드
Figure 112006031977210-pat00148
까지 모든 노 드의 +DQSet에 있는 질의들에서 -DQSet에 있는 질의들을 뺀 나머지 질의들을 원소로 갖는다. 마찬가지로
Figure 112006031977210-pat00149
는 -DQSet에 있는 질의들에서 +DQSet에 있는 질의들을 뺀 나머지 질의들의 집합이 된다. 반면에 j > h이면 노드
Figure 112006031977210-pat00150
에서 노드
Figure 112006031977210-pat00151
까지 모든 노드의 -DQSet에 있는 질의들에서 +DQSet에 있는 질의들을 뺀 나머지 질의들이
Figure 112006031977210-pat00152
이 된다.
Figure 112006031977210-pat00153
은 반대로 구해진다. 만약 j = h이면 차이질의는 없다.
도 2에서 점진식 검색 알고리즘의 동작 예를 보여준다. 이전 데이터 값
Figure 112006031977210-pat00154
가
Figure 112006031977210-pat00155
에 있었다고 가정하자. 만약 현재 데이터 값
Figure 112006031977210-pat00156
이
Figure 112006031977210-pat00157
에 속한다고 하면 차이질의집합은
Figure 112006031977210-pat00158
에서
Figure 112006031977210-pat00159
로 이동하면서 구해진다. 결과는
Figure 112006031977210-pat00160
= {
Figure 112006031977210-pat00161
}이고
Figure 112006031977210-pat00162
= { Q₂,Q₄}이다. 만약
Figure 112006031977210-pat00163
가
Figure 112006031977210-pat00164
에 속한다고 하면 차이질의집합은
Figure 112006031977210-pat00165
에서
Figure 112006031977210-pat00166
로 이동하면서 구해진다. 결과는
Figure 112006031977210-pat00167
= {Q₃,Q₁}이고
Figure 112006031977210-pat00168
= {Q₄}이다.
세 번째로, 다차원 BMQ-색인에 대하여 알아본다.
다차원 BMQ-색인은 일차원 BMQ-색인을 확장하여 구성할 수 있다. 예를 들어, N차원 BMQ-색인은 델타질의정보를 저장하는 N개의 RS 리스트로 구성될 수 있다. 각각의 RS 리스트는 N개의 차원 중 하나의 차원에 대한 경계 정보와 델타질의 정보를 저장한다. 새로운 데이터가 입력으로 들어오면 N개의 RS 리스트를 차례로 검색하여 각 차원별 차이질의집합을 얻을 수 있다. 이렇게 얻어진 차원별 차이질의집합으로부터 최종 결과를 얻기 위해서 교차검사(cross-check) 알고리즘을 개발하여 사용하였다.
앞서 설명한 다차원 BMQ-색인은 크게 세 가지 장점을 가진다. 첫째로, 색인을 구성하기 위해 필요한 메모리 사용량이 매우 작다는 것이다. 왜냐하면 질의 정보를 N차원의 영역에 매우 여러 번 저장하는 형태가 아니라, N개의 일차원 영역을 담당하는 RS 리스트에 나누어 적은 숫자만큼만 반복하여 저장하기 때문이다. 차원별 RS 리스트가 하나의 질의 정보를 최대 두 번만 저장하므로 N차원 질의 정보를 최대 2N번만 저장하면 된다. 둘째로, 색인 검색 속도가 매우 빠르다는 것이다. 교차검사 알고리즘을 사용한 N차원 색인의 검색은 일차원 BMQ-색인에 비해 (N-1)√N 배의 시간이 더 걸리는 것으로 분석이 되는데, 이는 이차원 BMQ-색인의 경우 일차원 BMQ-색인에 비해 단지 √2배의 시간만 더 소요될 만큼 효율적이다. 셋째로, N차원 색인을 N개의 일차원 색인으로 나누어 구성함으로써 색인 구조와 관련 알고리즘이 매우 명확하고 단순하여 실제로 구현하기 용이하다는 장점을 지닌다.
이차원 BMQ-색인의 예제를 통해, 다차원 BMQ-색인의 구조, 질의 등록 해지 알고리즘 및 검색 알고리즘에 대해 구체적으로 살펴보자.
< 색인 구조 >
이차원 BMQ-색인(200)은 두 개의 RS 리스트(RS-X 리스트:202, RS-Y 리스트:203)와 스트림 테이블(201), 질의 테이블(204)로 구성된다. 도 4는 세 개의 질의가 등록된 이차원 BMQ-색인의 예제를 보여준다. RS-X 리스트는 X차원을 구성하는 영역조각들로 나누어진다. 도 4에서는 RS-
Figure 112006031977210-pat00169
, RS-
Figure 112006031977210-pat00170
, …, RS-
Figure 112006031977210-pat00171
이 X차원을 구성하는 영역 조각들이다. 각각의 영역조각 RS-
Figure 112006031977210-pat00172
는 영역의 X차원에 대한 상단과 하단, 그리고 ± DQSet 정보를 유지한다. RS-Y 리스트는 RS-X 리스트와 마찬가지로 Y차원 에 대해 같은 정보를 유지한다.
이차원의 경우, 스트림 테이블의 각 엔트리는 두 개의 포인터 Px, Py를 가진다. Px는 스트림의 X차원 값을 포함하는 RS-
Figure 112006031977210-pat00173
를 가리키고 Py는 스트림의 Y차원 값을 포함하는 RS-
Figure 112006031977210-pat00174
를 가리킨다. 또한 다음번 검색 연산을 위해 가장 최근의 데이터 값도 포함하고 있다. 새로운 스트림 데이터가 입력으로 들어오면, 해당하는 스트림 테이블의 엔트리가 갱신된다. 교차검사 알고리즘을 위해 필요한 질의 테이블은 질의의 경계를 저장하며 질의 ID로 해시되어 있다.
<질의 등록 및 해지>
이차원 BMQ-색인은 동적인 질의 등록 및 해지를 지원한다. 등록 및 해지 시에는 질의의 X차원 조건(predicate)과 Y차원 조건을 분리해서 처리한다. 예를 들어, 질의 영역이 (
Figure 112006031977210-pat00175
,
Figure 112006031977210-pat00176
,
Figure 112006031977210-pat00177
,
Figure 112006031977210-pat00178
)인 질의
Figure 112006031977210-pat00179
을 생각해보자.
Figure 112006031977210-pat00180
을 색인에 등록할 때에는 X차원 조건 (
Figure 112006031977210-pat00181
,
Figure 112006031977210-pat00182
) 을 RS-X 리스트에 등록하고 Y차원 조건 (
Figure 112006031977210-pat00183
,
Figure 112006031977210-pat00184
)을 RS-Y 리스트에 등록한다. 이는 일차원 BMQ-색인의 등록 방법을 이용하여 할 수 있다. 또한 새롭게 등록된 질의
Figure 112006031977210-pat00185
을 질의 테이블에도 등록한다.
Figure 112006031977210-pat00186
의 해지는 등록과 비슷하게, 차원별로 일차원 해지 방식을 이용하여 처리할 수 있다.
< 검색 알고리즘 >
새로운 스트림 데이터가 입력으로 들어오면
Figure 112006031977210-pat00187
와
Figure 112006031977210-pat00188
를 얻기 위해 BMQ-색인을 검색한다. 도 5는 검색 알고리즘의 개괄적인 흐림을 보여준다. 알고리즘의 첫 번째 단계는 각 차원의 차이질의집합인 ± XQSet과 ± YQSet을 계산하는 것이다. 이는 RS-X 리스트와 RS-Y 리스트에 대해 일차원의 점진식 검색 알고리즘을 적용하여 간단히 구할 수 있다.
두 번째 단계는 새롭게 들어온 데이터의 값이 ± XQSet과 ± YQSet에 포함되는 질의들의 모든 경계를 실제 넘었는지의 여부를 확인하는 것이다. ± XQSet과 ± YQSet에 포함되는 질의들은 하나의 차원에 대해서만 조건을 만족하기 때문에, 다른 차원에 대해서도 조건을 만족하는지 확인하는 과정이 필요한 것이다. 확인(Validation) 작업을 위해 도 6에서 볼 수 있는 교차검사 알고리즘을 개발하여 사용하였다. 교차검사 알고리즘은 각 차원별 차이질의집합에 포함되어 있는 질의들에 대해 확인되지 않은 차원의 조건이 만족하는지를 조사한다. 예를 들어, 교차검사 알고리즘은 +XQSet에 속하는
Figure 112006031977210-pat00189
에 대해, 입력된 데이터가
Figure 112006031977210-pat00190
의 Y차원 경계를 넘었는지의 여부를 조사한다. +XQSet에 속하는 질의와 -XQSet에 속하는 질의에 대한 교차검사 방식에는 약간의 차이가 있다. +XQSet에 속하는 질의에 대해서는 새롭게 들어온 데이터 값이 Y차원 조건 영역 안에 포함되는지 조사해야 한다. 반면 -XQSet에 속하는 질의에 대해서는 스트림의 이전 값이 Y차원 조건 영역 안에 포함되었는지를 조사해야 한다.
교차검사를 통해, 각 차원별 차이질의집합으로부터, 모든 차원의 조건을 만족시키는 BMQ질의 집합인 ± XBMQSet 과 ± YBMQSet 을 얻을 수 있다. 마지막으로,
Figure 112006031977210-pat00191
는 +XBMQSet 과 +YBMQSet 의 합집합 연산을 통해 얻을 수 있으며
Figure 112006031977210-pat00192
도 비슷한 방식으로 구할 수 있다.
다음으로 상술한 이론적 배경을 바탕으로 본 발명의 실시예에 대하여 설명하기로 한다.
도 7은 본 발명의 실시예에 따른 시스템의 개략적인 구성도이다.
본 발명의 실시예에 따른 시스템은 중앙처리장치(701), 데이터베이스(702), 데이터 스트림 센서(703), 입력장치(704), 출력장치(705)를 포함하여 이루어진다.
상기 중앙처리장치(701)는 본 발명의 실시예의 방법을 프로그램된 절차에 따라 수행한다. 또한, 상기 데이터베이스에 저장된 위치 좌표를 이용하여 인식된 데이터 스트림 소스의 위치정보를 좌표화하며, 이 좌표값을 본 발명에서는 데이터값이라고 규정한다. 상기 중앙처리장치는 인식된 데이터 스트림의 좌표값을 일시적으로 저장하며, 만약 데이터값이 이차원 이상일 경우에는 각 차원별 차이질의집합의 교차검사에 상기 데이터값을 적용하며, BMQ-색인을 갱신하는데 상기 데이터값을 사용하게 된다.
상기 데이터베이스(702)는 본 발명의 실시예의 시스템이 관할하는 영역의 각 지점에 대한 위치를 좌표화하여 이를 저장하고 있고, 또한 본 발명의 실시예에 따른 BMQ-색인을 저장하고 있다. 본 발명의 실시예에 있어 영역구간 경계, 질의영역 경계, 영역구간, 질의영역 구간 등은 상기 데이터베이스에 저장된 위치좌표를 기준으로 정해진다.
상기 센서(703)는 특정 데이터 스트림을 인식하여 이를 상기 중앙처리장치에 보고하는 기능을 수행한다. 상기 데이터 스트림은 각 데이터 스트림을 구별하는 고유의 ID를 가지고 있어서 상기 시스템에서는 복수의 데이터를 처리할 수 있고, 데 이터 스트림 소스의 위치 정보를 가지고 있다.
상기 입력장치(704)는 상기 중앙처리장치에 새로운 질의에 대한 정보를 입력하거나 BMQ-색인에 등록되어 있는 기존의 질의에 대한 정보를 입력한다.
상기 출력장치(705)는 상기 중앙처리장치가 처리한 데이터에 대한 소정의 결과를 출력한다. 이는 프린터, 모니터 등이 될 수 있다.
도 8은 본 발명의 실시예에 따른 질의의 변동에 의한 BMQ-색인을 갱신하기 위한 흐름도이다.
도 8에서 알 수 있듯이, 본 발명의 실시예에 따른 질의의 변동에 의한 BMQ-색인을 갱신하는 방법은,
상기 입력장치(704)에서 상기 중앙처리장치(701)로 변동될 질의와 이에 대한 질의영역 구간을 입력하는 단계(S801);
상기 중앙처리장치(701)에서 변동될 질의영역구간의 경계를 기준으로 영역조각 및 델타질의집합을 정리하는 단계(S802);
상기 중앙처리장치(701)에서 새로운 영역조각경계(
Figure 112006031977210-pat00193
,
Figure 112006031977210-pat00194
, …,
Figure 112006031977210-pat00195
)를 설정하고 이에 부합하는 새로운 노드(
Figure 112006031977210-pat00196
,
Figure 112006031977210-pat00197
, …,
Figure 112006031977210-pat00198
)를 설정하는 단계(S803); 및
상기 중앙처리장치(701)에서 각 영역조각의 노드와 해당 노드의 영역구간 및 해당 노드의 델타질의집합을 매칭시킨 후 이를 데이터베이스화하여 저장하는 단계(S804)를 포함하여 이루어지며,
만약에, 변동될 질의가 이차원 이상의 질의 영역 구간을 갖는 경우에는 BMQ-색인에 있는 질의 테이블에 상기 변동될 질의 및 질의의 영역 구간을 등록하거나 해지하는 단계를 더 포함하게 되며 이는 도면에 표시되어 있지는 않다.
도 9는 본 발명의 실시예에 따른 경계관찰질의를 이용한 데이터 스트림 처리 방법을 나타내는 흐름도이다.
도 9에서 알 수 있듯이, 본 발명의 실시예에 따른 경계관찰질의를 이용한 데이터 스트림 처리 방법은,
상기 센서(703)에서 특정 데이터 스트림을 인식하는 단계(S901);
상기 중앙처리장치(701)에서 상기 데이터 스트림에 대한 ID를 확인한 후 이를 상기 MBQ-색인에 등록되어 있는 데이터 스트림인지를 검사하여 등록된 것임을 확인하는 단계(S902);
상기 중앙처리장치(701)에서 상기 인식된 데이터 스트림의 새로운 데이터값을 포함하는 영역조각 구간을 갖는 영역조각 노드를 상기 BMQ-색인에서 읽어내어 상기 데이터 스트림에 대한 새로운 노드 포인터를 설정하는 단계(S903);
상기 중앙처리장치(701)에서 상기 BMQ-색인에서 상기 데이터 스트림에 해당하는 이전의 노드 포인터와 영역조각 리스트를 읽어오는 단계(S904);
상기 중앙처리장치(701)에서 상기 새로운 노드 포인터와 이전의 노드 포인터를 비교한 후 상기 영역조각 리스트를 이용하여 차이질의집합을 추출하는 단계(S905);
상기 중앙처리장치(701)에서 상기 데이터 스트림과 이에 대한 현재 처리시간과 차이질의집합을 데이터베이스화하여 저장하는 단계(S906);
상기 중앙처리장치(701)에서 상기 설정된 새로운 노드 포인터를 데이터베이스화하여 상기 데이터 스트림에 대한 기존의 BMQ-색인을 갱신하는 단계로서, 상기 데이터값이 이차원이상일 경우에는 새로운 데이터값을 더 포함하여 데이터베이스화함으로써 상기 데이터 스트림에 대한 기존의 BMQ-색인을 갱신하는 단계(S907) ;
상기 중앙처리장치(701)에서 상기 데이터베이스(702)에 저장되어 있는 각 데이터 스트림에 대한 처리정보로부터 소정의 데이터를 추출하는 단계로서,
특정 질의
Figure 112006031977210-pat00199
에 대한 카운트별 데이터를 얻기 위하여는,
저장된 처리시간 중에서 특정 처리시간을 선택하고, 상기 처리시간에 등록된 차이질의집합 중에서 상기 질의
Figure 112006031977210-pat00200
를 포함하고 있는 데이터 스트림을 추출한 후,
Figure 112006031977210-pat00201
에 질의
Figure 112006031977210-pat00202
를 포함하는 데이터 스트림의 개수와
Figure 112006031977210-pat00203
에 질의
Figure 112006031977210-pat00204
를 포함하는 데이터 스트림의 개수를 각각 추출하고,
특정 질의
Figure 112006031977210-pat00205
에 대한 시간집계별 데이터를 얻기 위하여,
저장된 차이질의집합 중에서 특정 질의
Figure 112006031977210-pat00206
를 선택하고, 저장된 차이질의집합 중에서 질의
Figure 112006031977210-pat00207
를 포함하고 있는 데이터 스트림을 추출한 후, 각 데이터 스트림에 대하여
Figure 112006031977210-pat00208
에 질의
Figure 112006031977210-pat00209
를 포함하는 처리시간과
Figure 112006031977210-pat00210
에 질의
Figure 112006031977210-pat00211
를 포함하는 처리시간을 추출하는 것을 특징으로 하는 소정의 데이터를 추출하는 단계(S908);
상기 중앙처리장치(701)에서 추출한 데이터를 이용한 소정의 결과를 상기 출력장치를 통하여 출력하는 단계(S909);
상기 중앙처리장치(701)에서 상기 데이터 스트림에 대한 ID를 확인한 후 이 를 상기 MBQ-색인에 등록되어 있는 데이터 스트림인지를 검사하여 등록되지 않은 것임을 확인하는 단계(S910);
상기 중앙처리장치(701)에서 상기 인식된 데이터 스트림의 새로운 데이터값을 포함하는 영역조각 구간을 갖는 영역조각 노드를 상기 BMQ-색인에서 읽어내어 상기 데이터 스트림에 대한 노드 포인터를 설정하는 단계(S911); 및
상기 중앙처리장치(701)에서 상기 데이터 스트림에 대한 ID와 노드 포인터를 데이터베이스화하여 BMQ-색인에 등록하는 단계로서, 만약 상기 데이터값이 이차원이상일 경우에는 상기 데이터값을 더 포함하여 BMQ-색인에 등록하는 단계(S912)를 포함하여 이루어진다.
이상에서 설명한 본 발명에 의하면, BMQ라는 새로운 종류의 연속구간질의를 통해 새로운 데이터 스트림 기반 응용서비스들이 가능하고, BMQ-색인을 이용하여 공유식 처리 및 점진식 처리를 통한 높은 검색 성능과 낮은 저장 공간 비용을 획득함으로써 다수의 데이터 스트림 및 다수의 BMQ를 효율적으로 처리할 수 있기 때문에 기존의 가장 좋은 RMQ처리 방법과 비교했을 때 훨씬 더 나은 검색 성능과 저장비용을 제공하는 효과가 있다.

Claims (36)

  1. 중앙처리장치, BMQ-색인을 저장하고 있는 데이터베이스, 데이터 스트림 센서를 포함하는 시스템에서,
    상기 센서에서 특정 데이터 스트림을 인식하는 1 단계;
    상기 중앙처리장치에서 상기 데이터 스트림에 대한 새로운 노드 포인터를 설정하는 2 단계; 및
    상기 중앙처리장치에서 상기 BMQ-색인 및 상기 새로운 노드 포인터를 이용하여 상기 데이터 스트림에 대한 차이질의집합을 추출하는 3 단계를 포함하는 경계관찰질의(BMQ: Border Monitoring Query)를 이용한 데이터 스트림 처리 방법.
  2. 청구항 1에 있어서,
    상기 BMQ-색인은 스트림 테이블과 영역조각 리스트를 포함하여 구성되는 것을 특징으로 하는 경계관찰질의(BMQ: Border Monitoring Query)를 이용한 데이터 스트림 처리 방법.
  3. 청구항 1에 있어서,
    상기 BMQ-색인은 스트림 테이블과 복수의 영역조각 리스트와 질의테이블을 포함하여 구성되는 것을 특징으로 하는 경계관찰질의(BMQ: Border Monitoring Query)를 이용한 데이터 스트림 처리 방법.
  4. 청구항 1에 있어서,
    상기 데이터 스트림은 각 데이터 스트림을 구별하는 ID를 가지고 있어서 상기 시스템에서는 복수의 데이터를 처리할 수 있는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  5. 청구항 1에 있어서,
    상기 데이터베이스에는 상기 시스템이 관할하는 영역의 각 지점에 대한 위치를 좌표화하여 이를 저장하고 있는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  6. 청구항 1에 있어서, 상기 2 단계의 새로운 노드 포인터는,
    상기 데이터 스트림의 소스위치정보값 또는 가격정보값을 포함하는 영역조각 구간을 갖는 영역조각 노드를 상기 BMQ-색인에서 읽어내어 설정되는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  7. 청구항 1에 있어서, 상기 3 단계는,
    상기 BMQ-색인에서 상기 데이터 스트림에 해당하는 이전의 노드 포인터와 영역조각 리스트를 읽어오는 단계;
    상기 새로운 노드 포인터와 이전의 노드 포인터를 비교한 후 상기 영역조각 리스트를 이용하여 차이질의집합을 추출하는 단계; 및
    상기 데이터 스트림과 이에 대한 현재 처리시간과 차이질의집합을 데이터베이스화하여 저장하는 단계로 이루어지는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  8. 청구항 1에 있어서,
    상기 BMQ-색인은 1차원 색인으로서 스트림 테이블과 하나의 영역조각 리스트의 두 개의 데이터 구조로 구성되는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  9. 청구항 8에 있어서,
    상기 BMQ-색인의 스트림 테이블은 등록된 각 데이터 스트림 ID와 각 데이터 스트림에 대해 가장 최근 데이터가 위치했던 영역조각 노드를 가리키는 하나의 노드 포인터를 가진 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  10. 청구항 8에 있어서,
    상기 BMQ-색인의 영역조각 리스트는 서로 다른 영역조각 구간을 갖는 각 영역조각 노드와 이에 매칭되는 두 개의 델타질의집합의 쌍들로 이루어진 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  11. 청구항 7에 있어서, 1차원 BMQ-색인의 경우에 차이질의집합을 추출하는 단계는,
    이전 데이터 스트림에 매칭된 영역조각으로부터 현재 데이터 스트림에 매칭된 영역조각까지 선형횡단을 통해 차이질의집합을 점진적으로 추출하는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  12. 청구항 11에 있어서, 점진적 추출에 의한 차이질의집합에 있어서,
    특정 데이터 스트림에 대한 이전 노드 포인터가 노드
    Figure 112006031977210-pat00212
    에 속하고, 현재 노드 포인터가 노드
    Figure 112006031977210-pat00213
    에 속한다고 할 때,
    j ＜ h 이면,
    Figure 112006031977210-pat00214
    는 노드
    Figure 112006031977210-pat00215
    에서 노드
    Figure 112006031977210-pat00216
    까지 모든 노드의 +DQSet에 있는 질의들에서 -DQSet에 있는 질의들을 뺀 나머지 질의들을 원소로 갖고,
    Figure 112006031977210-pat00217
    는 노드
    Figure 112006031977210-pat00218
    에서 노드
    Figure 112006031977210-pat00219
    까지 모든 노드의 -DQSet에 있는 질의들에서 +DQset에 있는 질의들을 뺀 나머지 질의들을 원소로 갖으며,
    j ＞ h 이면,
    Figure 112006031977210-pat00220
    는 노드
    Figure 112006031977210-pat00221
    에서 노드
    Figure 112006031977210-pat00222
    까지 모든 노드의 -DQSet에 있는 질의들에서 +DQSet에 있는 질의들을 뺀 나머지 질의들을 원소로 갖고,
    Figure 112006031977210-pat00223
    는 노드
    Figure 112006031977210-pat00224
    에서 노드
    Figure 112006031977210-pat00225
    까지 모든 노드의 +DQSet에 있는 질의들에서 -DQSet에 있는 질의들을 뺀 나머지 질의들을 원소로 갖으며,
    j = h 이면, 차이질의는 없는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  13. 청구항 1에 있어서,
    상기 BMQ-색인은 2차원 색인으로서 스트림 테이블과 두 개의 영역조각 리스트와 질의 테이블로 구성되는 것을 특징으로 하는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  14. 청구항 13에 있어서,
    상기 BMQ-색인의 스트림 테이블은 등록된 각 데이터 스트림 ID와, 각 데이터 스트림에 대해 가장 최근 데이터가 위치했던 X차원 및 Y차원의 영역조각 노드를 가리키는 두 개의 노드 포인터, 및 각 데이터 스트림의 가장 최근의 데이터값을 가진 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  15. 청구항 13에 있어서,
    상기 BMQ-색인의 두 개의 영역조각 리스트는 X차원의 서로 다른 영역조각 구간을 갖는 각 영역조각 노드와 이에 매칭되는 두 개의 델타질의집합의 쌍들로 이루어진 X차원 영역조각 리스트와, Y차원의 서로 다른 영역조각 구간을 갖는 각 영역조각 노드와 이에 매칭되는 두 개의 델타질의집합의 쌍들로 이루어진 Y차원 영역조각 리스트로 구성되는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  16. 청구항 13에 있어서,
    상기 BMQ-색인의 질의테이블은 각 질의의 경계를 저장하며 질의 ID로 해시되어 있는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  17. 청구항 7에 있어서, 2차원 BMQ-색인의 경우에 차이질의집합을 추출하는 단계는,
    X차원 및 Y차원의 각 차원별로 이전 데이터 스트림에 매칭된 영역조각으로부터 현재 데이터 스트림에 매칭된 영역조각까지 선형횡단을 통해 각 차원별 차이질의집합인 ±XQSet와 ±YQSet를 점진적으로 추출한 다음에,
    각 차원별 차이질의집합이 다른 차원에 대해서도 만족하는지를 확인하는 교차검사를 거친 ±XBMQSet 및 ±YBMQSet를 구한 후에,
    상기 각 차원별로 확인된 결과를 합집합 연산을 통해 최종 결과를 얻는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  18. 청구항 17에 있어서, 점진적 추출에 의한 각 차원별 차이질의집합에 있어서,
    특정 데이터 스트림에 대한 X차원의 이전 노드 포인터가 노드
    Figure 112006031977210-pat00226
    에 속하고, 현재 노드 포인터가 노드
    Figure 112006031977210-pat00227
    에 속한다고 할 때,
    j ＜ h 이면, +XQSet는 X차원의 노드
    Figure 112006031977210-pat00228
    에서 노드
    Figure 112006031977210-pat00229
    까지 모든 노드의 +DQSet에 있는 질의들에서 -DQSet에 있는 질의들을 뺀 나머지 질의들을 원소로 갖고, -XQSet는 X차원의 노드
    Figure 112006031977210-pat00230
    에서 노드
    Figure 112006031977210-pat00231
    까지 모든 노드의 -DQSet에 있는 질의들에서 +DQset에 있는 질의들을 뺀 나머지 질의들을 원소로 갖으며,
    j ＞ h 이면, +XQSet는 X차원의 노드
    Figure 112006031977210-pat00232
    에서 노드
    Figure 112006031977210-pat00233
    까지 모든 노드의 -DQSet에 있는 질의들에서 +DQSet에 있는 질의들을 뺀 나머지 질의들을 원소로 갖고, -XQSet는 X차원의 노드
    Figure 112006031977210-pat00234
    에서 노드
    Figure 112006031977210-pat00235
    까지 모든 노드의 +DQSet에 있는 질의들에서 -DQSet에 있는 질의들을 뺀 나머지 질의들을 원소로 갖으며,
    j = h 이면, 차이질의는 없는 것을 특징으로 하고,
    Y차원에 대하여도 상기와 동일한 특징을 갖는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  19. 청구항 17에 있어서, 상기 교차검사는,
    상기 중앙처리장치에서 저장되어 있는 새로운 데이터값과 이전의 데이터값을 상기 BMQ-색인으로부터 읽어와 양자를 인식한 후에,
    X차원에 대하여는, +XQSet에 속하는 각 질의에 대해서 새롭게 들어온 Y차원 데이터값이 각 질의의 Y차원 조건 영역 안에 포함되는지를 조사하여 이를 만족하는 질의들의 집합인 +XBMQSet를 구하고, -XQSet에 속하는 각 질의에 대해서 스트림의 이전 Y차원 데이터값이 각 질의의 Y차원 조건 영역 안에 포함되는지를 조사하여 이를 만족하는 질의의 집합인 -XBMQSet를 구하며,
    Y차원에 대하여도 상기와 동일하게 이루어지는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  20. 청구항 17에 있어서, 최종결과에 있어서,
    차이질의집합
    Figure 112006031977210-pat00236
    는 +XBMQSet 와 +YBMQSet의 합집합 연산을 통해 얻을 수 있고, 차이질의집합
    Figure 112006031977210-pat00237
    는 -XBMQSet 와 -YBMQSet의 합집합 연산을 통해 얻을 수 있는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  21. 청구항 1 또는 7에 있어서, 상기 시스템에 출력장치를 더 포함하고,
    상기 중앙처리장치에서 상기 데이터베이스에 저장되어 있는 각 데이터 스트림에 대한 처리정보로부터 소정의 데이터를 추출하는 단계;
    상기 중앙처리장치에서 상기 추출한 데이터를 이용하여 얻은 소정의 결과를 출력장치를 통하여 출력하는 단계를 더 포함하는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  22. 청구항 21에 있어서, 소정의 데이터를 추출하는 단계는,
    특정 질의
    Figure 112006031977210-pat00238
    에 대한 카운트별 데이터를 얻기 위하여,
    저장된 처리 시간 중에서 특정 처리시간을 선택하고,
    상기 처리시간에 등록된 차이질의집합 중에서 상기 질의
    Figure 112006031977210-pat00239
    를 포함하고 있는 데이터 스트림을 추출한 후,
    Figure 112006031977210-pat00240
    에 질의
    Figure 112006031977210-pat00241
    를 포함하는 데이터 스트림의 개수와
    Figure 112006031977210-pat00242
    에 질의
    Figure 112006031977210-pat00243
    를 포함하는 데이터 스트림의 개수를 각각 추출하는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  23. 청구항 21에 있어서, 출력장치를 통해 얻어지는 소정의 결과는,
    특정질의
    Figure 112006031977210-pat00244
    에 대한 특정 처리시간에 있어서의 유입량, 유출량, 순유량, 총유량 중 어느 하나 이상을 포함하는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  24. 청구항 21에 있어서, 소정의 데이터를 추출하는 단계는,
    특정 질의
    Figure 112006031977210-pat00245
    에 대한 시간집계별 데이터를 얻기 위하여,
    저장된 차이질의집합 중에서 특정 질의
    Figure 112006031977210-pat00246
    를 선택하고,
    저장된 차이질의집합 중에서 질의
    Figure 112006031977210-pat00247
    를 포함하고 있는 데이터 스트림을 추출한 후,
    각 데이터 스트림에 대하여
    Figure 112006031977210-pat00248
    에 질의
    Figure 112006031977210-pat00249
    를 포함하는 처리시간과
    Figure 112006031977210-pat00250
    에 질의
    Figure 112006031977210-pat00251
    를 포함하는 처리시간을 추출하는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  25. 청구항 21에 있어서, 출력장치를 통해 얻어지는 소정의 결과는,
    특정 질의
    Figure 112006031977210-pat00252
    에 대한 각 데이터 스트림의 질의 영역 구간을 만족하기 시작한 시각, 질의 영역 구간을 나간 시각, 시작 시각과 끝난 시각을 연계해 질의영역 구간을 만족한 시간 중 어느 하나에 대한 최소값, 최대값, 평균값, 하위 소정 개수 , 상위 소정 개수 중 어느 하나 이상을 포함하고 있는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  26. 청구항 1에 있어서,
    상기 시스템은 윈도우로 BMQ의 결과의 크기를 제한한 후 집계하는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  27. 중앙처리장치, BMQ-색인을 저장하고 있는 데이터베이스, 데이터 스트림 센서를 포함하는 시스템에서,
    상기 센서에서 특정 데이터 스트림을 인식하는 1 단계;
    상기 중앙처리장치에서 상기 데이터 스트림에 대한 ID를 확인한 후 이를 상기 MBQ-색인에 등록되어 있는 데이터 스트림인지를 검사하여 등록되지 않은 것임을 확인하는 2 단계;
    상기 중앙처리장치에서 상기 데이터 스트림에 대한 노드 포인터를 설정하는 3 단계;
    상기 중앙처리장치에서 상기 데이터 스트림에 대한 ID와 노드 포인터를 데이터베이스화하여 상기 BMQ-색인에 등록하는 4 단계를 포함하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  28. 청구항 27에 있어서, 상기 3 단계의 노드 포인터는,
    상기 데이터 스트림의 소스위치정보값 또는 가격정보값을 포함하는 영역조각 구간을 갖는 영역조각 노드를 상기 BMQ-색인에서 읽어내어 설정되는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  29. 중앙처리장치, 중앙처리장치에 정보를 입력하는 입력 장치, BMQ-색인을 저장하고 있는 데이터베이스를 포함하는 시스템에서,
    상기 입력 장치에서 상기 중앙처리장치로 변동될 질의와 이에 대한 질의영역 구간을 입력하는 단계;
    상기 중앙처리장치에서 변동될 질의영역구간의 경계를 기준으로 영역조각 및 델타질의집합을 정리하는 단계;
    상기 중앙처리장치에서 새로운 영역조각경계(
    Figure 112006031977210-pat00253
    ,
    Figure 112006031977210-pat00254
    , …,
    Figure 112006031977210-pat00255
    )를 설정하고 이에 부합하는 새로운 노드(
    Figure 112006031977210-pat00256
    ,
    Figure 112006031977210-pat00257
    , …,
    Figure 112006031977210-pat00258
    )를 설정하는 단계; 및
    상기 중앙처리장치에서 각 영역조각의 노드와 해당 노드의 영역구간 및 해당 노드의 델타질의집합을 매칭시킨 후 이를 데이터베이스화하여 저장하는 단계를 포함하는 BMQ-색인을 갱신하는 방법.
  30. 청구항 29에 있어서, 상기 변동될 질의가 새로 등록될 질의의 경우에 있어 영역조각 및 델타질의집합을 정리하는 단계는,
    새로운 질의
    Figure 112006031977210-pat00259
    의 질의영역구간이 (
    Figure 112006031977210-pat00260
    ,
    Figure 112006031977210-pat00261
    )이라 할 때,
    질의의 하단
    Figure 112006031977210-pat00262
    을 포함하는 구간 (
    Figure 112006031977210-pat00263
    ,
    Figure 112006031977210-pat00264
    )를 갖는 영역조각 노드
    Figure 112006031977210-pat00265
    를 찾은 후에,
    Figure 112006031977210-pat00266
    이
    Figure 112006031977210-pat00267
    과 동일하면
    Figure 112006031977210-pat00268
    을
    Figure 112006031977210-pat00269
    의
    Figure 112006031977210-pat00270
    에 넣고,
    Figure 112006031977210-pat00271
    이
    Figure 112006031977210-pat00272
    과 동일하지 않으면
    Figure 112006031977210-pat00273
    는 두 개의 노드로 나뉘어 왼쪽 노드 구간은 (
    Figure 112006031977210-pat00274
    ,
    Figure 112006031977210-pat00275
    )가 되고
    Figure 112006031977210-pat00276
    와 동일한 ±DQSet를 가지며 오른쪽 노드 구간은 (
    Figure 112006031977210-pat00277
    ,
    Figure 112006031977210-pat00278
    )가 되고 +DQSet에
    Figure 112006031977210-pat00279
    을 포함하고,
    질의의 상단
    Figure 112006031977210-pat00280
    을 포함하는 구간 (
    Figure 112006031977210-pat00281
    ,
    Figure 112006031977210-pat00282
    )를 갖는 영역조각 노드
    Figure 112006031977210-pat00283
    를 찾은 후에,
    Figure 112006031977210-pat00284
    이
    Figure 112006031977210-pat00285
    과 동일하면
    Figure 112006031977210-pat00286
    을
    Figure 112006031977210-pat00287
    의
    Figure 112006031977210-pat00288
    에 넣고,
    Figure 112006031977210-pat00289
    이
    Figure 112006031977210-pat00290
    과 동일하지 않으면
    Figure 112006031977210-pat00291
    는 두 개의 노드로 나뉘어 왼쪽 노드 구간은 (
    Figure 112006031977210-pat00292
    ,
    Figure 112006031977210-pat00293
    )가 되고
    Figure 112006031977210-pat00294
    와 동일한 ±DQSet을 가지며 오른쪽 노드 구간은 (
    Figure 112006031977210-pat00295
    ,
    Figure 112006031977210-pat00296
    )가 되고 -DQSet에
    Figure 112006031977210-pat00297
    을 넣는 것을 특징으로 하는 BMQ-색인을 갱신하는 방법.
  31. 청구항 29에 있어서, 상기 변동될 질의가 해지될 질의의 경우에 있어 영역조각 및 델타질의집합을 정리하는 단계는,
    해지될 질의
    Figure 112006031977210-pat00298
    의 질의영역구간이 (
    Figure 112006031977210-pat00299
    ,
    Figure 112006031977210-pat00300
    )이라 할 때,
    질의영역구간의 하단
    Figure 112006031977210-pat00301
    과 동일한 하단을 갖는 영역조각 노드
    Figure 112006031977210-pat00302
    를 찾은 후에, 그 노드의
    Figure 112006031977210-pat00303
    에서
    Figure 112006031977210-pat00304
    을 삭제하고, 이때
    Figure 112006031977210-pat00305
    와
    Figure 112006031977210-pat00306
    이 공집합이 되면 노드
    Figure 112006031977210-pat00307
    를 노드
    Figure 112006031977210-pat00308
    과 합치고,
    질의영역구간의 상단
    Figure 112006031977210-pat00309
    과 동일한 하단을 갖는 영역조각 노드
    Figure 112006031977210-pat00310
    를 찾은 후에, 그 노드의
    Figure 112006031977210-pat00311
    에서
    Figure 112006031977210-pat00312
    을 삭제하고, 이때 +DQSetj와 -DQSetj가 공집합이 되면 노드
    Figure 112006031977210-pat00313
    를 노드
    Figure 112006031977210-pat00314
    과 합치는 것을 특징으로 하는 BMQ-색인을 갱신하는 방법.
  32. 청구항 29 내지 31 중 어느 하나에 있어서,
    상기 변동될 질의의 영역 구간이 이차원 이상일 경우에는 각 차원별로 모든 절차가 수행되는 것을 특징으로 하는 BMQ-색인을 갱신하는 방법.
  33. 청구항 29에 있어서, 상기 변동될 질의의 영역 구간이 이차원 이상일 경우에는,
    상기 BMQ-색인에 있는 질의 테이블에 상기 변동될 질의 및 질의의 영역 구간을 등록하거나 해지하는 단계를 더 포함하는 것을 특징으로 하는 BMQ-색인을 갱신하는 방법.
  34. 청구항 1 또는 27에 있어서,
    상기 중앙처리장치에서 상기 BMQ-색인의 영역조각리스트에 새로운 질의를 등록하거나 기존의 질의를 해지하는 단계를 더 포함하는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  35. 청구항 1에 있어서,
    상기 중앙처리장치에서 상기 설정된 새로운 노드 포인터를 데이터베이스화하여 상기 데이터 스트림에 대한 기존의 BMQ-색인을 갱신하는 4 단계를 더 포함하는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
  36. 청구항 27에 있어서, 상기 4단계에서는,
    상기 데이터 스트림의 소스위치정보값 또는 가격정보값을 상기 BMQ-색인에 더 등록하는 것을 특징으로 하는 경계관찰질의를 이용한 데이터 스트림 처리 방법.
KR1020060040879A 2006-05-08 2006-05-08 경계관찰질의를 이용한 데이터 스트림 처리 방법 Expired - Fee Related KR100828404B1 (ko)

Priority Applications (2)

Application Number Priority Date Filing Date Title
KR1020060040879A KR100828404B1 (ko) 2006-05-08 2006-05-08 경계관찰질의를 이용한 데이터 스트림 처리 방법
US11/741,923 US7895188B2 (en) 2006-05-08 2007-04-30 Processing method of data stream using border monitoring query

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020060040879A KR100828404B1 (ko) 2006-05-08 2006-05-08 경계관찰질의를 이용한 데이터 스트림 처리 방법

Publications (2)

Publication Number Publication Date
KR20070108616A KR20070108616A (ko) 2007-11-13
KR100828404B1 true KR100828404B1 (ko) 2008-05-08

Family

ID=39063338

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020060040879A Expired - Fee Related KR100828404B1 (ko) 2006-05-08 2006-05-08 경계관찰질의를 이용한 데이터 스트림 처리 방법

Country Status (2)

Country Link
US (1) US7895188B2 (ko)
KR (1) KR100828404B1 (ko)

Families Citing this family (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101067724B1 (ko) * 2008-08-04 2011-09-28 고려대학교 산학협력단 센서 노드 장치 및 센서 노드 읽기값의 모니터링 방법
US8615597B2 (en) * 2010-06-30 2013-12-24 Telcordia Technologies, Inc. Optimizing evaluation patterns and data acquisition for stream analytics in resource-constrained wireless environments
HUE033604T2 (en) 2012-04-13 2017-12-28 Ge Video Compression Llc Low delay picture coding
TWI849425B (zh) 2012-06-29 2024-07-21 美商Ｇｅ影像壓縮有限公司 視訊資料串流概念技術
JP5883937B2 (ja) * 2012-09-07 2016-03-15 株式会社日立製作所 計算機システム、データ管理方法及びプログラムを格納する記録媒体
US9305031B2 (en) * 2013-04-17 2016-04-05 International Business Machines Corporation Exiting windowing early for stream computing
WO2016141491A1 (en) * 2015-03-10 2016-09-15 Royal Bank Of Canada Systems and methods for managing data
CN109617962B (zh) * 2018-12-11 2020-08-18 电子科技大学 一种基于内容关联度的车联网雾节点内容缓存方法
US20240012835A1 (en) * 2022-07-08 2024-01-11 Redlist, Llc Synchronizing changes in a distributed system with intermittent connectivity
CN115238559B (zh) * 2022-09-21 2022-12-02 北京科技大学 一种三维轧件拉伸建模过程边界组元自动提取方法及系统

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20060024094A (ko) * 2004-09-13 2006-03-16 주식회사 케이티 멀티미디어 데이터 저장용 버퍼 구조 및 버퍼링 방법
KR20060069185A (ko) * 2004-12-17 2006-06-21 한국전자통신연구원 동적 윈도우 분할 기반의 대용량 스트림 데이터의 축소 방법
KR20070057599A (ko) * 2005-12-01 2007-06-07 한국전자통신연구원 데이터 중복 처리 방지 기능을 가지는 스트림 데이터 처리시스템 및 그 방법

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8543579B2 (en) * 2005-06-17 2013-09-24 International Business Machines Corporation Range query methods and apparatus

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20060024094A (ko) * 2004-09-13 2006-03-16 주식회사 케이티 멀티미디어 데이터 저장용 버퍼 구조 및 버퍼링 방법
KR20060069185A (ko) * 2004-12-17 2006-06-21 한국전자통신연구원 동적 윈도우 분할 기반의 대용량 스트림 데이터의 축소 방법
KR20070057599A (ko) * 2005-12-01 2007-06-07 한국전자통신연구원 데이터 중복 처리 방지 기능을 가지는 스트림 데이터 처리시스템 및 그 방법

Also Published As

Publication number Publication date
US7895188B2 (en) 2011-02-22
KR20070108616A (ko) 2007-11-13
US20080288441A1 (en) 2008-11-20

Similar Documents

Publication Publication Date Title
KR100828404B1 (ko) 경계관찰질의를 이용한 데이터 스트림 처리 방법
CN111949834B (zh) 选址方法和选址平台系统
Du Mouza et al. Mobility patterns
US20200012663A1 (en) Index Mechanism for Report Generation
US9734217B2 (en) Methods and systems for analyzing entity performance
CN100390790C (zh) 存储和访问数据,以及提高数据库查询语言语句性能的方法和机制
EP2884440A1 (en) Methods and systems for analyzing entity performance
CN103345521B (zh) 一种在哈希表数据库中处理键值的方法和装置
CN106651247A (zh) 基于gis拓扑分析的地址匹配区域块方法和系统
CN102402605A (zh) 用于搜索引擎索引的混合分布模型
CN108572958B (zh) 数据处理方法及装置
CN113254630B (zh) 一种面向全球综合观测成果的领域知识图谱推荐方法
US10579647B1 (en) Methods and systems for analyzing entity performance
CN101911065A (zh) 访问对象信息检索装置
CN115495478A (zh) 数据查询方法、装置、电子设备以及存储介质
Shen et al. A Generic Framework for Top-${\schmi k} $ Pairs and Top-${\schmi k} $ Objects Queries over Sliding Windows
Kobayashi et al. Indexing complex networks for fast attributed kNN queries
Brisaboa et al. Compact trip representation over networks
CN108833466A (zh) 交通网络空间文本发布/订阅的系统及方法
CN111107493B (zh) 一种移动用户位置预测方法与系统
CN114490833B (zh) 一种图计算结果可视化方法和系统
US20100036865A1 (en) Method For Generating Score-Optimal R-Trees
Gkoulalas-Divanis et al. A network aware privacy model for online requests in trajectory data
CN101609462B (zh) 一种个人数据空间环境下的任务识别系统和方法
Han et al. Simultaneous incomplete traffic data imputation and similarity pattern discovery with bayesian nonparametric tensor decomposition

Legal Events

Date Code Title Description
A201 Request for examination
PA0109 Patent application

St.27 status event code: A-0-1-A10-A12-nap-PA0109

PA0201 Request for examination

St.27 status event code: A-1-2-D10-D11-exm-PA0201

D13-X000 Search requested

St.27 status event code: A-1-2-D10-D13-srh-X000

D14-X000 Search report completed

St.27 status event code: A-1-2-D10-D14-srh-X000

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

St.27 status event code: A-1-2-D10-D21-exm-PE0902

P11-X000 Amendment of application requested

St.27 status event code: A-2-2-P10-P11-nap-X000

P13-X000 Application amended

St.27 status event code: A-2-2-P10-P13-nap-X000

PG1501 Laying open of application

St.27 status event code: A-1-1-Q10-Q12-nap-PG1501

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

St.27 status event code: A-1-2-D10-D22-exm-PE0701

GRNT Written decision to grant
PR0701 Registration of establishment

St.27 status event code: A-2-4-F10-F11-exm-PR0701

PR1002 Payment of registration fee

St.27 status event code: A-2-2-U10-U11-oth-PR1002

Fee payment year number: 1

PG1601 Publication of registration

St.27 status event code: A-4-4-Q10-Q13-nap-PG1601

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 4

FPAY Annual fee payment

Payment date: 20120430

Year of fee payment: 5

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 5

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

FPAY Annual fee payment

Payment date: 20130614

Year of fee payment: 6

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 6

LAPS Lapse due to unpaid annual fee
PC1903 Unpaid annual fee

St.27 status event code: A-4-4-U10-U13-oth-PC1903

Not in force date: 20140502

Payment event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

PN2301 Change of applicant

St.27 status event code: A-5-5-R10-R13-asn-PN2301

St.27 status event code: A-5-5-R10-R11-asn-PN2301

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

PC1903 Unpaid annual fee

St.27 status event code: N-4-6-H10-H13-oth-PC1903

Ip right cessation event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

Not in force date: 20140502

P22-X000 Classification modified

St.27 status event code: A-4-4-P10-P22-nap-X000

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

PN2301 Change of applicant

St.27 status event code: A-5-5-R10-R13-asn-PN2301

St.27 status event code: A-5-5-R10-R11-asn-PN2301

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

点击 这是indexloc提供的php浏览器服务，不要输入任何密码和下载