A Hexastore data structure
I only skimmed the paper for 10 seconds, but AFAICS, the fundamental idea (and the reason why it is called the Hexastore) is that the relationship triple (Subject, Relationship, Object) is stored in all 6 of its permutations separately:


(Subject, Relationship, Object)
(Subject, Object, Relationship)
(Object, Relationship, Subject)
(Object, Subject, Relationship)
(Relationship, Subject, Object)
(Relationship, Object, Subject)


Now, you can ask any question you want and the answers will only require a prefix search on the index.

Want to know about any relationship between Anna and Billy? Search for (A, B) or (B, A) (order doesn't matter since both are stored). Want to know all of Anna's Friends? Search for (A, f). Want to know about all married couples? Search for (m) and throw away every odd result. And so on.

Whether you are trying to find relationships between two fixed persons, finding a person that a fixed person has a fixed relationship with, finding all pairs of persons that have a particular relationship, finding all relationships a particular person has with anybody, all of that is fast because all of that is just an index search.

The paper does not actually store all six of those in the same index, rather they use six indices. (Whereas I believe the Redis article suggests to use a single index.)