NDLI: Join-distinct aggregate estimation over update streams

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

Context-sensitive program analysis as database queries

XML data exchange: consistency and query answering

Schema mappings, data exchange, and metadata management

On the complexity of division and set joins in the relational algebra

Security analysis of cryptographically controlled access to XML documents

Computing cores for data exchange: new algorithms and practical solutions

Multi-structural databases

Buffering in query evaluation over XML streams

Operator placement for in-network stream query processing

XML type checking with macro tree transducers

Models and methods for privacy-preserving data publishing and analysis: invited tutorial

Estimating arbitrary subset sums with few probes

Differential constraints

XPath satisfiability in the presence of DTDs

On the complexity of nonrecursive XQuery and functional query languages on complex values

Simulatable auditing

Peer data exchange

A divide-and-merge methodology for clustering

Histograms revisited: when are histograms the best approximation method for aggregates over joins?

Join-distinct aggregate estimation over update streams

Regular rewriting of active XML and unambiguity

Diagnosis of asynchronous discrete event systems: datalog to the rescue!

Deciding well-definedness of XQuery fragments

An incremental algorithm for computing ranked full disjunctions

Practical privacy: the SuLQ framework

Composition of mappings given by embedded dependencies

Allocating isolation levels to transactions

Lower bounds for sorting with few random accesses to external memory

Space efficient mining of multigraph streams

Determining source contribution in integration systems

Space complexity of hierarchical heavy hitters in multi-dimensional data streams

Relative risk and odds ratio: a data mining perspective

Views and queries: determinacy and rewriting

Privacy-enhancing k-anonymization of customer data

Join-distinct aggregate estimation over update streams

Content Provider	ACM Digital Library
Author	Garofalakis, Minos Rastogi, Rajeev Kumar, Amit Ganguly, Sumit
Abstract	There is growing interest in algorithms for processing andquerying continuous data streams (i.e., data that is seenonly once in a fixed order) with limited memory resources.Providing (perhaps approximate) answers to queries over suchstreams is a crucial requirement for many application environments;examples include large IP network installations where performancedata from different parts of the network needs to be continuouslycollected and analyzed.The ability to estimate the number of distinct (sub)tuples inthe result of a join operation correlating two data streams (i.e.,the cardinality of a projection with duplicate elimination over ajoin) is an important requirement for several data-analysisscenarios. For instance, to enable real-time traffic analysis andload balancing, a network-monitoring application may need toestimate the number of distinct (source,destination) IP-address pairs occurring in the stream of IP packetsobserved by router R1,where the source address is also seen in packets routed through adifferent router R2.Earlier work has presented solutions to the individual problems ofdistinct counting and join-size estimation (without duplicateelimination) over streams. These solutions, however, arefundamentally different and extending or combining them to handleour more complex "Join-Distinct" estimation problem is far fromobvious. In this paper, we propose the firstspace-efficient algorithmic solution to the general Join-Distinctestimation problem over continuous data streams (our techniques canactually handle general update streamscomprising tuple deletions as well as insertions). Our estimatorsare probabilistic in nature and rely on novel algorithms forbuilding and combining a new class of hash-based synopses (termed"JD sketches") for individual update streams. Wedemonstrate that our algorithms can provide low error,high-confidence Join-Distinct estimates using only small space andsmall processing time per update. In fact, we present lower boundsshowing that the space usage of our estimators is within smallfactors of the best possible for the Join-Distinct problem.Preliminary experimental results verify the effectiveness of ourapproach.
Starting Page	259
Ending Page	270
Page Count	12
File Format	PDF
ISBN	1595930620
DOI	10.1145/1065167.1065200
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-06-13
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

Join-Distinct aggregate estimation over update streams (2005)

Join-Distinct aggregate estimation over update streams (2005)

Approximate join processing over data streams

Window join approximation over data streams with importance semantics

Data Streams Join Aggregate Algorithms Based on Compound Sliding Window

Safety guarantee of continuous join queries over punctuated data streams

Processing complex aggregate queries over data streams

Probabilistic aggregate skyline join queries: skylines with aggregate operations over existentially uncertain relations

Adaptive optimization of join trees for multi-join queries over sensor streams.

Join-distinct aggregate estimation over update streams

Similar Documents

Join-Distinct aggregate estimation over update streams (2005)

Join-Distinct aggregate estimation over update streams (2005)

Approximate join processing over data streams

Window join approximation over data streams with importance semantics

Data Streams Join Aggregate Algorithms Based on Compound Sliding Window

Safety guarantee of continuous join queries over punctuated data streams

Processing complex aggregate queries over data streams

Probabilistic aggregate skyline join queries: skylines with aggregate operations over existentially uncertain relations

Adaptive optimization of join trees for multi-join queries over sensor streams.

Join-distinct aggregate estimation over update streams