On data partitioning in tree structure metric-space indexes

Rui MAO, Sheng LIU, Honglong XU, Dian ZHANG*, Daniel P. MIRANKER

*Corresponding author for this work

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

5 Citations (Scopus)

Abstract

Tree structure metric-space indexing methods recursively partition data according to their distances to a set of selected reference points (also called pivots). There are two basic forms of data partitioning: ball partition and General Hyper-plane (GH) partition. Most existing work only shows their superiority experimentally, and little theoretical proof is found. We propose an approach to unify existing data partitioning methods and analyze their performance theoretically. First, in theory, we unify the two basic forms of partitioning by proving that there are rotations of each other. Second, we show several theoretical or experimental results, which are able to indicate that ball partition outperforms GH partition. Our work takes a step forward in the theoretical study of metric-space indexing and is able to give a guideline of future index design.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications : 19th International Conference, DASFAA 2014, Bali, Indonesia, April 21-24, 2014. Proceedings, Part I
EditorsSourav S. BHOWMICK, Curtis E. DYRESON , Christian S. JENSEN , Mong Li LEE , Agus MULIANTARA , Bernhard THALHEIM
Place of PublicationSpringer
Pages141-155
Number of pages15
DOIs
Publication statusPublished - 2014
Externally publishedYes
EventThe 19th International Conference on Database Systems for Advanced Applications - Aerowisata Sanur Beach Hotel, Bali, Indonesia
Duration: 21 Apr 201424 Apr 2014
https://www.comp.nus.edu.sg/~dasfaa14/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
ISSN (Print)0302-9743

Conference

ConferenceThe 19th International Conference on Database Systems for Advanced Applications
Abbreviated titleDASFAA 2014
CountryIndonesia
CityBali
Period21/04/1424/04/14
Internet address

    Fingerprint

Keywords

  • data partitioning
  • metric-space access method
  • pivot space model

Cite this

MAO, R., LIU, S., XU, H., ZHANG, D., & MIRANKER, D. P. (2014). On data partitioning in tree structure metric-space indexes. In S. S. BHOWMICK, C. E. DYRESON , C. S. JENSEN , M. L. LEE , A. MULIANTARA , & B. THALHEIM (Eds.), Database Systems for Advanced Applications : 19th International Conference, DASFAA 2014, Bali, Indonesia, April 21-24, 2014. Proceedings, Part I (pp. 141-155). (Lecture Notes in Computer Science).. https://doi.org/10.1007/978-3-319-05810-8_10