KR101722419B1 - Index method based on irregular identifier space partition in wireless data broadcasting - Google Patents

Abstract

Translated fromKorean

본 발명은 무선 데이터 방송에서 다중데이터 항목을 빠르게 액세스할 수 있도록 불규칙한 식별자 공간분할에 기초한 인덱스 방법에 관한 것이다.
무선 데이터 방송에서 불규칙한 식별자 공간분할에 기초한 인덱스 방법은 방송을 위한 데이터 집합을 상위그룹과 하위그룹의 두 개 레벨의 데이터 집합으로 분리하여 식별자 공간을 분할하는 단계와, 클라이언트가 다중데이터 질의(Q_k)를 처리하기 위해 방송 채널에서 처음 액세스된 인덱싱 테이블을 이용하여 질의 처리를 시작하고, 제1큐(gpQueue)와 제2큐(dpQueue)의 우선순위 대기열을 사용하는 단계와, 인덱스가 상위 인덱스이면, 상위그룹 P_i의 상위 인덱스 PI_i에 액세스할 때 상기 제1큐(gpQueue)는 제1함수(getTimeFromCGT)와 제2함수(getTimeFromPGT)에 의해 업데이트되고, 인덱스가 하위 인덱스이면, 하위그룹 C_j의 하위 인덱스 CI_j에 액세스할 때 상기 제1큐(gpQueue)는 제3함수(getTimeFromCI)에 의해서, 상기 제2큐(dpQueue)는 제4함수(extractDataWithCI)에 의해 업데이트되는 단계를 포함한다.The present invention relates to an index method based on irregular identifier space division so that multiple data items can be accessed quickly in a wireless data broadcast.
And index method based on the random identifier space division in a radio data broadcast includes the steps of dividing the identifier space to separate the set of data for broadcast to the two level data set in the upper group and lower group, the client has multiple data query (Q_k , Starting query processing using the indexing table initially accessed in the broadcast channel and using the priority queues of the first queue (gpQueue) and the second queue (dpQueue), and if the index is a parent index said first queue (gpQueue) when accessing a high-index PI_i of the parent group P_i is updated by the first function (getTimeFromCGT) and the second function (getTimeFromPGT), if the index is the lower the index, the subgroup C_j when accessing a sub-index CI_j the first queue (gpQueue) comprises a third function by (getTimeFromCI), said second queues (dpQueue) is being updated by the fourth function (extractDataWithCI) And a step.

Description

Translated fromKorean

무선 데이터 방송에서 불규칙한 식별자 공간분할에 기초한 인덱스 방법{INDEX METHOD BASED ON IRREGULAR IDENTIFIER SPACE PARTITION IN WIRELESS DATA BROADCASTING}[0001] INDEX METHOD BASED ON IRREGULAR IDENTIFIER SPACE PARTITION IN WIRELESS DATA BROADCASTING [0002]

본 발명은 무선 데이터 방송에서 다중데이터 항목을 빠르게 액세스할 수 있도록 불규칙한 식별자 공간분할에 기초한 인덱스 방법에 관한 것으로, 클라이언트가 다중데이터 항목에 액세스 시 인덱스 대기시간을 줄여 액세스 시간을 향상시키는 것을 목적으로 하는 무선 데이터 방송에서 불규칙한 식별자 공간분할에 기초한 인덱스 방법에 관한 것이다.The present invention relates to an index method based on irregular identifier space division so that multiple data items can be accessed quickly in a wireless data broadcast. It is an object of the present invention to provide an index method for improving access time by reducing index waiting time when a client accesses multiple data items And an index method based on irregular identifier space division in wireless data broadcasting.

무선 데이터 방송 시스템은 대역폭이 제한된 통신 환경에서 임의의 수의 클라이언트에게 정보를 전달하는 방법이다. 방송서버가 무선 방송 채널에 주기적으로 데이터를 버켓(bucket, 논리적인 접근 단위) 단위로 방송하고 각 모바일 클라이언트가 그 무선 방송 채널에 액세스하여 원하는 데이터를 탐색한 후 다운로드하는 시스템이다. 이 시스템은 다수의 모바일 클라이언트들이 동시에 무선 방송 채널에 접속하여 원하는 컨텐츠를 다운로드할 수 있기 때문에 확장성이 높은 것이 특징이다.A wireless data broadcasting system is a method for transmitting information to an arbitrary number of clients in a limited bandwidth communication environment. A broadcast server periodically broadcasts data on a wireless broadcast channel in units of buckets (logical access units), and each mobile client accesses the wireless broadcast channel, searches for desired data, and downloads the system. This system is characterized by high scalability because a plurality of mobile clients can simultaneously access a wireless broadcast channel and download desired contents.

그러나 이 시스템에서 모바일 클라이언트는 원하는 데이터를 탐색하기 위해서 무선방송 채널에 액세스한 후, 원하는 데이터가 방송될 때까지 계속적으로 채널을 청취하여야 하며, 이런 방식의 질의 처리는 제약적인 사용시간을 가지는 배터리(battery)에 의존하는 모바일 클라이언트의 에너지 사용량을 크게 증가시키는 문제점을 야기시킨다. 채널을 지속적으로 청취할 필요없이 채널에서 원하는 데이터를 선택적으로 다운로드 받을 수 있는 효율적인 질의 처리를 위해 에어 인덱싱(air indexing) 기법이 개발되었다. 에어 인덱싱 기법은 무선 방송 채널에 방송되는 각각의 데이터의 방송시간을 유지하는 인덱싱 정보(indexing information)를 무선 채널에 추가하여 데이터와 함께 방송하는 기법이다. 에어 인덱싱 기법은 모바일 클라이언트로 하여금 원하는 데이터만을 청취하게 하여 에너지 효율적인 질의처리를 가능하게 해주며 에어 인덱싱 기법에 의한 모바일 클라이언트의 질의 처리는 다음과 같은 방식을 따른다.However, in this system, the mobile client must access the wireless broadcast channel to search for the desired data, and then listen to the channel continuously until the desired data is broadcasted. This type of query processing is performed by a battery battery-dependent mobile clients. Air indexing techniques have been developed for efficient query processing to selectively download desired data from a channel without having to constantly listen to the channel. The air indexing technique is a technique of adding indexing information for maintaining broadcast time of each data broadcast on a wireless broadcast channel to a wireless channel and broadcasting the data together with the data. The air indexing technique enables the mobile client to listen only to the desired data, thereby enabling energy efficient query processing. The query processing of the mobile client by the air indexing method follows the following method.

무선 방송 채널에 액세스한 모바일 클라이언트는 우선적으로 무선 채널의 인덱싱 정보를 액세스한 후, 그 인덱싱 정보를 이용하여 원하는 데이터의 방송 시간을 찾아낸다. 이때, 모바일 클라이언트가 인덱싱 정보에 우선적으로 접근하는 것을 돕기 위해 채널에서 방송되는 각 버켓의 버켓 헤더(bucket header)에 그 버켓 후 가장 먼저 액세스할 수 있는 인덱싱 정보가 방송되는 시간의 인덱스 포인터를 유지한다. 따라서 모바일 클라이언트는 무선 방송 채널에 액세스한 후, 첫 번째 버켓을 청취하면 바로 다음에 방송되는 인덱싱 정보의 방송 시간을 얻을 수 있다. 인덱싱 정보를 이용하여 모바일 클라이언트가 원하는 데이터의 방송 시간을 확인한 후, 모바일 클라이언트는 원하는 데이터의 방송 시간까지 휴지상태(doze mode, 에너지 절약모드)로 전환하고, 그 방송 시간에 활성 상태(active mode, 에너지를 사용하여 채널을 청취하는 모드)로 전환하여 무선 방송 채널에서 원하는 데이터만을 청취한다. 따라서 모바일 클라이언트는 무선 방송 채널에서 원하는 데이터만을 선택적으로 청취할 수 있게 되어 에너지 효율적인 질의 처리가 가능해 진다.The mobile client accessing the wireless broadcast channel first accesses the indexing information of the wireless channel, and then uses the indexing information to find the broadcast time of the desired data. At this time, in order to help the mobile client preferentially access the indexing information, the bucket header of each bucket broadcast in the channel maintains an index pointer of the time at which the indexing information that can be accessed first after the bucket is broadcast . Therefore, if the mobile client accesses the wireless broadcast channel and hears the first bucket, the broadcast time of the next indexing information broadcasted can be obtained. After the mobile client confirms the broadcast time of the desired data using the indexing information, the mobile client switches to the doze mode (energy saving mode) until the broadcasting time of the desired data, Mode for listening to a channel using energy) to listen only to desired data in a wireless broadcast channel. Therefore, the mobile client can selectively listen only to the desired data in the wireless broadcast channel, thereby enabling energy efficient query processing.

액세스 시간은 클라이언트가 방송 채널에 처음 액세스한 시간부터 클라이언트가 원하는 항목을 다운로드 하는 시간까지의 시간이다. 액세스 시간은 초기 조사(Initial Probe), 인덱스 대기시간(Index Waiting Time), 데이터 항목 검색 및 다운로드 시간으로 구성된다. 초기 조사에서, 클라이언트는 무선방송채널에 액세스 한 후, 처음 만나는 버킷으로부터 첫번째 인덱스에 대한 인덱스포인터를 획득한다. 각각의 버킷은 자기 뒤에 방송되는 첫번째 인덱스에 대한 인덱스포인터를 전달한다. 이후에 클라이언트는 휴지상태로 전환하여 인덱스를 대기하고 인덱스 포인터에서 활성상태로 전환하여 인덱스에 액세스한다. 액세스된 인덱스를 이용하여 클라이언트는 원하는 데이터항목에 대한 시간 포인터를 검색한다. 검색된 포인터를 사용하여 클라이언트는 채널에서 데이터항목을 선택적으로 다운로드한다.The access time is the time from when the client first accesses the broadcast channel to when the client downloads the desired item. The access time consists of an initial probe, an index waiting time, a data item search and a download time. In the initial investigation, the client accesses the wireless broadcast channel and then obtains an index pointer to the first index from the bucket being encountered for the first time. Each bucket carries an index pointer to the first index that is broadcast behind it. The client then goes to the dormant state to wait for the index and to transition from the index pointer to the active state to access the index. Using the accessed index, the client retrieves a time pointer for the desired data item. Using the retrieved pointer, the client selectively downloads data items from the channel.

액세스 시간을 개선하기 위해 Bcast라고 불리는 방송주기의 길이를 짧게 해야하기 때문에 인덱스의 크기를 줄이는 것이 중요하다. 또한, 액세스 시간을 개선하기 위해서 인덱스 대기 시간도 반드시 줄여야 한다. 인덱스 대기 시간은 방송채널에서 데이터와 교차적으로 방송되는 인덱스 사이의 간격에 영향을 받는다. 일반적으로 한 방송주기 내에서 방송되는 인덱스의 회수가 고정되어 있는 경우, 인덱스 사이의 간격을 규칙적으로 유지할 때 가장 좋은 인덱스 대기 시간이 된다.In order to improve access time, it is important to reduce the size of the index because the length of the broadcast period called Bcast must be shortened. Also, index waiting time must be reduced to improve access time. The index latency is influenced by the interval between the data and the index being broadcast cross-over in the broadcast channel. In general, when the number of indexes broadcast in one broadcasting cycle is fixed, the best index waiting time is maintained when the interval between the indexes is regularly maintained.

한편, 클라이언트의 효율적인 데이터 액세스를 위해 정수를 데이터 항목의 고유 식별자로 사용하는 다양한 인덱스가 제안되었다. 기존 인덱스를 사용하여 클라이언트는 인덱스 액세스를 통해 여러 데이터에 액세스할 수 있다. 클라이언트가 접근할 수 있는 데이터 항목의 수에 대한 제한이 없으므로 검색에서 다중데이터 액세스는 일반적이다. 예를 들어, DAB + 시스템에서 Journaline 서비스와 같은 무선 데이터 서비스를 사용하면 클라이언트는 다중 데이터 항목에 액세스할 수 있다. 스포츠 이벤트 정보를 제공하는 무선 데이터 방송 서비스를 통해 다중 데이터 액세스를 지원하는 인덱스 정보가 있으면 클라이언트는 축구, 야구, 농구 등 3개의 스포츠 이벤트 정보에 액세스 할 수 있다.On the other hand, various indexes have been proposed which use constants as unique identifiers of data items for efficient data access of clients. Existing indexes allow clients to access multiple data through index access. Multiple data accesses in retrieval are common because there is no limit to the number of data items a client can access. For example, a wireless data service such as the Journaline service on a DAB + system allows clients to access multiple data items. If there is index information supporting multiple data access through a wireless data broadcasting service providing sports event information, the client can access three sports event information such as soccer, baseball, and basketball.

지수 인덱스(EXP)는 각 데이터 항목에 할당된 분산 인덱스 테이블이다. 각 데이터 항목에 대한 지수 인덱스(EXP)는 방송채널에서 그 데이터 항목으로부터 지수거리만큼 떨어져 있는 데이터 항목들의 식별자와 시간 포인터를 유지한다. 데이터 항목과 해당 인덱스 테이블을 결합하여 청크(chunks)로 만든 후, 청크가 브로드캐스팅된다. 지수 인덱스(EXP)를 사용하면 클라이언트는 인덱스 테이블에 포함된 여러 개의 시간 포인터를 사용하여 채널에서 다중데이터에 액세스할 수 있다. 그러나 데이터 항목의 수가 증가함에 따라 지수인덱스(EXP)의 크기가 증가하므로 지수인덱스(EXP)에 의한 액세스 시간이 급격히 증가하는 문제가 있다.The exponent index (EXP) is a distributed index table assigned to each data item. The exponent index (EXP) for each data item maintains an identifier and a time pointer of data items that are separated by an exponential distance from the data item in the broadcast channel. The data item and its index table are combined into chunks, and then the chunk is broadcast. An exponential index (EXP) allows a client to access multiple data in a channel using multiple time pointers contained in the index table. However, since the size of the exponential index (EXP) increases as the number of data items increases, there is a problem that the access time by the exponential index (EXP) increases sharply.

GDI 방법은 지수 인덱스(EXP)와 달리 데이터 항목 그룹에 할당된 분산 인덱싱 테이블이다. GDI는 규칙적으로 데이터 항목의 식별자 공간(IS, Identifier Space)을 분할하여 전체 데이터 항목을 그룹으로 분리한다. 방송 채널에서 분할된 각각의 데이터그룹에 대한 GDI의 인덱싱 테이블이 방송되고 그 데이터 그룹에 속한 데이터들이 방송된다. GDI 방법은 인덱싱 테이블에 데이터 항목 그룹에 포함된 여러 데이터 항목들의 시간 포인터를 유지하여 클라이언트들이 다중데이터에 액세스 할 수 있게 해준다. 그러나 식별자 분포가 식별자공간(IS)상에서 치우쳐져 있는 경우, 규칙적 식별자공간(IS) 분할은 분할된 각 데이터그룹에 포함된 데이터 항목의 수를 다르게 만든다. 이로 인해 채널에서 방송되는 인덱스 테이블들 사이의 간격이 불규칙하게 되어 액세스 시간이 악화되는 문제가 있다.The GDI method is a distributed indexing table assigned to a data item group, unlike the exponential index (EXP). The GDI regularly divides the Identifier Space (IS) of a data item to separate all data items into groups. The indexing table of the GDI for each of the divided data groups in the broadcast channel is broadcast and data belonging to the data group is broadcast. The GDI method allows clients to access multiple data by maintaining the time pointer of the various data items contained in the data item group in the indexing table. However, if the identifier distribution is biased on the identifier space (IS), the regular identifier space (IS) partitioning makes the number of data items contained in each divided data group different. As a result, there is a problem that the interval between the index tables broadcast on the channel becomes irregular, and the access time deteriorates.

등록특허공보 제1067331호는 무선데이터 방송에서 셀기반의 복합 인덱스 구성 방법, 셀기반의 복합인덱스를 이용한 k근접 질의 처리 시스템 및 그 방법이 개시되어 있다.Patent Publication No. 1067331 discloses a cell-based composite index construction method in a wireless data broadcasting, a k-proximity query processing system using a cell-based composite index, and a method thereof.

본 발명은 상술한 바와 같은 문제점을 극복하기 위해 안출된 것으로, 무선 데이터 방송에서 인덱스 대기 시간을 줄여 클라이언트가 채널에서 다중 데이터에 빠르게 액세스할 수 있는 불규칙적 식별자 공간 분할에 기초한 인덱스 방법을 제공함에 그 목적이 있다.SUMMARY OF THE INVENTION The present invention has been made in order to overcome the above problems, and it is an object of the present invention to provide an index method based on irregular identifier space division in which a client can quickly access multiple data in a channel by reducing an index waiting time in wireless data broadcasting .

무선 데이터 방송에서 불규칙한 식별자 공간분할에 기초한 인덱스 방법은, 방송을 위한 데이터 집합을 상위와 하위의 두 개 레벨의 데이터 집합으로 분리하여 식별자 공간을 분할한 후, 각 데이터 그룹에 대한 인덱싱 테이블을 구성한다. 이를 이용하여, 방송채널에서 인덱싱 테이블과 데이터 그룹에 포함된 데이터를 교차적으로 방송하여 클라이언트들이 다중데이터 질의를 처리하여 질의된 데이터 항목을 채널에서 다운로드할 수 있게 한다.In an index method based on irregular identifier space division in wireless data broadcasting, an identifier space is divided by separating a data set for broadcast into two sets of data of upper and lower levels, and then an indexing table for each data group is formed . By using this, the data included in the indexing table and the data group are broadcast on the broadcast channel in an alternate manner, so that the clients can process the multi-data query and download the queried data item from the channel.

두 개 레벨의 식별자 공간 분할은 방송을 위한 데이터 집합의 데이터 항목들을 식별자의 증가순으로 정렬한 후, 같은 수의 데이터를 포함하도록 상위 데이터 그룹으로 분리하고, 그 그룹들에 포함된 데이터들의 식별자가 포함되도록 식별자 공간을 분할한다. 각각의 상위 그룹에 포함된 데이터들을 같은 수의 데이터를 포함하는 하위 데이터 그룹으로 분리하고 각 그룹에 포함된 데이터들의 식별자가 포함되도록 상위그룹에 대한 식별자 공간을 분할한다.The two-level identifier space division is performed by arranging the data items of the data set for broadcast in ascending order of identifiers, then dividing the data items into high-level data groups so as to include the same number of data, Divide the identifier space to include. Divides the data included in each upper group into lower data groups including the same number of data, and divides the identifier space for the upper group so that the identifiers of the data included in each group are included.

상위와 하위로 분할된 식별자 공간을 이용하여 상위 인덱싱 테이블과 하위 인덱스 테이블을 구성하고 채널에서 각 그룹에 포함된 데이터와 함께 인덱싱 테이블을 방송하여 클라이언트들이 다중데이터 질의를 처리할 수 있도록 한다. 클라이언트가 다중데이터질의(Q_k)를 처리하기 위해 방송 채널에서 처음 액세스된 인덱싱 테이블을 이용하여 질의 처리를 시작한다. 질의 처리 과정에서 제1큐(gpQueue)와 제2큐(dpQueue)의 우선순위 대기열을 사용하는 단계와, 상기 인덱스가 상위 인덱스이면, 상위그룹 P_i의 상위 인덱스 PI_i에 액세스할 때 상기 제1큐(gpQueue)는 제1함수(getTimeFromCGT)와 제2함수(getTimeFromPGT)에 의해 업데이트되고, 상기 인덱스가 하위 인덱스이면, 하위그룹 C_j의 하위 인덱스 CI_j에 액세스할 때 상기 제1큐(gpQueue)는 제3함수(getTimeFromCI)에 의해서, 상기 제2큐(dpQueue)는 제4함수(extractDataWithCI)에 의해 업데이트되는 단계를 포함한다.The upper indexing table and the lower indexing table are configured using the upper and lower identifier spaces, and the indexing table is broadcasted together with the data included in each group in the channel so that clients can process multiple data queries. The client begins query processing using the indexing table initially accessed in the broadcast channel to process multiple data queries (Q_k ). Using a priority queue of a first queue (gpQueue) and a second queue (dpQueue) in a query process, and when the index is an upper index, when accessing a higher index PI_i of a higher group P_i , queue (gpQueue) has a first function (getTimeFromCGT) and a is updated by the second function (getTimeFromPGT), the first cue (gpQueue) when when the index is the lower the index, the access to the sub-index CI_j of sub-group C_j And the second queue (dpQueue) is updated by a fourth function (extractDataWithCI) by a third function (getTimeFromCI).

본 발명은 클라이언트가 식별자 공간에 대해 데이터 항목의 식별자 분포가 치우쳐 있는 분포를 갖는 데이터 집합에 대한 무선 데이터 방송 채널에서 효율적인 다중데이터 질의(multipoint query)를 처리할 수 있다. 즉, 클라이언트가 다중 데이터 항목에 빠르게 액세스 할 수 있도록 불규칙한 식별자 공간 분할을 통해 데이터를 두 개의 레벨의 그룹으로 나누며, 이를 통해 방송되는 인덱스 테이블 간의 간격을 동일하게 유지하게 하여 채널에서 클라이언트의 인덱스 대기 시간을 줄이는 효과가 있다.The present invention can process an efficient multi-data query (multi-data query) in a wireless data broadcasting channel for a data set in which the client has a distribution in which the distribution of identifiers of data items is biased with respect to the identifier space. In other words, data is divided into groups of two levels through an irregular identifier space division so that the client can access to multiple data items quickly, and the intervals between the index tables broadcasted through the groups are kept the same, .

도 1은 본 발명의 일 실시예에 따른 데이터 그룹과 불규칙 식별자 공간 분할을 설명하는 도면이다.
도 2는 본 발명의 일 실시예에 따른 방송 채널의 구조를 설명하는 도면이다.
도 3은 본 발명의 일 실시예에 따른 다중데이터 질의처리를 위한 알고리즘을 설명하는 도면이다.
도 4는 본 발명의 일 실시예에 따른 다중데이터 질의 처리를 위한 알고리즘의 함수를 설명하는 도면이다.
도 5는 본 발명에 따른 무선 데이터 방송에서 불규칙한 식별자 공간 분할에 기초한 인덱스 방법과 다른 방법의 시뮬레이션 결과를 비교한 그래프들이다.1 is a view for explaining a data group and a random ID space division according to an embodiment of the present invention.
2 is a diagram illustrating a structure of a broadcast channel according to an embodiment of the present invention.
3 is a diagram illustrating an algorithm for multiple data query processing according to an embodiment of the present invention.
4 is a diagram illustrating a function of an algorithm for multiple data query processing according to an embodiment of the present invention.
FIG. 5 is a graph illustrating a comparison between the index method based on irregular ID space division and the simulation result of another method in the wireless data broadcasting according to the present invention.

본 명세서에 개시되어 있는 본 발명의 개념에 따른 실시 예들에 대해서 특정한 구조적 또는 기능적 설명은 단지 본 발명의 개념에 따른 실시 예들을 설명하기 위한 목적으로 예시된 것으로서, 본 발명의 개념에 따른 실시 예들은 다양한 형태들로 실시될 수 있으며 본 명세서에 설명된 실시 예들에 한정되지 않는다.It is to be understood that the specific structural or functional description of embodiments of the present invention disclosed herein is for illustrative purposes only and is not intended to limit the scope of the inventive concept But may be embodied in many different forms and is not limited to the embodiments set forth herein.

본 발명의 개념에 따른 실시 예들은 다양한 변경들을 가할 수 있고 여러 가지 형태들을 가질 수 있으므로 실시 예들을 도면에 예시하고 본 명세서에서 상세하게 설명하고자 한다. 그러나 이는 본 발명의 개념에 따른 실시 예들을 특정한 개시 형태들에 대해 한정하려는 것이 아니며, 본 발명의 사상 및 기술 범위에 포함되는 모든 변경, 균등물, 또는 대체물을 포함한다.The embodiments according to the concept of the present invention can make various changes and can take various forms, so that the embodiments are illustrated in the drawings and described in detail herein. It is not intended to be exhaustive or to limit the invention to the particular forms disclosed, but on the contrary, is intended to cover all modifications, equivalents, or alternatives falling within the spirit and scope of the invention.

본 명세서에서 사용한 용어는 단지 특정한 실시 예를 설명하기 위해 사용된 것으로서, 본 발명을 한정하려는 의도가 아니다. 단수의 표현은 문맥상 명백하게 다르게 뜻하지 않는 한, 복수의 표현을 포함한다. 본 명세서에서, "포함하다" 또는 "가지다" 등의 용어는 본 명세서에 기재된 특징, 숫자, 단계, 동작, 구성 요소, 부분품 또는 이들을 조합한 것이 존재함을 지정하려는 것이지, 하나 또는 그 이상의 다른 특징들이나 숫자, 단계, 동작, 구성 요소, 부분품 또는 이들을 조합한 것들의 존재 또는 부가 가능성을 미리 배제하지 않는 것으로 이해되어야 한다.The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the invention. The singular expressions include plural expressions unless the context clearly dictates otherwise. In this specification, the terms "comprises" or "having" and the like are used to specify that there are features, numbers, steps, operations, elements, parts or combinations thereof described herein, But do not preclude the presence or addition of one or more other features, integers, steps, operations, components, parts, or combinations thereof.

이하, 본 명세서에 첨부된 도면들을 참조하여 본 발명의 실시 예들을 상세히 설명한다.Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings attached hereto.

1. 불규칙한 식별자 공간분할에 기초한 인덱스 방법(IIP)1. Index method based on irregular identifier space division (IIP)

본 발명은 무선 데이터 방송에 적용되는 것으로, 방송서버가 데이터 집합 D의 N개 데이터 항목 들을 방송하는 채널에서 클라이언트가 자신의 다중데이터질의(Q_k)에 대한 결과를 검색한다. 상기 다중 데이터 질의(Q_k)는 채널에서 검색할 k 개의 데이터 항목의 정수 식별자 집합이다.The present invention is applied to wireless data broadcasting in which a client retrieves a result of its multiple data query (Q_k ) in a channel on which a broadcasting server broadcasts N data items of a data set D. The multiple data query (Q_k ) is a set of integer identifiers of k data items to be searched in the channel.

데이터 집합 D의 항목 di는 고유 식별자로 음이 아닌 정수 i를 가진다. 데이터 집합 D의 경우 식별자 공간(IS)은 0부터 데이터 집합 D의 항목 중 가장 큰 식별자까지의 정수 집합으로 정의된다. 예컨대, 도 1에서 데이터 집합 D = {d1, d2, d5, d8, d9, d10, d11, d15, d17, d19, d21, d27, d28, d31, d53, d63}에 대한 IS는 0 ≤ IS ≤ 63로 정의된다.The item di in data set D has a non-negative integer i as a unique identifier. In the case of the data set D, the identifier space (IS) is defined as an integer set from 0 to the largest identifier among the items in the data set D. For example, the IS for the data set D = {d1, d2, d5, d8, d9, d10, d11, d15, d17, d19, d21, d27, d28, d31, d53, d63} 63.

클라이언트의 다중데이터 질의가 Q₃={2, 10, 63}이면, 클라이언트는 채널로부터 데이터 항목 d2, d10 및 d63을 검색 및 다운로드한다.If multiple data query of a client_{Q 3 = {2, 10,} 63}, the client searches and downloads the data item d2, d10 and d63 from the channel.

본 발명의 불규칙한 식별자 공간분할에 기초한 인덱스 방법(IIP)을 구성하기 위해 데이터 집합 D의 N 개의 데이터 항목을 상위 데이터 그룹과 하위 데이터 그룹의 두 개의 레벨 그룹으로 분리한다. 데이터 집합 D를 식별자의 오름차순으로 정렬한 후

개의 데이터 항목들을 각각 분리하여 상위 데이터 그룹으로 설정한다. r_p는 상위 데이터 그룹의 크기를 결정하는 요소이다. 이후 각 상위 데이터 그룹에 대해

개의 데이터 항목을 하위 데이터 그룹으로 분할한다. 여기서 r_c는 하위 데이터 그룹의 크기를 결정하는 요소이다.In order to construct the index method (IIP) based on the irregular identifier space division according to the present invention, the N data items of the data set D are divided into two level groups, i.e., an upper data group and a lower data group. After sorting data set D in ascending order of identifier

Data items are separated and set as an upper data group. r_p is an element that determines the size of the upper data group. Then, for each upper data group

Data items into lower data groups. Where r_c is a factor that determines the size of the lower data group.

도 1의 (a)는 r_p = 0.25, r_c = 0.5에 대한 상위 및 하위 데이터 그룹을 나타낸다. 대응하는 데이터 그룹에 대한 상위 그룹 P_i 및 그 하위 그룹 C_j는 이하와 같이 불규칙한 IS 분할방식으로 정의된다.Figure 1 (a) shows the upper and lower data groups for r_p = 0.25 and r_c = 0.5. The upper group P_i and its subgroup C_j for the corresponding data group are defined by an irregular IS partitioning scheme as follows.

상위 그룹 P_i는 i 번째 상위 데이터 그룹에 포함되는 최소 식별자와 최대 식별자의 집합이다.The upper group P_i is a set of the minimum and maximum identifiers included in the i-th upper data group.

, 여기서 id^M_i는 i 번째 상위 그룹의 최대 식별자이고, id^m_i는 i 번째 상위 그룹의 최소로서 id^M_i-1 + 1 의 값을 갖는다.

Where id^M_i is the identifier of the i-th maximum of the parent group,^m id_i has a value of at least a top of the i-th group id^M_i-1 + 1.

하위 그룹 C_j는 상위 그룹 P_i의 j 번째 하위 데이터 그룹을 커버하는 최소 식별자와 최대 식별자의 집합이다.The subgroup C_j is a set of the minimum and maximum identifiers that cover the j-th lower data group of the parent group P_i .

, 여기서, id^M_j는 j 번째의 하위 데이터 그룹의 최대 식별자이고, id^m_j는 j 번째 하위 그룹의 최소 식별자로서 id^M_j-1 + 1 의 값을 갖는다. r_c는 각 상위그룹을 여러 개의 하위 그룹으로 분리하기 위한 비율이다.

, Where id^M_j is the maximum identifier of the j-th lower data group, and id^m_j is the minimum identifier of the_j- th lower group and has a value of id^M_j-1 + 1. r_c is the ratio for separating each higher group into several subgroups.

도 1 (a)는 데이터 그룹에 대응하는 상위 및 하위 그룹뿐만 아니라 데이터그룹 D의 상위 및 하위 데이터 그룹을 나타낸다. 도 1 (b)는 치우쳐진 식별자 분포와 그에 대한 불규칙적 분할에 의한 두 개 레벨의 계층 그룹을 나타낸다.1 (a) shows the upper and lower data groups of the data group D as well as the upper and lower groups corresponding to the data group. FIG. 1 (b) shows a hierarchical group of two levels by a biased identifier distribution and an irregular division thereof.

1.1 인덱스 구조1.1 Index structure

불규칙한 식별자 공간분할에 기초한 인덱스 방법(IIP)은 상위그룹 P_i에 대한 상위 인덱스 PI_i와 하위그룹 C_j에 대한 하위 인덱스 CI_j의 두 종류의 선형 인덱싱 테이블로 구성된다.Index method based on the random identifier space division (IIP) is composed of two kinds of linearly indexing table of the child index CI_j for the parent index PI_i and C_j sub-groups of the parent group P_i.

상위그룹 P_i에 대한 상위 인덱스 PI_i는 다음과 같이 구성된다.The upper index PI_i for the upper group P_i is constructed as follows.

PI_i=<P_i, CGT, PGT>PI_i = < P_i , CGT, PGT >

P_i : 상위그룹 P_i를 나타내는 식별자 집합.P_i : a set of identifiers representing the parent group P_i .

CGT (Child Group Table) : {<C_j, t_j>} 여기서, C_j는 상위그룹 P_i에 속하는 하위그룹이고, t_j는 하위그룹 C_j대한 하위인덱스 CI_j 의 방송 시간에 대한 시간 포인터이고 j는

이다. r_c는 각 상위그룹을 여러 개의 하위 그룹으로 분리하기 위한 비율이다.CGT (Child Group Table): { <C j, t j>} , where, C_j is a subgroup belonging to the upper group P_i, t_j is the time point of the broadcast time of the sub-group C_j sub-index CI_j for And j is

to be. r_c is the ratio for separating each higher group into several subgroups.

PGT (Parent Group Table) : {<P_a, T_a>}; 여기서 P_a는 상위 그룹이고, t_a는 상위 그룹 P_a에 대한 상위 인덱스 PI_a의 방송시간에 대한 시간 포인터이고 a는

이다.PGT (Parent Group Table): {<P_a , T_a >}; Where P_a is a higher group, t_a is a time pointer for the broadcast time of the higher index PI_a for the higher group P_a , and a is

to be.

상위그룹 P_i는 클라이언트에게 상위인덱스 PI_i의 식별자 범위(coverage)를 나타낸다. 상위그룹 P_i를 사용하여 클라이언트는 질의처리를 위해 상위그룹 P_i의 하위 그룹에 액세스해야 하는지 여부를 결정할 수 있다. 테이블 CGT는 클라이언트가 식별자 분할의 로컬 뷰(local view), 즉 상위그룹 P_i에 속한 각 하위 그룹의 커버리지와 각 하위그룹에 대한 시간포인터를 확인할 수 있게 한다. CGT를 사용하여 클라이언트는 주어진 다중 데이터 질의(Q_k)에 속한 식별자를 포함하는 하위 그룹에 액세스 할 수 있다.The upper group P_i represents the identifier range of the upper index PI_{i to} the client. Using the parent group P_i , the client can determine whether to access the child group of the parent group P_i for query processing. The table CGT allows the client to see the local view of the identifier partition, the coverage of each subgroup in the parent group P_i and the time pointer for each subgroup. Using CGT, the client can access a subgroup containing identifiers belonging to a given multiple data query (Q_k ).

테이블 PGT는 클라이언트에게 식별자 분할의 글로벌 뷰(global view)와 채널에서 각 상위 그룹에 대한 시간 포인터를 제공한다.The table PGT provides the client with a global view of the identifier partition and a time pointer for each higher group in the channel.

하위인덱스 CI_j에 대한 CI_j는 다음과 같이 구성된다.CI_j CI_j for the sub-index is organized as follows.

CI_j = <IDT, NCG, t_nc, t_np>CI_j = <IDT, NCG, t_nc , t_np >

IDT(ID 테이블) : {<id, t_d>} 여기서, id는 C_j에 포함된 데이터 항목의 식별자이고 t_d는 무선 채널에서 그 데이터에 대한 시간 포인터이다.IDT (ID table): {< id, t_d &gt;} where id is the identifier of the data item contained in C_j and t_d is the time pointer for that data in the wireless channel.

NCG (Next Child Group) : C_j의 다음 하위 그룹의 식별자집합.NCG (Next Child Group): A set of identifiers of the next child group of C_j .

t_nc : 방송채널에서 C_j 다음에 방송되는 하위 그룹에 대한 시간 포인터.t_nc : Time pointer for a subgroup broadcast after C_j in the broadcast channel.

t_np : 방송채널에서 C_j 다음에 방송되는 상위 그룹에 대한 시간포인터.t_np : Time pointer for the parent group broadcast after C_j in the broadcast channel.

테이블 IDT는 클라이언트가 주어진 다중 데이터 질의 Q_k 내의 식별자와 그 식별자에 대한 시간 포인터를 추출할 수 있게 한다. NCG는 다음 하위 그룹 C_j+1의 식별자범위를 클라이언트에게 알리고, t_nc는 클라이언트가 C_j+1에 액세스할 수 있게 한다. NCG와 t_nc는 채널에서 모든 하위 그룹을 연결하는 체인을 구성한다. NCG와 t_nc를 사용하여 클라이언트는 채널의 모든 하위 그룹에 차례로 액세스할 수 있다. 시간 포인터 t_np는 CI_j의 다음에 방송되는 상위 인덱스에 액세스할 수 있게 하여 클라이언트가 식별자 공간IS의 분할에 대한 글로벌 뷰를 얻을 수 있도록 한다.The table IDT allows the client to extract an identifier in a given multiple data query Q_k and a time pointer for that identifier. The NCG informs the client of the identifier range of the next subgroup C_{j + 1} , and t_nc allows the client to access C_{j + 1} . NCG and t_nc form a chain connecting all subgroups in the channel. Using NCG and t_nc , the client can in turn access all subgroups of the channel. The time pointer t_np allows access to the parent index broadcast next to CI_j so that the client can obtain a global view of the partitioning of the identifier space IS.

1.2 채널 구조1.2 Channel structure

도 2를 참조하면, 방송 채널의 구조는 상위 데이터 그룹에 대한 상위 인덱스가 그룹 번호가 큰 순서로 방송되고, 각 상위 데이터 그룹에 포함된 하위 데이터 그룹에 대한 하위 인덱스가 방송된 후, 그 하위 데이터 그룹에 포함된 데이터들이 방송된다. 도 2는 도 1의 데이터 집합 D에 대해 제안된 IIP에 의한 채널 구조를 보여주고 있다. 제안된 발명은 채널 상에서 방송되는 인덱스 사이의 간격을 균등하게 할 수 있다. 이렇게 하여 본 발명은 채널에서 인덱스 대기 시간을 단축시키고 액세스 시간을 향상시킨다.Referring to FIG. 2, the structure of a broadcast channel is such that an upper index for an upper data group is broadcast in the order of a larger group number, a lower index for a lower data group included in each upper data group is broadcast, Data contained in the group is broadcast. FIG. 2 shows the IIP-based channel structure proposed for the data set D of FIG. The proposed invention can equalize intervals between indexes broadcast on a channel. Thus, the present invention reduces index waiting time and improves access time in a channel.

1.3 다중데이터 질의(multipoint query) 처리1.3 Multipoint query processing

제안된 발명의 상위 및 하위 인덱스을 사용하여 클라이언트는 다중데이터 질의 Q_k를 처리할 수 있다. 클라이언트는 채널에 액세스 한 후의 첫번째 인덱스에 액세스하여 프로세스를 시작하고 질의 처리를 위해 클라이언트는 제1큐(gpQueue) 및 제2큐(dpQueue)의 두 가지 우선 순위 대기열을 사용한다. 이것은 인덱스와 데이터 항목에 대한 시간 포인터를 증가하는 순서로 유지하는 대기열이다.Using the upper and lower indexes of the proposed invention, the client can process multiple data queries Q_k . The client accesses the first index after accessing the channel to start the process and the client uses two priority queues, the first queue (gpQueue) and the second queue (dpQueue). This is a queue that keeps indexes and time pointers to data items in increasing order.

도 3의 알고리즘 1(Algorithm 1)은 제안된 IIP를 사용하여 다중데이터 질의를 처리하는 절차를 나타낸다. 클라이언트는 6행과 7행에서 상위그룹 P_i에 대한 상위인덱스 PI_i에 액세스한 후, 제1함수(getTimeFromCGT)와 제2함수(getTimeFromPGT)를 이용하여 제1큐(gpQueue)를 업데이트한다.Algorithm 1 of FIG. 3 shows a procedure for processing multiple data queries using the proposed IIP. Client to access the higher index PI_i for the parent group P_i inline 6 andline 7, by using a first function (getTimeFromCGT) and the second function (getTimeFromPGT) updates the first queue (gpQueue).

클라이언트는 9행과 10행에서 하위그룹 C_j에 대한 하위인덱스 CI_j를 사용하여 제1큐(gpQueue)는 제3함수(getTimeFromCI)를 이용하여 업데이트하고 제2큐(dpQueue)는 제4함수(extractDataWithCI)를 이용하여 업데이트한다.The client updates the first queue (gpQueue) using the third function (getTimeFromCI) using the sub-index CI_j for the subgroup C_j inrows 9 and 10 and the second queue (dpQueue) updates the fourth function extractDataWithCI).

이때, 도 4의 제1함수(getTimeFromCGT)는 상기 상위인덱스 PI의 CGT가 입력되고, (P_i∩Q_k≠Ø)이면, PI에 포함된 CGT의 모든 C_j에 대해, (C_j∩Q_k≠Ø) 이면, t_j를 제1큐(gpQueue)에 입력한다. 도4의 제2함수(getTimeFromPGT)는 상위인덱스 PI의 PGT가 입력되고, PGT의 모든 P_a에서, (P_a∩Q_k≠Ø)이면 t_a를 제1큐(gpQueue)에 입력한다. 도 4의 제3함수(getTimeFromCI)는 하위인덱스 CI가 입력되고, (NCG∩Q_k≠Ø)이면, t_nc를 제1큐(gpQueue)에 입력하고, 그렇지 않은 경우에 대해서는 제1큐(gpQueue)에 t_np를 입력한다.In this case, the first function (getTimeFromCGT) of Figure 4 is the CGT of the higher-index PI is_{input, (P i ∩Q k ≠ Ø} ) if, for any of the CGT C_j included in the PI, (C_j ∩Q_k ≠ Ø), t_j is input to the first queue (gpQueue). The second function (getTimeFromPGT) of FIG. 4 inputs the PGT of the upper index PI and inputs t_a to the first queue (gpQueue) if (P_a ∩Q_k ≠ Ø) in all P_a of the PGT. The third function (getTimeFromCI) of Figure 4 is the child index CI is input, (NCG∩Q_k ≠ Ø) is input to t_nc to the first queue (gpQueue), and the first queue for Otherwise (gpQueue ), Enter t_np .

도4의 제4함수(extractDataWithCI)는 하위인덱스 CI가 입력되고, (C_j∩Q_k≠Ø)이면, Q_k의 모든 id에서, (id∈IDT)이면 t_d(∈IDT)를 제2큐(dpQueue)에 입력하고, 그렇지 않은 경우에 대해서는, (id∈C_j)이면, 다중데이터질의 Q_k에서 id를 삭제한다.A fourth function (extractDataWithCI) of Figure 4 is the child index CI is_{input, (C j ∩Q k ≠ Ø} ) is, on all of the Q_k id, (id∈IDT) a second t_d (∈IDT) is It is for the case, and the input queue (dpQueue), otherwise, (id∈C_j), and deletes the data in a multi-id query Q_k.

2.1 시뮬레이션 환경2.1 Simulation environment

평가를 위해 이산 시간 시뮬레이션 패키지인 SimJava를 사용하여 브로드 캐스트 서버, 무선 채널 및 클라이언트로 구성된 시뮬레이션 테스트 베드를 구현했다. 무선 데이터 브로드캐스트에서 클라이언트는 서로 영향을 주지 않기 때문에 테스트 베드에서 클라이언트는 하나만 구현했다. 테스트 베드를 이용한 시뮬레이션에서 제안된 IIP, GDI 및 EXP에 의한 버킷 단위의 액세스 시간을 측정했다.For the evaluation, a discrete-time simulation package, SimJava, was used to implement a simulation testbed consisting of a broadcast server, a wireless channel and a client. In the wireless data broadcast, the clients did not affect each other, so we implemented only one client in the test bed. In the simulation using the test bed, the bucket-based access time was measured by the proposed IIP, GDI, and EXP.

시뮬레이션을 위해 그리스의 5922개의 도시의 위치정보에 대한 실제 데이터 집합을 사용했다. Hilbert Curve를 도시의 위치를 포함하는 2D 공간에 적용한 후 Hilbert Curve 값을 사용하여 각 도시의 위치를 도시의 고유한 정수 식별자로 변환하여 사용했다. 이 방법을 통해 자연스럽게 치우쳐진 식별자 분포를 얻을 수 있다.For the simulation, we used the actual data set for the location information of 5922 cities in Greece. After applying the Hilbert Curve to the 2D space containing the location of the city, we use the Hilbert Curve value to convert the location of each city to the city's unique integer identifier. With this method, you can obtain a natural-biased distribution of identifiers.

시뮬레이션을 위한 파라미터로서 식별자 크기와 시간 포인터 크기를 모두 8 바이트로 설정했다. 데이터 항목의 크기를 1024 바이트로 설정하고 버킷 크기를 64 바이트로 설정한다. 또한 상위그룹과 하위그룹에 대한 r_p와 r_c를 각각 0.01과 0.1로 설정했다. 공정한 비교를 위해 GDI에 r_p와 r_c의 동일한 값을 적용한다.Both the identifier size and the time pointer size are set to 8 bytes as parameters for the simulation. Set the size of the data item to 1024 bytes and the bucket size to 64 bytes. We also set r_p and r_c for the upper and lower groups to 0.01 and 0.1, respectively. Apply the same values of r_p and r_c to GDI for a fair comparison.

또한, 공정성을 위해 EXP의 인덱싱 테이블에 클라이언트에게 가장 많은 시간 포인터를 제공하기 위해 EXP를 위한 지수의 밑수로 2로 설정했다. Q_k의 k를 1, 10, 20, 40 및 60으로 설정하고, 각 k에 대해 50,000 번의 다중 데이터 질의를 실행했다. 실행된 각각의 다중데이터 질의의 액세스 시간에 대한 평균 액세스 시간을 버켓 단위로 측정했다.Also, for fairness, I set the base of the exponent for EXP to 2 to provide the client with the most time pointers in the index table of the EXP. The_k of k k was set to 1, 10, 20, 40, and 60, and 50,000 multiple data queries were performed for each k. The average access time to the access time of each executed multiple data query was measured in buckets.

2.2 성능 비교2.2 Performance Comparison

제안된 IIP의 성능을 평가하기 위해 IIP, GDI 및 EXP에 의한 방송주기의 길이인 Bcast와 다중데이터 질의 Q_k를 처리하는데 걸리는 액세스 시간을 비교한다.To evaluate the performance of the proposed IIP, we compare the access time taken to process Bcast, the length of the broadcast period by IIP, GDI, and EXP, and_Qk of multiple data queries.

도 5(a)는 식별자 공간 분할에 의한 그룹기반의 IIP와 GDI에 의한 Bcast가 EXP에 의한 Bcast보다 짧다는 것을 보여준다. 이는 그룹 기반 인덱싱이 클라이언트가 질의를 처리하는데 더 효율적임을 보인다. IIP와 GDI의 Bcast가 EXP보다 짧은 것은 IIP와 GDI의 크기가 EXP의 크기보다 작기 때문이다.FIG. 5 (a) shows that group-based IIP and GDI-based Bcast by identifier space division are shorter than Bcast by EXP. This shows that group-based indexing is more efficient for clients to process queries. The Bcast of IIP and GDI is shorter than EXP because the size of IIP and GDI is smaller than the size of EXP.

도 5(b)는 제안된 IIP, GDI 및 EXP의 버켓 수로 표시한 액세스 시간을 나타내며, 클라이언트가 단일데이터 질의 Q_k (k = 1)를 처리 할 때 및 다중데이터 질의(Q_k; k = 10, 20, 40, 60)를 처리할 때를 비교한다. 이는 다중데이터 질의에 대한 액세스시간뿐만 아니라 단일데이터에 대한 경우에도 제안된 IIP가 GDI 및 EXP보다 우월함을 보여준다. 또한, IIP는 치우쳐진 식별자 분포에 대한 불규칙한 ID공간 분할을 이용하여 채널상에 방송되는 인덱스 사이의 간격을 동일하게 하여 인덱스 대기 시간을 줄여서 클라이언트가 질의된 데이터에 신속하게 액세스 할 수 있도록 도와준다. 이는 제안된 IIP에 의한 인덱스 대기 시간 감소가 다중 데이터뿐만 아니라 단일 데이터에 대한 액세스 시간을 감소시키는데 효과적이라는 것을 보여준다.5 (b) shows the access times indicated by the number of buckets of the proposed IIP, GDI and EXP, and when the client processes a single data query_Qk (k = 1) and multiple data queries (_Qk ; k = , 20, 40, 60). This shows that the proposed IIP is superior to GDI and EXP for single data as well as access time for multiple data queries. In addition, IIP uses irregular ID space partitioning for biased identifier distributions to reduce the index latency by making the intervals between indexes broadcast on the channel the same, thus helping clients to quickly access the queried data. This shows that the reduction of index latency by the proposed IIP is effective in reducing access time to single data as well as multiple data.

본 발명은 도면에 도시된 실시 예를 참고로 설명되었으나 이는 예시적인 것에 불과하며, 본 기술 분야의 통상의 지식을 가진 자라면 이로부터 다양한 변형 및 균등한 타 실시 예가 가능하다는 점을 이해할 것이다. 따라서, 본 발명의 진정한 기술적 보호 범위는 첨부된 등록청구범위의 기술적 사상에 의해 정해져야 할 것이다.While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it is evident that many alternatives, modifications and variations will be apparent to those skilled in the art. Accordingly, the true scope of the present invention should be determined by the technical idea of the appended claims.

Claims (5)

Translated fromKorean

무선 데이터 방송에서 불규칙한 식별자 공간분할에 기초한 인덱스 방법에 관한 것으로,
방송을 위한 데이터 집합을 상위그룹(P_i)과 하위그룹(C_j)의 두 개 레벨의 데이터 집합으로 분리하여 식별자 공간을 분할하는 단계;
클라이언트가 다중데이터 질의(Q_k)를 처리하기 위해 방송 채널에서 처음 액세스된 인덱싱 테이블을 이용하여 질의 처리를 시작하고, 제1큐(gpQueue)와 제2큐(dpQueue)의 우선순위 대기열을 사용하는 단계; 및
인덱스는 다중 데이터 질의를 처리하는 과정에서 이용되는 상위인덱스와 하위인덱스를 포함하고, 인덱스가 상위 인덱스(PI_i)이면, 상위그룹(P_i)의 상위 인덱스(PI_i)에 액세스할 때 상기 제1큐(gpQueue)는 제1함수(getTimeFromCGT)와 제2함수(getTimeFromPGT)에 의해 업데이트되고, 상위 인덱스(PIi)는 상기 상위그룹(Pi)의 데이터 집합을 식별하는 인덱스이고,
인덱스가 하위 인덱스이면, 하위그룹(C_j)의 하위 인덱스(CI_j)에 액세스할 때 상기 제1큐(gpQueue)는 제3함수(getTimeFromCI)에 의해서, 상기 제2큐(dpQueue)는 제4함수(extractDataWithCI)에 의해 업데이트되는 단계를 포함하고, 하위 인덱스(CIj)는 상기 하위그룹(Cj)의 데이터 집합을 식별하는 인덱스이고, 상기 i는 상위그룹(Pi)의 번호이고,

의 범위를 가지며, r_p는 데이터 방송을 위한 데이터 집합을 여러 개의 상위그룹으로 분리하기 위한 비율을 의미하고,
상기 j는 하위그룹(C_j)의 번호로서 하위그룹(C_j)는 i번째 상위그룹(Pi)에 포함되는 무선 데이터 방송에서 불규칙한 식별자 공간분할에 기초한 인덱스 방법.The present invention relates to an index method based on irregular identifier space division in wireless data broadcasting,
Dividing a data set for broadcasting into a data set of two levels of a higher group (P_i ) and a lower group (C_j ), and dividing the identifier space;
The client starts query processing using the indexing table initially accessed in the broadcast channel to process the multiple data queries Q_k and uses the priority queues of the first queue gpQueue and the second queue dpQueue step; And
The index includes an upper index and a lower index used in the process of processing multiple data and when accessing the upper index PI_{i of the} upper group P_i when the index is the upper index PI_i , 1 queue (gpQueue) is updated by the first function (getTimeFromCGT) and the second function (getTimeFromPGT), the upper index PIi is an index for identifying the data set of the upper group Pi,
If the index is the lower the index, the lower group (C_j), by the first queue (gpQueue) is a third function (getTimeFromCI) when accessing the sub-index (CI_j) of the second queue (dpQueue) is a fourth Function extractDataWithCI, the lower index CIj is an index identifying a data set of the lower group Cj, i is a number of the upper group Pi,

R_p denotes a rate for separating a data set for data broadcasting into a plurality of upper groups,
Where j is the sub group (C_j) sub-group (C_j) as the number of the index method based on the random identifier space division in a radio data broadcast included in the i-th upper group (Pi).제1항에 있어서,
식별자 공간을 분할하는 단계는,
상위그룹(P_i)과 하위그룹(C_j)에 대한 인덱싱 테이블을 구성하고, 방송채널에서 인덱싱 테이블과 데이터 그룹에 포함된 데이터를 교차적으로 방송하는 것을 특징으로 하는 무선 데이터 방송에서 불규칙한 식별자 공간분할에 기초한 인덱스 방법.The method according to claim 1,
The step of partitioning the identifier space comprises:
And an indexing table for the upper group (P_i ) and the lower group (C_j ) is configured, and the indexing table and the data included in the data group are alternately broadcasted in the broadcast channel. A partition based index method.제2항에 있어서,
방송을 위한 데이터 집합의 데이터 항목들을 식별자의 증가순으로 정렬한 후 같은 수의 데이터를 포함하도록 상위 데이터 그룹으로 분리하고, 상기 상위 데이터 그룹에 포함된 데이터들의 식별자가 포함되도록 식별자 공간을 분할하고,
각각의 상위 그룹(P_i)에 포함된 데이터들을 같은 수의 데이터를 포함하는 하위 데이터 그룹으로 분리하고 각 그룹에 포함된 데이터들의 식별자가 포함되도록 상위그룹에 대한 식별자 공간을 분할하는 것을 특징으로 하는 무선 데이터 방송에서 불규칙한 식별자 공간분할에 기초한 인덱스 방법.3. The method of claim 2,
The data items of the data set for broadcasting are sorted in ascending order of identifiers, and then the data items are divided into an upper data group including the same number of data, an identifier space is divided so that the identifiers of the data included in the upper data group are included,
Dividing the data included in each of the higher-level groups (P_i ) into lower-level data groups including the same number of data, and dividing the identifier space for the higher-level group so that the identifiers of the data included in each group are included An index method based on irregular identifier space division in wireless data broadcasting.제1항에 있어서,
상기 다중데이터질의(Q_k)는 채널에서 검색할 k개의 데이터 항목의 정수 식별자 집합이고, 상기 제1큐(gpQueue)와 상기 제2큐(dpQueue)는 인덱스와 데이터 항목에 대한 시간 포인터를 증가하는 순서로 유지하는 대기열이고,
상위 그룹(P_i)는 i 번째 상위 데이터 그룹에 포함되는 최소 식별자와 최대 식별자의 집합이고,

, 여기서 id^M_i는 i 번째 상위 그룹의 최대 식별자이고, id^m_i는 i 번째 상위 그룹의 최소로서 id^M_i-1+ 1 의 값을 갖고,
하위그룹(C_j)는 상위 그룹(P_i)의 j번째 하위 데이터 그룹을 커버하는 최소식별자와 최대식별자의 집합으로,

, 여기서, id^M_j는 j 번째의 하위 데이터 그룹의 최대 식별자이고, r_c는 각 상위그룹을 여러 개의 하위 그룹으로 분리하기 위한 비율이고, id^m_j는 j 번째 하위 그룹의 최소 식별자로서 id^M_j-1 + 1 의 값을 갖는 것을 특징으로 하는 무선 데이터 방송에서 불규칙한 식별자 공간분할에 기초한 인덱스 방법.The method according to claim 1,
The multi-data query (Q_k ) is an integer identifier set of k data items to be searched in a channel, and the first queue (gpQueue) and the second queue (dpQueue) Queue to keep in order,
The upper group P_i is a set of the minimum and maximum identifiers included in the i-th upper data group,

, Wherein^M_i id i is a maximum value of the second identifier for the parent group,^m id_i has a value of at least a top of the i-th group id^M_i-1 +_1,
The lower group (C_j) is a set of a minimum identifier and a maximum identifier covering the j-th lower data group of the higher group (P_i )

Where, id^M_j is the maximum identifier of the sub-groups of data of the j-th, r_c is the ratio to the separation between the parent group into several subgroups, id^m_j is a minimum ID of the j-th sub-group id^M_j-1 +₁ &quot;._&lt;_{/ RTI} &gt;제1항에 있어서,
상기 제1함수(getTimeFromCGT)는 상기 상위인덱스(PI)의 CGT가 입력되고, (P_i∩Q_k≠Ø)이면, PI에 포함된 CGT의 모든 C_j에 대해, (C_j∩Q_k≠Ø) 이면, t_j를 제1큐(gpQueue)에 입력하고,상기 제2함수(getTimeFromPGT)는 상위인덱스(PI)의 PGT가 입력되고, PGT의 모든 P_a에서, (P_a∩Q_k≠Ø)이면 t_a를 제1큐(gpQueue)에 입력하고,
상기 제3함수(getTimeFromCI)는 하위인덱스(CI)가 입력되고, (NCG∩Q_k≠Ø)이면, t_nc를 제1큐(gpQueue)에 입력하고, 그렇지 않은 경우에 대해서는 제1큐(gpQueue)에 t_np를 입력하고, 상기 NCG는 C_j의 다음 하위 그룹의 식별자집합이고, 상기 t_nc는 방송채널에서 다음에 방송되는 하위 그룹에 대한 시간포인터이고, 상기 t_np는 방송채널에서 다음에 방송되는 상위 그룹에 대한 시간포인터이고,
상기 제4함수(extractDataWithCI)는 하위인덱스(CI)가 입력되고, (C_j∩Q_k≠Ø)이면, 다중데이터질의(Q_k)의 모든 id에서, (id∈IDT)이면 t_d(∈IDT)를 제2큐(dpQueue)에 입력하고, 그렇지 않은 경우에 대해서는, (id∈C_j)이면, 다중데이터질의(Q_k)에서 id를 삭제하고,
상기 CGT는 하위 그룹의 테이블이고 ,{<C_j, t_j>}, 여기서, C_j는 상위그룹 (P_i)에 속하는 하위그룹이고, t_j는 하위그룹(C_j)대한 하위인덱스(CI_j) 의 방송 시간에 대한 시간 포인터이고, j는

이고, r_c는 각 상위그룹을 여러 개의 하위 그룹으로 분리하기 위한 비율이고상기 PGT는 상위 그룹의 테이블이고, {<P_a, t_a>}, 여기서 P_a는 상위 그룹이고, t_a는 상위 그룹 P_a에 대한 상위 인덱스 PI_a의 방송시간에 대한 시간 포인터이고 a는

이고,
상기 IDT는 id의 테이블이고, {<id, t_d>}, 여기서, id는 C_j에 포함된 데이터 항목의 식별자이고, t_d는 무선 채널에서 그 데이터에 대한 시간 포인터인 것을 특징으로 하는 데이터 방송에서 불규칙한 식별자 공간분할에 기초한 인덱스 방법.
The method according to claim 1,
The first function (getTimeFromCGT) is a function for inputting the CGT of the upper index PI (P_i ∩Q_k ≠ Ø), for all C_j of the CGT included in the PI, (C_j ∩Q_k ≠ Ø) is input to t_j in the first queue (gpQueue), and the second function (getTimeFromPGT) is a PGT of higher index (PI) is input from any of_a PGT P, (P ≠_ka ∩Q Ø), t_a is input to the first queue (gpQueue)
The third function (getTimeFromCI) inputs the lower index (CI) and inputs t_nc to the first queue (gpQueue) if (NCG? Q_k ?? Ø) ), T_np is the set of identifiers of the next lower group of C_j , t_nc is a time pointer for the next broadcast subgroup in the broadcast channel, and t_np is the next Is a time pointer to a broadcasted upper group,
The fourth function (extractDataWithCI) is a sub-index (CI) is_{input, (C j ∩Q k ≠ Ø} ) is, when id in all of the multiple query data_{(Q k), (id∈IDT)} t d (∈ IDT) into the second queue (dpQueue), and if not (id? C_j ), delete id in the multiple data query (Q_k )
(C_j , t_j )}, where C_j is a child group belonging to a parent group (P_i ), t_j is a child group (C_j ) Is the time pointer for the broadcast time of the lower index (CI_j ), and j is

, R_c is a rate for separating each higher group into a plurality of lower groups, PGT is a table of higher groups, {P_a , t_a >}, where P_a is a higher group and t_a is a higher A time pointer for the broadcast time of the upper index PI_a for group P_a , and a is

ego,
Wherein the IDT is a table of id, {id, t_d }, where id is an identifier of a data item contained in C_j and t_d is a time pointer for the data in the wireless channel An index method based on irregular identifier space partitioning in a broadcast.

Images