메뉴 건너뛰기

ABSTRACT
Bitmap indexes are widely used in both scientific and commercial
databases. They bring fast read performance for specific types
of queries, such as equality and selective range queries. A major
drawback of bitmap indexes, however, is that supporting updates
is particularly costly. Bitmap indexes are kept compressed to minimize
storage footprint; as a result, updating a bitmap index requires
the expensive step of decoding and then encoding a bitvector. Today,
more and more applications need support for both reads and
writes, blurring the boundaries between analytical processing and
transaction processing. This requires new system designs and access
methods that support general updates and, at the same time,
offer competitive read performance.
In this paper, we propose scalable in-memory Updatable Bitmap
indexing (UpBit), which offers efficient updates, without hurting
read performance. UpBit relies on two design points. First, in addition
to the main bitvector for each domain value, UpBit maintains
an update bitvector, to keep track of updated values. Effectively, every
update can now be directed to a highly-compressible, easy-toupdate
bitvector. While update bitvectors double the amount of uncompressed
data, they are sparse, and as a result their compressed
size is small. Second, we introduce fence pointers in all update
bitvectors which allow for efficient retrieval of a value at an arbitrary
position. Using both synthetic and real-life data, we demonstrate
that UpBit significantly outperforms state-of-the-art bitmap
indexes for workloads that contain both reads and writes. In particular,
compared to update-optimized bitmap index designs UpBit is
15-29 faster in terms of update time and 2:7 faster in terms of
read performance. In addition, compared to read-optimized bitmap
index designs UpBit achieves efficient and scalable updates (51-
115 lower update latency), while allowing for comparable read
performance, having up to 8% overhead.

번호 제목 글쓴이 날짜 조회 수
46 데이터베이스및실습 101분반 11월 19일(월) 수업 9시 시작합니다. 관리자 2018.11.18 959
45 데이터베이스 중간고사 시간 및 장소 관리자 2018.10.10 1011
44 UML 참고자료 file 관리자 2018.10.08 351
43 '데이터베이스및실습101분반' 10월 8일(월) 수업 오전 9시부터 시작합니다 관리자 2018.10.05 686
42 102분반 게시판입니다. 누리관(A13) 2226 관리자 2018.09.04 333
41 101분반 게시판입니다. 웅비관(A12) 1320 관리자 2018.09.04 315
40 인터넷DB응용 중간고사 안내 관리자 2018.04.17 2484
39 2017-2학기 캡스톤디자인 결과물 제출 file 관리자 2017.12.15 351
38 데이터베이스및실습 기말고사 안내 관리자 2017.12.07 1254
37 JDBCExample.java file 관리자 2017.11.06 328
36 데이터베이스및실습 중간고사 안내 관리자 2017.09.29 961
35 데이터베이스및실습 9월 12일(화) 수업 오후 4:00부터 시작합니다 관리자 2017.09.12 584
34 UML 소개 file 관리자 2017.09.11 376
33 인터넷 DB 5월 18일(목) 수업 오후 2:30부터 시작합니다 관리자 2017.05.18 610
» UpBit: Scalable In-Memory Updatable Bitmap Indexing [1] file 관리자 2017.04.25 524
31 The shortest path is not always a straight line [1] file 관리자 2017.04.25 392
30 Specification을 볼때 알아야할 의미 관리자 2009.01.21 905
29 바이너리트리 file 관리자 2006.06.05 1092
28 BinaryTree file 관리자 2006.06.01 1010
27 LSTAFF (Flash Memeory) file 관리자 2006.05.29 887