18

Taken from Introduction to Algorithms by Thomas Cormen:

To keep things simple, we assume, as we have for binary search trees and red-black trees, that any “satellite information” associated with a key is stored in the same node as the key. In practice, one might actually store with each key just a pointer to another disk page containing the satellite information for that key. The pseudocode in this chapter implicitly assumes that the satellite information associated with a key, or the pointer to such satellite information, travels with the key whenever the key is moved from node to node.

So I've been trying to Google the meaning of the term satellite information but I can't find any (covered by things about NASA). My understanding based on the text alone is that "satellite information" is an address to the location of the actual key value like a pointer? Am I correct or did I misunderstand it?

EDIT: What makes it different from a key?

2
  • The answer to your very last question is most certainly "Yes".
    – Kerrek SB
    Jan 27, 2013 at 20:26
  • 1
    @KerrekSB "did I misunderstand it?" that one.. Jan 27, 2013 at 20:27

1 Answer 1

27

Satellite data refers to any "payload" data which you want to store in your data structure and which is not part of the structure of the data structure. It can be anything you want. It can be a single value, a large collection of values, or a pointer to some other location that holds the value.

For example, here's a list node for a singly linked list whose satellite data is a single integer:

struct node
{
    node * next;
    int satellite;
};

In other words, the whole value of any given data structure lies in the data which it contains, which is the satellite data in your book's terminology. The data structure will additionally consume structural data (like the next pointer in the example) to perform the algorithms which define it, but those are essentially "overhead" from the user's perspective.

For associative containers, the "key" value performs a dual role: On the one hand it is user data, but on the other hand it is also part of the structure of the container. However, a tree can be equipped with additional satellite data, in which case it becomes a "map" from key data to satellite data.

At one extreme you have a fixed-size array which has no overhead and only payload data, and on the other extreme you have complicated structures like multiindexes, tries, Judy arrays, or lockfree containers which maintain a comparably large amount of structural data.

7
  • But what makes it different from a "key"? Jan 27, 2013 at 20:30
  • @vincentbelkin: The key is needed for the operation of the tree. Everything else isn't. Let me edit that.
    – Kerrek SB
    Jan 27, 2013 at 20:33
  • @vincentbelkin: The situation is even more confusing in a trie: The "values" of a trie are actually made up of lots of "key"s... but the point is that satellite data is never involved in the structural algorithms.
    – Kerrek SB
    Jan 27, 2013 at 20:37
  • 2
    ohh! like BST trees use their key values to determine where to insert the new node right? Jan 27, 2013 at 20:40
  • @vincentbelkin: Yes, right. The point of an associative data structure is that it incorporates the key into the structural arrangement of the data.
    – Kerrek SB
    Jan 27, 2013 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.