Towards an Instance-Optimal Z-Index

Sachith Gopalakrishna Pai; Michael Mathioudakis; Yanhao Wang

Towards an Instance-Optimal Z-Index

Sachith Gopalakrishna Pai, Michael Mathioudakis, Yanhao Wang

Research output: Conference materials › Paper › peer-review

Abstract

We present preliminary results on instance-optimal variants of the Z-index, a well-known spatial index that makes use of the Z-order curve. Unlike the base Z-index, the variants we propose aim to adapt to the data and range-query workloads of the given setting. Specifically, we provide an optimal algorithm that builds a Z-index that minimizes the expected number of retrieved data points for the given data and query workload. Moreover, since the optimal algorithm requires supra-linear running time, we additionally propose efficient heuristic algorithms to use in its place. Our experiments evaluate the performance of the resultant Z-indexes.

Original language	English
Number of pages	4
Publication status	Published - 5 Sept 2022
MoE publication type	Not Eligible
Event	4th International Workshop on Applied AI for Database Systems and Applications (AIDB@VLDB2022) - Sydney, Australia Duration: 5 Sept 2022 → … https://sites.google.com/view/aidb2022/home

Workshop

Workshop	4th International Workshop on Applied AI for Database Systems and Applications (AIDB@VLDB2022)
Country/Territory	Australia
City	Sydney
Period	05/09/2022 → …
Internet address	https://sites.google.com/view/aidb2022/home

Fields of Science

113 Computer and information sciences

Access to Document

Towards_Learned_ZIndex_camera_readyAccepted author manuscript, 1.74 MBLicence: CC BY

https://drive.google.com/file/d/1KvvEOzlZ7vt78eyB8k5XdQT5XF2nFngM/view?usp=sharing

Cite this

@conference{78b9b61d86644fe3a09fbdab568a0f9d,

title = "Towards an Instance-Optimal Z-Index",

abstract = "We present preliminary results on instance-optimal variants of the Z-index, a well-known spatial index that makes use of the Z-order curve. Unlike the base Z-index, the variants we propose aim to adapt to the data and range-query workloads of the given setting. Specifically, we provide an optimal algorithm that builds a Z-index that minimizes the expected number of retrieved data points for the given data and query workload. Moreover, since the optimal algorithm requires supra-linear running time, we additionally propose efficient heuristic algorithms to use in its place. Our experiments evaluate the performance of the resultant Z-indexes.",

keywords = "113 Computer and information sciences",

author = "Pai, {Sachith Gopalakrishna} and Michael Mathioudakis and Yanhao Wang",

year = "2022",

month = sep,

day = "5",

language = "English",

note = "4th International Workshop on Applied AI for Database Systems and Applications (AIDB@VLDB2022) ; Conference date: 05-09-2022",

url = "https://sites.google.com/view/aidb2022/home",

}

TY - CONF

T1 - Towards an Instance-Optimal Z-Index

AU - Pai, Sachith Gopalakrishna

AU - Mathioudakis, Michael

AU - Wang, Yanhao

PY - 2022/9/5

Y1 - 2022/9/5

N2 - We present preliminary results on instance-optimal variants of the Z-index, a well-known spatial index that makes use of the Z-order curve. Unlike the base Z-index, the variants we propose aim to adapt to the data and range-query workloads of the given setting. Specifically, we provide an optimal algorithm that builds a Z-index that minimizes the expected number of retrieved data points for the given data and query workload. Moreover, since the optimal algorithm requires supra-linear running time, we additionally propose efficient heuristic algorithms to use in its place. Our experiments evaluate the performance of the resultant Z-indexes.

AB - We present preliminary results on instance-optimal variants of the Z-index, a well-known spatial index that makes use of the Z-order curve. Unlike the base Z-index, the variants we propose aim to adapt to the data and range-query workloads of the given setting. Specifically, we provide an optimal algorithm that builds a Z-index that minimizes the expected number of retrieved data points for the given data and query workload. Moreover, since the optimal algorithm requires supra-linear running time, we additionally propose efficient heuristic algorithms to use in its place. Our experiments evaluate the performance of the resultant Z-indexes.

KW - 113 Computer and information sciences

UR - https://sites.google.com/view/aidb2022/home

M3 - Paper

T2 - 4th International Workshop on Applied AI for Database Systems and Applications (AIDB@VLDB2022)

Y2 - 5 September 2022

ER -

Towards an Instance-Optimal Z-Index

Abstract

Workshop

Fields of Science

Access to Document

Other files and links

MLDB: Model Management Systems: Machine learning meets Database Systems

Cite this

Towards an Instance-Optimal Z-Index

Abstract

Workshop

Fields of Science

Access to Document

Other files and links

Projects

MLDB: Model Management Systems: Machine learning meets Database Systems

Cite this