Please use this identifier to cite or link to this item:
Title: Achieving optimal average data node storage utilization in k-dimensional point data indexes
Authors: Outsios, Evangelos
Evangelidis, Georgios
Type: Article
Subjects: FRASCATI::Natural sciences::Computer and information sciences
Keywords: Indexing of k-dimensional point data
Point Access Methods
Issue Date: 2011
Source: International Journal on Integrated Information Management
Abstract: Indexing of k-dimensional point data is becoming again a hot research topic because of the need to efficiently index and retrieve high dimensional vectors (points) in data mining applications. The most common query on such vectors is kNN searching, which is a variation of range searching. Most multidimensional indexes for point data follow the paradigm of the ubiquitous B+tree and store data entries at the leaf level of the index (data nodes). Since this level naturally occupies the majority of nodes in a multidimensional index tree, it is crucial that an index structure achieves the best possible average storage utilization regardless of data distribution and order of data insertion. An additional conflicting goal is the minimization of the index term that is posted at the levels above when data nodes are split. In this paper we revisit data node splitting techniques for point access methods like the KDB-tree, hB-tree, and, in general, any index that stores point data at its leaf level nodes and splits them so that no overlapping subspaces are created at the leaf level. We experiment with various splitting techniques that produce the minimum index term for posting but differ in the shape of the resulting nodes and the average storage utilization. We also test our splitting techniques using uniform and skewed data distributions. The comparison is on the average data node storage utilization and the efficiency of range query searches.
ISSN: 2241-827X
Other Identifiers: 10.15556/IJIIM.01.01.003
Appears in Collections:Department of Applied Informatics

Files in This Item:
File Description SizeFormat 
2011_IJIIM_outsios.pdf274,55 kBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons