Dismiss
The InnovationQ application will be updated on Sunday, May 31st from 10am-noon ET. You may experience brief service interruptions during that time.
Browse Prior Art Database

Construction of Optimal Binary Split Trees

IP.com Disclosure Number: IPCOM000041436D
Original Publication Date: 1984-Jan-01
Included in the Prior Art Database: 2005-Feb-02

Publishing Venue

IBM

Related People

Authors:
Huang, SH Wong, CK [+details]

Abstract

Split trees are a new technique for storing records with skewed frequency distribution, where the conflicting functions of frequency ordering and subtree construction are decoupled. A polynomial time algorithm to construct optimal binary split trees is described below. The crucial idea in such trees is that two values are stored in each node, one of them being the key, the other being a split value. The split value is used as a guide for further search in the tree if the key value is not equal to the search value. Note that the record associated with the split value is not stored in the node but in one of its subtrees. Given a set of n keys k1, ..., kn and their access probabilities p(k1), ...