Please use this identifier to cite or link to this item:

Branch-and-bound processing of ranked queries

Authors Tao, Yufei
Hristidis, Vagelis
Papadias, Dimitris
Papakonstantinou, Yannis
Issue Date 2007
Source Information systems , v. 32, (3), 2007, MAY, p. 424-445
Summary 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 multi-dimensional 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. (C) 2006 Elsevier B.V. All rights reserved.
ISSN 0306-4379
Rights Information systems © copyright (2007) Elsevier. The Journal's web site is located at
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Files in this item:
File Description Size Format
IS07Rank.pdf 394378 B Adobe PDF