| dc.date.accessioned |
2013-11-19T13:54:32Z |
und |
| dc.date.accessioned |
2017-10-24T12:24:40Z |
|
| dc.date.available |
2013-11-19T13:54:32Z |
und |
| dc.date.available |
2017-10-24T12:24:40Z |
|
| dc.date.issued |
2013-11-19T13:54:32Z |
|
| dc.identifier.uri |
http://radr.hulib.helsinki.fi/handle/10138.1/3253 |
und |
| dc.identifier.uri |
http://hdl.handle.net/10138.1/3253 |
|
| dc.title |
Online algorithms for partially ordered sets |
en |
| ethesis.discipline |
Computer science |
en |
| ethesis.discipline |
Tietojenkäsittelytiede |
fi |
| ethesis.discipline |
Datavetenskap |
sv |
| ethesis.discipline.URI |
http://data.hulib.helsinki.fi/id/1dcabbeb-f422-4eec-aaff-bb11d7501348 |
|
| ethesis.department.URI |
http://data.hulib.helsinki.fi/id/225405e8-3362-4197-a7fd-6e7b79e52d14 |
|
| ethesis.department |
Institutionen för datavetenskap |
sv |
| ethesis.department |
Department of Computer Science |
en |
| ethesis.department |
Tietojenkäsittelytieteen laitos |
fi |
| ethesis.faculty |
Matematisk-naturvetenskapliga fakulteten |
sv |
| ethesis.faculty |
Matemaattis-luonnontieteellinen tiedekunta |
fi |
| ethesis.faculty |
Faculty of Science |
en |
| ethesis.faculty.URI |
http://data.hulib.helsinki.fi/id/8d59209f-6614-4edd-9744-1ebdaf1d13ca |
|
| ethesis.university.URI |
http://data.hulib.helsinki.fi/id/50ae46d8-7ba9-4821-877c-c994c78b0d97 |
|
| ethesis.university |
Helsingfors universitet |
sv |
| ethesis.university |
University of Helsinki |
en |
| ethesis.university |
Helsingin yliopisto |
fi |
| dct.creator |
Herranen, Mikko |
|
| dct.issued |
2013 |
|
| dct.language.ISO639-2 |
eng |
|
| dct.abstract |
Partially ordered sets (posets) have various applications in computer science ranging from database systems to distributed computing. Content-based routing in publish/subscribe systems is a major poset use case. Content-based routing requires efficient poset online algorithms, including efficient insertion and deletion algorithms. We study the query and total complexities of online operations on posets and poset-like data structures. The main data structures considered are the incidence matrix, Siena poset, ChainMerge, and poset-derived forest. The contributions of this thesis are twofold: First, we present an online adaptation of the ChainMerge data structure as well as several novel poset-derived forest variants. We study the effectiveness of a first-fit-equivalent ChainMerge online insertion algorithm and show that it performs close to optimal query-wise while requiring less CPU processing in a benchmark setting. Second, we present the results of an empirical performance evaluation. In the evaluation we compare the data structures in terms of query complexity and total complexity. The results indicate ChainMerge as the best structure overall. The incidence matrix, although simple, excels in some benchmarks. Poset-derived forest is very fast overall if a 'true' poset data structure is not a requirement. Placing elements in smaller poset-derived forests and then merging them is an efficient way to construct poset-derived forests. Lazy evaluation for poset-derived forests shows some promise as well. |
en |
| dct.language |
en |
|
| ethesis.language.URI |
http://data.hulib.helsinki.fi/id/languages/eng |
|
| ethesis.language |
English |
en |
| ethesis.language |
englanti |
fi |
| ethesis.language |
engelska |
sv |
| ethesis.thesistype |
pro gradu-avhandlingar |
sv |
| ethesis.thesistype |
pro gradu -tutkielmat |
fi |
| ethesis.thesistype |
master's thesis |
en |
| ethesis.thesistype.URI |
http://data.hulib.helsinki.fi/id/thesistypes/mastersthesis |
|
| dct.identifier.urn |
URN:NBN:fi-fe2017112251363 |
|
| dc.type.dcmitype |
Text |
|
