NDLI: Optimal aggregation algorithms for middleware

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

A Web Odyssey: from Codd to XML

Querying websites using compact skeletons

Dynamically distributed query evaluation

Flexible queries over semistructured data

Multiobjective query optimization

Pipelining in multi-query optimization

Optimization of sequence queries in database systems

The parameterized complexity of database queries

Relaxed multi-way trees with group updates

Optimal aggregation algorithms for middleware

On XML integrity constraints in the presence of DTDs

Extended path expressions of XML

XML with data values: typechecking revisited

Representing and querying XML with incomplete information

Querying partially sound and complete data sources

On computing functions with uncertainty

String operations in query languages

Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width

On the complexity of join predicates

Equivalences among aggregate queries with negation

Optimal and approximate computation of summary statistics for range aggregates

Efficient computation of temporal aggregates with range predicates

The challenges of delivering content on the Internet

On the design and quantification of privacy preserving data mining algorithms

On the effects of dimensionality reduction on high dimensional similarity search

A condensed representation to find frequent patterns

Database-friendly random projections

Two-dimensional substring indexing

Process locking: a protocol based on ordered shared locks for the execution of transactional processes

Optimal aggregation algorithms for middleware

Content Provider	ACM Digital Library
Author	Naor, Moni Fagin, Ronald Lotem, Amnon
Abstract	Assume that each object in a database has m grades, or scores, one for each of m attributes. For example, an object can have a color grade, that tells how red it is, and a shape grade, that tells how round it is. For each attribute, there is a sorted list, which lists each object and its grade under that attribute, sorted by grade (highest grade first). There is some monotone aggregation function, or combining rule, such as min or average, that combines the individual grades to obtain an overall grade.To determine objects that have the best overall grades, the naive algorithm must access every object in the database, to find its grade under each attribute. Fagin has given an algorithm (“Fagin's Algorithm”, or FA) that is much more efficient. For some distributions on grades, and for some monotone aggregation functions, FA is optimal in a high-probability sense.We analyze an elegant and remarkably simple algorithm (“the threshold algorithm”, or TA) that is optimal in a much stronger sense than FA. We show that TA is essentially optimal, not just for some monotone aggregation functions, but for all of them, and not just in a high-probability sense, but over every database. Unlike FA, which requires large buffers (whose size may grow unboundedly as the database size grows), TA requires only a small, constant-size buffer.We distinguish two types of access: sorted access (where the middleware system obtains the grade of an object in some sorted list by proceeding through the list sequentially from the top), and random access (where the middleware system requests the grade of object in a list, and obtains it in one step). We consider the scenarios where random access is either impossible, or expensive relative to sorted access, and provide algorithms that are essentially optimal for these cases as well.
Starting Page	102
Ending Page	113
Page Count	12
File Format	PDF
ISBN	1581133618
DOI	10.1145/375551.375567
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2001-05-01
Publisher Place	New York
Access Restriction	Subscribed
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

Optimal aggregation algorithms for middleware (2001).

Optimal Aggregation Algorithms for Middleware , PODS , 2001 , ACM , 1 — 15

Optimal Score Aggregation Algorithms

Optimal Aggregation Algorithms for Middleware

Efficient data aggregation middleware for wireless sensor networks

An Experimental Evaluation of Aggregation Algorithms for Processing Top-K Queries

Optimal Aggregation Algorithms for Middleware (2001)

OPERETTA: Demonstrating an optimal energy efficient bandwidth aggregation system

Optimal Aggregation Algorithms for Middleware (2001)

Optimal aggregation algorithms for middleware

Similar Documents

Optimal aggregation algorithms for middleware (2001).

Optimal Aggregation Algorithms for Middleware , PODS , 2001 , ACM , 1 — 15

Optimal Score Aggregation Algorithms

Optimal Aggregation Algorithms for Middleware

Efficient data aggregation middleware for wireless sensor networks

An Experimental Evaluation of Aggregation Algorithms for Processing Top-K Queries

Optimal Aggregation Algorithms for Middleware (2001)

OPERETTA: Demonstrating an optimal energy efficient bandwidth aggregation system

Optimal Aggregation Algorithms for Middleware (2001)

Optimal aggregation algorithms for middleware