Home // GEOProcessing 2025, The Seventeenth International Conference on Advanced Geographic Information Systems, Applications, and Services // View article

DPS: A Novel Approach for Efficient Direction-Based Neighborhood Queries

Authors:
Pedro Henrique Bergamo Bertolli
Marcela Xavier Ribeiro

Keywords: Spatial databases; surrounding queries; efficient processing; directional diversity.

Abstract:
Current spatial search methods predominantly focus on distance-based metrics, while direction-based queries have emerged to address applications requiring diverse directional coverage. Existing direction-based approaches like the Direction-Based Surrounder (DBS) and Direction-Aware Nearest Neighbor (DNN) employ iterative algorithms that require examining multiple objects and their spatial relationships, leading to high computational costs particularly in dense datasets. These methods also suffer from either overly restricted results (DBS) or directionally clustered outcomes (DNN) due to their selection criteria. This paper introduces Direction Proximity Search (DPS), a novel approach that ensures directional diversity—defined as having at most one object per angular interval—while significantly reducing computational overhead. By employing geometric space partitioning to divide the search space into equal angular regions and a refinement phase that selects the nearest object per directional interval, DPS eliminates the need for extensive object-to-object comparisons. Experiments on both synthetic and real datasets show that DPS achieves processing time reductions of up to 99.9% specifically for high-density distributions (Bit and Sierpinski) with large datasets, while consistently maintaining the desired directional diversity property across all tested configurations.

Pages: 62 to 69

Copyright: Copyright (c) IARIA, 2025

Publication date: May 18, 2025

Published in: conference

ISSN: 2308-393X

ISBN: 978-1-68558-269-2

Location: Nice, France

Dates: from May 18, 2025 to May 22, 2025