4.3. Positioning and Tracking 53Figure 4.5 Different cases for p( s| s) at the junction point of a pathway: 1) 0-jumpwith constant p( s| s)=p( s)3. 2) Elevated p( s| s) due to long line of sight. 3) Mediumline of sight. 4) Reduced p( s| s) due to short line of sight. 5) p( s| s)= 0 due toblocking material.performing model that excludes most of the invalid path hypothesis and complieswith the patterns of natural walking.The last approach to fine tune the transition model, is given by adjusting p( s| s)to the length of the line of sight in the direction defined by the jump from s to s.More free space in jump direction leads to elevated p( s| s) whereas less free space,i.e. standing before a wall, gives a penalty on p( s| s). Employing this techniquesupports the natural moving direction in long pathways at the cost of paths thatlead directly before furniture or tables. See examples 2, 3 and 4 in figure 4.5.4.3.1.4 PruningThe viterbi algorithm is made more efficient by pruning unlikely hypothesis from thesearch space. This is motivated by the observation, that a lot of the intermediatehypothesis have a very low probability as they are terminal states of paths that arefar away from the real position. This induces a large number of mismatching RSSreadings leading to very low emission probabilities. A problem, that can arise byremoving unlikely hypothesis from the search space, is encountered if the pruningis to aggressive and removes hypothesis that are unlikely in the some time framet but will become later the most probable. In this case, the best hypothesis, thebest matching path to the measurements, is not found and the quality of the resultdegrades. It was sufficient to retain only the top 6% hypothesis of the search space,which are around 3000 in the UMIC scene, without loosing relevant hypothesis.Although the parallelizability of the Viterbi Algorithm is negatively affected, asthere is more shared data needed, leading to more critical sections, a speedup ofaround factor 10 is archived.A crucial data structure for an efficient implementation of the pruning viterbi decoderis a skiplist(William Pugh, 1990), which is needed to keep track of the top Nhypothesis during the evaluation of a time frame. The skiplist represents a list ofpermanently sorted items, here the top hypothesis, with insertion cost of O( log( n))during decoding. Although the data structure can be implemented to allow for