Published in

Elsevier, Information Systems, 4(36), p. 734-747, 2011

DOI: 10.1016/j.is.2011.01.002

Links

Tools

Export citation

Search in Google Scholar

Fully dynamic metric access methods based on hyperplane partitioning

Journal article published in 2011 by Gonzalo Navarro, Roberto Uribe Paredes ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Orange circle
Postprint: archiving restricted
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

Artículo de publicación ISI ; Metric access methods based on hyperplane partitioning have the advantage, compared to the ball partitioning-based ones, that regions do not overlap. The price is less flexibility for controlling the tree shape, especially in the dynamic scenario, that is, upon insertions and deletions of objects. In this paper we introduce a technique called ghost hyperplanes, which enables fully dynamic data structures based on hyperplane partitioning. We apply the technique to Brin's GNAT static index, obtaining a dynamic variant called EGNAT, which in addition we adapt to secondary memory. We show experimentally that the EGNAT is competitive with the M-tree, the baseline for this scenario. We also apply the ghost hyperplane technique to Voronoi trees, obtaining a competitive dynamic structure for main memory.