Multi-column bitmap indexing

Simple item page
dc.contributor.advisorKaser, Owen
dc.contributor.advisorLemire, Daniel
dc.contributor.authorGutarra Velez, Eduardo
dc.date.accessioned2023-03-01T16:16:40Z
dc.date.available2023-03-01T16:16:40Z
dc.date.issued2012
dc.date.updated2020-06-10T00:00:00Z
dc.description.abstractBitmap 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.noteScanned from archival print submission.
dc.formattext/xml
dc.format.extentx, 128 pages
dc.format.mediumelectronic
dc.identifier.oclc(OCoLC)1330245753en
dc.identifier.otherThesis 8996
dc.identifier.urihttps://unbscholar.lib.unb.ca/handle/1882/13251
dc.publisherUniversity of New Brunswick
dc.rightshttp://purl.org/coar/access_right/c_abf2
dc.subject.disciplineComputer Science
dc.subject.lcshDatabases.en
dc.subject.lcshIndexing.en
dc.subject.lcshHeuristic algorithms.en
dc.titleMulti-column bitmap indexing
dc.typemaster thesis
thesis.degree.disciplineComputer Science
thesis.degree.fullnameMaster of Computer Science
thesis.degree.grantorUniversity of New Brunswick
thesis.degree.levelmasters
thesis.degree.nameM.C.S.

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
item.pdf
Size:
10.37 MB
Format:
Adobe Portable Document Format
Download

Collections

Open Theses & Dissertations