Back to Search
Start Over
Reverse Furthest Neighbors Query in Road Networks
- Source :
- Journal of Computer Science and Technology. 32:155-167
- Publication Year :
- 2017
- Publisher :
- Springer Science and Business Media LLC, 2017.
-
Abstract
- Given a road network G = (V,E), where V (E) denotes the set of vertices(edges) in G, a set of points of interest P and a query point q residing in G, the reverse furthest neighbors (RfnR) query in road networks fetches a set of points p ∈ P that take q as their furthest neighbor compared with all points in P ∪ {q}. This is the monochromatic RfnR (MrfnR) query. Another interesting version of RfnR query is the bichromatic reverse furthest neighbor (BrfnR) query. Given two sets of points P and Q, and a query point q ∈ Q, a BrfnR query fetches a set of points p ∈ P that take q as their furthest neighbor compared with all points in Q. This paper presents efficient algorithms for both MrfnR and BrfnR queries, which utilize landmarks and partitioning-based techniques. Experiments on real datasets confirm the efficiency and scalability of proposed algorithms.
- Subjects :
- Theoretical computer science
Computer science
02 engineering and technology
Computer Science Applications
Theoretical Computer Science
Set (abstract data type)
Combinatorics
Computational Theory and Mathematics
Hardware and Architecture
020204 information systems
Road networks
Scalability
0202 electrical engineering, electronic engineering, information engineering
020201 artificial intelligence & image processing
Point (geometry)
Software
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- ISSN :
- 18604749 and 10009000
- Volume :
- 32
- Database :
- OpenAIRE
- Journal :
- Journal of Computer Science and Technology
- Accession number :
- edsair.doi...........8ccc6c3b56b21582794614c7707bfa24
- Full Text :
- https://doi.org/10.1007/s11390-017-1711-5