Ιδρυματικό Αποθετήριο [SANDBOX]
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

On a model of indexability and its bounds for range queries

Samoladas Vasilis, Koutsourias Elias, Miranker, Daniel P, Hellerstein, Joseph, 1952-, Papadimitriou, Christos H

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/8D1F3487-D2A0-43E8-A2D6-EDF966051916-
Αναγνωριστικόhttps://dl.acm.org/citation.cfm?doid=505241.505244-
Αναγνωριστικόhttps://doi.org/10.1145/505241.505244-
Γλώσσαen-
Μέγεθος22 pagesen
ΤίτλοςOn a model of indexability and its bounds for range queriesen
ΔημιουργόςSamoladas Vasilisen
ΔημιουργόςΣαμολαδας Βασιληςel
ΔημιουργόςKoutsourias Eliasen
ΔημιουργόςMiranker, Daniel Pen
ΔημιουργόςHellerstein, Joseph, 1952-en
ΔημιουργόςPapadimitriou, Christos Hen
ΕκδότηςAssociation for Computing Machineryen
ΠερίληψηWe develop a theoretical framework to characterize the hardness of indexing data sets on block-access memory devices like hard disks. We define an indexing workload by a data set and a set of potential queries. For a workload we can construct an indexing scheme, which is a collection of fixed-sized subsets of the data. We identify two measures of efficiency for an indexing scheme on a workload: storage redundancy, r (how many times each item in the data set is stored), and access overhead, A (how many times more blocks than necessary does a query retrieve). For many interesting families of workloads, there exists a trade-off between storage redundancy and access overhead. Given a desired access overhead A, there is a minimum redundancy that any indexing scheme must exhibit. We prove a lower-bound theorem for deriving the minimum redundancy. By applying this theorem we show interesting upper and lower bounds and trade-offs between A and r in the case of multi-dimensional range queries and set queries.en
ΤύποςPeer-Reviewed Journal Publicationen
ΤύποςΔημοσίευση σε Περιοδικό με Κριτέςel
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2015-10-16-
Ημερομηνία Δημοσίευσης2002-
Θεματική ΚατηγορίαInformation systemsen
Θεματική ΚατηγορίαData management systemsen
Θεματική ΚατηγορίαData structuresen
Θεματική ΚατηγορίαData access methodsen
Βιβλιογραφική ΑναφοράJ. Hellerstein, E. Koutsoupias, D. Miranker, C. Papadimitriou and V. Samoladas, "On a model of indexability and its Bounds for range queries," J ACM, vol. 49, no. 1, pp. 33-55, Jan. 2002. doi: 10.1145/505241.505244en

Υπηρεσίες

Στατιστικά