Approximate Top-K Retrieval from Hidden Relations

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorUkkonen, Antti
dc.contributor.departmentDepartment of Information and Computer Scienceen
dc.contributor.departmentTietojenkäsittelytieteen laitosfi
dc.contributor.schoolFaculty of Information and Natural Sciencesen
dc.contributor.schoolInformaatio- ja luonnontieteiden tiedekuntafi
dc.date.accessioned2011-11-28T13:27:11Z
dc.date.available2011-11-28T13:27:11Z
dc.date.issued2010
dc.description.abstractWe consider the evaluation of approximate top-k queries from relations with a-priori unknown values. Such relations can arise for example in the context of expensive predicates, or cloud-based data sources. The task is to find an approximate top-k set that is close to the exact one while keeping the total processing cost low. The cost of a query is the sum of the costs of the entries that are read from the hidden relation. A novel aspect of this work is that we consider prior information about the values in the hidden matrix. We propose an algorithm that uses regression models at query time to assess whether a row of the matrix can enter the top-k set given that only a subset of its values are known. The regression models are trained with existing data that follows the same distribution as the relation subjected to the query. To evaluate the algorithm and to compare it with a method proposed previously in literature, we conduct experiments using data from a context sensitive Wikipedia search engine. The results indicate that the proposed method outperforms the baseline algorithms in terms of the cost while maintaining a high accuracy of the returned results.en
dc.format.extent29
dc.format.mimetypeapplication/pdf
dc.identifier.isbn978-952-60-3329-7
dc.identifier.issn1797-5042
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/914
dc.identifier.urnurn:nbn:fi:tkk-013190
dc.language.isoenen
dc.publisherAalto University School of Science and Technologyen
dc.publisherAalto-yliopiston teknillinen korkeakoulufi
dc.relation.ispartofseriesTKK reports in information and computer scienceen
dc.relation.ispartofseries36en
dc.subject.keywordquery processingen
dc.subject.keywordnearest neighbor searchen
dc.subject.keywordmachine learningen
dc.subject.keywordInformation search and retrievalen
dc.subject.otherComputer scienceen
dc.titleApproximate Top-K Retrieval from Hidden Relationsen
dc.type.dcmitypetexten
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
isbn9789526033297.pdf
Size:
267.22 KB
Format:
Adobe Portable Document Format