Z曲線とかどうなの？

AddController.java

package com.ashigeru.appengine.query.tiling.controller.zorder;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import net.arnx.jsonic.JSON;

import org.slim3.controller.Controller;
import org.slim3.controller.Navigation;
import org.slim3.datastore.Datastore;

import com.ashigeru.appengine.query.tiling.meta.ZOrderVectorMeta;
import com.ashigeru.appengine.query.tiling.model.DistanceComparator;
import com.ashigeru.appengine.query.tiling.model.ZOrderVector;
import com.google.appengine.api.datastore.Query.FilterOperator;
import com.google.appengine.api.datastore.Query.SortDirection;

public class AddController extends Controller {

    private static final int CANDIDATES = 10;

    @Override
    public Navigation run() throws Exception {
        String name = asString("name");
        Integer d1 = asInteger("d1");
        Integer d2 = asInteger("d2");
        Integer d3 = asInteger("d3");
        Integer d4 = asInteger("d4");
        if (name == null || d1 == null || d2 == null || d3 == null || d4 == null) {
            return null;
        }

        ZOrderVector vector = new ZOrderVector(d1, d2, d3, d4);
        vector.setName(name);

        ZOrderVectorMeta m = ZOrderVectorMeta.get();

        // Z-Orderingの前後を取得
        List<ZOrderVector> front = Datastore.query(m)
            .filter("ordering", FilterOperator.LESS_THAN_OR_EQUAL, vector.getOrdering())
            .limit(CANDIDATES + 1)
            .sort("ordering", SortDirection.DESCENDING)
            .asList();
        List<ZOrderVector> back = Datastore.query(m)
            .filter("ordering", FilterOperator.GREATER_THAN, vector.getOrdering())
            .limit(CANDIDATES)
            .sort("ordering", SortDirection.ASCENDING)
            .asList();

        // ユークリッド距離で並べなおす
        List<ZOrderVector> candidates = new ArrayList<ZOrderVector>();
        candidates.addAll(front);
        candidates.addAll(back);
        Collections.sort(candidates, new DistanceComparator(vector));

        // ついでに自分も保存しておく
        Datastore.put(vector);

        List<Map<String, Object>> results = new ArrayList<Map<String, Object>>();
        for (int i = 0, n = Math.min(candidates.size(), 3); i < n; i++) {
            Map<String, Object> entry = new HashMap<String, Object>();
            ZOrderVector found = candidates.get(i);
            entry.put("name", found.getKey().getName());
            entry.put("vector", found.getVector());
            entry.put("distance", vector.distanceTo(found));
            results.add(entry);
        }

        JSON.encode(results, response.getWriter(), true);
        return null;
    }
}

ByteArrayBuilder.java

package com.ashigeru.appengine.query.tiling.model;

/**
 * バイト配列を操作する。
 * @author ashigeru
 */
public class ByteArrayBuilder {

    private byte[] bytes;

    public ByteArrayBuilder(int numberOfBytes) {
        bytes = new byte[numberOfBytes];
    }

    public static ByteArrayBuilder fromDouble(double value) {
        ByteArrayBuilder result = new ByteArrayBuilder(8);
        long bits = Double.doubleToRawLongBits(value);
        for (int b = 0; b < 8; b++) {
            result.bytes[b] = (byte) (bits >>> (Double.SIZE - (b + 1) * 8));
        }
        return result;
    }

    public static ByteArrayBuilder fromInt(int value) {
        ByteArrayBuilder result = new ByteArrayBuilder(4);
        for (int b = 0; b < 4; b++) {
            result.bytes[b] = (byte) (value >>> (Integer.SIZE - (b + 1) * 8));
        }
        return result;
    }

    public void set(int offset, boolean value) {
        int byteOffset = offset / 8;
        int bitOffset = offset % 8;
        byte mask = (byte) (0x80 >>> bitOffset);
        if (value) {
            bytes[byteOffset] |= mask;
        }
        else {
            bytes[byteOffset] &= ~mask;
        }
    }

    public boolean get(int offset) {
        int byteOffset = offset / 8;
        int bitOffset = offset % 8;
        byte mask = (byte) (0x80 >>> bitOffset);
        return (bytes[byteOffset] & mask) != 0;
    }

    public byte[] getBytes() {
        return this.bytes;
    }
}

DistanceComparator.java

package com.ashigeru.appengine.query.tiling.model;

import java.util.Comparator;

/**
 * 基点からの距離を基にした比較。
 * @author ashigeru
 */
public class DistanceComparator implements Comparator<ZOrderVector> {

    private ZOrderVector origin;

    public DistanceComparator(ZOrderVector origin) {
        this.origin = origin;
    }

    public int compare(ZOrderVector o1, ZOrderVector o2) {
        double d1 = origin.distanceTo(o1);
        double d2 = origin.distanceTo(o2);
        return Double.compare(d1, d2);
    }
}

ZOrderVector.java

package com.ashigeru.appengine.query.tiling.model;

import java.util.Arrays;

import org.slim3.datastore.Attribute;
import org.slim3.datastore.Datastore;
import org.slim3.datastore.Model;

import com.google.appengine.api.datastore.Key;
import com.google.appengine.api.datastore.ShortBlob;

/**
 * Z曲線用のビット列を持つ多次元ベクトル。
 * @author ashigeru
 */
@Model
public class ZOrderVector {

    @Attribute(primaryKey = true)
    private Key key;

    @Attribute(lob = true)
    private int[] vector;

    private ShortBlob ordering;

    public ZOrderVector() {
        return;
    }

    public ZOrderVector(int...vector) {
        this.vector = vector;
        ordering = new ShortBlob(computeOrder(vector));
    }

    private static byte[] computeOrder(int[] vector) {
        int dimensions = vector.length;
        ByteArrayBuilder results = new ByteArrayBuilder(dimensions * 8);
        for (int i = 0; i < dimensions; i++) {
            ByteArrayBuilder bits = ByteArrayBuilder.fromInt(vector[i]);
            for (int offset = 0; offset < Integer.SIZE; offset++) {
                results.set(offset * dimensions + i, bits.get(offset));
            }
        }
        return results.getBytes();
    }

    public double distanceTo(ZOrderVector other) {
        int[] v1 = vector;
        int[] v2 = other.vector;
        if (v1.length != v2.length) {
            return Double.NaN;
        }
        double sum = 0.0;
        for (int i = 0; i < v1.length; i++) {
            double diff = v1[i] - v2[i];
            sum += diff * diff;
        }
        return Math.sqrt(sum);
    }

    @Override
    public String toString() {
        return Arrays.toString(vector);
    }

    public Key getKey() {
        return this.key;
    }

    public void setKey(Key key) {
        this.key = key;
    }

    public int[] getVector() {
        return this.vector;
    }

    public void setVector(int[] vector) {
        this.vector = vector;
    }

    public ShortBlob getOrdering() {
        return this.ordering;
    }

    public void setOrdering(ShortBlob order) {
        this.ordering = order;
    }

    public void setName(String name) {
        this.key = Datastore.createKey(ZOrderVector.class, name);
    }
}

http://tiling.latest.ashigeru-demo.appspot.com/ でデモ中。