Conference Proceeding Article
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.
Corresponding weights, Different domains, High dimensional data, High-dimensional dataset, Preference functions, Pruning techniques, Resource-efficient, User's preferences
Databases and Information Systems | Numerical Analysis and Scientific Computing
Data Management and Analytics
Proceedings of the VLDB Endowment: 39th VLDB 2013, August 26-30, Riva del Garda, Trento, Italy
City or Country
MOURATIDIS, Kyriakos and PANG, Hwee Hwa.
Computing Immutable Regions for Subspace Top-k Queries. (2013). Proceedings of the VLDB Endowment: 39th VLDB 2013, August 26-30, Riva del Garda, Trento, Italy. 6, (2), 73-84. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/1624
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.