Abstract-I denna uppsats visar vi hur komplexiteten i att utföra närmaste granne (NNS) sökning på ett metriska utrymme är relaterad till utvidgningen av det metriska utrymmet. Med tanke på ett metriska utrymme vi tittar på grafen som erhålls genom att ansluta varje par av punkter inom ett visst avstånd r. Vi tittar sedan på olika begrepp om expansion i denna graf som relaterar dem till cellsonden komplexitet NNS för randomiserade och deterministiska, exakta och ungefärliga algoritmer. Till exempel om grafen har nodexpansion 0 så visar vi att varje deterministisk t-probe datastruktur för n-punkter måste använda mellanslag S där (St/n) t > 0. Vi visar liknande resultat för randomiserade algoritmer också. Dessa relationer kan användas för att härleda de flesta av de kända nedre gränserna i de välkända metriska utrymmen som l1, l2, l∞ och några nya, genom att helt enkelt beräkna deras expansion. I processen stärker och generaliserar vi våra tidigare resultat [18]. Dessutom förenar vi tillvägagångssättet [18] och det kommunikationskomplexa tillvägagångssättet. Vårt arbete minskar problemet med att bevisa cellsond nedre gränserna för nära granne sökande till att beräkna lämplig expansion parameter. I våra resultat, liksom i alla tidigare resultat, är beroendet av t svagt; d.v.s. den bundna sjunker exponentiellt i t. Vi visar en mycket starkare (tät) tid-rymd-avsättning för klassen av dynamiska låg stridsdatastrukturer. Dessa är datastrukturer som stöder uppdateringar i datauppsättningen och som inte slår upp någon enda cell alltför ofta. En fullständig version av pappret finns i [19].
Detta är inte en omfattande undersökning; REF ger en bra översikt över flera av de kända nedre gränserna.
Lower Bounds on Near Neighbor Search via Metric Expansion
{'venue': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'journal': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}