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

Fingerprint

Data structures
Data storage equipment

ASJC Scopus subject areas

  • Engineering(all)

Cite this

Lai, G. G., Fussell, D., & Wong, D. F. (1993). HV/VH trees: a new spatial data structure for fast region queries. In Proceedings - Design Automation Conference (pp. 43-47). (Proceedings - Design Automation Conference). Publ by IEEE.

HV/VH trees : a new spatial data structure for fast region queries. / Lai, Glenn G.; Fussell, Don; Wong, D. F.

Proceedings - Design Automation Conference. Publ by IEEE, 1993. p. 43-47 (Proceedings - Design Automation Conference).

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

Lai, GG, Fussell, D & Wong, DF 1993, HV/VH trees: a new spatial data structure for fast region queries. in Proceedings - Design Automation Conference. Proceedings - Design Automation Conference, Publ by IEEE, pp. 43-47, Proceedings of the 30th ACM/IEEE Design Automation Conference, Dallas, TX, USA, 6/14/93.
Lai GG, Fussell D, Wong DF. HV/VH trees: a new spatial data structure for fast region queries. In Proceedings - Design Automation Conference. Publ by IEEE. 1993. p. 43-47. (Proceedings - Design Automation Conference).
Lai, Glenn G. ; Fussell, Don ; Wong, D. F. / HV/VH trees : a new spatial data structure for fast region queries. Proceedings - Design Automation Conference. Publ by IEEE, 1993. pp. 43-47 (Proceedings - Design Automation Conference).
@inproceedings{654bd6d97c394ecd8e404cf2159c5ad4,
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 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.",
author = "Lai, {Glenn G.} and Don Fussell and Wong, {D. F.}",
year = "1993",
month = "1",
day = "1",
language = "English (US)",
isbn = "0897915771",
series = "Proceedings - Design Automation Conference",
publisher = "Publ by IEEE",
pages = "43--47",
booktitle = "Proceedings - Design Automation Conference",

}

TY - GEN

T1 - HV/VH trees

T2 - a new spatial data structure for fast region queries

AU - Lai, Glenn G.

AU - Fussell, Don

AU - Wong, D. F.

PY - 1993/1/1

Y1 - 1993/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=0027294301&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027294301&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0027294301

SN - 0897915771

T3 - Proceedings - Design Automation Conference

SP - 43

EP - 47

BT - Proceedings - Design Automation Conference

PB - Publ by IEEE

ER -