Den ökande volymen av tidsbaserade genererade data och den förändrade lagringstekniken tyder på att vi kan behöva ompröva indexeringen. Flera arbetsbelastningar -som social och serviceövervakning - inkluderar ofta attribut med implicit klusterbildning på grund av sin tidsberoende natur. Dessutom framträder solid state disks (SSD) (med hjälp av flash eller annan lågnivåteknik) som livskraftiga konkurrenter till hårddiskar (HDD). Lagringsenheters kapacitet och åtkomsttider skapar en kompromiss mellan SSD och HDD. Långsamma slumpmässiga åtkomster i HDD har ersatts av effektiva slumpmässiga åtkomster i SSD, men deras tillgängliga kapacitet är en eller flera storleksordningar dyrare än HDD. Indexering är dock utformad förutsatt HDD som sekundär lagring, vilket minimerar slumpmässiga åtkomster på bekostnad av kapacitet. Indexering av data med SSD som sekundär lagring kräver att kapaciteten behandlas som en knapp resurs. I detta syfte introducerar vi ungefärlig trädindexering, som använder probabilistiska datastrukturer (Bloom filter) för att handla noggrannhet för storlek och producera mindre, men kraftfulla, trädindex, som vi namnger Bloom filter träd (BF-Trees). BF-Trees utnyttjar befintlig databeställning eller partitionering för att erbjuda konkurrenskraftiga sökresultat. Vi visar, både genom en analytisk studie och genom experimentella resultat, att genom att använda arbetsbelastning kunskap och minska indexering noggrannhet i viss utsträckning, kan vi spara avsevärt på kapacitet när indexering på beställda eller partitionerade attribut. I synnerhet, i experiment med en syntetisk arbetsbelastning, ungefärlig indexering erbjuder 2.22x-48x mindre indexavtryck med konkurrenskraftiga svarstider, och i experiment med TPCH och en övervakning real-life dataset från ett energiföretag, erbjuder det 1,6x-4x mindre indexavtryck med konkurrenskraftiga söktider också.
I liknande anda används i REF blomfilter för att handla noggrannhet för prestanda.
BF-Tree: Approximate Tree Indexing
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}