HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Journal/Magazine Articles >

Please use this identifier to cite or link to this item:
Title: Branch-and-bound processing of ranked queries
Authors: Tao, Yufei
Hristidis, Vagelis
Papadias, Dimitris
Papakonstantinou, Yannis
Keywords: Databases
Ranked queries
Branch-and-bound algorithms
Issue Date: May-2007
Citation: Information systems, v. 32, no. 3, May 2007, p. 424-445
Abstract: Despite the importance of ranked queries in numerous applications involving multi-criteria decision making, they are not efficiently supported by traditional database systems. In this paper, we propose a simple yet powerful technique for processing such queries based on multidimensional access methods and branch-and-bound search. The advantages of the proposed methodology are: (i) it is space efficient, requiring only a single index on the given relation (storing each tuple at most once), (ii) it achieves significant (i.e., orders of magnitude) performance gains with respect to the current state-of-the-art, (iii) it can efficiently handle data updates, and (iv) it is applicable to other important variations of ranked search (including the support for non-monotone preference functions), at no extra space overhead. We confirm the superiority of the proposed methods with a detailed experimental study.
Rights: Information systems © copyright (2007) Elsevier. The Journal's web site is located at
Appears in Collections:CSE Journal/Magazine Articles

Files in This Item:

File Description SizeFormat
IS07Rank.pdfpre-published version385KbAdobe PDFView/Open

Find published version via OpenURL Link Resolver

All items in this Repository are protected by copyright, with all rights reserved.