A primogenitary linked quad tree data structure and its application to discrete multiple criteria optimization

Minghe Sun ()

Annals of Operations Research, 2006, vol. 147, issue 1, 87-107

Abstract: A data structure called the primogenitary linked quad tree is developed. Each node in the data structure has a pointer to its parent, a pointer to its immediate existing younger sibling, a pointer to its eldest existing son, and an integer as its successorship to its parent. To access any other son of a node, the first-born existing son must be accessed first. The siblings of the same parent are managed as a linked list. This data structure is an extension or enhancement of the traditional quad tree data structure. The primogenitary linked quad tree is applied to discrete multiple criteria optimization for the identification, storage, and retrieval of nondominated criterion vectors. Algorithms managing this data structure are developed and implemented. Major advantages of using the primogenitary linked quad tree instead of the traditional quad tree are savings in memory or storage space and savings in execution time. Examples are provided to demonstrate the application. A computational experiment is conducted to test the performances of the data structure and the algorithms. Computational results show that this data structure uses only a small fraction of the CPU time used by the traditional quad tree to perform the same task. Using this data structure, the identification, storage and retrieval of nondominated criterion vectors become an easy task for discrete multiple criteria optimization problems with many criteria and hundreds of thousands criterion vectors. This data structure can also be used for storage and retrieval of data with composite keys in other applications. Copyright Springer Science + Business Media, LLC 2006

Keywords: Data structures; Quad tree; Primogenitary linked quad tree; Multiple criteria optimization; Multiple criteria decision making (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-006-0063-2 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:147:y:2006:i:1:p:87-107:10.1007/s10479-006-0063-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-006-0063-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().