HP Labs Technical Reports

Click here for full text: Postscript PDF

Variable-Prefix Identifiers

Kent, William



Abstract: Prefixes provide uniqueness in identifiers which might not otherwise be unique, essentially subdividing the space of identified objects into "regions" which are identified in the prefix, such that the suffix values are unique within any one region. Fixed-length prefixes permanently fix the number of possible regions. If the overall identifier length is also fixed, hence fixing the suffix length, there is a further disadvantage that all regions must have the same capacity. Such identifiers must be designed from the outset with the prefix large enough to accommodate the maximum expected number of regions, while the suffix must be large enough to accommodate the region that will contain the most objects; suffix capacity is then wasted in regions which will contain fewer than this maximum number of objects. Variable-prefix identifiers overcome these disadvantages, even within the confines of a fixed overall identifier length. The main cost is the maintenance of a global table of prefixes, which does not have to be accessed very often.

Back to Index

[Research] [News] [Tech Reports] [Palo Alto] [Bristol] [Japan] [Israel] [Site Map] [Home] [Hewlett-Packard]