Processing ranked queries with the minimum space

Yufei Tao; Marios Hadjieleftheriou

doi:10.1007/11663881_17

Processing ranked queries with the minimum space

Yufei Tao, Marios Hadjieleftheriou

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

2 Citations (Scopus)

Abstract

Practical applications often need to rank multi-variate records by assigning various priorities to different attributes. Consider a relation that stores students' grades on two courses: database and algorithm. Student performance is evaluated by an "overall score" calculated as w ₁ · g_db + w₂ · g_alg, where w₁, w₂ are two input "weights", and g _db (g_alg) is the student grade on database (algorithm). A "top-k ranked query" retrieves the k students with the best scores according to specific w₁ and w₂. We focus on top-k queries whose k is bounded by a constant c, and present solutions that guarantee low worst-case query cost by using provably the minimum space. The core of our methods is a novel concept, "minimum covering subset", which contains only the necessary data for ensuring correct answers for all queries. Any 2D ranked search, for example, can be processed in O(log_B(m/B) + c/B) I/Os using O(m/B) space, where m is the size of the minimum covering subset, and B the disk page capacity. Similar results are also derived for higher dimensionalities and approximate ranked retrieval. © Springer-Verlag Berlin Heidelberg 2006.

Original language	English
Title of host publication	Foundations of Information and Knowledge Systems - 4th International Symposium, FoIKS 2006, Proceedings
Pages	294-312
Volume	3861 LNCS
DOIs	https://doi.org/10.1007/11663881_17
Publication status	Published - 2006
Externally published	Yes
Event	4th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2006 - Budapest, Hungary Duration: 14 Feb 2006 → 17 Feb 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3861 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	4th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2006
Place	Hungary
City	Budapest
Period	14/02/06 → 17/02/06

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

This work was fully supported by RGC Grant CityU 1163/04E from the government of HKSAR.

RGC Funding Information

RGC-funded

Access Output

10.1007/11663881_17

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Tao, Y., & Hadjieleftheriou, M. (2006). Processing ranked queries with the minimum space. In Foundations of Information and Knowledge Systems - 4th International Symposium, FoIKS 2006, Proceedings (Vol. 3861 LNCS, pp. 294-312). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3861 LNCS). https://doi.org/10.1007/11663881_17

@inproceedings{b447038320b24f608e572a563d3b85af,

title = "Processing ranked queries with the minimum space",

abstract = "Practical applications often need to rank multi-variate records by assigning various priorities to different attributes. Consider a relation that stores students' grades on two courses: database and algorithm. Student performance is evaluated by an {"}overall score{"} calculated as w 1 · gdb + w2 · galg, where w1, w2 are two input {"}weights{"}, and g db (galg) is the student grade on database (algorithm). A {"}top-k ranked query{"} retrieves the k students with the best scores according to specific w1 and w2. We focus on top-k queries whose k is bounded by a constant c, and present solutions that guarantee low worst-case query cost by using provably the minimum space. The core of our methods is a novel concept, {"}minimum covering subset{"}, which contains only the necessary data for ensuring correct answers for all queries. Any 2D ranked search, for example, can be processed in O(logB(m/B) + c/B) I/Os using O(m/B) space, where m is the size of the minimum covering subset, and B the disk page capacity. Similar results are also derived for higher dimensionalities and approximate ranked retrieval. {\textcopyright} Springer-Verlag Berlin Heidelberg 2006.",

author = "Yufei Tao and Marios Hadjieleftheriou",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].; 4th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2006 ; Conference date: 14-02-2006 Through 17-02-2006",

year = "2006",

doi = "10.1007/11663881_17",

language = "English",

isbn = "3540317821",

volume = "3861 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "294--312",

booktitle = "Foundations of Information and Knowledge Systems - 4th International Symposium, FoIKS 2006, Proceedings",

}

Tao, Y & Hadjieleftheriou, M 2006, Processing ranked queries with the minimum space. in Foundations of Information and Knowledge Systems - 4th International Symposium, FoIKS 2006, Proceedings. vol. 3861 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3861 LNCS, pp. 294-312, 4th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2006, Budapest, Hungary, 14/02/06. https://doi.org/10.1007/11663881_17

Processing ranked queries with the minimum space. / Tao, Yufei; Hadjieleftheriou, Marios.
Foundations of Information and Knowledge Systems - 4th International Symposium, FoIKS 2006, Proceedings. Vol. 3861 LNCS 2006. p. 294-312 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3861 LNCS).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Processing ranked queries with the minimum space

AU - Tao, Yufei

AU - Hadjieleftheriou, Marios

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 2006

Y1 - 2006

N2 - Practical applications often need to rank multi-variate records by assigning various priorities to different attributes. Consider a relation that stores students' grades on two courses: database and algorithm. Student performance is evaluated by an "overall score" calculated as w 1 · gdb + w2 · galg, where w1, w2 are two input "weights", and g db (galg) is the student grade on database (algorithm). A "top-k ranked query" retrieves the k students with the best scores according to specific w1 and w2. We focus on top-k queries whose k is bounded by a constant c, and present solutions that guarantee low worst-case query cost by using provably the minimum space. The core of our methods is a novel concept, "minimum covering subset", which contains only the necessary data for ensuring correct answers for all queries. Any 2D ranked search, for example, can be processed in O(logB(m/B) + c/B) I/Os using O(m/B) space, where m is the size of the minimum covering subset, and B the disk page capacity. Similar results are also derived for higher dimensionalities and approximate ranked retrieval. © Springer-Verlag Berlin Heidelberg 2006.

AB - Practical applications often need to rank multi-variate records by assigning various priorities to different attributes. Consider a relation that stores students' grades on two courses: database and algorithm. Student performance is evaluated by an "overall score" calculated as w 1 · gdb + w2 · galg, where w1, w2 are two input "weights", and g db (galg) is the student grade on database (algorithm). A "top-k ranked query" retrieves the k students with the best scores according to specific w1 and w2. We focus on top-k queries whose k is bounded by a constant c, and present solutions that guarantee low worst-case query cost by using provably the minimum space. The core of our methods is a novel concept, "minimum covering subset", which contains only the necessary data for ensuring correct answers for all queries. Any 2D ranked search, for example, can be processed in O(logB(m/B) + c/B) I/Os using O(m/B) space, where m is the size of the minimum covering subset, and B the disk page capacity. Similar results are also derived for higher dimensionalities and approximate ranked retrieval. © Springer-Verlag Berlin Heidelberg 2006.

UR - http://www.scopus.com/inward/record.url?scp=33745652469&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-33745652469&origin=recordpage

U2 - 10.1007/11663881_17

DO - 10.1007/11663881_17

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 3540317821

SN - 9783540317821

VL - 3861 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 294

EP - 312

BT - Foundations of Information and Knowledge Systems - 4th International Symposium, FoIKS 2006, Proceedings

T2 - 4th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2006

Y2 - 14 February 2006 through 17 February 2006

ER -

Tao Y, Hadjieleftheriou M. Processing ranked queries with the minimum space. In Foundations of Information and Knowledge Systems - 4th International Symposium, FoIKS 2006, Proceedings. Vol. 3861 LNCS. 2006. p. 294-312. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11663881_17

Processing ranked queries with the minimum space

Abstract

Publication series

Conference

Bibliographical note

Funding

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this