@inproceedings{b14dcb5e3fe14127a35b48f4dfc61514,
title = "T-LevelIndex: Towards Efficient Query Processing in Continuous Preference Space",
abstract = "Top-k related queries in continuous preference space (e.g., k-shortlist preference query kSPR, uncertain top-k query UTK, output-size specified utility-based query ORU) have numerous applications but are expensive to process. Existing algorithms process each query via specialized optimizations, which are difficult to generalize. In this work, we propose a novel and general index structure T-LevelIndex, which can be used to process various queries in continuous preference space efficiently. We devise efficient approaches to build the T-LevelIndex by fully exploiting the properties of continuous preference space. We conduct extensive experimental studies on both real-and synthetic-benchmarks. The results show that (i) our proposed index building approaches have low costs in terms of both space and time, and (ii) T-LevelIndex significantly outperforms specialized solutions for processing a spectrum of queries in continuous preference space, and the speedup can be two to three orders of magnitude.",
keywords = "k-level index, preference space, top-k query processing",
author = "Jiahao Zhang and Bo Tang and Yiu, {Man Lung} and Xiao Yan and Keming Li",
note = "Funding Information: In this work, we proposed -LevelIndex, which can be used to process a spectrum of queries in continuous preference space. We proposed three approaches with several optimization techniques to build -LevelIndex efficiently. In particular, we represent each cell in an implicit manner to reduce index size, and devise a fast candidate set computation method to partition the geometric region of each cell. We first conducted extensive experiments to demonstrate the superiority of our proposals in terms of index building time and index size. We then investigated the performance of three queries with -LevelIndex. Our solution is faster than their state-of-the-art solutions in the literature by 2 to 3 orders of magnitude. For future work, we plan to enhance -LevelIndex to handle dynamic updates of the options for online applications. ACKNOWLEDGMENTS This work was supported by grant GRF 152050/19E from the Hong Kong RGC, the Guangdong Provincial Key Laboratory (Grant No. 2020B121201001) and the Guangdong Basic and Applied Basic Research Foundation (Grant No. 2021A1515110067). Publisher Copyright: {\textcopyright} 2022 ACM.",
year = "2022",
month = jun,
day = "10",
doi = "10.1145/3514221.3526182",
language = "English",
series = "Proceedings of the ACM SIGMOD International Conference on Management of Data",
publisher = "Association for Computing Machinery (ACM)",
pages = "2149–2162",
booktitle = "SIGMOD 2022 - Proceedings of the 2022 International Conference on Management of Data",
address = "United States",
}