En Yakın Komşu Arama (Nearest Neighbor Search) - Locality Sensitive Hashing - Hash Kullanır

Giriş

En yakın komşuları aramak için benim kanaatimce en uygun olanı Locality sensitive hashing. Bu yöntemde dünya sisteminin eksi değerler alıp almadığına dikkat etmek gerekir!. Eğer eksi değer alıyorsa formülümüzden eksik değer çıkmaması için düzeltme yapmak lazım gelebilir.

Design A Location Based Service videosu da faydalı

1.Hash Fonksiyonu
Şeklen şöyle

1.1. Cell döndüren Hash Fonksiyon

Elimizdeki nesnelerin koordinat bilgisini bir hash fonksiyonuna sokup hangi hücreye yerleşeceğine karar veriyoruz. Arama için hızlı bir yöntem. hash fonksiyonunun birbirlerine yakın nesneleri komşu hücrelere yerleştirmesi gerekiyor.

1.2 GeoHash Fonksion

String döndürür. Önce binary bir string üretir daha sonra bu Base32 olarak kodeklenir

2. Verinin Saklanması
2.1 Matrix Şeklinde Locality Hashing
Matrix'in en zor tarafı hücre bulunduktan sonra etrafındaki hücreleri de dolaşmak. Bu kod parçasında matrix'in dışına taşıp IndexOutOfBounds tipi bir exception alma ihtimaline karşı dikkatli kodlamak gerekiyor.

Örnek - Etraftaki Hücreleri Dolaşmak

Elimizde iki boyutlu bir dünya olsun

Cell[][] cells;

Şöyle yaparız

Optional<Cell> getCell(int x, int y) {
  if(x >= 0 && x < width && y >= 0 && y < height) {
    return Optional.of(cells[y][x]);
   }
   return Optional.empty();
}

List<Cell> getCellNeighbours(Cell cell) {
  List<Optional<Cell>> neighbours = new ArrayList<>();

  neighbours.add(getCell(cell.x, cell.y+1)); // TOP
  neighbours.add(getCell(cell.x, cell.y-1)); // BOTTOM
  neighbours.add(getCell(cell.x-1, cell.y)); // LEFT
  neighbours.add(getCell(cell.x+1, cell.y)); // RIGHT

  return neighbours.stream()
              .filter(Optional::isPresent)
              .map(Optional::get)
              .collect(Collectors.toList());
}

Örnek - 3 boyutlu dünya

Eğer dünya koordinatımız eksi değerlere de sahip olsaydı (mesela -10,000 , 10,000 arasında) şöyle yaparız. Önce 1 satırında offset değerini ekleyerek eksi değerleri artı hale getiririz. Daha sonra 2 satırında ChunkSize'lara böleriz. Mesela X,Y ve Z için chunksize 100 kabul edilebilir. Bu durumda her chunk merkezi arasında 1000 birimlik mesafe olur

Chunk GetChunkForWorldPosition(Vector3 position) {
  float offset = WorldWidth * 0.5; //1
  int x = (int)Math.Floor((position.x + offset) / ChunkSizeX); //2
  int y = (int)Math.Floor((position.y + offset) / ChunkSizeY);
  int z = (int)Math.Floor((position.z + offset) / ChunkSizeZ);

  return chunks[x][y][z];
}

Örnek - İki Boyutlu Dünya

Açıklaması şöyle

Imagine a 2D example. You have a 2D world where each chunk contains 10 x 10 pixels. At the world level you want to access the pixel data for pixel (342,103). First you need to find the chunk that contains the data. You can easily find that because you know each chunk contains 10 x 10 pixels. To get chunk coordinates, just divide by the number of pixels per chunk, (int)342/10 = 34 and (int)103/10 = 10, giving you chunk (34,10).

Now you just need to get the coordinates within the chunk. Those coordinates can easily be found by getting the remainder after the division, i.e. a modulo operation. 342%10 =  2 and 103%10 = 3, giving you pixel (2,3).

That means world position (342,103) can be found in chunk (34,10) at position (2,3).

2.2. Tree Şeklinde Locality Hashing

Java'da TreeMap kullanarak hücreleri sıralı tutmak ve daha sonra xmin, xmax arasında kalan (örneğin 2 enlem arası) ve daha sonra ymin, ymax (iki boylam arası) değerleri dolaşmak mümkün.

TreeMap<Integer, TreeMap<Integer, Integer>> values;
for (int x : values.subMap(xmin, xmax).keySet()) {
 for (int y : values.get(x).subMap(ymin, ymax).values()) {
            // y here, represents the values of points in range...
 }
}

3. Diğer

3.1 Zaman İçin Hashing
Locality zaman için de kullanılabilir. Örnekte birbirlerine yakın zamanlar aynı kümeye ekleniyor.

model.get_time_bucket(seconds) {
  return floor(self.timestamp / seconds);
}

Örnek - Birbirlerine en yakın zamanları eşleştirme
Eğer birbirlerine en yakın zamanları eşleştirmek istersek şöyle yapabiliriz.

//compute reasonably aligned pairs
var max_tolerable_offset = 500; //do not match more then 500 miliseconds distant ones

Dictionary<long, long> alignedPairs = new Dictionary<long, long>();

foreach(var s in s_timestamps)
{
  //for every timestamp in first timeline find the nearest one from r
  var nearest_r = r_timestamps.OrderBy(r => Math.Abs(r - s)).First(); 

  //if that is closer than allowed offset
  if ((Math.Abs(nearest_r - s)) <= max_tolerable_offset * 10000)
  {
    //so now I need to find nearest s mark for this r mark
    var closest_s = s_timestamps.OrderBy(s=> Math.Abs(s- nearest_r )).First();

    //if they are mutually in love, marry them
    if (closest_s == s)
      alignedPairs.Add(s, nearest_r);
   }
}