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)

Abstract

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
Pages392-407
Number of pages16
EditionPART 2
DOIs
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

Conference

Conference23rd International Conference on Database and Expert Systems Applications, DEXA 2012
CountryAustria
CityVienna
Period3/09/126/09/12

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this