(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
Released Data Link
Team
Principal Investigator
Team Members