We introduce an innovative decomposition technique which reduces a multi-dimensional searching problem to a sequence of one-dimensional problems, each one easily manageable in optimal timer space complexity using traditional searching strategies. The reduction has no additional storage requirement and the time complexity to reconstruct the result of the original multi-dimensional query is linear in the dimension. More precisely, we show how to preprocess a set of S subset of or equal to INd of multi-dimensional objects into a data structure requiring O(mlogn) space, where m = \S\ and n is the maximum number of different values for each coordinate. The obtained data structure is implicit, i.e. does not use pointers, and is able to answer the exact match query in 7(d - 1) steps. Additionally the model of computation required for querying the data structure is very simple; the only arithmetic operation needed is the addition and no shift operation is used. The technique introduced, overcoming the multi-dimensional bottleneck, can be also applied to non traditional models of computation as external memory, distributed, and hierarchical environments. Additionally, we will show how the proposed technique permits the effective realizability of the well known perfect hashing techniques on real data. The algorithms for building the data structure are easy to implement and run in polynomial time.

Nardelli, E., Talamo, M., & Vocca, P. (1999). Efficient searching for multi-dimensional data made simple. In ALGORITHMS - ESA'99 (pp.339-353). BERLIN : SPRINGER-VERLAG BERLIN.

Efficient searching for multi-dimensional data made simple

NARDELLI, ENRICO;TALAMO, MAURIZIO;
1999

Abstract

We introduce an innovative decomposition technique which reduces a multi-dimensional searching problem to a sequence of one-dimensional problems, each one easily manageable in optimal timer space complexity using traditional searching strategies. The reduction has no additional storage requirement and the time complexity to reconstruct the result of the original multi-dimensional query is linear in the dimension. More precisely, we show how to preprocess a set of S subset of or equal to INd of multi-dimensional objects into a data structure requiring O(mlogn) space, where m = \S\ and n is the maximum number of different values for each coordinate. The obtained data structure is implicit, i.e. does not use pointers, and is able to answer the exact match query in 7(d - 1) steps. Additionally the model of computation required for querying the data structure is very simple; the only arithmetic operation needed is the addition and no shift operation is used. The technique introduced, overcoming the multi-dimensional bottleneck, can be also applied to non traditional models of computation as external memory, distributed, and hierarchical environments. Additionally, we will show how the proposed technique permits the effective realizability of the well known perfect hashing techniques on real data. The algorithms for building the data structure are easy to implement and run in polynomial time.
Annual European Symposium on Algorithms (ESA 99)
PRAGUE, CZECH REPUBLIC
JUL 16-18, 1999
7th
Ctr Discrete Math Theoret Comp Sci & Applicat, Charles Univ, Czech Acad Sci, Inst Chem Technol
Rilevanza internazionale
Settore INF/01 - Informatica
English
15
Intervento a convegno
Nardelli, E., Talamo, M., & Vocca, P. (1999). Efficient searching for multi-dimensional data made simple. In ALGORITHMS - ESA'99 (pp.339-353). BERLIN : SPRINGER-VERLAG BERLIN.
Nardelli, E; Talamo, M; Vocca, P
File in questo prodotto:
File Dimensione Formato  
ESA-99.pdf

non disponibili

Dimensione 168.92 kB
Formato Adobe PDF
168.92 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2108/33328
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 8
social impact