Gustavo Lau
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Gustavo Lau has a total of 2 co-authors. Here are the top co-authors by number of shared publications:
- Amalia Duch
Universitat Politècnica de Catalunya, Barcelona Tech
2 shared publications - Conrado Martínez
Universitat Politecnica de Catalunya
1 shared publication
Latest Publications
- 4 January 2017
- Published by Society for Industrial & Applied Mathematics (SIAM)
Partial Match Queries in Relaxed K-dt trees
The study of partial match queries on random hierarchical multidimensional data structures dates back to Ph. Flajolet and C. Puech's 1986 seminal paper on partial match retrieval. It was not until recently that fixed (as opposed to random) partial match queries were studied for random relaxed K-d trees, random standard K-d trees, and random 2-dimensional quad trees. Based on those results it seemed natural to classify the general form of the cost of fixed partial match queries into two families: that of either random hierarchical structures or perfectly balanced structures, as conjectured by Duch, Lau and Martínez (On the Cost of Fixed Partial Queries in K-d trees Algorithmica, 75(4):684–723, 2016). Here we show that the conjecture just mentioned does not hold by introducing relaxed K-dt trees and providing the average-case analysis for random partial match queries as well as some advances on the average-case analysis for fixed partial match queries on them. In fact this cost –for fixed partial match queries– does not follow the conjectured forms.
- 4 January 2017
- Published by Society for Industrial & Applied Mathematics (SIAM)
Partial Match Queries in Relaxed K-dt trees
The study of partial match queries on random hierarchical multidimensional data structures dates back to Ph. Flajolet and C. Puech's 1986 seminal paper on partial match retrieval. It was not until recently that fixed (as opposed to random) partial match queries were studied for random relaxed K-d trees, random standard K-d trees, and random 2-dimensional quad trees. Based on those results it seemed natural to classify the general form of the cost of fixed partial match queries into two families: that of either random hierarchical structures or perfectly balanced structures, as conjectured by Duch, Lau and Martínez (On the Cost of Fixed Partial Queries in K-d trees Algorithmica, 75(4):684–723, 2016). Here we show that the conjecture just mentioned does not hold by introducing relaxed K-dt trees and providing the average-case analysis for random partial match queries as well as some advances on the average-case analysis for fixed partial match queries on them. In fact this cost –for fixed partial match queries– does not follow the conjectured forms.
- 11 December 2015
- Published by Springer Nature in Algorithmica
- Vol. 75 (4) , 684-723
On the Cost of Fixed Partial Match Queries in K-d Trees
- 11 December 2015
- Published by Springer Nature in Algorithmica
- Vol. 75 (4) , 684-723
On the Cost of Fixed Partial Match Queries in K-d Trees