En Yakın Komşu Arama

Giriş

Geospatial Searches yazısına göz atabilirsiniz

Top K Elements veya Top K Frequent Elements

Top K Elements veya Top K Frequent Elements yazısına taşıdım

En yakın komşu arama
Özellikle harita 3D uygulamalar en yakın komşu arama işlemi çokça yapılır. Spatial işlemler için bir çok veri yapısı mevcut. Bunlar arasında kD-tree, quad-tree, octree, bounding volume hierarchy gibi yapılar sayılabilir.

Eşleştirme için Nearest neighbor search algoritmalarından birisi kullanılabilir. Bu algoritma tiplerinden bazını aşağıda anlattım.

Quad Tree
İndekslenecek alanın büyüklüğü önceden bilinir. Alan 4'lü hücrelere ayrılır. Aranılan bir alan hangi hücre ile kısmi veya tamamen çakışıyorsa hücreler içindeki nesnelere kolayca erişilir. Konuyu şekillerle anlatan iyi bir yazı burada.

Basit olarak kod şuna benzer. AABB sınırdır. Wikideki örnek kodda bu isim kullanıldığı için aynı isimle kodlanmış.

template <class T>
class Quadtree
{
  private:
  //4 children
  Quadtree* nw;
  Quadtree* ne;
  Quadtree* sw;
  Quadtree* se;

  AABB boundary;
  
 public:
  
 Quadtree<T>(AABB boundary);
  
};

Buradaki bir yazıda QuadTree'nin neden tercih edilmediği var.

Locality sensitive hashing 
Locality Sensitive Hashing yazısına taşıdım

K-D Tree
K-D agaç yapısını 2 boyutlu olarak anlatan ve okuması kolay bir yazı burada.
K-D Tree algoritmaları bence karmaşık şeyler. K-D Tree'nin bazı özellikleri şöyle.
1. Dengeli (balanced) olmak zorunda değil.
2. N boyutlu arama yapmaya izin verir.

PostgreSQL
Eğer çok hassas sonuç istemiyorsak şöyle yaparız.

SELECT * FROM tweets WHERE location <@ circle '((-34.603722, -58.381592), 2000)'

Buradaki yazıda PostgreSQL + PosGIS ile verilen noktayan en yakın 10 tane nesneyi çekme örneği verilmiş.

SQL'de kullanılan 4326 WGS-84 için kullanılan numara ise SRID. Konuyla ilgili Vektor Harita başlıklı yazıya bakabilirsiniz.