polytoken

Polytoken is a utility that handles the hashing of one or more arbitrary data dimensions, for use in database indexing and queries.

Usage

const polytoken = require('polytoken');

let longLatDimension = new polytoken.coreDimensions.LongLatDimension({
	step: {
		type: 'exponential',
		base: 0.001,  // Degrees of latitude/longitude
		multipler: 10,
		stepNum: 5
	}
});

let timeDimension = new polytoken.coreDimensions.TimeDimension({
	step: {
		type: 'exponential',
		base: 1000,  // Seconds
		multipler: 5,
		stepNum: 4
	}
});

let polytype = new polytoken.Polytype([ longLatDimension, timeDimension ]);

// Range to tokenize
let polygon = {
	type: 'Polygon',
	coordinates: [ [ [ 1, 1 ], [1, 2 ], [2, 2], [2, 1], [1, 1] ] ]
};
let timeRange = [ '2015-01-01', '2015-02-28' ];
let rangeTokens = polytype.getRangeTokens([ polygon, timeRange ]);
// Save rangeTokens on database object

// Point to tokenize
let point = [ 1.5, 1.6 ];
let time = '2015-01-05T00:05:35Z';
let pointTokens = polytype.getTokensForPoint(point, time);
// Use pointTokens to query against rangeTokens for matching database entries

// Do this to filter out returned database entries
let pointTuple = [ /* Point from query */, /* Time from query */ ];
let rangeTuples = [
	[ /* Polygon from document 0 */, /* Time range from document 0 */],
	/* ... */
];
rangeTuples = rangeTuples.filter((rangeTuple) => polytype.checkRangeInclusion(rangeTuple, pointTuple);

Glossary

• Dimension - A single 'type' of data. For example, the LongLat dimension handles GeoJSON data that represents data on a 2D geographic plane, and the Time dimension handles temporal data.
• Point - A single discrete point on the dimension. This would be a longitute / latitude pair for LongLat, and a date for Time.
• Range - A specification of a (usually infinite) set of points on a dimension. This is a Polygon or MultiPolygon object for LongLat, and a start and end time pairing for Time.
• Polytype - A class that combines multiple dimensions together.
• Token - A string that represents a specific range for a dimension.
• Polytoken - A combination of tokens from multiple dimensions.

Principles

Polytoken is designed to be a geohashing library extensible into multiple and arbitrary dimensions. When only a single LongLat dimension is passed into the Polytype, it will act as a simple geohasher. If both a LongLat and Time dimension are passed, it can hash data that takes place over both an area and range of time (for example, a parade). The Dimension class can also be extended to create new dimensions for a specific purpose.

The options argument to each Dimension specifies how tokens will be generated. Usually, an exponentially increasing range of token sizes is desired, and the fields under step specify how this is generated. An example object:

{
	step: {
		type: 'exponential',
		base: 0.001,  // The smallest token size
		multipler: 10 // Each token size will be this many times larger than the previous one
		stepNum: 5 // The total number of token sizes
	}
}

These parameters should be chosen carefully. Smaller values for multiplier and larger values for stepNum will yield greater accuracy in token generation, at the expense of more tokens being generated by getTokensForPoint, which will linearly increase the execution times of queries.