Weighted Set Containment in Redundant Data Sets

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/251546
Download file(s):
File Description SizeFormat 
251546.pdfFulltext983.58 kBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: Weighted Set Containment in Redundant Data Sets
Authors: Grönvall, Johan
Wermensjö, Johan
Abstract: Given 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.
Keywords: Data- och informationsvetenskap;Computer and Information Science
Issue Date: 2017
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
URI: https://hdl.handle.net/20.500.12380/251546
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.