NDLI: Logging every footstep: quantile summaries for the entire history

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

2010 SIGMOD Awards Presentations

The flow of on-line information in global networks

Efficiently evaluating complex boolean expressions

Leveraging spatio-temporal redundancy for RFID data cleansing

TEDI: efficient shortest path query answering on graphs

PR-join: a non-blocking join achieving higher early result rate with statistical guarantees

Spreadsheet as a relational database engine

Processing proximity relations in road networks

GRN model of probabilistic databases: construction, transition and querying

FAST: fast architecture sensitive tree search on modern CPUs and GPUs

Automatically incorporating new sources in keyword search-based data integration

Multiple feature fusion for social media applications

Automatic contention detection and amelioration for data-intensive operations

Variance aware optimization of parameterized queries

An evaluation of alternative architectures for transaction processing in the cloud

Hierarchically organized skew-tolerant histograms for geographic data objects

Lineage processing over correlated probabilistic databases

SecureBlox: customizable secure distributed data processing

Structured annotations of web queries

Optimizing content freshness of relations extracted from the web using keyword search

Towards proximity pattern mining in large graphs

Bed-tree: an all-purpose index structure for string similarity search based on edit distance

Overview of sciDB: large scale array storage, processing and analysis

Ricardo: integrating R and Hadoop

Extreme scale with full SQL language support in microsoft SQL Azure

OpenII: an open source information integration toolkit

Continuous analytics over discontinuous streams

HadoopDB in action: building real world applications

Symbiote: a Reconfigurable Logic Assisted Data Stream Management System (RLADSMS)

Exploring schema similarity at multiple resolutions

QRelX: generating meaningful queries that provide cardinality assurance

Mining knowledge from databases: an information network analysis approach

Database systems research on data mining

Information theory for data management

Enterprise information extraction: recent developments and open challenges

Crowds, clouds, and algorithms: exploring the human side of "big data" applications

Warehouse-scale Computing

How to ConQueR why-not questions

Sampling dirty data for matching attributes

GBLENDER: towards blending visual query formulation and query processing in graph databases

PODS: a new model and processing algorithms for uncertain data streams

Scalable architecture and query optimization fortransaction-time DBs with evolving schemas

Searching trajectories by locations: an efficiency study

Consistent query answers in inconsistent probabilistic databases

Fast sort on CPUs and GPUs: a case for bandwidth oblivious SIMD sort

Active knowledge: dynamically enriching RDF knowledge bases by web services

Finding maximal cliques in massive networks by H*-graph

Efficient parallel set-similarity joins using MapReduce

Positional update handling in column stores

Indexing multi-dimensional data in a cloud system

Logging every footstep: quantile summaries for the entire history

Evaluation of probabilistic threshold queries in MCDB

Differentially private aggregation of distributed time-series with transformation and encryption

On active learning of record matching packages

Feeding frenzy: selectively materializing users' event feeds

GAIA: graph classification using evolutionary computation

On indexing error-tolerant set containment

Integrating hadoop and parallel DBMs

PYMK: friend recommendation at myspace

Pay-as-you-go: an adaptive approach to provide full context-aware text search over document content

Google fusion tables: web-centered data management and collaboration

IBM infosphere streams for scalable, real-time, intelligent transportation services

Online aggregation and continuous query support in MapReduce

Interactive visual exploration of neighbor-based patterns in data streams

An automated, yet interactive and portable DB designer

Performing sound flash device measurements: some lessons from uFLIP

Call to order: a hierarchical browsing approach to eliciting users' preference

ERACER: a database approach for statistical inference and data cleaning

Computing label-constraint reachability in graph databases

Fast approximate correlation for massive time-series data

Data conflict resolution using trust mappings

Processing continuous join queries in sensor networks: a filtering approach

Threshold query optimization for uncertain data

Page-differential logging: an efficient and DBMS-independent approach for storing data into flash memory

Schema clustering and retrieval for multi-domain pay-as-you-go data integration systems

K-isomorphism: privacy preserving network publication against structural attacks

ParaTimer: a progress indicator for MapReduce DAGs

Durable top-k search in document archives

Low overhead concurrency control for partitioned main memory databases

Continuous sampling for online aggregation over multiple queries

K-nearest neighbor search for fuzzy objects

Non-homogeneous generalization in privacy preserving data publishing

I4E: interactive investigation of iterative information extraction

Constructing and exploring composite items

Finding maximum degrees in hidden bipartite graphs

Workload-aware storage layout for database systems

A comparison of join algorithms for log processing in MaPreduce

Forecasting high-dimensional data

Sedna: native XML database management system (internals overview)

Visual interfaces to data

SIE-OBI: a streaming information extraction platform for operational business intelligence

MapDupReducer: detecting near duplicates over massive datasets

TwitterMonitor: trend detection over the twitter stream

Midas: integrating public financial data

GDR: a system for guided data repair

Boosting spatial pruning: on optimal pruning of MBRs

Recsplorer: recommendation algorithms based on precedence mining

Pregel: a system for large-scale graph processing

An algorithmic approach to event summarization

Analyzing the energy efficiency of a database server

TACO: tunable approximate computation of outliers in wireless sensor networks

Probabilistic string similarity joins

Similarity search and locality sensitive hashing using ternary content addressable memories

Expressive and flexible access to web-extracted data: a keyword-based structured query language

Load-balanced query dissemination in privacy-aware online communities

The DataPath system: a data-centric analytic processing engine for large data warehouses

Ajax-based report pages as incrementally rendered views

Efficient querying and maintenance of network provenance at internet-scale

Histograms reloaded: the merits of bucket diversity

An optimal labeling scheme for workflow provenance using skeleton labels

Preserving privacy and fairness in peer-to-peer data integration

ONDUX: on-demand unsupervised learning for information extraction

Unbiased estimation of size and other aggregates over hidden web databases

Connected substructure similarity search

Querying data provenance

Data warehousing and analytics infrastructure at facebook

Optimizing schema-last tuple-store queries in graphd

Graphical XQuery in the aqualogic data services platform

Large graph processing in the cloud

Glacier: a query-to-hardware compiler

Worry-free database upgrades: automated model-driven evolution of schemas and complex mappings

DCUBE: discrimination discovery in databases

Exploratory keyword search on data graphs

US-SQL: managing uncertain schemata

iTuned: a tool for configuring and visualizing database parameters

S-OLAP: an OLAP system for analyzing sequence data

Integrating keyword search with multiple dimension tree views over a summary corpus data cube

PAROS: pareto optimal route selection

Pluggable personal data servers

ProgXe: progressive result generation framework for multi-criteria decision support queries

Query portals: dynamically generating portals for entity-oriented web queries

MoveMine: mining moving object databases

Mask: a system for privacy-preserving policy-based access to published content

XTaGe: a flexible XML collection generator

Creating and exploring web form repositories

PIQL: a performance insightful query language

SimDB: a similarity-aware database system

K*SQL: a unifying engine for sequence patterns and XML

DoCQS: a prototype system for supporting data-oriented content query

A demonstration of FlexPref: extensible preference evaluation inside the DBMS engine

Logging every footstep: quantile summaries for the entire history

Content Provider	ACM Digital Library
Author	Yi, Ke Sheng, Cheng Pei, Jian Li, Feifei Tao, Yufei
Abstract	Quantiles are a crucial type of order statistics in databases. Extensive research has been focused on maintaining a space-efficient structure for approximate quantile computation as the underlying dataset is updated. The existing solutions, however, are designed to support only the current, most-updated, snapshot of the dataset. Queries on the past versions of the data cannot be answered. This paper studies the problem of historical quantile search. The objective is to enable ε-approximate quantile retrieval on any snapshot of the dataset in history. The problem is very important in analyzing the evolution of a distribution, monitoring the quality of services, query optimization in temporal databases, and so on. We present the first formal results in the literature. First, we prove a novel theoretical lower bound on the space cost of supporting ε-approximate historical quantile queries. The bound reveals the fundamental difference between answering quantile queries about the past and those about the present time. Second, we propose a structure for finding ε-approximate historical quantiles, and show that it consumes more space than the lower bound by only a square-logarithmic factor. Extensive experiments demonstrate that in practice our technique performs much better than predicted by theory. In particular, the quantiles it returns are remarkably more accurate than the theoretical precision guarantee.
Starting Page	639
Ending Page	650
Page Count	12
File Format	PDF
ISBN	9781450300322
DOI	10.1145/1807167.1807237
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-06-06
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Lower bound Approximation Quantile
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