Abstract-Finding k närmaste grannar (kNN) av en frågepunkt, eller en uppsättning frågepunkter (kNN-Join) är grundläggande problem i många tillämpningsområden. Många tidigare insatser för att lösa dessa problem inriktade på rumsliga databaser eller fristående system, där ändringar i databasmotorn kan krävas, vilket kan begränsa deras tillämpning på stora datamängder som lagras i ett relationellt databashanteringssystem. Dessutom får dessa metoder inte automatiskt optimera kNN-frågor eller kNN-Joins när ytterligare frågevillkor anges. I detta arbete studerar vi både kNN-frågan och kNN-Join i en relationsdatabas, eventuellt förstärkt med ytterligare frågevillkor. Vi söker efter relationella algoritmer som inte kräver några ändringar i databasmotorn. Den enkla lösningen använder den användardefinierade funktionen (UDF) som en frågeoptimerare inte kan optimera. Vi designar algoritmer som kan implementeras av SQL-operatörer utan ändringar i databasmotorn, vilket gör det möjligt för frågeoptimeraren att förstå och generera den "bästa" frågeplanen. Med hjälp av bara ett litet konstant antal slumpmässiga skift för databaser i alla fasta dimensioner garanterar vår strategi att hitta ungefärlig kNN med endast logaritmiskt antal sidåtkomster i förväntan med en konstant approximation förhållande och det skulle kunna utökas för att hitta den exakta kNN effektivt i alla fasta dimensioner. Vårt designparadigm stöder enkelt kNN-Join och uppdateringar. Omfattande experiment på stora, verkliga och syntetiska, datauppsättningar bekräftar effektiviteten och praktiskheten i vår strategi.
Yao och Al. REF föreslår Z-KN, en Zordering-baserad metod för att svara på kNN, att SQL-operatörer ansluter sig till RDBMS i förhållande till varandra utan ändringar av databasmotorn.
K nearest neighbor queries and kNN-Joins in large relational databases (almost) for free
{'venue': '2010 IEEE 26th International Conference on Data Engineering (ICDE 2010)', 'journal': '2010 IEEE 26th International Conference on Data Engineering (ICDE 2010)', 'mag_field_of_study': ['Computer Science']}