Density-based reverse nearest neighbourhood search in spatial databases

Nasser Allheeib, Md Saiful Islam, David Taniar, Zhou Shao, Muhammad Aamir Cheema

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

The widespread use of location-aware services and technologies which retrieve or answer spatial queries has received much interest in today’s society. An increasing number of popular applications, such as digital maps, make use of spatial databases and associated technologies. One of the most important branches of traditional spatial queries is the reverse nearest neighbour (RNN) search. This search retrieves points of interest that consider the query facility as the nearest facility. Most of the existing works on spatial databases only focus on point of interest retrieval. There is barely any work on a region of interest or neighbourhood retrieval. In this paper, we introduce the concept of a group version of reverse nearest neighbour queries called reverse nearest neighbourhood (RNNH) queries. The RNNH query finds all possible reverse nearest neighbourhoods where all the neighbourhoods consider the query facility as the nearest facility. We propose an efficient algorithm for processing snapshot RNNH queries by using R-tree index. The proposed algorithm incrementally retrieves all reverse nearest neighbourhoods of the query facility. We have conducted exhaustive experiments on both real and synthetic datasets to demonstrate the superiority of the proposed algorithm.

Original languageEnglish
Number of pages12
JournalJournal of Ambient Intelligence and Humanized Computing
DOIs
Publication statusAccepted/In press - 2019

Keywords

  • Influence zone
  • Query processing algorithm
  • Reverse nearest neighbourhood
  • Voronoi diagram

Cite this

@article{fdca33c4c85e4f4890d0a18a1adc8fbd,
title = "Density-based reverse nearest neighbourhood search in spatial databases",
abstract = "The widespread use of location-aware services and technologies which retrieve or answer spatial queries has received much interest in today’s society. An increasing number of popular applications, such as digital maps, make use of spatial databases and associated technologies. One of the most important branches of traditional spatial queries is the reverse nearest neighbour (RNN) search. This search retrieves points of interest that consider the query facility as the nearest facility. Most of the existing works on spatial databases only focus on point of interest retrieval. There is barely any work on a region of interest or neighbourhood retrieval. In this paper, we introduce the concept of a group version of reverse nearest neighbour queries called reverse nearest neighbourhood (RNNH) queries. The RNNH query finds all possible reverse nearest neighbourhoods where all the neighbourhoods consider the query facility as the nearest facility. We propose an efficient algorithm for processing snapshot RNNH queries by using R-tree index. The proposed algorithm incrementally retrieves all reverse nearest neighbourhoods of the query facility. We have conducted exhaustive experiments on both real and synthetic datasets to demonstrate the superiority of the proposed algorithm.",
keywords = "Influence zone, Query processing algorithm, Reverse nearest neighbourhood, Voronoi diagram",
author = "Nasser Allheeib and Islam, {Md Saiful} and David Taniar and Zhou Shao and Cheema, {Muhammad Aamir}",
year = "2019",
doi = "10.1007/s12652-018-1103-x",
language = "English",
journal = "Journal of Ambient Intelligence and Humanized Computing",
issn = "1868-5137",
publisher = "Springer-Verlag London Ltd.",

}

Density-based reverse nearest neighbourhood search in spatial databases. / Allheeib, Nasser; Islam, Md Saiful; Taniar, David; Shao, Zhou; Cheema, Muhammad Aamir.

In: Journal of Ambient Intelligence and Humanized Computing, 2019.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Density-based reverse nearest neighbourhood search in spatial databases

AU - Allheeib, Nasser

AU - Islam, Md Saiful

AU - Taniar, David

AU - Shao, Zhou

AU - Cheema, Muhammad Aamir

PY - 2019

Y1 - 2019

N2 - The widespread use of location-aware services and technologies which retrieve or answer spatial queries has received much interest in today’s society. An increasing number of popular applications, such as digital maps, make use of spatial databases and associated technologies. One of the most important branches of traditional spatial queries is the reverse nearest neighbour (RNN) search. This search retrieves points of interest that consider the query facility as the nearest facility. Most of the existing works on spatial databases only focus on point of interest retrieval. There is barely any work on a region of interest or neighbourhood retrieval. In this paper, we introduce the concept of a group version of reverse nearest neighbour queries called reverse nearest neighbourhood (RNNH) queries. The RNNH query finds all possible reverse nearest neighbourhoods where all the neighbourhoods consider the query facility as the nearest facility. We propose an efficient algorithm for processing snapshot RNNH queries by using R-tree index. The proposed algorithm incrementally retrieves all reverse nearest neighbourhoods of the query facility. We have conducted exhaustive experiments on both real and synthetic datasets to demonstrate the superiority of the proposed algorithm.

AB - The widespread use of location-aware services and technologies which retrieve or answer spatial queries has received much interest in today’s society. An increasing number of popular applications, such as digital maps, make use of spatial databases and associated technologies. One of the most important branches of traditional spatial queries is the reverse nearest neighbour (RNN) search. This search retrieves points of interest that consider the query facility as the nearest facility. Most of the existing works on spatial databases only focus on point of interest retrieval. There is barely any work on a region of interest or neighbourhood retrieval. In this paper, we introduce the concept of a group version of reverse nearest neighbour queries called reverse nearest neighbourhood (RNNH) queries. The RNNH query finds all possible reverse nearest neighbourhoods where all the neighbourhoods consider the query facility as the nearest facility. We propose an efficient algorithm for processing snapshot RNNH queries by using R-tree index. The proposed algorithm incrementally retrieves all reverse nearest neighbourhoods of the query facility. We have conducted exhaustive experiments on both real and synthetic datasets to demonstrate the superiority of the proposed algorithm.

KW - Influence zone

KW - Query processing algorithm

KW - Reverse nearest neighbourhood

KW - Voronoi diagram

UR - http://www.scopus.com/inward/record.url?scp=85055999628&partnerID=8YFLogxK

U2 - 10.1007/s12652-018-1103-x

DO - 10.1007/s12652-018-1103-x

M3 - Article

JO - Journal of Ambient Intelligence and Humanized Computing

JF - Journal of Ambient Intelligence and Humanized Computing

SN - 1868-5137

ER -