javascript implementation of Dunning's T-Digest for streaming quantile approximation. 

javascript implementation of Dunning's T-Digest for streaming quantile approximation

welch

tdigest

Error

Ignore

Warn

License

Maintenance

Miscellaneous

Quality

Supply chain risk

Vulnerability

Admins only

Organization members

Dashboard

<upgradeLink>Upgrade</upgradeLink> to access this feature

About

Blog

Socket CLI

Customers

Socket Dependency Search

Docs

Socket for GitHub

Love

Impersonation Mode Active

Update your browser to the latest version for the best experience.

Your web browser is outdated

Use another browser for the best experience.

Your web browser is unsupported

{{count, number}} commits last two months

{{count, number}} critical severity alert

{{count, number}} critical severity alerts

{{count, number}} dependency vulnerability

{{count, number}} dependency vulnerabilities

{{count, number}} development dependencies

{{count, number}} transitive dependencies

{{count, number}} version published last month

{{count, number}} versions published last month

{{count, number}} version published in last two months

{{count, number}} versions published in last two months

{{count, number}} version published last week

{{count, number}} versions published last week

{{count, number}} version published last year

{{count, number}} versions published last year

Socket undergoes annual SOC2 Type II audits. Socket customers can request a copy of the full SOC2 Type II report.

Allows organization owners and admins to access detailed records of actions taken by members of their organization, complete with timestamps.

Prevent compromised packages from infiltrating your supply chain by monitoring for changes in real-time.

Join our Discord community to get help from Socket engineers and other Socket users.

Compare millions of open source packages on socket.dev

Detect malicious code and risky behavior (e.g. network) in your dependencies using "deep package inspection"

All data is encrypted in transit and at rest using industry standard encryption algorithms.

Get a dedicated Socket account manager and access to Socket’s Customer Success team.

Get dedicated support from Socket engineers via email and Slack.

"Shift left" with the Socket Chrome extension and give intervene early, before developers choose risky or low quality dependencies.

Catch developers using risky dependencies and give them a "speed bump" to encourage good behavior

Install the Socket GitHub app to receive real-time dependency scanning and reports with every pull request.

Integrate Socket into your GitHub SCM to prevent risky dependencies from being installed.

Socket scans for vulnerabilities in your dependencies, including CVEs, security advisories, and more.

Socket supports dependencies in many languages, with most popular ecosystems coming in 2024. We've got you covered no matter what languages you use.

Enforce license policies across your organization

Receive a Microsoft Teams message to the channel of your choice anytime Socket runs a new analysis, has a new finding, or a policy has changed.

Get help migrating from Socket's free plan to Socket's paid plans.

Run Socket on-premises or in your own cloud environment.

Query for any dependency (at any version) across your entire organization

Integrate Socket into your CI/CD pipeline to prevent risky dependencies from being deployed to production.

Analyze an entire project to find supply chain risks

Tag projects to organize and filter your projects

Restrict access based on the roles of individual users within an organization.

Receive a Slack message to the channel of your choice anytime Socket runs a new analysis, has a new finding, or a policy has changed.

Socket is SOC2 Type II compliant and undergoes annual audits.

The Socket CLI allows teams to prevent risky dependencies from being installed, and to get dependency insights from the command line.

Socket supports SAML SSO for single sign-on and identity management.

Integrate Socket into your VS Code IDE to prevent risky dependencies from being installed.

Get a POST request anytime Socket runs a new analysis, has a new finding, or a policy has changed.

Socket will analyzed your SBOMs up to a maximum number of dependencies.

API that allows you to analyze a project, lookup package scores and alerts, and more.

Create API tokens to authenticate with the Socket API and CLI.

The number of developers in your team. A developer is someone who made a commit to your organization's repositories scanned by Socket in the past month.

Use Socket to protect your private repositories.

Socket is always free for open source projects.

Socket retains all reporting data for 3 months, 1 year, or a custom term of your choice.

Access the threat feed that powers Socket.

Unlimited scale, self-hosting, and priority support for large teams.

For open-source projects, individuals, and small teams.

For growing teams with enhanced scale, security, and support.

There is a package with a similar name that is downloaded much more often.

There are packages with similar names that are downloaded much more often.

This may not be the package you want!

Instance

Alert Locations

Package

The {{ecosystem}} package {{- packageName}} receives a total of <strong>{{numWeeklyDownloadCount, number}}</strong> weekly downloads. As such, {{- packageName}} popularity was classified as <strong>{{popularity}}</strong>.

Is {{- packageName}} popular?

Is {{- packageName}} safe to use?

Is {{- packageName}} well maintained?

What is {{- packageName}}?

{{packageDescription}}Version: {{versionString}} was published by {{publisherName}}. Start using Socket to analyze {{- packageName}} and its {{dependencyCount, number}} dependencies to secure your app from supply chain attacks.

Sorry, it seems this package was removed from the registry

Package was removed

This package version has been unpublished, mostly likely due to security reasons

Package version was removed

Provide a detailed description of the malware...

Socket fights vulnerabilities and provides visibility, defense-in-depth, and proactive supply chain protection for JavaScript, Python, and Go dependencies.

Socket - Secure your dependencies. Ship with confidence.

Compare versions

{{- packageName}} - npm Package Compare versions

  "description": "javascript implementation of Dunning's T-Digest for streaming quantile approximation",

    "url": "https://github.com/welch/tdigest.git"

  "author": "Will Welch <welch@quietplease.com> (http://quietplease.com/)",

    "url": "https://github.com/welch/tdigest/issues"

  "homepage": "https://github.com/welch/tdigest",

[![Build Status][travis-image]][travis-url] [![NPM version][npm-image]][npm-url] [![NPM download][download-image]][npm-url]

Javascript implementation of Dunning's T-Digest for streaming quantile approximation

The T-Digest is a data structure and algorithm for constructing an

approximate distribution for a collection of real numbers presented as a

stream. The algorithm makes no guarantees, but behaves well enough in

practice that implementations have been included in Apache Mahout and

ElasticSearch for computing summaries and approximate order

For an overview of T-Digest's behavior, see Davidson-Pilon's

[blog post](http://dataorigami.net/blogs/napkin-folding/19055451-percentile-and-quantile-estimation-of-big-data-the-t-digest) regarding a python implementation. For more details,

there are the [tdigest paper](https://github.com/tdunning/t-digest/blob/master/docs/t-digest-paper/histo.pdf) and [reference implementation](https://github.com/tdunning/t-digest) (Java).

This javascript implementation is based on a reading of the paper,

with some boundary and performance tweaks.

Updated the bintree dependency to 1.0.2 to pick up its licencing declaration

1. percentile on an empty digest returns *undefined* or array of *undefined*

3. bugfix for discrete percentile and p_rank, make boundary conditions

Discrete mode: when a TDigest is created with delta=false, the sample

distribution is treated as discrete. TDigest behavior is disabled,

differing samples are never merged (they needn't even be numeric), and

percentiles are reported as nearest exact data values rather than

Digest: distribution digest structure. Starts in exact histogram

(discrete) mode, remains in exact mode for reasonable numbers of

distinct values as sample size inreases, and automatically switches to

TDigest mode for large samples that appear to be from a continuous

Renamed quantile() -> p_rank(), Percentile Rank.

percentile() and p_rank() now accept arrays or singleton arguments.

A `grunt dist` task has been added to create a UMD-wrapped version of tdigest

and dependencies for importing as a standalone module in client-side javascript.

* pushing an array no longer triggers compression

var TDigest = require('tdigest').TDigest;

console.log("median ~ "+td.percentile(0.5));

See also [example.js](https://github.com/welch/tdigest/blob/master/example.js) in this package.

The `grunt dist` task has been configured to generate

a self-contained [UMD-wrapped](https://github.com/umdjs/umd) version of tdigest in dist/tdigest.js.

See also [example.html](https://github.com/welch/tdigest/blob/master/example.html) in this package.

`bintrees`: [https://www.npmjs.com/package/bintrees](https://www.npmjs.com/package/bintrees)

[travis-image]: https://travis-ci.org/welch/tdigest.svg?branch=master

[travis-url]: https://travis-ci.org/welch/tdigest

[npm-image]: http://img.shields.io/npm/v/tdigest.svg

[download-image]: http://img.shields.io/npm/dm/tdigest.svg

[npm-url]: https://www.npmjs.org/package/tdigest

// approximate distribution percentiles from a stream of reals

    // delta is the compression factor, the max fraction of mass that

    // can be owned by one centroid (bigger, up to 1.0, means more

    // compression). delta=false switches off TDigest behavior and treats

    // the distribution as discrete, with no merging and exact values

    // K is a size threshold that triggers recompression as the TDigest

    // grows during input.  (Set it to 0 to disable automatic recompression)

    // CX specifies how often to update cached cumulative totals used

    // for quantile estimation during ingest (see cumulate()).  Set to

    // 0 to use exact quantiles for each new point.

    this.CX = (CX === undefined) ? 1.1 : CX;

    this.centroids = new RBTree(compare_centroid_means);

TDigest.prototype.toArray = function(everything) {

    // return {mean,n} of centroids as an array ordered by mean.

        this._cumulate(true); // be sure cumns are exact

        this.centroids.each(function(c) { result.push(c); });

        this.centroids.each(function(c) { result.push({mean:c.mean, n:c.n}); });

    var approx = (this.discrete) ? "exact " : "approximating ";

    var s = [approx + this.n + " samples using " + this.size() + " centroids",

             "min = "+this.percentile(0),

             "Q1  = "+this.percentile(0.25),

             "Q2  = "+this.percentile(0.5),

             "Q3  = "+this.percentile(0.75),

             "max = "+this.percentile(1.0)];

    return (a.mean > b.mean) ? 1 : (a.mean < b.mean) ? -1 : 0;

function compare_centroid_mean_cumns(a, b) {

TDigest.prototype.push = function(x, n) {

    // incorporate value or array of values x, having count n into the

    for (var i = 0 ; i < x.length ; i++) {

TDigest.prototype.push_centroid = function(c) {

    // incorporate centroid or array of centroids c

    for (var i = 0 ; i < c.length ; i++) {

        c.mean_cumn = cumn + c.n / 2; // half of n at the mean

TDigest.prototype.find_nearest = function(x) {

    // find the centroid closest to x. The assumption of

    // unique means and a unique nearest centroid departs from the

    var iter = this.centroids.lowerBound({mean:x}); // x <= iter || iter==null

    var c = (iter.data() === null) ? iter.prev() : iter.data();

        return c; // c is either x or a neighbor (discrete: no distance func)

    if (prev && Math.abs(prev.mean - x) < Math.abs(c.mean - x)) {

TDigest.prototype._new_centroid = function(x, n, cumn) {

    // create and insert a new centroid into the digest (don't update

TDigest.prototype._addweight = function(nearest, x, n) {

    // add weight at location x to nearest centroid.  adding x to

    // nearest will not shift its relative position in the tree and

        nearest.mean += n * (x - nearest.mean) / (nearest.n + n);

TDigest.prototype._digest = function(x, n) {

    // incorporate value x, having count n into the TDigest.

        // accumulate exact matches into the centroid without

		{
		"name": "tdigest",
		"version": "0.1.1",
		"version": "0.1.2",
		"description": "javascript implementation of Dunning's T-Digest for streaming quantile approximation",
		@@ -27,3 +27,3 @@ "main": "tdigest.js",
		"dependencies": {
		"bintrees": "1.0.1"
		"bintrees": "1.0.2"
		},
		@@ -30,0 +30,0 @@ "devDependencies": {

		@@ -20,2 +20,6 @@ tdigest

		changes in 0.1.2:

		Updated the bintree dependency to 1.0.2 to pick up its licencing declaration

		changes in 0.1.1:
		@@ -22,0 +26,0 @@

		@@ -116,3 +116,2 @@ //
		var cumn = 0;
		var self = this;
		this.centroids.each(function(c) {
		@@ -299,4 +298,2 @@ c.mean_cumn = cumn + c.n / 2; // half of n at the mean
		this._cumulate(true); // be sure cumns are exact
		var min = this.centroids.min();
		var max = this.centroids.max();
		var h = this.n * p;
		@@ -303,0 +300,0 @@ var bound = this.bound_mean_cumn(h);

Improved metrics

Worsened metrics

Dependency changes