Boots – shoes – and leggings
Patent
1992-01-16
1995-01-03
Black, Thomas G.
Boots, shoes, and leggings
364252, 3642821, 364DIG1, G06F 1540, G06F 702
Patent
active
053794222
ABSTRACT:
A random sample is obtained from an inverted tree data structure by maintaining a cardinality estimate for each intermediate node in the tree, and selecting a leaf node at random by descending from the root node and performing an acceptance/rejection selection at each intermediate node weighted proportional to the cardinality estimates of the children and weighted inversely proportional to the cardinality estimate of the intermediate node. Even though the selection of an intermediate node is based upon only an estimate of the true cardinality of the intermediate node, the error in the estimate does not cause bias in the overall sampling method because any bias in the selection of the intermediate node is cancelled by an opposite bias in the selection of the child of the intermediate node. The cardinality estimates are maintained when a leaf is inserted or deleted from the data structure by checking whether the insertion or deletion causes the cardinality estimate of a parent of the leaf node to differ from the actual cardinality by a predetermined error bound, and if so, the cardinality estimate of the parent is updated, and the checking and updating process is escalated up the tree. The error bound is adjustable for balancing rejection rate during sampling against I/O overhead of cardinality maintenance during database updates.
REFERENCES:
patent: 4987536 (1991-01-01), Humblet
Aragon et al., "Randomized Search Trees", 1989 IEEE pp. 540-545.
D. Montgomery, Introduction to Statistical Quality Control, Wiley, 1985, pp. 23-55 and 351-429.
MS-DOS Version 3.3 Reference Guide, Compaq Computer Corporation (Feb. 1988), pp. 2-1 to 2-16 and 4-270 to 4-271.
Hobbs & England Rdb/VMS --A Comprehensive Guide, Digital Press, Digital Equipment Corp., Maynard, Mass. (1991).
Carey et al., "Object and File Management in the Exodus Extensible Database System," Proceedings of the Twelfth International Conference on Very Large Data Bases, Koyoto, (Aug. 1986), pp. 91-100.
Olken & Rotem, "Random Sampling from B+ trees," Proceedings of the Fifteenth International Conference on Very Large Data Bases, Amsterdam 1989, pp. 269-277.
Jaideep Srivastava, "A Tree Based Access Method (TBSAM) for Fast Processing of Aggregate Queries," Proceedings of the 4th International Conference on Data Engineering, IEEE Computer Society (1988), pp. 504-510.
Donald E. Kunth, The Art of Computer Programming, vol. 3, Sorting and Searching, Addison-Wesley Publishing Company, Menlow Park, Calif. (1979), pp. 462-479.
Basic Version 3.3 Reference Guide, 4th Edition, Compaq Computer Corporation (Sep. 1987), pp. 8-321 to 8-323 and 8-340 to 8-341.
Zhang Bo, et al., "A New Weighted Technique in Heuristic Search" (English abstract); Journal of Tsinghua University, vol. 26, No. 3, 1986, China, pp. 10-17.
Black Thomas G.
Digital Equipment Corporation
Orzech Jennifer M.
LandOfFree
Simple random sampling on pseudo-ranked hierarchical data struct does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Simple random sampling on pseudo-ranked hierarchical data struct, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simple random sampling on pseudo-ranked hierarchical data struct will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2218216