More Web Proxy on the site http://driver.im/

research-article

Public Access

ReHub: Extending Hub Labels for Reverse k-Nearest Neighbor Queries on Large-Scale Networks

Authors:

Alexandros Efentakis,

Dieter PfoserAuthors Info & Claims

Journal of Experimental Algorithmics (JEA), Volume 21

Article No.: 1.13, Pages 1 - 35

https://doi.org/10.1145/2990192

Published: 04 November 2016 Publication History

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 k-nearest neighbor (RkNN) 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 RkNN 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.

References

[1]

Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. 2012a. HLDB: Location-based services in databases. In Proceedings of the 20th International Conference on Advances in Geographic Information Systems (SIGSPATIAL’12). ACM, New York, NY, 339--348.

Digital Library

[2]

Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2011. A hub-based labeling algorithm for shortest paths in road networks. In Experimental Algorithms. Lecture Notes in Computer Science, Vol. 6630. Springer, 230--241.

Digital Library

[3]

Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2012b. Hierarchical hub labelings for shortest paths. In Algorithms ESA 2012. Lecture Notes in Computer Science, Vol. 7501. Springer, 24--35.

Digital Library

[4]

Takuya Akiba, Yoichi Iwata, Ken-ichi Kawarabayashi, and Yuki Kawata. 2014. Fast shortest-path distance queries on road networks by pruned highway labeling. In Proceedings of the 16th Workshop on Algorithm Engineering and Experiments (ALENEX’14). 147--154.

Digital Library

[5]

Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD’13). 349--360.

Digital Library

[6]

Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. 2015. Pruned Landmark Labeling. Retrieved September 29, 2016, from https://github.com/iwiwi/pruned-landmark-labeling.

[7]

Rka Albert, Hawoong Jeong, and Albert-Lszl Barabsi. 1999. The diameter of the World Wide Web. arXiv:cond-mat/9907038v2. http://dblp.uni-trier.de/db/journals/corr/corr9907.html#cond-mat-9907038.

[8]

David A. Bader, Henning Meyerhenke, Peter Sanders, Christian Schulz, Andrea Kappes, and Dorothea Wagner. 2014. Benchmarking for graph clustering and partitioning. In Encyclopedia of Social Network Analysis and Mining, R. Alhajj and J. Rokne (Eds.). Springer, New York, NY, 73--82.

[9]

Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. 2015. Route planning in transportation networks. arXiv:1504.05140. http://arxiv.org/abs/1504.05140

[10]

Felix Borutta, Mario A. Nascimento, Johannes Niedermayer, and Peer Kröger. 2014. Monochromatic RkNN queries in time-dependent road networks. In Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems (MobiGIS’14). ACM, New York, NY, 26--33.

Digital Library

[11]

Muhammad Aamir Cheema, Wenjie Zhang, Xuemin Lin, Ying Zhang, and Xuefei Li. 2012. Continuous reverse k nearest neighbors queries in Euclidean space and in spatial networks. VLDB Journal 21, 1, 69--95.

Digital Library

[12]

Eunjoon Cho, Seth A. Myers, and Jure Leskovec. 2011. Friendship and mobility: User movement in location-based social networks. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD’11). 1082--1090.

Digital Library

[13]

Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. 2002. Reachability and distance queries via 2-hop labels. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’02). 937--946. http://dl.acm.org/citation.cfm?id=545381.545503

Digital Library

[14]

Daniel Delling, Julian Dibbelt, Thomas Pajor, and Renato F. Werneck. 2015. Public transit labeling. In Experimental Algorithms. Lecture Notes in Computer Science, Vol. 9125. Springer, 273--285.

Digital Library

[15]

Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck. 2011a. PHAST: Hardware-accelerated shortest path trees. In Proceedings of the 25th IEEE International Symposium on Parallel and Distributed Processing (IPDPS’11). 921--931.

Digital Library

[16]

Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck. 2013a. PHAST: Hardware-accelerated shortest path trees. Journal of Parallel and Distributed Computing 73, 7, 940--952.

Digital Library

[17]

Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. 2014. Robust distance queries on massive networks. In Algorithms—ESA 2014. Lecture Notes in Computer Science, Vol. 8737. Springer, 321--333.

[18]

Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2011b. Faster batched shortest paths in road networks. In Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’11). 52--63.

[19]

Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2013b. Hub label compression. In Experimental Algorithms. Lecture Notes in Computer Science, Vol. 7933. Springer, 18--29.

[20]

Daniel Delling and Renato F. Werneck. 2015. Customizable point-of-interest queries in road networks. IEEE Transactions on Knowledge and Data Engineering 27, 3, 686--698.

Digital Library

[21]

Alexandros Efentakis. 2016. Scalable public transportation queries on the database. In Proceedings of the 19th International Conference on Extending Database Technology (EDBT’16). 527--538.

[22]

Alexandros Efentakis, Christodoulos Efstathiades, and Dieter Pfoser. 2015a. COLD. Revisiting hub labels on the database for large-scale graphs. In Advances in Spatial and Temporal Databases. Lecture Notes in Computer Science, Vol. 9239. Springer, 22--39.

[23]

Alexandros Efentakis and Dieter Pfoser. 2014. GRASP. Extending graph separators for the single-source shortest-path problem. In Algorithms—ESA 2014. Lecture Notes in Computer Science, Vol. 8737. Springer, 358--370.

[24]

Alexandros Efentakis, Dieter Pfoser, and Yannis Vassiliou. 2015b. SALT. A unified framework for all shortest-path query variants on road networks. In Experimental Algorithms. Lecture Notes in Computer Science, Vol. 9125. Springer, 298--311.

Digital Library

[25]

Fletcher Foti, Paul Waddell, and Dennis Luxen. 2012. A generalized computational framework for accessibility: From the pedestrian to the metropolitan scale. In Proceedings of the 4th Transportation Research Board Conference on Innovations in Travel Modeling (ITM’12).

[26]

Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz. 2001. Distance labeling in graphs. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’01). 210--219. http://dl.acm.org/citation.cfm?id=365411.365447

Digital Library

[27]

Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz. 2004. Distance labeling in graphs. Journal of Algorithms 53, 1, 85--112.

Digital Library

[28]

Robert Geisberger. 2011. Advanced Route Planning in Transportation Networks. Ph.D. Dissertation. Institute of Theoretical Informatics, Algorithmics II, Karlsruhe Institute of Technology, Karlsruhe, Germany.

[29]

Robert Geisberger, Peter Sanders, and Dominik Schultes. 2008a. Better approximation of betweenness centrality. In Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX’08). 90--100. http://dblp.uni-trier.de/db/conf/alenex/alenex2008.html#GeisbergerSS08.

Digital Library

[30]

Robert Geisberger, Peter Sanders, Dominik Shultes, and Daniel Delling. 2008b. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Proceedings of the 7th International Workshop on Experimental Algorithms. 319--333.

Digital Library

[31]

Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. 2012. Exact routing in large road networks using contraction hierarchies. Transportation Science 46, 3, 388--404.

Digital Library

[32]

Minhao Jiang, Ada Wai-Chee Fu, Raymond Chi-Wing Wong, and Yanyan Xu. 2014. Hop doubling label indexing for point-to-point distance querying on scale-free networks. Proceedings of the VLDB Endowment 7, 12, 1203--1214. http://www.vldb.org/pvldb/vol7/p1203-jiang.pdf.

Digital Library

[33]

Sebastian Knopp, Peter Sanders, Dominik Schultes, Frank Schulz, and Dorothea Wagner. 2007. Computing many-to-many shortest paths using highway hierarchies. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX’07).

Digital Library

[34]

F. Korn and S. Muthukrishnan. 2000. Influence sets based on reverse nearest neighbor queries. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data (SIGMOD’00). ACM, New York, NY, 201--212.

Digital Library

[35]

Jure Leskovec and Andrej Krevl. 2014. Stanford Large Network Dataset Collection. Retrieved September 29, 2016, from http://snap.stanford.edu/data.

[36]

Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, and Michael W. Mahoney. 2009. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics 6, 1, 29--123.

[37]

Ling Liu and M. Tamer Özsu (Eds.). 2009. Encyclopedia of Database Systems. Springer.

Digital Library

[38]

Julian J. McAuley and Jure Leskovec. 2012. Learning to discover social circles in ego networks. In Proceedings of the 26th Annual Conference on Neural Information Processing Systems. 548--556. http://papers.nips.cc/paper/4532-learning-to-discover-social-circles-in-ego-networks

Digital Library

[39]

Kurt Mehlhorn and Peter Sanders. 2008. Algorithms and Data Structures: The Basic Toolbox. Springer, Berlin, Germany.

Digital Library

[40]

Maytham Safar, Dariush Ibrahimi, and David Taniar. 2009. Voronoi-based reverse nearest neighbor query processing on spatial networks. Multimedia Systems 15, 5, 295--308.

[41]

Sibo Wang, Wenqing Lin, Yi Yang, Xiaokui Xiao, and Shuigeng Zhou. 2015. Efficient route planning on public transportation networks: A labelling approach. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (SIGMOD’15). ACM, New York, NY, 967--982.

Digital Library

[42]

Jaewon Yang and Jure Leskovec. 2012. Defining and evaluating network communities based on ground-truth. In Proceedings of the 12th IEEE International Conference on Data Mining (ICDM’12). 745--754.

Digital Library

[43]

M. L. Yiu, D. Papadias, N. Mamoulis, and Y. Tao. 2006. Reverse nearest neighbors in large graphs. IEEE Transactions on Knowledge and Data Engineering 18, 4, 540--553.

Digital Library

Cited By

Li WCai MGao MWen DQin LWang W(2023)Expanding Reverse Nearest NeighborsProceedings of the VLDB Endowment10.14778/3636218.363622017:4(630-642)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.14778/3636218.3636220
Efentakis AEfstathiades CPfoser D(2017)Hub Labels on the database for large-scale graphs with the COLD frameworkGeoinformatica10.1007/s10707-016-0287-521:4(703-732)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s10707-016-0287-5
Aljubayrin SQi JJensen CZhang RHe ZLi Y(2017)Finding lowest-cost paths in settings with safe and preferred zonesThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-017-0455-826:3(373-397)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s00778-017-0455-8
Show More Cited By

Index Terms

ReHub: Extending Hub Labels for Reverse k-Nearest Neighbor Queries on Large-Scale Networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Shortest paths
    2. Streaming, sublinear and near linear time algorithms
      1. Nearest neighbor algorithms

Recommendations

Hub Labels on the database for large-scale graphs with the COLD framework

Shortest-path computation on graphs is one of the most well-studied problems in algorithmic theory. An aspect that has only recently attracted attention is the use of databases in combination with graph algorithms, so-called distance oracles, to compute ...
Constrained reverse nearest neighbor search on mobile objects
GIS '09: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

In this paper, we formalize the novel concept of Constrained Reverse k-Nearest Neighbor (CRkNN) search on mobile objects (clients) performed at a central server. The CRkNN query computes for a given query object q the set RkNN(q) of objects having q as ...
Reverse k-Nearest Neighbor monitoring on mobile objects
GIS '10: Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems

In this paper we focus on the problem of continuously monitoring the set of Reverse k-Nearest Neighbors (RkNNs) of a query object in a moving object database using a client server architecture. The RkNN monitoring query computes for a given query object ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Journal of Experimental Algorithmics

ACM Journal of Experimental Algorithmics Volume 21, Issue

Special Issue SEA 2014, Regular Papers and Special Issue ALENEX 2013

2016

404 pages

ISSN:1084-6654

EISSN:1084-6654

DOI:10.1145/2888418

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 November 2016

Accepted: 01 August 2016

Revised: 01 May 2016

Received: 01 July 2015

Published in JEA Volume 21

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Science Foundation
Research Programs for Excellence 2014-2016/CitySense-ATHENA R.I.C

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
253
Total Downloads

Downloads (Last 12 months)52
Downloads (Last 6 weeks)7

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li WCai MGao MWen DQin LWang W(2023)Expanding Reverse Nearest NeighborsProceedings of the VLDB Endowment10.14778/3636218.363622017:4(630-642)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.14778/3636218.3636220
Efentakis AEfstathiades CPfoser D(2017)Hub Labels on the database for large-scale graphs with the COLD frameworkGeoinformatica10.1007/s10707-016-0287-521:4(703-732)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s10707-016-0287-5
Aljubayrin SQi JJensen CZhang RHe ZLi Y(2017)Finding lowest-cost paths in settings with safe and preferred zonesThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-017-0455-826:3(373-397)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s00778-017-0455-8
Efentakis AEfstathiades CPfoser D(2015)COLD. Revisiting Hub Labels on the Database for Large-Scale GraphsAdvances in Spatial and Temporal Databases10.1007/978-3-319-22363-6_2(22-39)Online publication date: 13-Aug-2015
https://doi.org/10.1007/978-3-319-22363-6_2

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents