# Reverse k Nearest Neighbors Query Processing: Experiments and

Reverse k Nearest Neighbors Query Processing: Experiments and Analysis Shiyu Yang , Muhammad Aamir Cheema , Xuemin Lin , Wei Wang The University of New South Wales, Australia Monash University, Australia Outline Introduction Framework Motivation Algorithms TPL++ Experiments Conclusion 2 Introduction Reverse k Nearest Neighbors Find every user u for which the query facility q is one of its k-closest facilities RNN of f1 is {u1,u2} RNN of f2 is {u3} f1

u2 u1 Applications Influence computation, marketing, cluster and outlier analysis and decision support systems f2 u3 K=1 3 Framework Pruning Verification Six-regions (SIGMOD 2000) Six-regions (Stanoi et al., UCSB, SIGMOD 2000) Region-based SLICE (ICDE 2014) TPL (Tao et al., CUHK, VLDB 2004) FINCH (Wu et al., NUS, VLDB 2008) TPL (VLDB 2004), TPL++ (VLDB2015) Half-space InfZone (Cheema et al., UNSW, ICDE2011) FINCH

(VLDB 2008), SLICE (Yang et al.,UNSW, ICDE 2014) InfZone (ICDE 2011) 4 Motivation and Contributions 10ms per I/O 400 300 Motivation 200 Reporting overall cost may be misleading 100 0 Buffer size affects the ranking Six All in one comparison TPL FINCH INF SLICE 0.1ms per I/O 27.5 Contributions 22

16.5 Comprehensive experiments 11 5.5 Improved TPL algorithm: TPL++ 0 Six 5 TPL FINCH INF SLICE Algorithms Half-space Pruning --TPL TPL [Tao et al., CUHK, VLDB 2004] b c Property of perpendicular bisector p Sort facilities according Hilbert value

Draw bisectors between facilities and query A point can be filtered if it is in a combination of a q u the half-spaces of k facilities. Pruning power <> Pruning cost k=2 6 d Algorithms Optimisation 1: --TPL++ A point can be filtered if it is pruned by k facilities. Add a counter for point to be pruned. Iterate over facilities.

O(mk) -> O(m) b c p a q e Optimisation 2: Include more facilities for pruning k=2 7 Effect of Optimisations I/O cost 40 TPL 30 CPU cost (ms) 240 TPL++ TPL 180 20 120

10 60 0 0 2 5 10 15 20 25 k 2 5 TPL++ 10 15 20 k 20 times better 2 times better 8

25 Algorithms Region-based Pruning Half-space Pruning Six-regions SLICE FINCH InfZone Stanoi et al., UCSB, Yang et al., UNSW, Wu et al., NUS, Cheema et al., UNSW, SIGMOD 2000 ICDE 2014 VLDB 2008 ICDE 2011 9 Experiments Setup

Intel Xeon 2.66 GHz CPU, 4GB Memory and Hard disk Index: R*-tree 100 buffers I/O cost and CPU cost Average cost per query Data sets Three real data sets (up to 25M points) CA, LA and NA Synthetic data sets follows different distributions (up to 20M points) Source code and data sets are available online 10 Experiments Ranking Criteria 1st I/O (no buffer) 2nd 3rd 4th 5th 6th

TPL++,InfZone SLICE TPL FINCH SIX I/O (small buffer) TPL++,InfZone FINCH SLICE TPL,SIX CPU (k<10) SLICE InfZone TPL++ FINCH SIX,TPL CPU (10

SIX TPL CPU (25

InfZone SLICE node O(1) O(km) O(m) O(m) O(m) O(t) point O(1) O(km) O(m) O(logm) O(m) O(1) Add O(log k) O(logm) O(logm)

O(m2) O(m2) O(tlogm) node O(1) O(km) O(m) O(m) O(m) O(t) point O(1) O(km) O(m) O(logm) O(logm) O(1) Verify Cand Range query Range query

Range query Range query O(logm) O(m) Verification 12 Conclusion Review of existing RkNN algorithms An improved version of TPL: TPL++ Experiments and analysis 13 Thanks :) Q&A 14

## Recently Viewed Presentations

• Coordinates allow us to pinpoint exactly where a point or shape is on a graph or map. Coordinates are written in brackets separated by a comma, like this (1, 6). They are an 'ordered pair' of numbers which means the...
• Aardmagnetisch veld en Kosmische straling Anneke de Leeuw St. Michaëlcollege te Zaandam HiSPARC Kosmische straling Hisparc project Verband tussen aardmagnetisch veld en kosmische straling Oorzaak van aardmagnetisch veld Meten van aardmagnetisch veld AVM en SAM Paleomagnetisme Experimenten in de klas...
• L'astre lunaire gravite autour de la Terre en 28 jours et la Terre tourne autour d'elle en 24h.Comme la Terre tourne plus vite, la lune change de position par rapport à un lieu sur la Terre (la raison pour laquelle...
• Physical Therapy Program for Pelvic Floor Dysfunction. Jennifer Shifferd, MSPT, CLT WCS. ... The vulval area also changes with ageing, as fatty tissue reduces and the labia majora (outer lips of the vagina) and the hood of skin covering the...
• Deviance and social control . This Photo by Unknown Author is licensed under CC BY-SA. Culture and norms regarding appropriate behavior. Social Control. Social control: techniques and strategies employed for preventing deviant human behavior in any society.
• A spelling test is administered containing 20 words, lasting approximately 15 minutes. A separate test is given on punctuation, vocabulary and grammar. This test lasts for 45 minutes and requires short answer questions, including some multiple choice. Marks for these...
• Flowers for Algernon by Daniel Keyes. Objective: I will evaluate structural elements of the plot, including subplots and parallel episodes.
• Pedagogy can influence how content is delivered and created - so can technology. Content can influence pedagogy - so can technology. We may want to consider all three - as equal elements - during the process of curriculum design and...