File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Efficient top-k aggregation of ranked inputs

TitleEfficient top-k aggregation of ranked inputs
Authors
KeywordsRank aggregation
Top-k queries
Issue Date2007
PublisherAssociation for Computing Machinery, Inc.
Citation
Acm Transactions On Database Systems, 2007, v. 32 n. 3 How to Cite?
AbstractA top-k query combines different rankings of the same set of objects and returns the k objects with the highest combined score according to an aggregate function. We bring to light some key observations, which impose two phases that any top-k algorithm, based on sorted accesses, should go through. Based on them, we propose a new algorithm, which is designed to minimize the number of object accesses, the computational cost, and the memory requirements of top-k search with monotone aggregate functions. We provide an analysis for its cost and show that it is always no worse than the baseline no random accesses algorithm in terms of computations, accesses, and memory required. As a side contribution, we perform a space analysis, which indicates the memory requirements of top-k algorithms that only perform sorted accesses. For the case, where the required space exceeds the available memory, we propose disk-based variants of our algorithm. We propose and optimize a multiway top-k join operator, with certain advantages over evaluation trees of binary top-k join operators. Finally, we define and study the computation of top-k cubes and the implementation of roll-up and drill-down operations in such cubes. Extensive experiments with synthetic and real data show that, compared to previous techniques, our method accesses fewer objects, while being orders of magnitude faster. © 2007 ACM.
Persistent Identifierhttp://hdl.handle.net/10722/88889
ISSN
2023 Impact Factor: 2.2
2023 SCImago Journal Rankings: 1.730
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorMamoulis, Nen_HK
dc.contributor.authorYiu, MLen_HK
dc.contributor.authorCheng, KHen_HK
dc.contributor.authorCheung, DWen_HK
dc.date.accessioned2010-09-06T09:49:44Z-
dc.date.available2010-09-06T09:49:44Z-
dc.date.issued2007en_HK
dc.identifier.citationAcm Transactions On Database Systems, 2007, v. 32 n. 3en_HK
dc.identifier.issn0362-5915en_HK
dc.identifier.urihttp://hdl.handle.net/10722/88889-
dc.description.abstractA top-k query combines different rankings of the same set of objects and returns the k objects with the highest combined score according to an aggregate function. We bring to light some key observations, which impose two phases that any top-k algorithm, based on sorted accesses, should go through. Based on them, we propose a new algorithm, which is designed to minimize the number of object accesses, the computational cost, and the memory requirements of top-k search with monotone aggregate functions. We provide an analysis for its cost and show that it is always no worse than the baseline no random accesses algorithm in terms of computations, accesses, and memory required. As a side contribution, we perform a space analysis, which indicates the memory requirements of top-k algorithms that only perform sorted accesses. For the case, where the required space exceeds the available memory, we propose disk-based variants of our algorithm. We propose and optimize a multiway top-k join operator, with certain advantages over evaluation trees of binary top-k join operators. Finally, we define and study the computation of top-k cubes and the implementation of roll-up and drill-down operations in such cubes. Extensive experiments with synthetic and real data show that, compared to previous techniques, our method accesses fewer objects, while being orders of magnitude faster. © 2007 ACM.en_HK
dc.languageengen_HK
dc.publisherAssociation for Computing Machinery, Inc.en_HK
dc.relation.ispartofACM Transactions on Database Systemsen_HK
dc.rightsACM Transactions on Database Systems. Copyright © Association for Computing Machinery, Inc.en_HK
dc.subjectRank aggregationen_HK
dc.subjectTop-k queriesen_HK
dc.titleEfficient top-k aggregation of ranked inputsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0730-0301&volume=32&issue=3&spage=&epage=&date=2007&atitle=Efficient+Top-k+Aggregation+of+Ranked+Inputsen_HK
dc.identifier.emailMamoulis, N:nikos@cs.hku.hken_HK
dc.identifier.emailCheung, DW:dcheung@cs.hku.hken_HK
dc.identifier.authorityMamoulis, N=rp00155en_HK
dc.identifier.authorityCheung, DW=rp00101en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1145/1272743.1272749en_HK
dc.identifier.scopuseid_2-s2.0-34548407283en_HK
dc.identifier.hkuros149702en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-34548407283&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume32en_HK
dc.identifier.issue3en_HK
dc.identifier.eissn1557-4644-
dc.identifier.isiWOS:000249890400006-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridMamoulis, N=6701782749en_HK
dc.identifier.scopusauthoridYiu, ML=8589889600en_HK
dc.identifier.scopusauthoridCheng, KH=34467513500en_HK
dc.identifier.scopusauthoridCheung, DW=34567902600en_HK
dc.identifier.issnl0362-5915-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats