-, Fendy (2017) Studi Kinerja Wavelet Tree Pada Variasi Permasalahan Range Query. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
5113100017-Undergraduate-Theses.pdf - Published Version Download (1MB) | Preview |
Abstract
Komputasi range query merupakan sebuah masalah yang melibatkan sebuah rentang pencarian. Tipe query secara umum dibagi menjadi dua yaitu, operasi pencarian dan perubahan. Operasi perubahan pada suatu rentang akan menyebabkan perubahan hasil pencarian selanjutnya. Dalam permasalahan range query ini cukup
banyak operasi yang harus dilakukan sehingga dibutuhkan struktur data yang mampu mendukung operasi-operasi tersebut secara efisien.
Pada Tugas Akhir ini akan dirancang penyelesaian permasalahan variasi range query antara lain, operasi pencarian bilangan terkecil ke-k, menghitung jumlah elemen yang aktif, mengubah status dari sebuah elemen, dan menukar elemen yang bersebelahan.
Struktur data klasik yang sering digunakan untuk permasalahan ini adalah balanced binary search tree atau segmented tree. Namun pada Tugas Akhir ini digunakan Wavelet Tree untuk menyelesaikan operasi-operasi tersebut.
Hasil dari Tugas Akhir ini telah berhasil menyelesaikan permasalahan di atas dengan cukup efisien dengan kompleksitas waktu O(lg N) per query.
=====================================================================================
Range query computation is a problem which involves a specific range of data. Generally it is divided by two type of query, range search and update. An update operation would have an impact for the following range search query. Typically these kind of problems will have quite large number of queries. Thus, an efficient data structure is needed to support the operations.
This undergraduate thesis will design the problem solving for range query variation such as, find the k-th smallest element, count the number of active elements, toggle an element status, and swap contiguous element. Well known data structures, e.g. balanced binary search tree and segmented tree, are commonly used for solving this problem. Yet, in this undergraduate thesis Wavelet Tree will be used instead for solving those range query variations.
The result shows that wavelet tree has been successfully solve the problem efficiently with overall complexity of O(lg N) each query.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Uncontrolled Keywords: | range query; wavelet tree; rank query; quantile query |
| Subjects: | Z Bibliography. Library Science. Information Resources > ZA Information resources > Z699.5 Information storage and retrieval systems |
| Divisions: | Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Fendy Fendy Fendy |
| Date Deposited: | 30 Mar 2017 05:07 |
| Last Modified: | 05 Mar 2019 04:05 |
| URI: | http://repository.its.ac.id/id/eprint/1756 |
Actions (login required)
 |
View Item |