Table of Contents
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 | 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 on fetch | NO | FAST | FAST | FAST | FAST | FAST | FAST | FAST | NO | NO | FAST | NO | NO | FAST | SLOW | SLOW | NO | FAST | SLOW | NO | 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 | FAST | SLOW | SLOW | FAST | SLOW | FAST | ||
convert to array on fetch | FAST | SLOW | FAST | FAST | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | SLOW | FAST | FAST | 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 | FAST | SLOW | SLOW | FAST | SLOW | FAST | key=proxy URI |
Triple Store Data Structure | Pros | Cons | Comments |
---|---|---|---|
doubly linked list | + all updates effect at most 3 items (i.e., 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 a range (i.e., single query gets all items) | - adding/removing items from list can be very slow when item is early in the list (worst case touches all list items) |
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. |
User is browsing the list starting from the beginning, displaying N items at a time with the ability to move forward and back through the display of N items.
Display information is not part of ORE triples. For example, proxyFor is a URI to a book which has a DC.title, DC.description, etc. Would like to be able to add this information to each ListItemInfo structure and pass that to the UI code for display.
User is browsing the list and drags an item to a new position in the list.
User is browsing the catalog and decides to add one or more bibliographic references to the list. Add items defaults to append to end of list.
User chooses to sort list items by a display value that is not stored as part of the triples associated with the ORE list triples. For example, the list is aggregating bibliographic references. The properties of the bibliographic references may be stored in a separate triplestore. Example sort criteria are title, publication date,
The list header info will be a hash. It holds information about the list as a whole and the currently loaded range of items as a sub-structure. The values for the list information stored depends on the type of the loaded items sub-structure. The loaded items sub-structure holds items as a group are in-memory using one of four possible grouping methods: doubly linked lists, doubly linked lists + order index, array, or hash with proxy URI as the key. NOTE: Order index is global to the entire list. The array and hash implementations may also have this global order index information stored with the item info.
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 | last.index | last.index | last.index | Count for full list is available for array and hash when order index is stored in triplestore. |
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_next_token | pointer to item after last_loaded | URI of proxy | URI of proxy | URI of proxy | URI of proxy | |
resume_prev_token | pointer to item just before first_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 |
Each item's info is stored in a hash. It holds information about the individual item. The loaded items as a group are in-memory using one of four possible grouping methods: doubly linked lists, doubly linked lists + order index, array, or hash with proxy URI as the key.
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 | p | Position in full list is available for array and hash when order index is stored in triplestore. |
position_loaded (pl) | position in loaded range of items | X | pl | pl | X |