NDLI: Efficient Top-k Indexing via General Reductions

Please wait, while we are loading the content...

A Theory of Regular Queries

2016 ACM PODS Alberto O. Mendelzon Test-of-Time Award

Optimal Score Aggregation Algorithms

Incremental View Maintenance For Collection Programming

Data Management for Social Networking

Verification of Hierarchical Artifact Systems

Schema Validation via Streaming Circuits

Logical Aspects of Massively Parallel and Distributed Systems

Counting Answers to Existential Positive Queries: A Complexity Classification

Towards Tight Bounds for the Streaming Set Cover Problem

Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures

FAQ: Questions Asked Frequently

Hypertree Decompositions: Questions and Answers

AJAR: Aggregations and Joins over Annotated Relations

Recency-Bounded Verification of Dynamic Database-Driven Systems

Variability in Data Streams

Computing Join Queries with Functional Dependencies

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems

Space Lower Bounds for Itemset Frequency Sketches

Shortest Paths and Distances with Differential Privacy

Bounded Query Rewriting Using Views

Making SQL Queries Correct on Incomplete Databases: A Feasibility Study

Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors

Semantic Acyclicity Under Constraints

Better Algorithms for Counting Triangles in Data Streams

Are Few Bins Enough: Testing Histogram Distributions

Minimization of Tree Pattern Queries

Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable

Designing a Query Language for RDF: Marrying Open and Closed Worlds

Efficient Top-k Indexing via General Reductions

Tractable Lineages on Treelike Instances: Limits and Extensions

Locating a Small Cluster Privately

Range-Max Queries on Uncertain Data

Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins

Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries

Fast Algorithms for Parsing Sequences of Parentheses with Few Errors

On the Complexity of Inner Product Similarity Join

Efficient Top-k Indexing via General Reductions

Content Provider	ACM Digital Library
Author	Rahul, Saladi Tao, Yufei
Abstract	Let D be a set of n elements each associated with a real-valued weight, and Q be the set of all possible predicates allowed on those elements. Given a predicate in Q and integer k, a top-k query returns the k elements with the largest weights among the elements of D satisfying q. The corresponding data structure problem aims to store D in small space to allow every query to be answered efficiently. It is already known that, before settling the problem, one must be able to solve two degenerated accompanying problems: (i) prioritized reporting: given a predicate q ∈ Q and a real value τ, return all the elements of D satisfying q and having weights at least τ (ii) max reporting: top-k queries with k fixed to 1. In this paper we prove general reductions in external memory that explore the opposite direction. Our first reduction shows that, (under mild conditions) any prioritized reporting structure yields a static top-\$k\$ structure with only a slow-down in query time by a factor of $O(log_{B}$ n), where B is the block size. Our second reduction shows that if one additionally has a max reporting structure, then combining the two structures yields a top-k structure with no performance slow down (in space, query, and update) in expectation. These reductions significantly simplify the design of top-k structures, as we showcase on numerous problems including halfspace reporting, circular reporting, interval stabbing, point enclosure, and 3d dominance. All the techniques proposed work directly in the RAM model as well.
Starting Page	277
Ending Page	288
Page Count	12
File Format	PDF
ISBN	9781450341912
DOI	10.1145/2902251.2902290
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-06-15
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Top-k Algorithms Reductions Data structures External memory Ram
Content Type	Text
Resource Type	Article

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

Top-k Indexes Made Small and Sweet (Invited Talk)

RAM-Efficient External Memory Sorting

Space-Efficient Framework for Top-k String Retrieval Problems

Efficient in-memory top-k document retrieval

I/O-Efficient Compressed Text Indexes: From Theory to Practice

Dynamic top-k range reporting in external memory

RAM-Efficient External Memory Sorting

External Memory Three-Sided Range Reporting and Top-$k$ Queries with Sublogarithmic Updates

Lightweight Data Indexing and Compression in External Memory

Efficient Top-k Indexing via General Reductions

Similar Documents

Top-k Indexes Made Small and Sweet (Invited Talk)

RAM-Efficient External Memory Sorting

Space-Efficient Framework for Top-k String Retrieval Problems

Efficient in-memory top-k document retrieval

I/O-Efficient Compressed Text Indexes: From Theory to Practice

Dynamic top-k range reporting in external memory

RAM-Efficient External Memory Sorting

External Memory Three-Sided Range Reporting and Top-$k$ Queries with Sublogarithmic Updates

Lightweight Data Indexing and Compression in External Memory

Efficient Top-k Indexing via General Reductions