Earticle

IP 주소에 대한 관리 및 특정 IP의 접속 허용 여부를 결정하기 위한 기능들은 기업 또는 학교 등 많은 곳에서 사용 된다. IP 정보를 기반으로 한 접속 허용 여부의 판단을 위한 정보의 보관은 파일 또는 데이터베이스를 이용하여 구 성되는데, 추가 정보에 의해 지속적으로 정보의 크기가 커질 수 있는 문제점을 가지고 있다. 본 논문에서는 이러한 문제점을 해결하기 위해 IP 접속 허용 여부 정보를 비트맵 형식으로 저장하여 업데이트 여부와 관계없이 동일한 파 일 크기를 유지할 수 있는 파일 데이터베이스와 탐색을 위한 효율적인 알고리즘을 제안한다. 제안 파일 데이터베이 스는 IP 주소의 앞 3자리 옥텟을 이용하여 파일명을 생성하고, 나머지 옥텟 값은 비트맵 파일에 IP의 접속 여부를 판단 여부 값을 획득하기 위한 파일 내에서의 변위로 구성하였다. 파일 데이터베이스 탐색 성능은 SQLite와의 비교 를 통해 IP 접속 허용 여부를 위한 비트맵 파일 접근을 통한 차단 정보 확인 알고리즘이 효율적으로 구성되었음을 증명하였다.

The ability to mange IP addresses and decide whether to allow access to specific IPs is used in many places such as business and schools. Information storage, which determines whether to allow access based on IP information, is configured using a file or database, so you can continue to increase the size of the information. To solve this problem, this white paper proposes an efficient algorithm for file database and navigation, which can store IP access permission information in bitmap format and maintain the same file size whether or not it is updates. The proposed file database uses the first three digits of the IP address to generate a file name, and the remaining octets consist of displacements in the file to get a value indicating whether the IP is linked to the bitmap file. Compare file database scan performance with SQLite to show that the blocking information verification through bitmap file access has configured IP access efficiently.

영상처리를 이용한 차량 번호판 인식은 경찰의 범죄 추적과 무인 주차관리에서 많이 사용되고 있다. 특히 경찰은 속 도위반, 주정차 위반과 같은 범죄 차량 추적 등에 많이 사용한다. 추적을 위한 시스템은 카메라 이미지를 중앙 시스 템으로 전송하면, 중앙 시스템에서 이미지 처리를 통해 디지털 데이터로 변환한 정보와 데이터베이스에 저장된 범죄 차량 정보를 비교하여 범죄 차량 여부를 판단한다. 이로 인해 범죄 차량 여부의 확인까지 상대적으로 긴 시간과 높 은 비용이 발생하여 정보 획득과 빠른 범죄 차량 판단이 어렵다. 본 논문에서는 이러한 문제점을 해결하기 위해 차 량 번호판 정보를 저장하고 관리할 수 있는 파일 데이터베이스 구조와 효율적인 탐색을 위한 알고리즘을 제안한다. 차량 번호한은 한국 표준 번호판을 기준으로 작성하였고, 용도와 차량 등록번호를 이용한 2차원 배열 형태로 구성하 여 효율적으로 정보를 구조화하였다. 파일 데이터베이스의 성능 평가는 SQLite와 비교를 통해 탐색 알고리즘을 통 한 차량 정보의 빠른 접근을 증명하였다.

License plate recognition using image processing is widely used for police crime tracking and unmanned parking management. The tracking system transmits the camera image to the central system, and compares the information converted into digital data and the criminal vehicle information stored in the database through image processing in the central system to determine whether the vehicle is a criminal vehicle. This incurs a relatively long time and high cost until the identification of the crime vehicle, it is difficult to obtain information and quickly determine the crime vehicle. In this paper, to solve this problem, we propose a database structure for storing and managing license plate information and an algorithms for efficient retrieval. Vehicle number limit was prepared based on Korean standard license plate and structured information efficiently by constructing two-dimensional array form using purpose and vehicle registration number. The performance evaluation of the file database demonstrates the fast access of vehicle information through a search algorithm through comparison with SQLite.

비트맵 인덱스는 낮은 카디널리티를 갖는 컬럼에 대한 OLAP 질의의 수행 속도에 있어서 매우 우수한 성능을 보이고 있기 때문에, 데이터 웨어하우스에서 많이 사용하고 있는 인덱스 기법 중에 하나이다. 일반적으로 데이터 웨어하우스에 기반을 둔 많은 응용 프로그램들은 컬럼 값들이 계층 구조를 형성하는 경우가 많이 있다. 만일, 컬럼 값들이 계층적으로 표현될 수 있는 경우 일반적인 비트맵 인덱스 보다 계층적 비트맵 인덱스를 이용하는 것이 질의 처리 수행 속도에 있어서 더 높은 성능을 보인다고 알려지고 있다. 그러나 계층적 비트맵 인덱스의 경우 사용하는 계층 구조의 크기가 큰 경우 저장 공간 오버헤드가 발생할 수 있다는 문제점을 가지고 있다. 그러므로 본 논문에서는 저장 공간이 제약된 환경에서 컬럼 값들이 거대 계층 구조를 형성하고 있을 때, 질의 워크로드에 기반하여 계층적 비트맵 인덱스를 효과적으로 생성하기 위한 방법을 제안한다. 특히, 본 논문에서는 주어진 계층 구조를 두 개의 배타적 역영으로 나누는 Cut 선택 방법 제안함으로써, 계층적 비트맵 인덱스의 저장 공간 오버헤드 문제를 해결한다.

Since bitmap indices are useful for OLAP queries over low-cardinality data columns, they are frequently used in data warehouses. In many data warehouse applications, the domain of a column tends to be hierarchical, such as categorical data and geographical data. When the domain of a column is hierarchical, hierarchical bitmap index is able to significantly improve the performance of queries with conditions on that column. This strategy, however, has a limitation in that when a large scale hierarchy is used, building a bimamp for each distinct node leads to a large space overhead. Thus, in this paper, we introduce the way to build hierarchical bitmap index on an attribute whose domain is organized into a large-scale hierarchy in space-constrained environments. Especially, in order to figure out space overhead of hierarchical bitmap indices, we propose the cut-selection strategy which divides the entire hierarchy into two exclusive regions.

Inkjet technology is one of the commonly used technologies in the printed-electronics field. The primary issue regarding the usage of inkjet technology as a printed-electronics tool is the printing resolution; therefore, to print complicated patterns of precise dimensions, we developed software that can convert a CAD file into a bitmap image. Moreover, as a bitmap image is not comprised of physical dimensions, its resolution needs to be defined in terms of pixel distance to print a rasterized bitmap image. In this study, we investigated the effects of pixel distance and dot size on printing resolution; based on the experiment results, we concluded that the printed dot size should be used to determine the optimal pixel distance. Lastly, we also propose inkjet printing procedures for bitmap images.

대용량 민감 데이터에 대한 아웃소싱이 각광받음에 따라, 이를 보호하기 위한 데이터 암호화 기법이 요구되고 있다. 이에 따라, 대용량 암호화 데이터 관리를 지원하는 분산 색인 구조 및 암호화된 데이터 상에서의 질의처리 알고리즘 이 요구되고 있다. 그러나 기존 분산 색인 구조 중 암호화 데이터의 특성을 고려한 연구는 존재하지 않는다. 또한, 기존 암호화 질의처리 알고리즘은 지원 가능한 질의 타입이 한정적이며, 상이한 방식으로 암호화된 컬럼 간 연산을 지원하지 못하는 문제점이 존재한다. 이를 해결하기 위해, 본 논문에서는 비트맵 기반 분산 색인 구조 및 암호화 질 의처리 기법을 제안한다. 제안하는 분산 암호화 색인 구조는 데이터 프라이버시를 보장하며, 다양한 종류의 질의에 대해 성능 향상을 제공한다. 아울러, 제안하는 암호화 질의처리 기법은 복호화를 수행하지 않고 질의처리를 수행함 으로써 데이터 보호 수준을 향상시키며, 높은 질의 처리 성능 및 정확도를 보장한다. 아울러 성능평가를 통해 제안 하는 색인구조 및 암호화 질의처리 기법이 대용량 민감 데이터 보호에 적합함을 보인다.

As the outsourcing of the large sensitive data has been highlighted, data encryption schemes to protect the sensitive data are required. Accordingly, it is necessary to develop not only a distributed index structure to manage the large amount of encrypted data, but also a query processing scheme over the encrypted data. However, there has been no index structure considering the encrypted data. Existing query processing schemes over the encrypted data can support limited types of queries. In addition, the schemes cannot support operations among data with different columns because they use different types of encryption schemes depending on their attribute type. To solve these problems, in this paper, we propose a bitmap-based distributed index structure and a query processing scheme for the encrypted data. The proposed distributed index structure guarantees data privacy preservation and performance improvement for the various types of queries. In addition, by processing a query over the encrypted data without data decryption, the proposed query processing scheme guarantees the high query performance and accuracy while preserving the data privacy. Finally, we show from our performance evaluation that our proposed index structure and query processing scheme are suitable for protecting the data privacy of the large sensitive data.

우리는 논문에서 차량 간 통신을 이용한 Ad-hoc 게임에서 브로드캐스트 메시지에 의한 게임속도 저하를 방지하기 위한 비트맵 기반의 메시지 제어 기법(BitBMC:bitmap-based broadcast message control scheme)을 제안한다. 이 기법은 차량 그룹을 비트맵으로 관리하여 여러 차량으로부터 브로드캐스트되는 게임 메시지를 제어함으로써 게임 성능을 보장한다. 중심차량(mc: main car)은 관리그룹 내부에 진입하는 차량에 비트 번호를 부여하여 그룹을 관리하며 비트맵에는 게임메시지 송수신 정보를 포함함으로써 메시지 수신 여부를 빠르게 파악할 수 있다. 이 기법은 기존 VANET(Vehicle Area NETwork)의 메시지 전송과 비교하여 높은 수준의 메시지 필터링 기능을 제공함으로써 신속한 게임메시지 전송을 통해 안정적인 차량 간 게임을 보장한다. 제안기법은 실험데이터를 사용한 시뮬레이션에서 기존의 메시지 플러딩(flooding) 기법보다 빠른 메시지 송수신 시간을 나타낸다.

We propose BitMap-based Broadcast Message Control scheme(BitBMC), which prevents decreasing of message transmission speed by broadcast in Vehicle Ad-hoc NETwork(VANET) mobile game. This scheme manages vehicles and messages in bitmap. Then, It guarantees the performance of the VANET game. The main vehicle assigns a number to a vehicle, which comes into a group as a group member and manages the vehicle. The vehicle checks whether game message is included in a bitmap message. This scheme provides the higher filtering performance than existing Ad-hoc game and maintains the performance of message broadcast in VANET mobile game. In simulation, this proposed scheme represents the fast broadcast time of messages than message flooding scheme.

최근 인공지능, 빅데이터 등 분산 컴퓨팅과 관련된 수요가 증가하면서 분산 컴퓨팅 성능을 개선하려는 연구가 활발 히 진행되고 있다. 분산 컴퓨팅 환경에서는 다수의 프로세스가 공유 메모리에 접근하기 때문에 이를 공유하는 메모 리 공간을 분할해야할 필요가 있다. 따라서 본 논문에서는 동일한 연산을 수행하는 프로세스들에 키로 구분되는 공 통의 메모리 영역을 할당 및 공유할 수 있는 S/W를 설계 및 구현하였으며, PCIe로 연결된 FPGA 메모리의 특성상 로컬 메모리에 비해 느린 접근 속도를 보완하기 위해 ‘비트맵 기반 페이지 할당 알고리즘’을 적용하여 메모리 할당, 공유, 반납의 기능을 구현하였다. 그 결과 다중 프로세스가 메모리 간섭을 일으키지 않으며 메모리 할당, 공유, 반납 을 안정적으로 수행함을 확인하였고, 링크 기반 버디 시스템 알고리즘의 성능보다 비트맵 기반 페이지 할당 알고리 즘의 성능이 더 우수함을 확인하였다.

As demands for distributed computing such as artificial intelligence and big data have increased recently, there has been an active study to improve distributed computing performance. In a distributed computing environment, since many processes access shared memory, it is necessary to separate the partitions of the shared memory space. Therefore, in this paper, we design and implement a S/W that can allocate and share a common memory area divided into keys in processes that perform the same operation. In order to compensate for slower access speed compared to local memory due to the nature of FPGA connected with PCIe, memory allocation, sharing, and return functions are implemented by applying 'bitmap-based page allocation algorithm'. As a result, it is confirmed that multiple processes do not cause memory interference, and that memory allocation, sharing, and return are performed reliably, and that bitmap-based page allocation algorithm is superior to link-based buddy system algorithm.

현재의 초등컴퓨터교육과정은 응용소프트웨어 및 학습용 소프트웨어의 기능을 익히는 측면이 강조되어 왔다. 최근 컴퓨터과학원리 교육을 통한 사고력 교육을 주장하는 측면도 있지만, 그에 따른 문제점, 학생들의 반응 등 다양한 연구 결과가 많지 않다. 이에 본 연구에서는 초등학생에게 컴퓨터 교과 내용학의 컴퓨터 과학 원리를 도입할 수 있는지 그 가능성을 알아보고자 한다. 다양한 컴퓨터과학 원리 가운데, 이진수의 개념, 영상의 표현, 파일 저장을 하나의 주제로 통합한 비트맵이미지 저장원리를 학습주제로 선정하여 연구를 진행하였다. 연구 결과, 초등학생의 특성을 고려하여 수업을 활동 중심으로 진행하고, 학습내용을 초등학생의 수준에 맞춘다면 초등학생들도 내용을 이해할 수 있음을 확인할 수 있었다.

In the existing curriculum of the Elementary Computer Education, it is hard to improve the CPS(Creative Problem Solving) skill and logical thought since the 7th national curriculum emphasizes application programs and CAI softwares. To complement this drawback, it is required to teach the principal of the computer science but there is not many researches for what problems of teaching computer science exist and what the response of students are. Thus, we carried out a research to know whether the students of elementary school can understand principal of computer science in the field of subject matter education. We found that the students can learn the principle of Saving Bitmap Image if the class level is adjusted properly.

BTC는 단색 이미지 데이터의 압축을 위해서 사용되는 최근의 기술이다. BTC의 알고리즘은 평균과 표준편차 를 사용하여 구현한다. 데이터 은닉을 위해, 이미지의 비트-구조를 변경하는 과정이 요구된다. 이러한 변경은 BTC 이 미지의 질의 성능을 나쁘게 만든다. 따라서, 우리는 데이터 은닉의 성능 개선을 위해서 BTC를 개선한 IODBTC를 제 한하였다. 실험 결과 복원한 비밀 메시지가 원본 비밀 메시지와 같음을 증명하였고 제안한 방법이 이전의 스킴에 비해 서 좋은 BTC 이미지임을 증명하였다.

Block truncation coding (BTC) is a recent technique used for compression of monochrome image data. The original algorithm of BTC implement to use the standard mean and the standard deviation. For data hiding, it is needed to modify bit-planes of an images. These modifications yields unacceptable quality of BTC images. Thus, we propose IODBTC (Improved Ordered dithering BTC) improving BTC. In this paper, we improve this problem. Experimental results show that the reconstructed secret messages are the same as the original secret messages, and that the proposed scheme exhibits a good BTC images compared to that of previous schemes.

With the development of cloud computing, the interest on spatial database outsourcing has been sharply increasing. Therefore, researches on data encryption methods for protecting location data privacy in outsourced databases have been actively performed. However, the existing data encryption schemes do not consider data distribution when generating data clusters and they use a tree-based index for processing k-nearest neighbor queries. As a result, the performance of query processing algorithm can fluctuate depending on the tree depth. To solve these problems, we propose a density-aware data encryption scheme and a query processing algorithm for database outsourcing. Our density-aware data encryption scheme uses a grid index to generate clusters and transforms the original data information into a bitmap. To provide efficient query processing, we use an algebraic coding based hash index to reduce the data retrieval time. Finally, in performance analysis, we show that the proposed scheme provides better query processing performance and guarantees the privacy of users, compared with the existing schemes.

Distributed block storage system is one of the fundamental components of cloud computing, and many important services, including cloud database, cloud queue, are built upon it. It is common practice to build block storage system based on reliable and efficient Linux open source software, i.e. software RAID, to meet the I/O requirements of cloud database. Bitmap is a critical data structure of software RAID, and hence is important to reliability and performance of this kind of storage system. We describe several existing software RAID bitmap management solution, and propose REMB (Recoverable External Memory Bitmap), which is reliable and efficient. Experimental results show that REMB improve cloud database performance by 30%~60%.

현대사회에서는 자신도 알지못하는 많은 정보들이 유포된다. 이때 정보들은 개인의 익명성을 보장하기위해 성명, 성별, 주민등록번호와 같은 개인식별 애트리뷰트를 생략한채로 유포된다. 그러나 널리퍼져있는 이러한 정보들은 다른 외부 정보와 조인되므로써 유일하게 개인을 식별하게끔 하는 조인공격을 받을 수 있다. 하지만 이러한 조인공격시 여러데이터가나오게하므로써 개인식별을 어렵게 또는 불가능하게하는 방법을 k-anonymization이라고하고 이러한 k-anonymization을 지원하는 방법으로 이전부터 여러가지가 있다. 이전의 방법들로는 각 subset마다 k-anonymization을 검사해야했으나 Lefevre와 DeWitt가 제안한 Incognito 방법을 사용하면 한번의 검사로 모든k-anonymization을 보장할 수 있다. 이 논문에서는 이러한 Incognito를 bitmap index를 사용하므로써 성능을 개선시키는 기법을 제시한다.

데이터베이스 성능이 저하되면, 가장 먼저 SQL 튜닝을 고려한다. SQL 튜닝에서 가장 주의 깊게 사용 해야하는 부분이 바로 Index의 설정과 관련된 부분이다. 본 논문에서 OLAP 환경에서 다양하고 복잡한 질의처리 요구와 관련하여, B-Tree Index의 문제점을 개선하고 질의 성능을 향상시키기 위해서 Bitmap Index를 사용하였다. 또한, Bitmap Index 사용의 최적 임계점을 추적하기 위하여, 데이터 분포도와 조건절의 복잡도를 조사하였으며, 샘플링된 질의문을 기준으로 B-Tree Index를 사용하였을 때와 Bitmap Index를 사용하였을 때의 비교 실험을 통하여 Bitmap Index의 사용으로 RDBMS의 성능향상이 있음을 증명하였다.

공간 질의 및 색인에 관한 기존 연구는 주로 실외 환경에 기반을 두고 있다. 실내 환경은 실외 환경과는 달리 질의 특성 및 환경적 요소가 다르다. 실내 환경 질의의 대표적인 특징은 객체의 현재 위치를 파악하고 즉시 응답해야하며, 질의 범위도 지역적으로 제한되어 있는 점이다. 본 논문에서는 기존 연구가 가진 문제점을 해결하기 위해 메인 메모리 기반의 DBMS를 사용하며, 실내 환경에서 객체의 위치 탐색시 효율적으로 적응할 수 있는 비트맵 인덱스 기법을 제안한다.

인터넷 회선이 빨라짐에 따라 고속라우터에 대한 요구가 증가하고 있다. 본 논문에서는 고속 라우팅의 핵심인 포워딩 룩업의 고속화를 위하여 비트맵을 이용한 기존의 룩업 알고리즘의 문제점을 실행-구동 시뮬레이션을 통하여 정확히 진단한 후, 카운티드 테이블을 추가하고, 룩업과정에서 사용되는 트랜스퍼 테이블의 중복된 라우팅 정보를 제거함과 아울러 주소 검색범위를 다원화함으로써 성능을 획기적으로 향상시킨 알고리즘을 소개한다. 이 방법은 기존 알고리즘의 룩업시간을 최소 46%, 최대 18%로 단축시키며, 카운티드 테이블을 간단한 하드웨어로 구현한다면 보다 향상된 성능을 기대찬 수 있을 것이다.

The scalable vector graphics (SVG) standard has allowed the complex bitmap images to be represented by vector based graphics and provided some advantages over the raster based graphics in applications, for example, where scalability is required. This paper presents an algorithmto convert bitmap images into SVG format. The algorithm is an integration of pixel-level triangulation, data dependent triangulation, a new image mesh simplification algorithm, and a polygonization process. Both triangulation techniques enable the image quality (especially the edge features) to be preserved well in the reconstructed image and the simplification and polygonization procedures reduce the size of the SVG file. Experiments confirm the effectiveness of the proposed algorithm.

Index selection is one of the most important decisions to take in the physical design of relational data warehouses. Indices reduce significantly the cost of processing complex OLAP queries, but require storage cost and induce maintenance overhead. Two main types of indices are available: mono-attribute indices (e.g., B-tree, bitmap, hash, etc.) and multi-attribute indices (join indices, bitmap join indices). To optimize star join queries characterized by joins between a large fact table and multiple dimension tables and selections on dimension tables, bitmap join indices are well adapted. They require less storage cost due to their binary representation. However, selecting these indices is a difficult task due to the exponential number of candidate attributes to be indexed. Most of approaches for index selection follow two main steps: (1) pruning the search space (i.e., reducing the number of candidate attributes) and (2) selecting indices using the pruned search space. In this paper, we first propose a data mining driven approach to prune the search space of bitmap join index selection problem. As opposed to an existing our technique that only uses frequency of attributes in queries as a pruning metric, our technique uses not only frequencies, but also other parameters such as the size of dimension tables involved in the indexing process, size of each dimension tuple, and page size on disk. We then define a greedy algorithm to select bitmap join indices that minimize processing cost and verify storage constraint. Finally, in order to evaluate the efficiency of our approach, we compare it with some existing techniques.

XML 데이터 량의 증가에 따라 DBMS를 이용한 XML 데이터의 저장 관리 기법들이 고안되었다. 하지만, 현재의 가지 패턴 질의 처리 알고리즘들은 XML 데이터를 태그 또는 임의 단위로 분할되고, 각 항목들이 특정 순서로 정렬된 역 리스트들을 입력으로 한다. 이러한 저장 기법의 불일치는 관계형 테이블에 나뉘어 저장되는 XML 데이터의 질의 처리에 이 알고리즘들의 적용을 어렵게 한다. 이 논문에서는 관계형 테이블에 저장된 XML 데이터에 대한 홀리스틱 가지 조인을 지원하기 위한 비트맵 인덱스와 이를 이용한 질의 처리 기법을 제안한다. 비트맵 인덱스는 많은 데이터베이스 시스템에서 지원하므로, 제안하는 인덱스와 가지 질의 처리 기법은 관계형 질의 처리 프레임워크에서 보다 이식이 용이하다. 제안하는 인덱스 기법은 압축을 통해 인덱스 크기를 줄이면서도 질의 처리시 압축해제가 불필요해 시간과 공간 효율적이다. 또한, 이 논문에서는 비트맵 인덱스만을 이용해 XML 노드들 간의 관계성을 식별함으로써, 가지 패턴 질의 처리를 레코드에 저장된 XML 데이터의 접근 없이 수행할 수 있는 혼합 인덱스를 제시한다.

Due to an increasing volume of XML data, it is considered prudent to store XML data on an industry-strength database system instead of relying on a domain specific application or a file system. For shredded XML data stored in relational tables, however, it may not be straightforward to apply existing algorithms for twig query processing, since most of the algorithms require XML data to be accessed in a form of streams of elements grouped by their tags and sorted in a particular order. In order to support XML query processing within the common framework of relational database systems, we first propose several bitmap indexes and their strategies for supporting holistic twig joining on XML data stored in relational tables. Since bitmap indexes are well supported in most of the commercial and open-source database systems, the proposed bitmapped indexes and twig query processing strategies can be incorporated into relational query processing framework with more ease. The proposed query processing strategies are efficient in terms of both time and space, because the compressed bitmap indexes stay compressed during data access. In addition, we propose a hybrid index which computes twig query solutions with only bit-vectors, without accessing labeled XML elements stored in the relational tables.