Histogram domain ordering for path selectivity estimation

N. Yakovets; Li Wang; G.H.L. Fletcher; Craig Taverner; Alexandra Poulovassilis

doi:10.5441/002/edbt.2018.55

Histogram domain ordering for path selectivity estimation

N. Yakovets, Li Wang, G.H.L. Fletcher, Craig Taverner, Alexandra Poulovassilis

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

141 Downloads (Pure)

Abstract

We aim to improve the accuracy of path selectivity estimation in graph databases by intelligently ordering the domain of a histogram used for estimation. This problem has not, to our knowledge, received adequate attention in the research community. We present a novel framework for the systematic study of path ordering strategies in histogram construction and use. In this framework, we introduce new ordering strategies which we experimentally demonstrate lead to significant improvement of the accuracy of path selectivity estimation over current strategies. These positive results highlight the fundamental role that domain ordering plays in the design of effective histograms for efficient and scalable graph query processing.

Original language	English
Title of host publication	Advances in Database Technology - EDBT 2018
Subtitle of host publication	21st International Conference on Extending Database Technology, Proceedings
Editors	Michael Bohlen, Reinhard Pichler, Norman May, Erhard Rahm, Shan-Hung Wu, Katja Hose
Publisher	OpenProceedings.org
Pages	493-496
Number of pages	4
ISBN (Electronic)	978-3-89318-078-3
DOIs	https://doi.org/10.5441/002/edbt.2018.55
Publication status	Published - 2018
Event	EDBT/ICDT 2018 Joint Conference 21st International Conference on Extending Database Technology - Vienna, Austria Duration: 26 Mar 2018 → 29 Mar 2018

Conference

Conference	EDBT/ICDT 2018 Joint Conference 21st International Conference on Extending Database Technology
Country/Territory	Austria
City	Vienna
Period	26/03/18 → 29/03/18

Access to Document

10.5441/002/edbt.2018.55

published versionFinal published version, 2.77 MB

Cite this

Yakovets, N., Wang, L., Fletcher, G. H. L., Taverner, C., & Poulovassilis, A. (2018). Histogram domain ordering for path selectivity estimation. In M. Bohlen, R. Pichler, N. May, E. Rahm, S.-H. Wu, & K. Hose (Eds.), Advances in Database Technology - EDBT 2018: 21st International Conference on Extending Database Technology, Proceedings (pp. 493-496). OpenProceedings.org. https://doi.org/10.5441/002/edbt.2018.55

Yakovets, N. ; Wang, Li ; Fletcher, G.H.L. et al. / Histogram domain ordering for path selectivity estimation. Advances in Database Technology - EDBT 2018: 21st International Conference on Extending Database Technology, Proceedings. editor / Michael Bohlen ; Reinhard Pichler ; Norman May ; Erhard Rahm ; Shan-Hung Wu ; Katja Hose. OpenProceedings.org, 2018. pp. 493-496

@inproceedings{798497ae66104c6ca90953d7382361c7,

title = "Histogram domain ordering for path selectivity estimation",

abstract = "We aim to improve the accuracy of path selectivity estimation in graph databases by intelligently ordering the domain of a histogram used for estimation. This problem has not, to our knowledge, received adequate attention in the research community. We present a novel framework for the systematic study of path ordering strategies in histogram construction and use. In this framework, we introduce new ordering strategies which we experimentally demonstrate lead to significant improvement of the accuracy of path selectivity estimation over current strategies. These positive results highlight the fundamental role that domain ordering plays in the design of effective histograms for efficient and scalable graph query processing.",

author = "N. Yakovets and Li Wang and G.H.L. Fletcher and Craig Taverner and Alexandra Poulovassilis",

year = "2018",

doi = "10.5441/002/edbt.2018.55",

language = "English",

pages = "493--496",

editor = "Michael Bohlen and Reinhard Pichler and Norman May and Erhard Rahm and Shan-Hung Wu and Katja Hose",

booktitle = "Advances in Database Technology - EDBT 2018",

publisher = "OpenProceedings.org",

note = "EDBT/ICDT 2018 Joint Conference 21st International Conference on Extending Database Technology ; Conference date: 26-03-2018 Through 29-03-2018",

}

Yakovets, N, Wang, L, Fletcher, GHL, Taverner, C & Poulovassilis, A 2018, Histogram domain ordering for path selectivity estimation. in M Bohlen, R Pichler, N May, E Rahm, S-H Wu & K Hose (eds), Advances in Database Technology - EDBT 2018: 21st International Conference on Extending Database Technology, Proceedings. OpenProceedings.org, pp. 493-496, EDBT/ICDT 2018 Joint Conference 21st International Conference on Extending Database Technology, Vienna, Austria, 26/03/18. https://doi.org/10.5441/002/edbt.2018.55

Histogram domain ordering for path selectivity estimation. / Yakovets, N.; Wang, Li; Fletcher, G.H.L. et al.
Advances in Database Technology - EDBT 2018: 21st International Conference on Extending Database Technology, Proceedings. ed. / Michael Bohlen; Reinhard Pichler; Norman May; Erhard Rahm; Shan-Hung Wu; Katja Hose. OpenProceedings.org, 2018. p. 493-496.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Histogram domain ordering for path selectivity estimation

AU - Yakovets, N.

AU - Wang, Li

AU - Fletcher, G.H.L.

AU - Taverner, Craig

AU - Poulovassilis, Alexandra

PY - 2018

Y1 - 2018

N2 - We aim to improve the accuracy of path selectivity estimation in graph databases by intelligently ordering the domain of a histogram used for estimation. This problem has not, to our knowledge, received adequate attention in the research community. We present a novel framework for the systematic study of path ordering strategies in histogram construction and use. In this framework, we introduce new ordering strategies which we experimentally demonstrate lead to significant improvement of the accuracy of path selectivity estimation over current strategies. These positive results highlight the fundamental role that domain ordering plays in the design of effective histograms for efficient and scalable graph query processing.

AB - We aim to improve the accuracy of path selectivity estimation in graph databases by intelligently ordering the domain of a histogram used for estimation. This problem has not, to our knowledge, received adequate attention in the research community. We present a novel framework for the systematic study of path ordering strategies in histogram construction and use. In this framework, we introduce new ordering strategies which we experimentally demonstrate lead to significant improvement of the accuracy of path selectivity estimation over current strategies. These positive results highlight the fundamental role that domain ordering plays in the design of effective histograms for efficient and scalable graph query processing.

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

U2 - 10.5441/002/edbt.2018.55

DO - 10.5441/002/edbt.2018.55

M3 - Conference contribution

SP - 493

EP - 496

BT - Advances in Database Technology - EDBT 2018

A2 - Bohlen, Michael

A2 - Pichler, Reinhard

A2 - May, Norman

A2 - Rahm, Erhard

A2 - Wu, Shan-Hung

A2 - Hose, Katja

PB - OpenProceedings.org

T2 - EDBT/ICDT 2018 Joint Conference 21st International Conference on Extending Database Technology

Y2 - 26 March 2018 through 29 March 2018

ER -

Yakovets N, Wang L, Fletcher GHL, Taverner C, Poulovassilis A. Histogram domain ordering for path selectivity estimation. In Bohlen M, Pichler R, May N, Rahm E, Wu SH, Hose K, editors, Advances in Database Technology - EDBT 2018: 21st International Conference on Extending Database Technology, Proceedings. OpenProceedings.org. 2018. p. 493-496 doi: 10.5441/002/edbt.2018.55

Histogram domain ordering for path selectivity estimation

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this