On data partitioning in tree structure metric-space indexes

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

doi:10.1007/978-3-319-05810-8_10

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 Proceedings › Conference paper (refereed) › peer-review

6 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 language	English
Title of host publication	Database Systems for Advanced Applications : 19th International Conference, DASFAA 2014, Bali, Indonesia, April 21-24, 2014. Proceedings, Part I
Editors	Sourav S. BHOWMICK, Curtis E. DYRESON , Christian S. JENSEN , Mong Li LEE , Agus MULIANTARA , Bernhard THALHEIM
Place of Publication	Springer
Pages	141-155
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-319-05810-8_10
Publication status	Published - 2014
Externally published	Yes
Event	The 19th International Conference on Database Systems for Advanced Applications - Aerowisata Sanur Beach Hotel, Bali, Indonesia Duration: 21 Apr 2014 → 24 Apr 2014 https://www.comp.nus.edu.sg/~dasfaa14/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
ISSN (Print)	0302-9743

Conference

Conference	The 19th International Conference on Database Systems for Advanced Applications
Abbreviated title	DASFAA 2014
Country/Territory	Indonesia
City	Bali
Period	21/04/14 → 24/04/14
Internet address	https://www.comp.nus.edu.sg/~dasfaa14/

Keywords

data partitioning
metric-space access method
pivot space model

Access to Document

10.1007/978-3-319-05810-8_10

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

MAO, Rui ; LIU, Sheng ; XU, Honglong ; ZHANG, Dian ; MIRANKER, Daniel P. / On data partitioning in tree structure metric-space indexes. Database Systems for Advanced Applications : 19th International Conference, DASFAA 2014, Bali, Indonesia, April 21-24, 2014. Proceedings, Part I. editor / Sourav S. BHOWMICK ; Curtis E. DYRESON ; Christian S. JENSEN ; Mong Li LEE ; Agus MULIANTARA ; Bernhard THALHEIM. Springer, 2014. pp. 141-155 (Lecture Notes in Computer Science).

@inproceedings{491625b16a944c75b0613050e5d22a60,

title = "On data partitioning in tree structure metric-space indexes",

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.",

keywords = "data partitioning, metric-space access method, pivot space model",

author = "Rui MAO and Sheng LIU and Honglong XU and Dian ZHANG and MIRANKER, {Daniel P.}",

year = "2014",

doi = "10.1007/978-3-319-05810-8_10",

language = "English",

isbn = "9783319058092",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "141--155",

editor = "BHOWMICK, {Sourav S.} and {DYRESON }, {Curtis E.} and {JENSEN }, {Christian S.} and {LEE }, {Mong Li} and {MULIANTARA }, Agus and THALHEIM, {Bernhard }",

booktitle = "Database Systems for Advanced Applications : 19th International Conference, DASFAA 2014, Bali, Indonesia, April 21-24, 2014. Proceedings, Part I",

note = "The 19th International Conference on Database Systems for Advanced Applications, DASFAA 2014 ; Conference date: 21-04-2014 Through 24-04-2014",

url = "https://www.comp.nus.edu.sg/~dasfaa14/",

}

MAO, R, LIU, S, XU, H, ZHANG, D & MIRANKER, DP 2014, On data partitioning in tree structure metric-space indexes. in SS BHOWMICK, CE DYRESON , CS JENSEN , ML 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. Lecture Notes in Computer Science, Springer, pp. 141-155, The 19th International Conference on Database Systems for Advanced Applications, Bali, Indonesia, 21/04/14. https://doi.org/10.1007/978-3-319-05810-8_10

On data partitioning in tree structure metric-space indexes. / MAO, Rui; LIU, Sheng; XU, Honglong; ZHANG, Dian; MIRANKER, Daniel P.

Database Systems for Advanced Applications : 19th International Conference, DASFAA 2014, Bali, Indonesia, April 21-24, 2014. Proceedings, Part I. ed. / Sourav S. BHOWMICK; Curtis E. DYRESON ; Christian S. JENSEN ; Mong Li LEE ; Agus MULIANTARA ; Bernhard THALHEIM. Springer, 2014. p. 141-155 (Lecture Notes in Computer Science).

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › peer-review

TY - GEN

T1 - On data partitioning in tree structure metric-space indexes

AU - MAO, Rui

AU - LIU, Sheng

AU - XU, Honglong

AU - ZHANG, Dian

AU - MIRANKER, Daniel P.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - data partitioning

KW - metric-space access method

KW - pivot space model

UR - http://www.scopus.com/inward/record.url?scp=84900309870&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-05810-8_10

DO - 10.1007/978-3-319-05810-8_10

M3 - Conference paper (refereed)

AN - SCOPUS:84900309870

SN - 9783319058092

T3 - Lecture Notes in Computer Science

SP - 141

EP - 155

BT - Database Systems for Advanced Applications : 19th International Conference, DASFAA 2014, Bali, Indonesia, April 21-24, 2014. Proceedings, Part I

A2 - BHOWMICK, Sourav S.

A2 - DYRESON , Curtis E.

A2 - JENSEN , Christian S.

A2 - LEE , Mong Li

A2 - MULIANTARA , Agus

A2 - THALHEIM, Bernhard

CY - Springer

T2 - The 19th International Conference on Database Systems for Advanced Applications

Y2 - 21 April 2014 through 24 April 2014

ER -

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

On data partitioning in tree structure metric-space indexes

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this