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 | |
| Publication status | Published - 2014 |
| Externally published | Yes |
| Event | 19th International Conference on Database Systems for Advanced Applications, DASFAA 2014 - Bali, Indonesia Duration: 21 Apr 2014 → 24 Apr 2014 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer Verlag |
| ISSN (Print) | 0302-9743 |
Conference
| Conference | 19th International Conference on Database Systems for Advanced Applications, DASFAA 2014 |
|---|---|
| Country | Indonesia |
| City | Bali |
| Period | 21/04/14 → 24/04/14 |
Fingerprint
Keywords
- data partitioning
- metric-space access method
- pivot space model
Cite this
}
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) › Research › 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)
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
ER -