Multi-column bitmap indexing
dc.contributor.advisor | Kaser, Owen | |
dc.contributor.advisor | Lemire, Daniel | |
dc.contributor.author | Gutarra Velez, Eduardo | |
dc.date.accessioned | 2023-03-01T16:16:40Z | |
dc.date.available | 2023-03-01T16:16:40Z | |
dc.date.issued | 2012 | |
dc.date.updated | 2020-06-10T00:00:00Z | |
dc.description.abstract | Bitmap indices are used to accelerate queries against large databases. We often expect bitmap indices over high-cardinality columns to be too large to be practical. Thus, we might expect multi-column bitmap indices to be disastrous because they are similar to indices over high-cardinality columns. Our findings, however, contradict this intuition. We find that multi-column bitmap indices can be smaller than conventional bitmap indices over individual columns. Yet multi-column bitmap indices can also be alarmingly large in some instances. Hence, our discovery motivates an engineering question: how do we efficiently determine whether a multi-column bitmap index is relatively small without first constructing it? We tried modeling the problem in terms of statistical characteristics such as correlation. However, we found simple heuristics based on indexing samples most effective. Our heuristics could be integrated in database systems to help database administrators pick a better indexing strategy. | |
dc.description.copyright | ©Eduardo Gutarra Velez, 2012 | |
dc.description.note | Scanned from archival print submission. | |
dc.format | text/xml | |
dc.format.extent | x, 128 pages | |
dc.format.medium | electronic | |
dc.identifier.other | Thesis 8996 | |
dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/13251 | |
dc.publisher | University of New Brunswick | |
dc.rights | http://purl.org/coar/access_right/c_abf2 | |
dc.subject.discipline | Computer Science | |
dc.title | Multi-column bitmap indexing | |
dc.type | master thesis | |
thesis.degree.discipline | Computer Science | |
thesis.degree.fullname | Master of Computer Science | |
thesis.degree.grantor | University of New Brunswick | |
thesis.degree.level | masters | |
thesis.degree.name | M.C.S. |
Files
Original bundle
1 - 1 of 1