Weighted Set Containment in Redundant Data Sets

Visa enkel post
dc.contributor.authorGrönvall, Johan
dc.contributor.authorWermensjö, Johan
dc.contributor.departmentChalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)sv
dc.contributor.departmentChalmers University of Technology / Department of Computer Science and Engineering (Chalmers)en
dc.date.accessioned2019-07-03T14:35:42Z
dc.date.available2019-07-03T14:35:42Z
dc.date.issued2017
dc.description.abstractGiven a set family F and a query set Q, weighted set containment is the problem of finding the set C 2 F with the largest sum of weights, such that C Q, where every element has a corresponding weight. This problem was investigated at the request of Volvo Group IT, who rely heavily on weighted set containment queries in many of their applications. In this thesis we show that weighted set containment can be solved efficiently using trie based preprocessing when applied to redundant data sets. We show that finding the most efficient trie which represents F is NP-complete and we introduce a number of approximation algorithms. We show through empirical testing that some of our algorithms outperform state-of-the-art methods for similar problems when applied to Volvo’s particular data set.
dc.identifier.urihttps://hdl.handle.net/20.500.12380/251546
dc.language.isoeng
dc.setspec.uppsokTechnology
dc.subjectData- och informationsvetenskap
dc.subjectComputer and Information Science
dc.titleWeighted Set Containment in Redundant Data Sets
dc.type.degreeExamensarbete för masterexamensv
dc.type.degreeMaster Thesisen
dc.type.uppsokH
local.programmeComputer science – algorithms, languages and logic (MPALG), MSc
Ladda ner
Original bundle
Visar 1 - 1 av 1
Bild (thumbnail)
Namn:
251546.pdf
Storlek:
983.58 KB
Format:
Adobe Portable Document Format
Beskrivning:
Fulltext
Ladda ner
Samling
Examensarbeten för masterexamen