Ett stort spektrum av tillämpningar som lokaliseringsbaserade tjänster och miljöövervakning kräver effektiv frågebehandling i osäkra databaser. I detta papper föreslår vi den probabilistiska Voronoi diagram (PVD) för att behandla rörliga närmaste granne frågor om osäkra data, nämligen den probabilistiska rörliga närmaste granne (PMNN) frågor. En PMNN fråga finner den mest sannolika närmaste granne till en rörlig frågepunkt kontinuerligt. För att kunna behandla PMNN-frågor på ett effektivt sätt tillhandahåller vi två tekniker: en förberäkningsmetod och en inkrementell metod. I pre-computation metoden utvecklar vi en algoritm för att effektivt utvärdera PMNN frågor baserat på den precomputerade PVD för hela datamängden. I det inkrementella tillvägagångssättet föreslår vi en stegvis probabilistisk säker regionbaserad teknik som inte behöver förbeställa hela PVD för att svara på PMNN-frågan. I detta inkrementella tillvägagångssätt utnyttjar vi kunskapen för en känd region att beräkna den nedre gränsen av sannolikheten för att ett objekt är närmaste granne. Experimentella resultat visar att våra tillvägagångssätt avsevärt överträffar ett provtagningsbaserat tillvägagångssätt enligt storleksordningar när det gäller I/O, frågebehandlingstid och kommunikations omkostnader.
I REF är en Voronoi-diagram-baserad struktur utvecklad för en "kontinuerlig" närmaste granne fråga, där en 2D frågepunkt ständigt rör sig.
Probabilistic Voronoi Diagrams for Probabilistic Moving Nearest Neighbor Queries
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}