NDLI: Flexible approximate counting

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

Aggregates and priorities in P2P data management systems

Databases on the web: national web domain survey

A family of graph-theory-driven algorithms for managing complex probabilistic graph data efficiently

Scalable queries for large datasets using cloud computing: a case study

An efficient local region and clustering-based ensemble system for intrusion detection

Addressing resource usage in stream processing systems: sizing window effect

Trajectory data analysis using complex networks

A new architectural paradigm for content-based web applications: Borè

A landmark-model based system for mining frequent patterns from uncertain data streams

A predictable storage model for scalable parallel DW

Efficient incremental breadth-depth XML event mining

Using an inference mechanism for helping the data integration

FB-tree: a $B^{+}-tree$ for flash-based SSDs

Semantics-enabled web APIs selection patterns

Query language constructs for provenance

Union rewritings for XPath fragments

Top-k query processing for combinatorial objects using Euclidean distance

Mining semantic data for solving first-rater and cold-start problems in recommender systems

M-TOP: multi-target operator placement of query graphs for data streams

Query answering on trajectory cuboids using prime numbers encodings

A data masking technique for data warehouses

A statically typed query language for property graphs

A clustering-based visualization of colocation patterns

Black-box determination of cost models' parameters for federated stream-processing systems

Scrubbing query results from probabilistic databases

Flexible approximate counting

Online outlier detection for data streams

Query optimization using column statistics in hive

Boosting tuple propagation in multi-relational classification

Answering complex structured queries over the deep web

SciQL: bridging the gap between science and relational DBMS

Cache-conscious data placement in an in-memory key-value store

Extend core UDF framework for GPU-enabled analytical query evaluation

Chimera: data sharing flexibility, shared nothing simplicity

ParallelGDB: a parallel graph database based on cache specialization

An approach towards automatic workflow composition through information retrieval

Flexible approximate counting

Content Provider	ACM Digital Library
Author	Mitchell, Scott A. Day, David M.
Abstract	Approximate counting [18] is useful for data stream and database summarization. It can help in many settings that allow only one pass over the data, want low memory usage, and can accept some relative error. Approximate counters use fewer bits; we focus on 8-bits but our results are general. These small counters represent a sparse sequence of larger numbers. Counters are incremented probabilistically based on the spacing between the numbers they represent. Our contributions are a customized distribution of counter values and efficient strategies for deciding when to increment them. At run-time, users may independently select the spacing (accuracy) of the approximate counter for small, medium, and large values. We allow the user to select the maximum number to count up to, and our algorithm will select the exponential base of the spacing. These provide additional flexibility over both classic and Csűrös's [4] floating-point approximate counting. These provide additional structure, a useful schema for users, over Kruskal and Greenberg [13]. We describe two new and efficient strategies for incrementing approximate counters: use a deterministic countdown or sample from a geometric distribution. In Csűrös all increments are powers of two, so random bits rather than full random numbers can be used. We also provide the option to use powers-of-two but retain flexibility. We show when each strategy is fastest in our implementation.
Starting Page	233
Ending Page	239
Page Count	7
File Format	PDF
ISBN	9781450306270
DOI	10.1145/2076623.2076655
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-09-21
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Random number generator Data stream summarization Implementation Approximate counting
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

A New Type of Random Number Generator for Software Implementation

A Quasigroup Based Random Number Generator for Resource Constrained Environments

Approximate counting of inversions in a data stream

Chaos-based pseudo-random number generators and chip implementation.

Testing parallel random number generators (1999)

Approximate counting of cycles in streams ⋆.

A simple omnet++ queuing experiment using different random number generators (2002).

Pseudo Random Bit Generator using Logistic and Bernoulli Maps

Testing Parallel Random Number Generators

Flexible approximate counting

Similar Documents

A New Type of Random Number Generator for Software Implementation

A Quasigroup Based Random Number Generator for Resource Constrained Environments

Approximate counting of inversions in a data stream

Chaos-based pseudo-random number generators and chip implementation.

Testing parallel random number generators (1999)

Approximate counting of cycles in streams ⋆.

A simple omnet++ queuing experiment using different random number generators (2002).

Pseudo Random Bit Generator using Logistic and Bernoulli Maps

Testing Parallel Random Number Generators

Flexible approximate counting