A Data Mining Approach for Selecting Bitmap Join Indices

Ladjel Bellatreche,Rokia Missaoui,Hamid Necir,Habiba Drias 한국정보과학회 2007 Journal of Computing Science and Engineering Vol.1 No.2

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.

A Data Mining Approach for Selecting Bitmap Join Indices

Bellatreche, Ladjel,Missaoui, Rokia,Necir, Hamid,Drias, Habiba Korean Institute of Information Scientists and Eng 2007 Journal of Computing Science and Engineering Vol.1 No.2

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.

Efficient bitmap-based indexing of time-based interval sequences

Roh, Jong-won,Hwang, Seung-won,Yi, Byoung-Kee Elsevier 2012 Information sciences Vol.194 No.-

<P><B>Abstract</B></P><P>In this paper, we discuss similarity searches for time series data represented as interval sequences. For instance, the time series of phone call records can be represented by time-based interval sequences, or T-interval sequences, which consist of the start and end times of the call records. To support an efficient similarity search for such sequences, we address the desirable semantics for similarity measures for the T-interval sequences, observe how existing measures fail to address such semantics, and propose a new measure that satisfies all our semantics. We then propose approximate encoding methods for T-interval sequences. More specifically, we propose two bitmap-based feature extraction methods: (1) a bin-bitmap encoding method that transforms the T-interval sequences into bitmaps of fixed length, and (2) a segmented feature extraction method that takes the longest bitmap sequences of consecutive ‘1’ elements. Finally, we propose two query processing schemes using these bitmap-based approximate representations. We validate the efficiency and effectiveness of our proposed solutions empirically.</P>

데이터베이스 아웃소싱을 위한 그리드 인덱스 기반 비트맵 암호화 기법

윤민(Min Yoon),신영성(Youngsung Shin),장재우(Jaewoo Chang) 한국정보과학회 2013 정보과학회논문지 : 데이타베이스 Vol.40 No.4

최근 클라우드 컴퓨팅이 빠르게 발전함에 따라, 공간 데이터베이스 아웃소싱에 대한 관심이 급증하고 있다. 따라서 데이터베이스 아웃소싱에서 위치 데이터 보호를 위한 암호화 기법이 연구되고 있다. 그러나 기존 공간 좌표 변환 기법은 위치 데이터의 분포를 고려하지 않고 암호화를 수행하기 때문에, 공격자가 암호화 변환 데이터로부터 원본 데이터 분포를 유추하는 것이 가능하다. 아울러, 트리 기반 인덱스를 통해 질의 처리를 수행하기 때문에, 데이터의 양이 많아질수록 질의 처리 성능이 저하되는 문제점이 존재한다. 이를 위해, 본 논문에서는 데이터베이스 아웃소싱에서 위치 데이터 보호를 위한 비트맵 기반 데이터 암호화 기법 및 질의처리 알고리즘을 제안한다. 제안하는 기법은 공격자의 원본 데이터 유추 방지를 위해 데이터 분포 기반 앵커 선정 및 영역 분할/병합 정책을 통해 앵커를 선정한다. 아울러, 최적의 질의처리 성능을 보장하기 위해, 해시 인덱스를 통한 질의 처리를 수행한다. 한편, 성능평가를 통해 제안하는 기법이 공격자로의 원본 데이터베이스 노출 확률을 감소시키면서, 빠른 질의 처리를 수행함을 검증한다. With the development of cloud computing, the interest on spatial database outsourcing has been sharply increasing. Therefore, researches for protecting location data privacy in outsourced databases have been actively performed. However, the existing schemes are weak to access original data because they do not consider data distribution. In addition, since they perform the nearest neighbor query processing by using a tree-based index, query processing time can be increased depending on tree depth. To solve these problems, we propose a grid index-based bitmap encryption scheme and a query processing algorithm for database outsourcing. We propose an anchor selection algorithm using split and merge policies based on data distribution to protect privacy of users from attacker. Furthermore, we reduce the communication cost for query processing by performing searching based on the hash index. Finally, we show through performance analysis that the proposed scheme provides better query processing performance and guarantees the privacy of users, compared with the existing schemes.

무선방송환경에서 계층적 비트맵 기반 공간 색인을 이용한 k-최근접 질의처리

송두희(Doo-Hee Song),박광진(Kwang-Jin Park) 한국컴퓨터정보학회 2012 韓國컴퓨터情報學會論文誌 Vol.17 No.1

최근 무선방송 환경을 기반으로 하는 k-최근접(k-Nearest Neighbor) 질의처리가 활발히 연구되고 있다. 무선방송환경의 장점은 서버 내에 존재하는 불특정 다수에게 일괄적으로 질의처리를 할 수 있는 확장성을 가진다는 것이다. 그러나 기존의 k-NN 질의는 무선방송환경에 적용할 경우 탐색과정에서 백트래킹이 발생하여 질의처리시간이 증가하는 단점을 가진다. 본 논문은 무선방송환경에서 k-NN 질의를 효과적으로 처리하기 위하여 계층적 비트맵 기반 공간색인(Hierarchical Bitmap-based Spatial Index: HBI)을 제안한다. HBI는 비트맵 정보와 트리 구조를 이용하여 비트맵의 크기를 줄인다. 결과적으로 방송주기를 줄임으로써 클라이언트의 청취시간과 질의처리 시간을 줄일 수 있다. 또한 비트맵 정보를 활용하여 객체의 위치를 모두 파악할 수 있기 때문에 필요한 데이터를 선택적으로 청취할 수 있다. 본 논문에서는 HBI를 k-NN 질의에 적용하여 실험을 실시하고 성능평가에서 제안 기법이 우수함을 증명한다. Recently, k-nearest neighbors query methods based on wireless broadcasting environment are actively studied. The advantage of wireless broadcasting environment is the scalability that enables collective query processing for unspecified users connected to the server. However, in case existing k-NN query is applied in wireless broadcasting environment, there can be a disadvantage that backtracking may occur and consequently the query processing time is increasing. In this paper proposes a hierarchical bitmap-based spatial index in order to efficiently process the k-NN queries in wireless broadcasting environment. HBI reduces the bitmap size using such bitmap information and tree structure. As a result, reducing the broadcast cycle can reduce the client's tuning time and query processing time. In addition, since the locations of all the objects can be detected using bitmap information, it is possible to tune to necessary data selectively. For this paper, a test was conducted implementing HBI to k-NN query and the proposed technique was proved to be excellent by a performance evaluation.

관계형 XML 가지 패턴 질의를 위한 비트맵 인덱스와 질의 처리 기법

이경하(Kyong-Ha Lee),문봉기(Bongki Moon),이규철(Kyu-Chul Lee) 한국정보과학회 2010 정보과학회논문지 : 데이타베이스 Vol.37 No.3

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.

저장 공간이 제약된 환경에서 계층적 비트맵 인덱스 생성에 관한 연구

김종욱(Jong Wook Kim) 한국디지털콘텐츠학회 2015 한국디지털콘텐츠학회논문지 Vol.16 No.1

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.

Nonlinear Approximate Indexing for Multimedia Data

Guang-Ho Cha 보안공학연구지원센터 2016 International Journal of Software Engineering and Vol.10 No.11

This paper presents a new nonlinear approximate indexing method for high-dimensional data such as multimedia data. The new indexing method is designed for approximate similarity searches and all the work is performed in the transformed Gaussian space. In this indexing method, we first map the input space into a feature space via the Gaussian mapping, and then compute the top eigenvectors in the Gaussian space to capture the cluster structure based on the eigenvectors. We describe each cluster with a minimal hypersphere containing all objects in the cluster, derive the similarity measure for each cluster individually and construct a bitmap index for each cluster. Finally we transform the nearest neighbor query into the hyper-rectangular range query and search the clusters near the query point. The experimental results for our new indexing method show considerable effectiveness and efficiency.

스트림 데이터 처리를 위한 비트맵 인덱스 기반 복합 이벤트 검출 기법에 관한 연구

박용민(Yong-Min Park),오영환(Young-Hwan Oh) 大韓電子工學會 2011 電子工學會論文誌-TC (Telecommunications) Vol.48 No.4

이벤트 기반 서비스 기술은 실시간으로 발생하는 이벤트를 감지하고 분석하여 이에 대한 반응으로 서비스가 연동되는 기술로, 실시간 기업 환경 구축이나 유비쿼터스 서비스 환경 구축을 위한 핵심 기반 기술이다. 실시간 기업 환경에서 요구되고 있는 기업 내 업무 프로세스에서 발생하는 다양한 정보를 실시간 모니터링, 분석하여 변화에 대한 신속한 대응을 제공하거나, 유비쿼터스 서비스 환경에서 상황에 맞게 적시에 맞춤형서비스를 제공하기 위해서는 이벤트 기반의 서비스 기술이 요구된다. 최근 이벤트 중심의 비즈니스 프로세스로 복합 이벤트 처리(CEP : Complex Event Processing) 방식이 사용된다. 복합 이벤트처리 방식은 여러 이벤트 소스로부터 발생한 이벤트를 대상으로 이벤트들의 영향을 분석하여 대응되는 액션을 처리하는 방식으로 가장 핵심이 되는 기술은 어떻게 사용자에게 의미있는 이벤트(복합 이벤트)를 검출하는가이다. 기존의 연구에서는 복합 이벤트를 구성하는 모든 이벤트가 발생하지 않아도 부분적으로 발생하는 이벤트에 대해 계속적으로 연산을 수행하여 많은 연산과 많은 메모리를 소비하는 문제점이 있다. 이러한 문제를 해결하기 위해 본 논문에서는 대용량의 스트림 데이터에서 발생한 모든 이벤트를 처리하지 않고 응용 계층에서 등록한 복합 이벤트를 구성하는 모든 이벤트가 발생하면, 복합 이벤트를 처리하는 이벤트 검출 기법을 제안한다. 제안 하는 기법은 먼저 비트맵 인덱스를 이용하여 이벤트의 발생 유/무를 관리한다. 또한 복합 이벤트 질이의 마지막 이벤트를 트리거 이벤트로 정의하며, 이 트리거 이벤트가 발생하는 시점을 통해 이벤트의 발생을 표시한 비트맵 인덱스에 복합 이벤트를 구성하는 모든 이벤트의 발생 유/무를 검사하여 모든 이벤트가 발생하였다면, 연산을 수행할 수 있도록 제안한다. 제안하는 기법은 실험을 통해 복합 이벤트를 구성하는 이벤트의 검사를 매번 수행하지 않고 모든 이벤트가 발생하였을 때에만 연산을 수행함으로 불필요한 연산을 방지하고, 처리하는 이벤트의 수를 감소시켜 연산의 효율성을 증가 시켰다. Event-based service technology integrate service to detect events that occur in real time by analyzing the response. Is the core technology for real-time business and ubiquitous service environment construction. Is required event-based service technology on business processes in real-time business environment that providing rapid response to changing and custom service using a variety of information real-time monitoring and analysis in ubiquitous service environment. Last event-driven business processes can be used as a CEP(Complex Event Processing). The core of CEP technology, the event from multiple event sources analysis of events affecting and the way to handle action, is detect complex event to user. In previous studies, an event occurs that continue to perform without the need for partial operations. so many operations and spend a lot of memory is a problem. To solve these problems, event detection technique is proposed that large streams of data without processing any events, registered to configure a complex event occurs when all events in the application layer, complex event processing. The proposed method, first using a bitmap index to manage the event occurs. The complex events of the last event in response to define a trigger event. The occurrence of an event to display a bitmap index, a composite event occurrence of all event to configure the test through the point at which a trigger event occurs. Is proposed, If any event occurs to perform the operation. The proposed scheme perform operations when all event occurs without events having to perform each of the tests. As a result, avoid unnecessary operations and reducing the number of events to handle the increased efficiency of operations.

계층적인 비트맵 인텍스에 의한 집합 조인의 성능향상

임선경,황환규 강원대학교 정보통신연구소 2009 정보통신논문지 Vol.13 No.-

In this paper we study an efficient processing of set join operations which are important in object-relational database systems. Even if the set join operation is a significant part in the database field, it has been limited research on the evaluation of query operators that apply on sets. Because evaluating set joins based on inverted file is not only difficult, but also leads to algorithms that are very expensive. We propose an efficient set join algorithm using hierarchical bitmap index in inverted file and compare the proposed method with the inverted file. Our experiments show that the method using hierarchical bitmap index in inverted file outperforms that of the inverted file.