Performance evaluation of bitmap indexing based on time granularity

การประเมินประสิทธิภาพของ bitmap indexing ตามความละเอียดของหน่วยเวลา

Name: Varunya Klangcharoenlap

keyword: Time-series analysis Data processing

; Time granularity

Abstract: A data warehouse is a collection of a large amount of data gathered from numerous sources in one organization. Those data must be efficiently organized so that they can be analyzed and the summarized results can be used to support a particular decision. Thus, querying data in a data warehouse must be fast. Implementing indexing on those data can help improve the query response time significantly. One indexing technique commonly used is bitmap indexing since it has the advantage of dealing with replicated data in a data warehouse where the cardinality of the data is often more than one. Another common scenario found in a data warehouse is that most queries involve a time domain such as a monthly or yearly report of sales volume for a particular product. In addition, time domain used is finite and has little different granularity ranging from just days to years. Hence, bitmap indices for time seem to be a good fit. To improve both time and space requirements for bitmap indices, there are several bitmap indexing techniques designed and implemented. However, due to the vast amount of data and numerous data cardinalities, most bitmap techniques aim to reduce the amount of space required to store bitmap indices. Therefore, most of them propose to encode or compress bitmap indices. This thesis proposes a model to evaluate the performance of five common bitmap indexing techniques. They are simple bitmap (SB), simple bitmap with range encoding (SBR), simple bitmap with interval encoding (SBI), bit-sliced indexing (BI) and encoded bitmap indexing (EB). TPC-H benchmark data and five selected TPC-H queries are used to evaluate the model. In addition, the query response time of both exact and range queries under various time granularities are measured for all five bitmap indexing methods. The experimental results show that the simple bitmap gives the best response time for exact queries, and the simple bitmap with interval encoding gives the best response time for range queries. Even though the simple bitmap techniques require more space and generate more bitmap vectors, their performance gain should considerably overcome the cost of storage space, which is now getting lower every day.

Abstract: Data Warehouse จะถูกสร้างขึ้นมาโดยเก็บรวบรวมข้อมูลจากแหล่งข้อมูลต่างๆ ในองค์กร ข้อมูลเหล่านี้จะต้องถูกจัดเก็บอย่างมีประสิทธิภาพเพื่อให้สามารถนำข้อมูลมาวิเคราะห์ สรุปผล และนำข้อมูลมาประกอบการตัดสินใจได้อย่างรวดเร็ว. การสร้างดัชนีบนข้อมูล จะช่วยเพิ่ม ประสิทธิภาพในการสอบถามข้อมูลได้. ดัชนีแบบ Bitmap เป็นดัชนีแบบหนึ่งที่นิยมใช้ใน Data Warehouse เนื่องจากดัชนีแบบ Bitmap เหมาะกับข้อมูลที่มีลักษณะซ้ำๆ กันและมีค่าของข้อมูลที่ แตกต่างกันมากกว่า 1 ค่า. การสอบถามข้อมูลส่วนใหญ่ใน Data Warehouse มักเกี่ยวข้องกับ ข้อมูล Time เสมอ ดังเช่นการสอบถามข้อมูลรายงานยอดขายสินค้าประจำเดือนหรือประจำปีเป็น ต้น นอกจากนั้นข้อมูล Time เป็นข้อมูลที่มีขอบเขตของข้อมูลที่แน่นอนและเป็นข้อมูลที่มีความ หลากหลายของข้อมูลไม่มาก ซึ่งเหมาะสำหรับการทำดัชนีแบบ Bitmap. เพื่อเป็นการปรับปรุง ประสิทธิภาพของดัชนีแบบ Bitmap ในการตอบการสอบถามข้อมูลและปรับปรุงพื้นที่ที่ใช้ในการ จัดเก็บดัชนี Bitmap ได้มีการนำเสนอเทคนิคของการทำดัชนีแบบ Bitmap แบบต่างๆ โดยส่วน ใหญ่จะมุ่งเน้นไปในแนวทางของการเข้ารหัสหรือการบีบอัดข้อมูลของดัชนี Bitmap. ในงานวิจัย นี้ได้นำเสนอวิธีการในการประเมินประสิทธิภาพของดัชนีแบบ Bitmap 5 ประเภท ได้แก่ Simple Bitmap (SB), Simple Bitmap with Range Encoding (SBR), Simple Bitmap with Interval Encoding (SBI), Bit-Sliced Indexing (BI) และ Encoded Bitmap Indexing (EB). โดยใช้ข้อมูลจาก TPC-H benchmark และเลือก query 5 query จาก 22 query และวัด เวลาที่ใช้ในการตอบการสอบถามข้อมูลตามความละเอียดของเวลาต่างๆที่ใช้ในการทดลอง โดยแบ่ง ประเภทของการสอบถามข้อมูลเป็น 2 ประเภทได้แก่การสอบถามข้อมูลแบบ Exact Query และ แบบ Range Query. จากการทดลองสรุปว่า SB จะใช้เวลาในการตอบการสอบถามข้อมูลน้อย ที่สุดในการสอบถามข้อมูลแบบ Exact Query และ SBI จะใช้เวลาในการตอบการสอบถามข้อมูล น้อยที่สุดในการสอบถามข้อมูลแบบ Range Query ถึงแม้ว่า SB จะใช้พื้นที่ในการจัดเก็บข้อมูล มากที่สุดก็ตาม.

Mahidol University

Address: NAKHON PATHOM

Email: liwww@mahidol.ac.th

Name: Sudsanguan Ngamsuriyaroj

Role: Thesis Advisors

Created: 2007

Modified: 2025-05-19

Issued: 2010-06-09

วิทยานิพนธ์/Thesis

application/pdf

CallNumber: TH V327p 2007

eng

DegreeName: Master of Science

Level: Master's Degree

Descipline: Computer Science

Grantor: Mahidol University

©copyrights Mahidol University

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	4437183.pdf	717.09 KB	9	2018-05-29 11:43:25

ใช้เวลา

0.263946 วินาที