Table of Contents
Data Structure Approaches
In-memory Processing | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Triple Store Data Structure | In-memory Data Structure | Direct access at loaded position | Direct access URI as ID (pre-loaded) | Iteration foward | Iteration | Append | Append after global last | Insert after loaded item | Insert before loaded item | Insert after loaded position | Insert before loaded position | Delete loaded item | Delete from loaded position | Fetch one by global position | Fetch | Fetch range | Fetch next range | Persist one at global position | Persist one by URI | Persist range | List size | Issues | ORE Compliance | Comments |
doubly linked list | ||||||||||||||||||||||||
doubly linked list | NO | SLOW | FAST | FAST | FAST | FAST | FAST | FAST | NO | NO | FAST | NO | NO | FAST | SLOW | SLOW | NO | FAST | SLOW | NO | ||||
convert to array on fetch | FAST | SLOW | FAST | FAST | FAST | FAST | FAST | FAST | FAST | FAST | FAST | FAST | NO | FAST | SLOW | SLOW | NO | FAST | SLOW | NO | ||||
convert to hash (key=proxy URI) on fetch | NO | FAST | FAST | FAST | FAST | FAST | FAST | FAST | NO | NO | FAST | NO | NO | FAST | SLOW | SLOW | NO | FAST | SLOW | NO | ||||
doubly linked list + order index | ||||||||||||||||||||||||
doubly linked list | SLOW | SLOW | FAST | FAST | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | FAST | SLOW | SLOW | SLOW | FAST | SLOW | FAST | ||||
convert to array on fetch | FAST | SLOW | FAST | FAST | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | FAST | SLOW | SLOW | SLOW | FAST | SLOW | FAST | ||||
convert to hash (key=proxy URI) on fetch | SLOW | FAST | FAST | FAST | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | FAST | SLOW | SLOW | SLOW | FAST | SLOW | FAST |
NOTE: All operations are available by adding order index to each proxy for the list as a triple in the triplestore, but most operations that change the list become very slow as it requires updates to all items after the effected item. Delete could be made fast be allowing for missing index values, but then list size becomes a slow operation.
List Header Info
Lists with headers will hold the following information.
example value types | Comments | |||||
---|---|---|---|---|---|---|
key | description of value | doubly linked | doubly linked + order | array | hash | |
first | pointer to first item in list | URI of first proxy | URI of first proxy | URI of first proxy | URI of first proxy | |
last | pointer to last item in list | URI of last proxy | URI of last proxy | URI of last proxy | URI of last proxy | |
count | count of all items in list | X | X | X | X | |
first_loaded | pointer to first item in loaded range of items | item | item | array[0] | URI of first loaded proxy | |
current | pointer to current item | item | item | int cpos | URI of current proxy | |
last_loaded | pointer to last item in loaded range of items | item | item | array[size of array] | URI of last loaded proxy | |
count_loaded | count of items in currently loaded range | X | =position of last - position of first | size of array | size of hash | |
resume_token | pointer to item after last_loaded | URI of proxy | URI of proxy | URI of proxy | URI of proxy | |
loaded_items | pointer to loaded items | use first_loaded | use first_loaded | array | hash |
List Item Info
example value types | ||||||
---|---|---|---|---|---|---|
key | description of value | doubly linked | doubly linked + order | array | hash | Comments |
uri | URI of proxy for this item | URI of this proxy | URI of this proxy | URI of this proxy | URI of this proxy | This is the hash key for loaded_items when the list is implemented as a hash. |
prev | pointer to previous item in list | URI of prev proxy | URI of prev proxy | = p - 1 | URI of prev proxy | |
next | pointer to next item in list | URI of next proxy | URI of next proxy | = p + 1 | URI of next proxy | |
prev_loaded | pointer to previous item in loaded range of items | prev item | prev item | = pl - 1 | URI of prev proxy | |
next_loaded | pointer to next item in loaded range of items | next item | next item | = pl + 1 | URI of next proxy | |
proxyFor | URI of list item being aggregated | URI | URI | URI | URI | |
proxyIn | URI of list aggregation | URI of aggregation | URI of aggregation | URI of aggregation | URI of aggregation | |
proxyIn_loaded | pointer to List Header | header | header | header | header | |
position (p) | position in full list | X | p | p | X | |
position_loaded (pl) | position in loaded range of items | X | pl | pl | X |