An O(1) solution to the prefix sum problem on a specialized memory architecture

In this paper we study the Prefix Sum problem introduced by Fredman. We show that it is possible to perform both update and retrieval in O(1) time simultaneously under a memory model in which individual bits may be shared by several words. We also show that two variants (generalizations) of the prob...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Brodnik, Andrej, Karlsson, Johan, Munro, J. Ian, Nilsson, Andreas
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2006
Materias:
Ciencias Informáticas
random access machine (RAM)
Modeling
Bounded-action devices (e.g., Turing machines, random access machines)
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/24379
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-24379
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
random access machine (RAM)
Modeling
Bounded-action devices (e.g., Turing machines, random access machines)
spellingShingle Ciencias Informáticas
random access machine (RAM)
Modeling
Bounded-action devices (e.g., Turing machines, random access machines)
Brodnik, Andrej
Karlsson, Johan
Munro, J. Ian
Nilsson, Andreas
An O(1) solution to the prefix sum problem on a specialized memory architecture
topic_facet Ciencias Informáticas
random access machine (RAM)
Modeling
Bounded-action devices (e.g., Turing machines, random access machines)
description In this paper we study the Prefix Sum problem introduced by Fredman. We show that it is possible to perform both update and retrieval in O(1) time simultaneously under a memory model in which individual bits may be shared by several words. We also show that two variants (generalizations) of the problem can be solved optimally in Θ (lgN) time under the comparison based model of computation.
format Objeto de conferencia
Objeto de conferencia
author Brodnik, Andrej
Karlsson, Johan
Munro, J. Ian
Nilsson, Andreas
author_facet Brodnik, Andrej
Karlsson, Johan
Munro, J. Ian
Nilsson, Andreas
author_sort Brodnik, Andrej
title An O(1) solution to the prefix sum problem on a specialized memory architecture
title_short An O(1) solution to the prefix sum problem on a specialized memory architecture
title_full An O(1) solution to the prefix sum problem on a specialized memory architecture
title_fullStr An O(1) solution to the prefix sum problem on a specialized memory architecture
title_full_unstemmed An O(1) solution to the prefix sum problem on a specialized memory architecture
title_sort o(1) solution to the prefix sum problem on a specialized memory architecture
publishDate 2006
url http://sedici.unlp.edu.ar/handle/10915/24379
work_keys_str_mv AT brodnikandrej ano1solutiontotheprefixsumproblemonaspecializedmemoryarchitecture
AT karlssonjohan ano1solutiontotheprefixsumproblemonaspecializedmemoryarchitecture
AT munrojian ano1solutiontotheprefixsumproblemonaspecializedmemoryarchitecture
AT nilssonandreas ano1solutiontotheprefixsumproblemonaspecializedmemoryarchitecture
AT brodnikandrej o1solutiontotheprefixsumproblemonaspecializedmemoryarchitecture
AT karlssonjohan o1solutiontotheprefixsumproblemonaspecializedmemoryarchitecture
AT munrojian o1solutiontotheprefixsumproblemonaspecializedmemoryarchitecture
AT nilssonandreas o1solutiontotheprefixsumproblemonaspecializedmemoryarchitecture
bdutipo_str Repositorios
_version_ 1764820467047202816

Ejemplares similares