HV/VH Trees: A New Spatial Data Structure for Fast Region Queries

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

doi:10.1145/157485.164562

HV/VH Trees: A New Spatial Data Structure for Fast Region Queries

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

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding

9 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 language	English
Title of host publication	30th ACM/IEEE Design Automation Conference - Proceedings 1993
Publisher	Association for Computing Machinery (ACM)
Pages	43-47
Number of pages	5
ISBN (Print)	0897915771, 9780897915779
DOIs	https://doi.org/10.1145/157485.164562
Publication status	Published - Jul 1993
Event	30th ACM/IEEE Design Automation Conference, DAC 1993 - Dallas, United States Duration: 14 Jun 1993 → 18 Jun 1993 https://dl.acm.org/doi/proceedings/10.1145/157485 https://ieeexplore.ieee.org/xpl/conhome/10664/proceeding

Publication series

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

Conference

Conference	30th ACM/IEEE Design Automation Conference, DAC 1993
Country/Territory	United States
City	Dallas
Period	14/06/93 → 18/06/93
Internet address	https://dl.acm.org/doi/proceedings/10.1145/157485 https://ieeexplore.ieee.org/xpl/conhome/10664/proceeding

User-Defined Keywords

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

Access to Document

10.1145/157485.164562

Cite this

@inproceedings{8503f391b77e420ea3d081835713d8d3,

title = "HV/VH Trees: A New Spatial Data Structure for Fast Region Queries",

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.",

keywords = "Tree data structures, Very large scale integration, Shape, Counting circuits, Testing, Performance evaluation, Geometry, Data structures",

author = "Lai, {Glenn G.} and Don Fussell and D.F. Wong",

year = "1993",

month = jul,

doi = "10.1145/157485.164562",

language = "English",

isbn = "0897915771",

series = "ACM/IEEE Design Automation Conference - Proceedings",

publisher = "Association for Computing Machinery (ACM)",

pages = "43--47",

booktitle = "30th ACM/IEEE Design Automation Conference - Proceedings 1993",

address = "United States",

note = "30th ACM/IEEE Design Automation Conference, DAC 1993 ; Conference date: 14-06-1993 Through 18-06-1993",

url = "https://dl.acm.org/doi/proceedings/10.1145/157485, https://ieeexplore.ieee.org/xpl/conhome/10664/proceeding",

}

Lai, GG, Fussell, D & Wong, DF 1993, HV/VH Trees: A New Spatial Data Structure for Fast Region Queries. in 30th ACM/IEEE Design Automation Conference - Proceedings 1993. ACM/IEEE Design Automation Conference - Proceedings, Association for Computing Machinery (ACM), pp. 43-47, 30th ACM/IEEE Design Automation Conference, DAC 1993, Dallas, Texas, United States, 14/06/93. https://doi.org/10.1145/157485.164562

HV/VH Trees: A New Spatial Data Structure for Fast Region Queries. / Lai, Glenn G.; Fussell, Don; Wong, D.F.
30th ACM/IEEE Design Automation Conference - Proceedings 1993. Association for Computing Machinery (ACM), 1993. p. 43-47 (ACM/IEEE Design Automation Conference - Proceedings).

Research output: Chapter in book/report/conference proceeding › Conference proceeding

TY - GEN

T1 - HV/VH Trees: A New Spatial Data Structure for Fast Region Queries

AU - Lai, Glenn G.

AU - Fussell, Don

AU - Wong, D.F.

PY - 1993/7

Y1 - 1993/7

N2 - 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.

AB - 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.

KW - Tree data structures

KW - Very large scale integration

KW - Shape

KW - Counting circuits

KW - Testing

KW - Performance evaluation

KW - Geometry

KW - Data structures

UR - https://dl.acm.org/doi/10.1145/157485.164562

UR - https://ieeexplore.ieee.org/document/1600190/

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-0027294301&origin=inward

U2 - 10.1145/157485.164562

DO - 10.1145/157485.164562

M3 - Conference proceeding

SN - 0897915771

SN - 9780897915779

T3 - ACM/IEEE Design Automation Conference - Proceedings

SP - 43

EP - 47

BT - 30th ACM/IEEE Design Automation Conference - Proceedings 1993

PB - Association for Computing Machinery (ACM)

T2 - 30th ACM/IEEE Design Automation Conference, DAC 1993

Y2 - 14 June 1993 through 18 June 1993

ER -

HV/VH Trees: A New Spatial Data Structure for Fast Region Queries

Abstract

Publication series

Conference

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this