|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE Journal/Magazine Articles >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/2985
|
| Title: | Branch-and-bound processing of ranked queries |
| Authors: | Tao, Yufei
Hristidis, Vagelis
Papadias, Dimitris
Papakonstantinou, Yannis |
| Keywords: | Databases
Ranked queries
R-tree
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 http://www.sciencedirect.com/ |
| URI: | http://hdl.handle.net/1783.1/2985 |
| Appears in Collections: | CSE Journal/Magazine Articles
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| IS07Rank.pdf | pre-published version | 385Kb | Adobe PDF | View/Open |
|
Find published version via |
All items in this Repository are protected by copyright, with all rights reserved.
|
