T-LevelIndex: Towards Efficient Query Processing in Continuous Preference Space

Zhang，Jiahao1; Tang，Bo2; Yiu，Man Lung1; Yan，Xiao2; Li，Keming2

10.1145/3514221.3526182

2022-06-10

0730-8078

Proceedings of the ACM SIGMOD International Conference on Management of Data

2149-2162

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.

k-level index preference space top-k query processing

Corresponding

English

EI

20222612274894

Information retrieval

Information Retrieval and Use:903.3

2-s2.0-85132728180

Scopus

1.Hong Kong Polytechnic University,Hong Kong,Hong Kong
2.Southern University of Science and Technology,Shenzhen,China

Zhang，Jiahao,Tang，Bo,Yiu，Man Lung,et al. T-LevelIndex: Towards Efficient Query Processing in Continuous Preference Space[C],2022:2149-2162.