Skip to main content

(csei2)data structures for dynamic lists in computational science applications


EMSL Project ID
2190

Abstract

This account is requested to implement and benchmark sub-logarithmic access data structures developed by the CS&E LDRD project of the same name. Recent advances in data structures have resulted in sequential search algorithms for integer keys whose is O (log (n)**0.5) and O (log (log (n))) at worst. These structures rely on so-called exponential trees whose node size increases by a constant factor from the leaf level to the root level. An exponential tree with n keys has an O (log (log (n))) depth. This is advantageous on distributed system where remote memory accesses are more expensive than local memory accesses. The root holds O (n**0.2) keys and can become very large. The SMP nodes of Jupiter and ECS1 are ideally suited for managing the larger internal nodes of an otherwise distributed exponential trees.

Project Details

Project type
Capability Research
Start Date
2002-04-20
End Date
2002-10-01
Status
Closed

Team

Principal Investigator

Joel Malard
Institution
SIMUCAD Design Automation

Team Members

Robert Stewart
Institution
Purdue University