NDLI: MAXENT: consistent cardinality estimation in action

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

Speeding up search in peer-to-peer networks with a multi-way tree structure

Query evaluation using overlapping views: completeness and efficiency

MauveDB: supporting model-based user views in database systems

Forensic analysis of database tampering

Contour map matching for event detection in sensor networks

Modeling skew in data streams

Injecting utility into anonymized datasets

Interactive query formulation over web service-accessed sources

Communication-efficient distributed monitoring of thresholded counts

GPUTeraSort: high performance graphics co-processor sorting for large database management

Boolean + ranking: querying a database by k-constrained optimization

High-performance complex event processing over streams

Rewriting nested XML queries using nested views

Refreshing the sky: the compressed skycube with efficient support for frequent updates

Provenance management in curated databases

On the database/network interface in large-scale publish/subscribe systems

On-the-fly sharing for streamed aggregation

DADA: a data cube for dominant relationship analysis

Data delivery in a service-oriented world: the BEA aquaLogic data services platform

Documentum ECI self-repairing wrappers: performance analysis

Trends in high performance analytics

Using the oracle database as a declarative RSS hub

Data management projects at Google

PADS: an end-to-end system for processing ad hoc data

Generic similarity detection in ontologies with the SOQA-SimPack toolkit

MAXENT: consistent cardinality estimation in action

Managing information extraction: state of the art and research directions

Programming for XML

Record linkage: similarity measures and algorithms

Accessing the web: from search to integration

Adaptive query processing: why, how, when, what next

Reconciling while tolerating disagreement in collaborative data sharing

User-defined aggregate functions: bridging theory and practice

Database support for matching: limitations and opportunities

Dynamic authenticated index structures for outsourced databases

Constraint chaining: on energy-efficient continuous monitoring in sensor networks

Fast range-summable random variables for efficient aggregate estimation

Personalized privacy preservation

To search or to crawl?: towards a query optimizer for text-centric tasks

A geometric approach to monitoring threshold functions over distributed data streams

Recovery from "bad" user transactions

Ranking objects based on relationships

Quality-aware dstributed data delivery for continuous query services

Meta-data indexing for XPath location steps

Finding k-dominant skylines in high dimensional space

Efficient query processing on unstructured tetrahedral meshes

Relaxed-currency serializability for middle-tier caching and replication

Continuous monitoring of top-k queries over sliding windows

Integrating compression and execution in column-oriented database systems

LINQ: reconciling object, relations and XML in the .NET framework

Identity resolution: 23 years of practical experience and observations at scale

VizQL: a language for query, analysis and visualization

Windows and RSS: beyond blogging

Data management in the CarTel mobile sensor computing system

Searching in time

InMAF: indexing music databases via multiple acoustic features

Approximately detecting duplicates for streaming data using stable bloom filters

Supporting ad-hoc ranking aggregates

Declarative networking: language, execution and optimization

Redundancy and information leakage in fine-grained access control

Energy-efficient monitoring of extreme values in sensor networks

Graph-based synopses for relational selectivity estimation

Simultaneous scalability and security for data-intensive web applications

Efficient query processing in geographic web search engines

Continuous query processing in data streams using duality of data and queries

Run-time operator state spilling for memory intensive long-running queries

Context-sensitive ranking

Design, implementation, and evaluation of the linear road bnchmark on the stream processing core

Locking-aware structural join operators for XML query processing

Efficient reverse k-nearest neighbor search in arbitrary metric spaces

Effective keyword search in relational databases

Extensible optimization in overlay dissemination trees

Optimal multi-scale patterns in time series streams

Automatic physical design tuning: workload as a sequence

PHP: supporting the new paradigm of situational and composite web applications

Using SPIDER: an experience report

Fast approximate computation of statistics on views

VGM: visual graph mining

Derby/S: a DBMS for sample-based query answering

Quark: an efficient XQuery full-text implementation

Ordering the attributes of query results

MonetDB/XQuery: a fast XQuery processor powered by a relational engine

A non-linear dimensionality-reduction technique for fast similarity search in large databases

Flexible and efficient XML search with complex full-text predicates

Data integration through transform reuse in the Morpheus project

Automatic client-server partitioning of data-driven web applications

aAqua: a database-backended multilingual, multimedia community forum

Testing database applications

Paper-based mobile access to databases

CS cache engine: data access accelerator for location-based service in mobile environments

The BEA AquaLogic data services platform (Demo)

Proactive identification of performance problems

Avatar semantic search: a database approach to information retrieval

VisTrails: visualization meets data management

XPORT: extensible profile-driven overlay routing trees

COLT: continuous on-line tuning

OMCAT: optimal maintenance of continuous queries' answers for trajectories

A system for specification and verification of interactive, data-driven web applications

ObjectRank: a system for authority-based search on databases

MAXENT: consistent cardinality estimation in action

Content Provider	ACM Digital Library
Author	Megiddo, N. Kutsch, M. Haas, P. J. Tran, T. M. Markl, V.
Abstract	When comparing alternative query execution plans (QEPs), a cost-based query optimizer in a relational database management system needs to estimate the selectivity of conjunctive predicates. To avoid inaccurate independence assumptions, modern optimizers try to exploit multivariate statistics (MVS) that provide knowledge about joint frequencies in a table of a relation. Because the complete joint distribution is almost always too large to store, optimizers are given only partial knowledge about this distribution. As a result, there exist multiple, non-equivalent ways to estimate the selectivity of a conjunctive predicate. To consistently combine the partial knowledge during the estimation process, existing optimizers employ cumbersome ad hoc heuristics. These methods unjustifiably ignore valuable information, and the optimizer tends to favor QEPs for which the least information is available. This bias problem yields poor QEP quality and performance. We demonstrate MAXENT, a novel approach based on the maximum entropy principle, prototyped in IBM DB2 LUW. We illustrate MAXENT's ability to consistently estimate the selectivity of conjunctive predicates on a per-table basis. In contrast to the DB2 optimizer's current ad hoc methods, we show how MAXENT exploits all available information about the joint column distribution and thus avoids the bias problem. For some complex queries against a real-world database, we show that MAXENT improves selectivity estimates by orders of magnitude relative to the current DB2 optimizer, and also show how these improved estimate influence plan choices as well as query execution times.
Starting Page	775
Ending Page	777
Page Count	3
File Format	PDF
ISBN	1595934340
DOI	10.1145/1142473.1142586
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2006-06-27
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Cardinality bias Selectivity estimation Maximum entropy Query optimization
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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