z-tree

README.md

dv-z-tree

Z-Tree spatial ordering interactively visualized

Screenshot

Left side shows, for different tile sizes, which tiles contain the mouse pointer respectively. Number in that cell is index in z-ordering. Each tile is guaranteed to be allocated in a continuous memory space by storing the matrix with z-ordering.

Right side shows the memory access pattern of convolutional operation on either z-ordering (top) or C-style row-oriented (bottom) 2D array.

• Blue line - number of times (y axis) that the memory address (x axis) is visited.
• Red line - number of times that different sizes of memory space is jumped across.

Z ordering can also apply to multidimensional arrays for better spatial coherence in many frequently used data access patterns. e.g. row/column scanning, convolutional operation, even diagonal access if you are doing some algorithm like dynamic programming.

In this project a "slow" version (which also works for any arbitrary spatial ordering like z-ordering with simple change of kernel function), and a "fast" version (which transforms between 2d coordinates and z-indices via simple bit operation) are implemented.

Conclusion

As another counterintuitively genius way of storing a matrix, Z-ordering can be good for many regular data access patterns with little performance cost. It's certainly a compromise between row and column oriented ordering. It is also a kind of useful adaptive tiling technique.

Related links

• Damn Cool Algorithms: Spatial indexing with Quadtrees and Hilbert Curves
• Data visualization: D3 API

d3svg.css

.row{
    position: relative;
}

.row>div{
    position: absolute;
}

#hist{
    top: 0px;
    left: 730px;
}

#hist2{
    top: 370px;
    left: 730px;
}

.line {
    fill: none;
    stroke-width: 1.5px;
}

.line0 {
    stroke: steelblue;
}

.line1 {
    stroke: #f54242;
}

.axis--x text {
    font: 10px sans-serif;
}

.axis--y text {
    font: oblique 15px Georgia, serif;
}

.axis path, .axis line {
    fill: none;
    stroke: #000;
    shape-rendering: crispEdges;
}

grid.js

var ztree = ztree || {};
var d3 = d3 || {};
var hist = hist || {};

var transformer = new ztree.Transformation(5);

var color_scale = d3.scaleLinear()
    .domain([0, 4])
    .range(["white", "steelblue"])
    .interpolate(d3.interpolateLab);
    
function clearGrid() {
	d3.select("#grid").selectAll(".row").selectAll(".square").style("fill", "#fff");
}

function gridData() {
	var data = new Array();
	var xpos = 1; //starting xpos and ypos at 1 so the stroke will show when we make the grid below
	var ypos = 1;
	var width = 45;
	var height = 45;
	var click = 0;
	
	// iterate for rows	
	for (var row = 0; row < 16; row++) {
		data.push( new Array() );
		
		// iterate for cells/columns inside rows
		for (var column = 0; column < 16; column++) {
			data[row].push({
				x: xpos,
				y: ypos,
				width: width,
				height: height,
				click: click,
				i: row, j: column
			})
			// increment the x position. I.e. move it over by 50 (width variable)
			xpos += width;
		}
		// reset the x position after a row is complete
		xpos = 1;
		// increment the y position for the next row. Move it down 50 (height variable)
		ypos += height;	
	}
	return data;
}

function highlightBlock(highlight, color){
	var row_0 = highlight[0], row_m = highlight[2],
		col_0 = highlight[1], col_m = highlight[3];
	d3.select("#grid").selectAll(".row").filter(function(d, i){
		return i>=row_0 && i<row_m ? this : null;
	}).selectAll(".square").filter(function(d, j){
		return j>=col_0 && j<col_m ? this : null;
	}).style("fill", color);
}

var gridData = gridData();

var grid = d3.select("#grid")
	.append("svg")
	.attr("width","730px")
	.attr("height","730px");
	
var row = grid.selectAll(".row")
	.data(gridData)
	.enter().append("g")
	.attr("class", "row");
	
var column = row.selectAll(".square")
	.data(function(d) { return d; })
	.enter().append("rect")
	.attr("class","square")
	.attr("x", function(d) { return d.x; })
	.attr("y", function(d) { return d.y; })
	.attr("width", function(d) { return d.width; })
	.attr("height", function(d) { return d.height; })
	.style("fill", "#fff")
	.style("stroke", "#000")
	.style("stroke-width", ".5px")
	.on('click', function(d) {
    //   d.click ++;
    //   if ((d.click)%4 == 0 ) { d3.select(this).style("fill","#fff"); }
	   //if ((d.click)%4 == 1 ) { d3.select(this).style("fill","#2C93E8"); }
	   //if ((d.click)%4 == 2 ) { d3.select(this).style("fill","#F56C4E"); }
	   //if ((d.click)%4 == 3 ) { d3.select(this).style("fill","#838690"); }
    })
    .on('mouseover', function(d) {
        clearGrid();
        var z_order = transformer.transform(d.i, d.j);
        var hierarchy = transformer.getHierarchy(z_order);
        for(var level = hierarchy.length-1; level>=0;--level)
        	highlightBlock(hierarchy[level].highlight, color_scale(hierarchy.length-level));
        current_label.text(z_order)
	        .attr("x", d.x+d.width/2).attr("y", d.y+d.height/2);
	    hist.visit_z_order(z_order);
	    hist.visit_row_oriented(d.i*16+d.j);
    });

var current_label = row.append("svg:text")
	.attr("text-anchor","middle")
	.attr("dy",".25em")
	.style("fill", "rgba(25, 25, 25, 0.82)")
	.style("font", '1.8em impact, georgia, times, serif')
	.style("text-rendering", "optimizeLegibility");

hist.js

var hist = hist || {};
var d3 = d3 || {};
var $ = $ || {};

function mk_hist(id){
    var superscript = "⁰¹²³⁴⁵⁶⁷⁸⁹",
        formatPower = function(d) { return (d + "").split("").map(function(c) { return superscript[c]; }).join(""); };
    
    var margin = {top: 10, right: 10, bottom: 40.5, left: 40.5},
        width = 600 - margin.left - margin.right,
        height = 340 - margin.top - margin.bottom;
    
    var x = d3.scaleLinear()
        .domain([0, 300])
        .range([0, width]);
    
    var y = d3.scaleLog()
        .base(Math.E)
        .domain([Math.exp(0), Math.exp(9)])
        .range([height, 0]);
    
    var xAxis = d3.axisBottom(x);
    
    var yAxis = d3.axisLeft(y)
        .tickFormat(function(d) { return "e" + formatPower(Math.round(Math.log(d))); });
    
    var line = d3.line()
        .x(function(d) { return x(d[0]); })
        .y(function(d) { return y(d[1]); });
    
    var svg = d3.select(id).append("svg")
        .attr("width", width + margin.left + margin.right)
        .attr("height", height + margin.top + margin.bottom)
        .append("g")
        .attr("transform", "translate(" + margin.left + "," + margin.top + ")");
    
    svg.append("g")
        .attr("class", "axis axis--y")
        .attr("transform", "translate(-10,0)")
        .call(yAxis);
    
    svg.append("g")
        .attr("class", "axis axis--x")
        .attr("transform", "translate(0," + (height + 10) + ")")
        .call(xAxis);
        
    var z0 = svg.append("path")
        .datum(d3.range(300).map(function(x) { return [x, 1]; }))
        .attr("class", "line line0")
        .attr("d", line);
        
    var z1 = svg.append("path")
        .datum(d3.range(300).map(function(x) { return [x, 1]; }))
        .attr("class", "line line1")
        .attr("d", line);
        
    function updatePath(path, z){
        ++path.datum()[z][1];
        path.transition().attr("d", line);
    }
    
    var _pre_z = 0;
    
    return function(z){
        updatePath(z0, z);
        updatePath(z1, Math.abs(z-_pre_z));
        _pre_z = z;
    };
}

hist.visit_z_order = mk_hist("#hist");
hist.visit_row_oriented = mk_hist("#hist2");

index.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
	<script src="https://d3js.org/d3.v4.min.js"></script>
	<script src="//code.jquery.com/jquery-3.1.1.min.js" integrity="sha256-hVVnYaiADRTO2PzUGmuLJr8BLUSjGIZsDYGmIJLv2b8=" crossorigin="anonymous"></script>
	<link rel="stylesheet" href="d3svg.css">
</head>
<body>
<div class="container-fluid">
    <div class="row">
        <div id="grid" class="span4"></div>
        <div id="hist" class="span4"></div>
        <div id="hist2" class="span4"></div>
    </div>
</div>
<script src="ztree.js" type="text/javascript"></script>
<script src="grid.js" type="text/javascript"></script>
<script src="hist.js" type="text/javascript"></script>
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css" integrity="sha384-BVYiiSIFeK1dGmJRAkycuHAHRg32OmUcww7on3RYdg4Va+PmSTsz/K68vbdEjh4u" crossorigin="anonymous">
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap-theme.min.css" integrity="sha384-rHyoN1iRsVXV4nD0JutlnGaslCJuC7uwjduW9SVrLvRYooPp2bWYgmgJQIXwl/Sp" crossorigin="anonymous">
<script src="//maxcdn.bootstrapcdn.com/bootstrap/3.3.7/js/bootstrap.min.js" integrity="sha384-Tc5IQib027qvyjSMfHjOMaLkfuWVxZxUPnCJA7l2mCWNIpG9mGCD8wGNIcPD7Txa" crossorigin="anonymous"></script>
<script type="text/javascript" src="//cdn.rawgit.com/aleozlx/a8483cfd882f184db00fec9ca8c32eec/raw/75e6db60b74aea7690936e68ab24e300a0a5d972/ga.js" integrity="sha384-XpTms6exzm5d+cDUXt8PmJI+TXm8fR5StCiIjEmWsWOJY2hzzkd1OgxyrTcCZjI9" crossorigin="anonymous"></script>
</body>
</html>

LICENSE

MIT License

Copyright (c) 2016 Alex Yang

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

thumbnail.png

ztree.js

var ztree = ztree || {};

ztree.Transformation = function(level, kernel){
    this.dim = level - 1;
    if(kernel == undefined && level <= 5)
        ztree.useFastZIndexing(this);
    else{
        this.a = new Array(this.dim);
        this.a2 = new Array(this.dim);
        for(var i=0, t=1;i<this.dim;++i, t<<=1){
            this.a[i]=t; this.a2[i]=t*t;
        }
        if(kernel){ this.kernel = kernel[0]; this.inv = kernel[1]; }
        else{
            this.kernel = function(i, j){ return i+i+j; };
            this.inv = function(z){ return [[0,0],[0,1],[1,0],[1,1]][z]; };
        }
    }
};

ztree.Transformation.prototype.transform = function(i, j){
    var bi = new Array(this.dim), bj = new Array(this.dim), k;
    for(k=this.dim;k--;){
        var t = this.a[k];
        if(i-t>=0){ bi[k]=1; i-=t; }
        else { bi[k]=0; }
        if(j-t>=0){ bj[k]=1; j-=t; }
        else { bj[k]=0; }
    }
    var s = 0;
    for(k=0;k<this.dim;k++)
        s+=this.a2[k]*this.kernel(bi[k], bj[k]);
    return s;
};

ztree.Transformation.prototype.inverse = function(z){
    var b = new Array(this.dim), k;
    for(k=this.dim;k--;){
        var t = this.a2[k];
        b[k] = Math.floor(z / t);
        z %= t;
    }
    var si = 0, sj = 0;
    for(k=0;k<this.dim;k++){
        var v = this.inv(b[k]);
        if(v[0]) si+=this.a[k];
        if(v[1]) sj+=this.a[k];
    }
    return [si, sj];
};

ztree.Transformation.prototype.getHierarchy = function(z){
    var b = new Array(this.dim);
    for(var k=this.dim;k--;){
        var t = this.a2[k];
        var bz = Math.floor(z / t);
        var bij = this.inv(bz);
        b[k] = {
            highlight: [bij[0], bij[1], bij[0]+t, bij[1]+t], 
            z_order: bz, 
            level: k
        };
        z %= t;
    }
    // for(var k=0;k<)
    return b;
};

ztree.getZHierarchy = function(z, level){
    var b = new Array(level - 1), k;
    for(k = level - 1;k--;){
        var a = (1<<k), a2 = a*a;
        var bz = Math.floor(z / a2);
        var bij = [[0,0],[0,1],[1,0],[1,1]][bz];
        b[k] = {
            highlight: [bij[0]*a, bij[1]*a, bij[0]*a+a, bij[1]*a+a], 
            z_order: bz, 
            level: k
        };
        z %= a2;
    }
    for(k=b.length-2;k>=0;--k){
        b[k].highlight[0]+=b[k+1].highlight[0];
        b[k].highlight[1]+=b[k+1].highlight[1];
        b[k].highlight[2]+=b[k+1].highlight[0];
        b[k].highlight[3]+=b[k+1].highlight[1];
    }
    return b;
};

ztree.Transformation.prototype.validate = function(){
    var ct=0, N=this.dim*this.dim;
    for(var z=0;z<N;z++) {
        var t=this.inverse(z);
        if(this.transform(t[0], t[1])==z) ++ct;
    }
    return {accuracy: ct / N, isValid: ct / N==1};
};

ztree.useFastZIndexing = function(transformation){
    delete transformation.kernel, transformation.inv;
    const dilation = [0,1,4,5,0x10,0x11,0x14,0x15,0x40,0x41,0x44,0x45,0x50,0x51,0x54,0x55],
        undilation = {0:0,1:1,4:2,5:3,0x10:4,0x11:5,0x14:6,0x15:7,0x40:8,0x41:9,0x44:10,0x45:11,0x50:12,0x51:13,0x54:14,0x55:15};
    transformation.transform = function(i, j){ return (dilation[i]<<1)|dilation[j]; };
    transformation.inverse = function(z){ return [undilation[(z&0xAA)>>1],undilation[z&0x55]]; };
    transformation.getHierarchy = function(z){
        return ztree.getZHierarchy(z, transformation.dim + 1);
    };
};