NDLI: Optimal algorithms for evaluating rank joins in database systems

Content Provider	ACM Digital Library
Author	Schnaitter, Karl Polyzotis, Neoklis
Copyright Year	2010
Abstract	In the rank join problem, we are given a set of relations and a scoring function, and the goal is to return the join results with the top $\textit{k}$ scores. It is often the case in practice that the inputs may be accessed in ranked order and the scoring function is monotonic. These conditions allow for efficient algorithms that solve the rank join problem without reading all of the input. In this article, we present a thorough analysis of such rank join algorithms. A strong point of our analysis is that it is based on a more general problem statement than previous work, making it more relevant to the execution model that is employed by database systems. One of our results indicates that the well-known HRJN algorithm has shortcomings, because it does not stop reading its input as soon as possible. We find that it is NP-hard to overcome this weakness in the general case, but cases of limited query complexity are tractable. We prove the latter with an algorithm that infers provably tight bounds on the potential benefit of reading more input in order to stop as soon as possible. As a result, the algorithm achieves a cost that is within a constant factor of optimal.
Starting Page	1
Ending Page	47
Page Count	47
File Format	PDF
ISSN	03625915
e-ISSN	15574644
DOI	10.1145/1670243.1670249
Volume Number	35
Issue Number	1
Journal	ACM Transactions on Database Systems (TODS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-02-15
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
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

Adaptive algorithms for set containment joins

On the optimal nesting order for computing $\textit{N}-relational$ joins

Performing joins without decompression in a compressed database system

Multiway spatial joins

On optimal processor allocation to support pipelined hash joins

Provisional reporting for rank joins

Ripple joins for online aggregation

Top-k spatial joins

Extending a relational database with deferred referential integrity checking and intelligent joins

Optimal algorithms for evaluating rank joins in database systems

Similar Documents

Adaptive algorithms for set containment joins

On the optimal nesting order for computing $\textit{N}-relational$ joins

Performing joins without decompression in a compressed database system

Multiway spatial joins

On optimal processor allocation to support pipelined hash joins

Provisional reporting for rank joins

Ripple joins for online aggregation

Top-k spatial joins

Extending a relational database with deferred referential integrity checking and intelligent joins

Optimal algorithms for evaluating rank joins in database systems