Dynamic pipelining of multidimensional range queries
| Autor: | Duch Brown, Amalia|||0000-0003-4371-1286, Lugosi, Daniel, Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977, Zoltan Torres, Ana Cristina |
|---|---|
| Přispěvatelé: | Universitat Politècnica de Catalunya. Departament de Ciències de la Computació, Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals |
| Předmět: | |
| Zdroj: | Recercat. Dipósit de la Recerca de Catalunya instname UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) |
| Popis: | The problem of evaluating orthogonal range queries efficiently has been studied widely in the data structures community. It has been common wisdom for several years that for queries containing more than 20% of the elements of the dataset a linear scanning of the data was the most efficient solution. In recent experimental works using modern hardware –with main memory and parallelism– the conclusion is that linear scan is preferable for almost every query configuration (even containing a 1% of the data). In this work we propose an alternative approach to evaluate multidimensional range queries based on the dynamic pipeline paradigm –using main memory and concurrency. Our aim is to prove that under this framework, it is possible to beat the performance of linear scanning by the one of hierarchical multidimensional data structures –such as kd trees, quad trees, Rtrees or similar. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|