NDLI: Using Histograms for Skyline Size Estimation

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

Web Data Management in the RDF Age: Keynote talk abstract

A Deterministic Model for P2P Deductive Databases

A New XML Schema based on Type Dependencies

Panel: The State of Data: Invited Paper from panelists

A new scalable aggregation scheme for fuzzy clustering Taking unstructured textual resources as a case

The Twitter Bullishness Index: A Social Media Analytics Indicator for the Stock Market

Computing Marginals Using MapReduce: Keynote talk paper

Efficient Approximate OLAP Querying Over Time Series

Clickstream Prediction Using Sequential Stream Mining Techniques with Markov Chains

A Big Data Approach For Querying Data in EHR Systems

TPRED: a Spatio-Temporal Location Predictor Framework

Ontology-Based Data Integration System for Conservation-Restoration Data (OBDIS-CR)

A Two-Phase MapReduce Algorithm for Scalable Preference Queries over High-Dimensional Data

A Case Study of the Aggregation Query Model in Read-Mostly NoSQL Document Stores

On the Discovery of Relaxed Functional Dependencies

Performance Evaluation of NoSQL Multi-Model Data Stores in Polyglot Persistence Applications

An Innovative Framework for Effectively and Efficiently Supporting Big Data Analytics over Geo-Located Mobile Social Media

On computing temporal functions for a time-dependent networks using trajectory data

The Influence of Crowd Type and Task Complexity on Crowdsourced Work Quality

How, Who and When: Enhancing Business Process Warehouses By Graph Based Queries

Optimizing Druid with Roaring bitmaps

Valet SADI: Provisioning SADI Web Services for Semantic Querying of Relational Databases

Data on the move and Issues of Privacy and security: Dangers of the web

A New Approach to Preserving Data Confidentiality in the Cloud

Content-preserving Text Watermarking through Unicode Homoglyph Substitution

JARS: Join-Aware Distributed RDF Storage

Mintra: Mining anonymized trajectories with annotations

XML Type Dependency and XML Type Normal Form

Lazy Evaluation for Concurrent OLTP and Bulk Transactions

Secure and Efficient Multiparty Computation on Genomic Data

Using Histograms for Skyline Size Estimation

Introducing a New Arabic Endpoint for DBpedia Internationalization Project

Improving GraphChi for Large Graph Processing: Fast Radix Sort in Pre-Processing

A Large-Scale Study of Online Shopping Behavior

DynamicDFEP: A Distributed Edge Partitioning Approach for Large Dynamic Graphs

CUTiS: optimized online ClUstering of Trajectory data Stream

Software Analytics in Practice: A Defect Prediction Model Using Code Smells

The Butterfly: An Intelligent Framework for Violation Prediction within Business Processes

Enhanced variational approach by Fast-Marching to recover a 3D shape from shading

Mobile Web Application Generation Features for SuperSQL

The Hilbert PDC-tree: A High-Velocity Structure for Many-Dimensional Data

Hierarchical Crowd Curation of Very Large and Predicted Protein-Protein Interaction Data

Enriching Mobility Data with Linked Open Data

Enhancing applications with filtering of XML message streams

Comparative Mining of B2C Web Sites by Discovering Web Database Schemas

SCI-F: Social-Corporate Data Integration Framework

A Scientist's Impact over Time: The Predictive Power of Clustering with Peers

Modern Web Page Generation by Using Exclusively SuperSQL

Optimization of a Class of Temporal Queries

Extension of Semantic Generalization for Considering a Class-Lattice

Visual Spatial-OLAP for Vehicle Recorder Data on Micro-sized Electric Vehicles

The Extraction from News Stories a Causal Topic Centred Bayesian Graph for Sugarcane

Conceptual and Database Modelling of Graph Databases

Predicting SQL Query Execution Time for Large Data Volume

Provenance Support for Biomedical Big Data Analytics

Using Histograms for Skyline Size Estimation

Content Provider	ACM Digital Library
Author	Hanusse, Nicolas Maabout, Sofian Wanko, Patrick Kamnang
Abstract	Let T be a table of n points described by a set of d attributes/dimensions. Let p, q ∈ T. p dominates q iff it is better than q in every dimension and there exists at least one attribute for which p is strictly better than p. p is a skyline point of T iff it is not dominated by any point of T. A skyline query returns the set of all skyline points. In order to integrate Skyline queries into database management systems, deriving an estimation of the skyline cardinality is important for query optimization purposes. We propose techniques for estimating skyline cardinality when data distribution is known. We first provide an unbiased estimator which requires one traversal of the whole data which is much faster than computing the exact skyline. Then, we show that this estimator can be used on a sample of the underlying data while preserving the estimation quality, i.e., it is still unbiased. Next, we provide a convergent estimator which does not require any data access but the data distribution. It estimates skyline cardinality expectation for those data sets respecting data distribution. The advantages of these solutions are their ease of implementation and, by contrast to other proposals, no costly subskyline queries are required. Our solutions are implemented and some experiments are reported showing both the accuracy of the estimations and the execution time efficiency by which they are obtained.
Starting Page	125
Ending Page	134
Page Count	10
File Format	PDF
ISBN	9781450341189
DOI	10.1145/2938503.2938531
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-07-11
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Algorithms Estimation Expectation Sampling Skyline cardinality
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