Thumbnail
Access Restriction
Subscribed

Author Efentakis, Alexandros ♦ Pfoser, Dieter
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword k-nearest neighbors ♦ kNN ♦ Query processing ♦ RkNN ♦ RNN ♦ ReHub algorithm ♦ Graph algorithms ♦ Hub labels ♦ Reverse k-nearest neighbors
Abstract Quite recently, the algorithmic community has focused on solving multiple shortest-path query problems beyond simple vertex-to-vertex queries, especially in the context of road networks. Unfortunately, those advanced query-processing techniques cannot be applied to large-scale graphs, such as social or collaboration networks, or to efficiently answer reverse $\textit{k}-nearest$ neighbor $(R\textit{k}NN)$ queries, which are of practical relevance to a wide range of applications. To remedy this, we propose ReHub, a novel main-memory algorithm that extends the hub labeling technique to efficiently answer $R\textit{k}NN$ queries on large-scale networks. Our experimentation will show that ReHub is the best overall solution for this type of queries, requiring only minimal additional preprocessing and providing very fast query times in all cases.
Description Author Affiliation: Research Center “Athena”, Marousi, Greece (Efentakis, Alexandros); Department of Geography and GeoInformation Science, George Mason University, VA, USA (Pfoser, Dieter)
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-11-04
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 21
Page Count 35
Starting Page 1
Ending Page 35


Open content in new tab

   Open content in new tab
Source: ACM Digital Library