NDLI: Space efficient mining of multigraph 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

Space efficient mining of multigraph streams

Content Provider	ACM Digital Library
Author	Cormode, Graham Muthukrishnan, S.
Abstract	The challenge of monitoring massive amounts of data generated by communication networks has led to the interest in data stream processing. We study streams of edges in massive communication multigraphs, defined by (source, destination) pairs. The goal is to compute properties of the underlying graph while using small space (much smaller than the number of communicants), and to avoid bias introduced because some edges may appear many times, while others are seen only once. We give results for three fundamental problems on multigraph degree sequences: estimating frequency moments of degrees, finding the heavy hitter degrees, and computing range sums of degree values. In all cases we are able to show space bounds for our summarizing algorithms that are significantly smaller than storing complete information. We use a variety of data stream methods: sketches, sampling, hashing and distinct counting, but a common feature is that we use cascaded summaries: nesting multiple estimation techniques within one another. In our experimental study, we see that such summaries are highly effective, enabling massive multigraph streams to be effectively summarized to answer queries of interest with high accuracy using only a small amount of space.
Starting Page	271
Ending Page	282
Page Count	12
File Format	PDF
ISBN	1595930620
DOI	10.1145/1065167.1065201
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

Abstract space efficient mining of multigraph streams ∗.

Space efficient mining of multigraph streams

Efficient Mining of High Utility Itemsets on Data Streams Efficient Mining of High Utility Itemsets on Data Streams

Efficient algorithms for stream mining of constrained frequent patterns in a limited memory environment

Efficient frequent pattern mining over data streams

Enhanced situation space mining for data streams

Memory efficient subspace clustering for online data streams

DSWFP: Efficient mining of weighted frequent pattern over data streams

Efficient decision tree construction for mining time-varying data streams

Space efficient mining of multigraph streams

Similar Documents

Abstract space efficient mining of multigraph streams ∗.

Space efficient mining of multigraph streams

Efficient Mining of High Utility Itemsets on Data Streams Efficient Mining of High Utility Itemsets on Data Streams

Efficient algorithms for stream mining of constrained frequent patterns in a limited memory environment

Efficient frequent pattern mining over data streams

Enhanced situation space mining for data streams

Memory efficient subspace clustering for online data streams

DSWFP: Efficient mining of weighted frequent pattern over data streams

Efficient decision tree construction for mining time-varying data streams

Space efficient mining of multigraph streams