I would like to be able to make O(1) time random samples of elements of a DOM tree. The minimal usable thing would be a random DOM element according to any distribution with full support. Any of the following, if done, would be more useful: - Allow distribution with support only on leaves or DOM nodes of certain types. - Allow a uniform distribution over candidate nodes. - Allow a representation-length-uniform distribution over candidate nodes. - Allow limiting the distribution to a subset of all the elements defined by a start and end fractions, i.e. "give me an node which is located, in preorder/postorder/inorder after at least a 0.2 fraction of the nodes and before a 0.4 fraction of them" (this can be simulated using a uniform distribution, but at a hefty price in the O() constants). - Provide a O(1) time estimate of relative position of a node in a DOM tree (w.r.t. some order). If you're wondering what this is good for, think: probabilistic heuristics on (very, but not necessarily all that) large documents.