· 2015
Ağlarda gezinme: yakınlık araması için basit algoritmalar
Navigating nets: simple algorithms for proximity search
- 319atıf
- 2015yıl
Kısa özet
Genel metrik uzaylardaki noktalar için yakınlık aramalarını (en yakın komşu, aralık sorguları) ve güncellemeleri (ekleme, silme) verimli bir şekilde destekleyen, -ağ dizisi kullanan yeni bir deterministik veri yapısı sunulmuştur.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Ana noktalar
- Genel metrik uzaylarda yakınlık araması ve güncellemeler için deterministik bir veri yapısı sunar.
- Yapı, ölçekler arasında gezinme için işaretçilere sahip, giderek incelen -ağlardan oluşur.
- Sınırlı boyutlu metrikler için yüksek verimlilik ve uzaklık hesaplamada neredeyse optimalite sağlar.
- Karger ve Ruhl'un yöntemi dahil olmak üzere mevcut algoritmalardan daha iyi performans gösterir.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Özet (abstract)
We present a simple deterministic data structure for maintaining a set S of points in a general metric space, while supporting proximity search (nearest neighbor and range queries) and updates to S (insertions and deletions). Our data structure consists of a sequence of progressively finer -nets of S, with pointers that allow us to navigate easily from one scale to the next. We analyze the worst-case complexity of this data structure in terms of the “abstract dimensionality ” of the metric S. Our data structure is extremely efficient for metrics of bounded dimension and is essentially optimal in a certain model of distance computation. Finally, as a special case, our approach improves over one recently devised by Karger and Ruhl [KR02]. 1
Yazarların özeti; kaynağından alınmıştır., 2015 · DOI ↗
Ücretsiz hesapla devam et
Makaleye Sor ile bu makaleye günde 3 soru ücretsiz; makaleyi kaydet, kaynakçasını al, ilgi alanına göre her gün yeni özetler. Çıkarımlar Premium.
Web'de ücretsiz devam etGoogle ya da Apple hesabınla giriş; kart istemez. Bu makaleye geri dönersin.
Telefonda:
Alan: Bilgisayar Grafikleri ve Bilgisayar Destekli Tasarım
Computer Graphics and Computer-Aided DesignComputer Science