ORE Ontology GEM Implementation

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 backward	Append after last loaded	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 one by URI	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

Analysis of Triple Store Data Structure

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)

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 + faster iteration than traversing next links (may not be significant)
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.

List Header Info

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	points to first item on fetch updated to next/prev item during traversal points to last modified item when changes are made
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

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

Page tree