Towards robust indexing for ranked queries

Dong Xin, Chen Chen, Jiawei Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Top-k query asks for k tuples ordered according to a specific ranking function that combines the values from multiple participating attributes. The combined score function is usually linear. To efficiently answer top-k queries, preprocessing and indexing the data have been used to speed up the run time performance. Many indexing methods allow the online query algorithms progressively retrieve the data and stop at a certain point. However, in many cases, the number of data accesses is sensitive to the query parameters (i.e., linear weights in the score functions). In this paper, we study the sequentially layered indexing problem where tuples are put into multiple consecutive layers and any top-k query can be answered by at most k layers of tuples. We propose a new criterion for building the layered index. A layered index is robust if for any k, the number of tuples in the top k layers is minimal in comparison with all the other alternatives. The robust index guarantees the worst case performance for arbitrary query parameters. We derive a necessary and sufficient condition for robust index. The problem is shown solvable within O(n d log n) (where d is the number of dimensions, and n is the number of tuples). To reduce the high complexity of the exact solution, we develop an approximate approach, which has time complexity 0(2dn(Iog n) r(d)-1), where r(d) = [d/2] + [ d/2][d/2] Our experimental results show that our proposed method outperforms the best known previous methods.

Original languageEnglish (US)
Title of host publicationVLDB 2006 - Proceedings of the 32nd International Conference on Very Large Data Bases
Pages235-246
Number of pages12
StatePublished - Dec 1 2006
Event32nd International Conference on Very Large Data Bases, VLDB 2006 - Seoul, Korea, Republic of
Duration: Sep 12 2006Sep 15 2006

Publication series

NameVLDB 2006 - Proceedings of the 32nd International Conference on Very Large Data Bases

Other

Other32nd International Conference on Very Large Data Bases, VLDB 2006
CountryKorea, Republic of
CitySeoul
Period9/12/069/15/06

ASJC Scopus subject areas

  • Hardware and Architecture
  • Information Systems
  • Software
  • Information Systems and Management

Fingerprint Dive into the research topics of 'Towards robust indexing for ranked queries'. Together they form a unique fingerprint.

Cite this