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 proceeding

8 Citations (Scopus)

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 with bisector lists performed poorly because of their need to search bisector lists at successive levels; therefore, later improvements to quad trees took the form of eliminating the bisector lists in one way or the other to achieve better region-query performance. 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 or faster 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 perfomance while using the least amount of memory.
Original languageEnglish
Title of host publication30th ACM/IEEE Design Automation Conference - Proceedings 1993
PublisherAssociation for Computing Machinery (ACM)
Pages43-47
Number of pages5
ISBN (Print)0897915771, 9780897915779
DOIs
Publication statusPublished - Jul 1993
Event30th ACM/IEEE Design Automation Conference, DAC 1993 - Dallas, United States
Duration: 14 Jun 199318 Jun 1993
https://dl.acm.org/doi/proceedings/10.1145/157485
https://ieeexplore.ieee.org/xpl/conhome/10664/proceeding

Publication series

NameACM/IEEE Design Automation Conference - Proceedings
ISSN (Print)0738-100X

Conference

Conference30th ACM/IEEE Design Automation Conference, DAC 1993
Country/TerritoryUnited States
CityDallas
Period14/06/9318/06/93
Internet address

User-Defined Keywords

  • Tree data structures
  • Very large scale integration
  • Shape
  • Counting circuits
  • Testing
  • Performance evaluation
  • Geometry
  • Data structures

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