HV/VH trees: a new spatial data structure for fast region queries

Glenn G. Lai, Don Fussell, D. F. Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Rosenberg compared linked lists, quad trees with bisector lists, and kD trees, and showed that kD trees significantly outperformed their two rivals on region queries. Quad trees bisector lists performed poorly because of their need to search bisector lists at successive levels, therefore, later improvements to quad trees look the form of eliminating the bisector lists in one way or the other to achieve better region-query performed. In this paper, we explode the myth that bisector lists imply slow region queries by introducing a new data structure, HV/VH trees, which, even though it uses bisector lists, is as fast as than kD trees and two improved forms of quad trees on region queries performed on data from real VLSI designs. Furthermore, we show that HV/VH trees achieve this superb performance while using the least amount of memory.

Original languageEnglish (US)
Title of host publicationProceedings - Design Automation Conference
PublisherPubl by IEEE
Pages43-47
Number of pages5
ISBN (Print)0897915771
StatePublished - Jan 1 1993
Externally publishedYes
EventProceedings of the 30th ACM/IEEE Design Automation Conference - Dallas, TX, USA
Duration: Jun 14 1993Jun 18 1993

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0146-7123

Other

OtherProceedings of the 30th ACM/IEEE Design Automation Conference
CityDallas, TX, USA
Period6/14/936/18/93

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint

Dive into the research topics of 'HV/VH trees: a new spatial data structure for fast region queries'. Together they form a unique fingerprint.

Cite this