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

Jiahao Zhang, Bo Tang, Man Lung Yiu, Xiao Yan, Keming Li

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

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.

Original languageEnglish
Title of host publicationSIGMOD 2022 - Proceedings of the 2022 International Conference on Management of Data
PublisherAssociation for Computing Machinery (ACM)
Pages2149–2162
Number of pages14
ISBN (Electronic)978-1-4503-9249-5
DOIs
Publication statusPublished - 10 Jun 2022

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078

Keywords

  • k-level index
  • preference space
  • top-k query processing

ASJC Scopus subject areas

  • Software
  • Information Systems

Fingerprint

Dive into the research topics of 'T-LevelIndex: Towards Efficient Query Processing in Continuous Preference Space'. Together they form a unique fingerprint.

Cite this