Extended K-D tree database organization: a dynamic multi-attribute clustering method
- 25 August 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The problem of performing multiple attribute clustering in a dynamic database is studied. The extended K-d tree method is presented. in an extended K-d tree organization, the basic k-d tree structure after modification is used as the struc ture of the directory which organizes the data records in the secondary storage. The discrimina tor value of each level of the directory determines the partitioning direction of the corresponding attribute subspace. When the record insertion causes the data page to overload, the attribute space will be further partitioned along the direction specified by the corresponding discriminator. For a given query, the number of disk accesses involved is estimated. The design of the discriminator function are then described.Keywords
This publication has 3 references indexed in Scilit:
- Multi-dimensional clustering for data base organizationsInformation Systems, 1977
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975
- Attribute based file organization in a paged memory environmentCommunications of the ACM, 1974