Hierarchical List

Much of the information used in the Financial industry, as well as many others, in naturally hierarchical in nature. For example, a user may be managing a set of portfolios, each made up of different asset types, with these further sub-divided by region, then by sector, then by security. In short, a Hierarchical Model is one where the information is naturally viewed as a tree, and the user can open or close parts of the tree (nodes) to access additional information.

Many modern list/grid components support hierarchical data - examples in different programming languages include TreeModel in Java and the HierarchicalCollectionView in Flex. Each of these models provide mechanisms to their respective views to access the hierarchical data as if it was one big flattened list instead of a complex hierarchy.

A list structure designed for performance normally include the following features:

• Data items can be referenced by index
• Accessing a data item at any index should take the same amount of time regardless of list size
• THere are no constraints on the values of data items in the list e.g. uniqueness
• Changes to the list are notified by events enabling interested parties to update any references accordingly.

 

However, existing hierarchical models share similar limitations:

• No concept of an item index within the hierarchy
• Cannot easily access an an object by list position
• Objects often need to be unique with the hierarchy
• Position in the hierarchy is stateful and generally stored by complex hierarchy of cursors
• Reacting to modifications in parts of the model generally invalidates the entire model and cursors on the model

While these restrictions are bearable for small static hierarchies, once a hierarchy grows, it becomes extremely performance-intensive to locate items in the hierarchy, move to random positions in the hierarchy and reacting to change events makes the model extremely sluggish.

Representing hierarchical data was an important goal of KineticGrid but I experienced poor performance issues with the Flex HierarchicalCollectionView (and lack of support for some change events). As a result, I wanted to create a Hierarchical List that was able to treat a hierarchical data model exactly the same as it could treat a flat list of data without significant performance degradation as the list got very large.

Small aside: one issue I had to solve with KineticGrid was how to calculate and maintain the content height of the Data Grid (that supports different row heights) in the face of continuous model updates. For example, in a grid with 100 rows with a default height of 20 pixels, the content height would be 2000 pixels. If rows 20 and 70 had a row height of 50, then the content height would be 2060 i.e. 98 * 20 + 50 + 50. Now, when I move my scroll bar so content position 1000 is at the top of the screen, the layout needs to determine which row to display, taking into account the increased height of row 20 but not of row 70. As this is a frequent process, the times needed for these calculations needs to be constant, it needs to be scalable, it needs to be able to react to delete/add/move operations with constant time, and preferably needs low memory usage. To address this, I create a sparse differential balanced tree, capable of performing all height-specific operations in O(log(n)), where n is the number of rows with non-default heights.

For the KineticGrid Hierarchical List I used a similar structure to above to represent the open children of a single node in the hierarchical model and then created a hierarchical tree of these structures. The end result: For a tree with a max depth of d, and a maximum number of open nodes at any level of n, then the worse case performance for all operations is O(d log(n)).

Compared to the default hierarchical model:

• Every item is the hierarchy is identified by its unique index
• Items are always accessed by list index rather than by identity
• There are no uniqueness constraints
• There are no cursors as invalidation takes more time than accessing directly
• All modifications to any part of the model i.e. add/remove/update/move are processed by the list in O(d log(n)) - worst case - and emitted as normal list events

Currently the list is implemented in ActionScript 3.0 - Java will be available shortly.

 

The Hierarchical List can be seen in action in the Financials Demo which has a maximum model size of 80,000 rows and a depth of 4 representing Currency Pair, Active Orders, Dependent Orders, Dependent Orders.