Bir harita üzerinde ilgi çekici nokta (POI) işaretlerini verimli bir şekilde arama

Booking.com'da en iyi tesis arama özelliklerini sunarak kullanıcılarımızın hayatını kolaylaştırma konusunda tutkuluyuz. Kullanıcılarımızın en iyi konaklama yerini seçmek için tüm bilgilere sahip olmalarını istiyoruz. Gezi deneyiminin önemli bir parçası olduğundan, bir konaklama yeri seçerken tesisin konumunun en önemli kriterlerden biri olduğu muhtemelen bir sır değil.

Booking.com harita özelliği, konum bilgilerini çok görsel bir şekilde sağladığı için güçlü bir araçtır. Kullanıcılar, mülkün tercih ettikleri konumda olup olmadığını yalnızca birkaç saniye içinde belirleyebilir. Ancak, genellikle sadece mülkün konumunu görmek yeterli değildir. Gezi sırasında ziyaret edilecek en ilginç yerlerin konumunu göstermek de önemlidir. Ne kadar uzaktalar? Mülkten onlara ulaşmak ne kadar kolay?

Kullanıcılarımızın bu soruları yanıtlamasına yardımcı olmak için, özellik işaretçilerinin yanı sıra ilgi noktası (POI) işaretçileri de gösteriyoruz. Adından da anlaşılacağı gibi, bu işaretçiler plajlar, kayak merkezleri, önemli noktalar ve şehirler ve havaalanları gibi gezginlerin ilgi çekici yerlerini vurgular ve bunların tümü kullanıcıya mülkün konumunu daha iyi anlar.

Haritada nasıl arama yapılır?

Bir kullanıcı haritayı açtığında, genellikle sınırlayıcı kutu (BBox) adı verilen belirli bir alan görünür. Teknik olarak bir BBox, köşeleri 4 coğrafi nokta ile temsil edilen bir dikdörtgendir:

• Kuzey-Batı (KB);
• Kuzey-Doğu (KD);
• Güneydoğu (SE);
• Güney-Batı (GB).

Mantıksal olarak, yalnızca bu BBox'ın içindeki POI işaretçilerini görüntülemek yeterlidir, çünkü dünyanın geri kalanı bir kullanıcı tarafından görülemez. Böylece, harita içeriğini ararken arama anahtarımız olarak bir BBox kullanabiliriz.

Kullanıcılar, haritayı kaydırarak ve yakınlaştırarak görünür alanı değiştirebilir ve bu tür etkileşimlerin sayısı nispeten yüksek olabilir. En iyi kullanıcı deneyimini sağlamak istiyoruz ve BBox'ın olağandışı arama anahtarıyla çalışabilecek etkili bir arama mekanizması gerektirecek şekilde haritada görüntülenen bilgileri mümkün olan en kısa sürede sağlamak istiyoruz.

Bir anahtarla arama yapmaktan bahsederken, arama ağaçları klasik bir çözümdür ve elbette bu durum da bir istisna değildir! Ama önce böyle bir ağacı kullanmanın bir yolunu bulmalı ve bir BBox'ın nasıl anahtar olarak kullanılabileceğini bulmalıyız. Bu sorunu çözmek için bir dörtlü ağaç kullanacağız.

dört ağaç

Bir dörtlü ağaç, her dahili düğümün tam olarak dört çocuğa sahip olduğu bir arama ağacıdır. Neden dört, soruyorsun? İki alt düğüme sahip basit bir arama ağacı, genellikle arama kümesini her düzeyde ikiye böler. Bir harita, enlem ve boylamdan oluşan iki boyutlu bir yapıdır, her seviyede her boyutu iki parçaya bölmemiz gerekir, bu da dört kadranla sonuçlanır. Bu ağacın her düğümü de bir BBox olacaktır. Kök düğüm, tüm dünyayı içeren BBox olacaktır, her alt düğüm, üst BBox'ın bir çeyreği olacaktır.

Asıl amacımız haritada gösterilecek işaretler bulmak olduğu için, ağacın her düğümü de bir miktar (genellikle nispeten az miktarda) işaretçi içerecektir. En basit dörtlü ağaç düğümünün kod temsili şöyle görünecektir:

class QuadTreeNode {
   private Set<Marker> markers;
   private BoundingBox bbox;
   private QuadTreeNode[] children; // Always size of 4
   private final int maxEntryCount;

   …
}

Örneğin, BBox'ta bulunan beş yer işaretini bulmak için dörtlü ağacı nasıl kullanabileceğimizi görelim. Ağacımızın her düğümünün, geçerli düğümü temsil eden BBox'ın içinde bulunan 10 yer işareti içerdiğini varsayalım. Bir BFS uyguluyoruz ve her zamanki gibi kök düğümle başlıyoruz:

1. Bu düğümdeki tüm işaretleyicileri yineleyin ve bunlardan herhangi birinin bir arama anahtarı olan BBox ile kesişip kesişmediğini kontrol edin. Yer işaretinin koordinatlarını bilmek çok basit, sadece bu koordinatların BBox dikdörtgeninin içinde olup olmadığını kontrol etmemiz gerekiyor. Koşul doğruysa
   (SW lat <= Marker lat <= NE lat) && (SW lon <= Marker lon <= NE lon)
   , işaretçi BBox'ın içindedir. BBox'ın kenarındaki işaretçileri kesişen olarak kabul ediyoruz.
2. Kesişen işaretçileri kaydedin.
3. Beş yer işareti bulursak, aramamız biter.
4. Daha fazla yer işareti bulmamız gerekirse, verilen arama anahtarı BBox ile hangi alt düğümlerin kesiştiğini kontrol eder ve daha fazla kontrol için kuyruğa kaydederiz. Bir ila dört düğüm arasında olabilir.
5. Sıradaki düğümü seçin ve 1. adıma geçin.

class QuadTree {
       private QuadTreeNode root;

       … 
  
       public Set<Marker> findMarkers(BoundingBox bbox, int n) {
        Set<Marker> foundEntries = new HashSet<>();
        Queue<QuadTreeNode> nextNodesToCheck = new LinkedList<>();
        nextNodesToCheck.add(root);

        while (foundEntries.size() < n && !nextNodesToCheck.isEmpty()) {
            int stillToFind = n - foundEntries.size();
            QuadTreeNode nodeToCheck = nextNodesToCheck.poll();

            List<Marker> currentEntries = nodeToCheck.getIntersectingEntries(bbox, stillToFind);
            foundEntries.addAll(currentEntries);

            if (foundEntries.size() < n) {
                nextNodesToCheck.addAll(
                  nodeToCheck.getIntersectingChildren(bbox)
                );
            }
        }

        return foundEntries;
    }
}

En önemli belirteçler kök düğümde tutulacak, harita ölçeğini tüm dünyanın görünür olduğu seviyeye düşürürseniz bunları göreceksiniz. Kullanıcı haritayı yakınlaştırdığında, alt yakınlaştırma seviyesinde görünmemiş olsalar bile görünür alan için en önemli olan işaretçileri görecektir.

Bir işaretleyicinin önemi, iş gereksinimleri tarafından tanımlanabilen özel kriterlere bağlıdır. Örneğin, yer işareti işaretlerinin önemini kullanıcı incelemelerine dayandırabiliriz.

Kenar Kasası

Bahsetmemiz gereken ilginç bir uç durum da var. Basit kağıt dünya haritasının neye benzediğini hayal edin: bu bir dikdörtgen, yan kenarları sağda 180. meridyen ve solda -180. meridyen. Kullanıcının burada mülk aradığını hayal edin.

Bu durumda, BBox'ın GB boylamı NE boylamından daha büyük olacaktır. BBox dikdörtgeninin içindeki işaretleyiciyi kontrol ederken bu durumu dikkate almamız gerekir. Örneğin:

• Diyelim ki BBox koordinatları SW (160, 60), NE (-160, 70). Geçerli bir BBox.
• (-162, 62)Koordinatları olan işaretçi , .SW lon > Marker lon

• BBox1:SW (160, 60), NE (180, 70)
• BBox2:SW (-180, 60), NE (-160, 70)

Dört ağaçlı bina

Neyse ki, arama ağaçları yoktan var olmuyor, bu yüzden yazılım mühendislerinin hala işlerinin olmasının sebeplerinden biri de bu. Kullanım durumumuzu tatmin edecek bir dörtlü ağacı nasıl uygulayabileceğimizi görelim.

İlk başta, ağacımız sadece tüm dünya olan bir kök düğüme sahip olacak ve herhangi bir işaretçi içermeyecek, boş olacak.

Ağacı işaretçilerle doldurmak için elimizdeki tüm işaretçileri yinelemeli ve her işaretçiyi ağaca eklemeliyiz . Diyelim ki her düğüm en fazla 10 işaret içerebilir. Ardından, her eklemede şunları yaparız:

1. Geçerli işaretçiyi, geçerli düğümün işaretçileri kümesine koyun.
2. İşaretçilerin boyutu <= 10 olarak ayarlandıysa, işimiz bitti — işaretçi yerini buldu. Bir sonraki işaretçiye ilerleyin.
3. İşaretçilerin boyutu > 10 olarak ayarlandıysa, bu düğümün en az önemli işaretçisini alıp çocuklardan birine itmemiz gerekir. (Unutmayın: düğüm köke ne kadar yakınsa, düğümdeki işaretçilerin önemi o kadar yüksektir).
4. Düğümün BBox'ını dört alt BBox'a bölerek, henüz oluşturulmamışlarsa, geçerli düğümün alt öğelerini oluşturun.
5. En düşük öncelikli işaretçiyle kesişen alt BBox'ı arayın.
6. Bu işaretçiyi yinelemeli olarak alt düğüme yerleştirin (yani, giriş olarak en az önemli işaretçi ve alt düğüm ile yukarıdaki 1. adıma gidin).

Ekleme uygulaması şöyle görünebilir:

class QuadTreeNode {
   // Keeps the lowest priority markers on top of the queue
   private PriorityQueue<Marker> markers; 
   private BoundingBox bbox;
   private QuadTreeNode[] children; // Always size of 4
   private final int maxEntryCount;

   …

   public void insert(Marker marker) {
       markers.add(marker);
       if (markers.size() > maxEntryCount) {
           if (children == null) {
               children = initializeChildren(); // Create 4 quad tree nodes
           }
      
           Marker entryToPassToChild = markers.poll(); // Get the lowest priority marker
           List<QuadTreeNode> intersectingChildren = 
               getIntersectingChildren(entryToPassToChild.getBoundingBox());

           // Marker can be on the edge of the node. 
           // As edge is a shared area among multiple nodes, 
           // markers can belong to multiple nodes.
           for (QuadTreeNode intersectingChild : intersectingChildren) {
               intersectingChild.insert(entryToPassToChild);
           }
      }
   }
     …
}

Çözüm

Bir dörtlü ağaç, BBox görevine göre işaretçi aramayı mükemmel bir şekilde çözen nispeten basit ve (aynı zamanda) güçlü bir kavramdır. Ayrıca bu çözümü oldukça ölçeklenebilir buluyoruz çünkü artan yükle başa çıkmak için tek yapmamız gereken hizmetimizi yatay olarak ölçeklendirmek.

Örneğin, (hizmet yüküne bağlı olarak) 300.000'den fazla işaretçi depolayan bir dörtlü ağaç araması, %99 için 1 ila ~5,5 ms arasında sürer ve bu bizim amaçlarımız için son derece hızlıdır.



Bu makaleyi okuduğunuz için teşekkür ederiz ve mutlu aramalar!

Teşekkür : Post fikri ve teknik düzenleme için Gregory Zak'a ve güzel çizimler için Al-Jerreau Davids'e teşekkür ederiz .