Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

8-2013

Abstract

Given a high-dimensional dataset, a top-k query can be used to shortlist the k tuples that best match the user’s preferences. Typically, these preferences regard a subset of the available dimensions (i.e., attributes) whose relative significance is expressed by user-specified weights. Along with the query result, we propose to compute for each involved dimension the maximal deviation to the corresponding weight for which the query result remains valid. The derived weight ranges, called immutable regions, are useful for performing sensitivity analysis, for finetuning the query weights, etc. In this paper, we focus on top-k queries with linear preference functions over the queried dimensions. We codify the conditions under which changes in a dimension’s weight invalidate the query result, and develop algorithms to compute the immutable regions. In general, this entails the examination of numerous non-result tuples. To reduce processing time, we introduce a pruning technique and a thresholding mechanism that allow the immutable regions to be determined correctly after examining only a small number of non-result tuples. We demonstrate empirically that the two techniques combine well to form a robust and highly resource-efficient algorithm. We verify the generality of our findings using real high- dimensional data from different domains (documents, images, etc) and with different characteristics.

Keywords

Corresponding weights, Different domains, High dimensional data, High-dimensional dataset, Preference functions, Pruning techniques, Resource-efficient, User's preferences

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Science and Engineering

Publication

Proceedings of the VLDB Endowment: 39th VLDB 2013, August 26-30, Riva del Garda, Trento, Italy

Volume

6

Issue

2

First Page

73

Last Page

84

ISSN

2150-8097

Identifier

10.14778/2535568.2448941

Publisher

VLDB Endowment

City or Country

New York

Copyright Owner and License

Publisher

Additional URL

https://doi.org/10.14778/2535568.2448941

Download

Share

COinS