...
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 | YES | ||||
| 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 | YES | ||||
| 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 | YES | key=proxy URI | |||
| doubly linked list + order index | |||||||||||||||||||||||||
| doubly linked list | SLOW | SLOW | FAST | FAST | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | FAST | SLOWFAST | SLOW | SLOW | FAST | SLOW | FAST | YES | ||||
| convert to array on fetch | FAST | SLOW | FAST | FAST | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | FAST | SLOWFAST | SLOW | SLOW | FAST | SLOW | FAST | YES | ||||
| convert to hash (key=proxy URI) on fetch | SLOW | FAST | FAST | FAST | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | FAST | SLOWFAST | SLOW | SLOW | FAST | SLOW | FAST | YES | key=proxy URI | |||
...
Analysis of Triple Store Data Structure
| Triple Store Data Structure | Pros | Cons | Comments |
|---|---|---|---|
| doubly linked list | + all updates effect at most 3 items (prev, current, and next) | - requires traversal of links during fetch (i.e. fetch each item individually - one query for each item) | |
| doubly linked list + order index | + much faster fetch retrieving all items in the range with a single query | - adding/removing items from list can be very slow when item is early in the list (worst case touches all list items) |
Analysis of In-memory Data Structure
| In-memory Data Structure | Pros | Cons | Comments |
|---|---|---|---|
| doubly linked list | + least amount of processing during fetch (probably not significant relative to overall processing required) | - iteration requires traversing next links | |
| convert to array on fetch | + allows for fast access by position to loaded items | ||
| convert to hash on fetch | + allows for fast fast access by proxy URI to loaded items | - iteration requires traversing next links | I anticipate the need to have direct access by proxy URI more than positional. |
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.
...