NDLI: Efficient $top-\textit{k}$ aggregation of ranked inputs

Content Provider	ACM Digital Library
Author	Yiu, Man Lung Cheng, Kit Hung Cheung, David W. Mamoulis, Nikos
Copyright Year	2007
Abstract	A $top-\textit{k}$ query combines different rankings of the same set of objects and returns the $\textit{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-\textit{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-\textit{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-\textit{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-\textit{k}$ join operator, with certain advantages over evaluation trees of binary $top-\textit{k}$ join operators. Finally, we define and study the computation of $top-\textit{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.
File Format	PDF
ISSN	03625915
e-ISSN	15574644
DOI	10.1145/1272743.1272749
Volume Number	32
Issue Number	3
Journal	ACM Transactions on Database Systems (TODS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-08-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	$Top-\textit{k}$ queries Rank aggregation
Content Type	Text
Resource Type	Article
Subject	Information Systems

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Probabilistic $top-\textit{k}$ and ranking-aggregate queries

An integrated efficient solution for computing frequent and $top-\textit{k}$ elements in data streams

$Top-\textit{k}$ selection queries over relational databases: Mapping strategies and performance evaluation

Evaluating $top-\textit{k}$ queries over web-accessible databases

A survey of $top-\textit{k}$ query processing techniques in relational database systems

Space-Efficient Frameworks for $Top-\textit{k}$ String Retrieval

Top-k diversity queries over bounded regions

Supporting top-k join queries in relational databases

Top-k aggregation using intersections of ranked inputs.

Efficient $top-\textit{k}$ aggregation of ranked inputs

Similar Documents

Probabilistic $top-\textit{k}$ and ranking-aggregate queries

An integrated efficient solution for computing frequent and $top-\textit{k}$ elements in data streams

$Top-\textit{k}$ selection queries over relational databases: Mapping strategies and performance evaluation

Evaluating $top-\textit{k}$ queries over web-accessible databases

A survey of $top-\textit{k}$ query processing techniques in relational database systems

Space-Efficient Frameworks for $Top-\textit{k}$ String Retrieval

Top-k diversity queries over bounded regions

Supporting top-k join queries in relational databases

Top-k aggregation using intersections of ranked inputs.

Efficient $top-\textit{k}$ aggregation of ranked inputs