All-visible-k-nearest-neighbor queries

Yafei Wang, Yunjun Gao, Lu Chen, Gang Chen, Qing Li

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

9 Citations (Scopus)


The All-k-Nearest-Neighbor (AkNN) operation is common in many applications such as GIS and data analysis/mining. In this paper, for the first time, we study a novel variant of AkNN queries, namely All-Visible-k-Nearest-Neighbor (AVkNN) query, which takes into account the impact of obstacles on the visibility of objects. Given a data set P, a query set Q, and an obstacle set O, an AVkNN query retrieves for each point/object in Q its visible k nearest neighbors in P. We formalize the AVkNN query, and then propose efficient algorithms for AVkNN retrieval, assuming that P, Q, and O are indexed by conventional data-partitioning indexes (e.g., R-trees). Our approaches employ pruning techniques and introduce a new pruning metric called VMDIST. Extensive experiments using both real and synthetic datasets demonstrate the effectiveness of our presented pruning techniques and the performance of our proposed algorithms.

Original languageEnglish
Title of host publicationDatabase and Expert Systems Applications - 23rd International Conference, DEXA 2012, Proceedings
Number of pages16
EditionPART 2
Publication statusPublished - 14 Sep 2012
Externally publishedYes
Event23rd International Conference on Database and Expert Systems Applications, DEXA 2012 - Vienna, Austria
Duration: 3 Sep 20126 Sep 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 2
Volume7447 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference23rd International Conference on Database and Expert Systems Applications, DEXA 2012

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'All-visible-k-nearest-neighbor queries'. Together they form a unique fingerprint.

Cite this