@INPROCEEDINGS{STKarydisMT2011,
  AUTHOR =       {Spyros Sioutas and Kostas Tsichlas and Ioannis Karydis and Yannis Manolopoulos and Yannis Theodoridis},
  TITLE =        {NEFOS: Rapid Cache-Aware Range Query Processing with Probabilistic Guarantees},
  BOOKTITLE =    {Database and Expert Systems Applications},
  YEAR =         {2011},
%  pages =        {},
  abstract =     {We present NEFOS (NEsted FOrest of balanced treeS), a new cache-aware indexing scheme that supports insertions and deletions in O(1) worst-case block transfers for rebalancing operations (given and update position) and searching in O(logB log n) expected block transfers, (B= disk block size and n= number of stored elements). The expected search bound holds with high probability for any (unknown) realistic input distribution. Our expected search bound constitutes an improvement over the O(logB log n) expected bound for search achieved by the ISBtree (Interpolation Search B-tree), since the latter holds with high probability for the class of smooth only input distributions. We define any unknown distribution as realistic if the smoothness doesn’t appear in the whole data set, still it may appear locally in small spatial neighborhoods. This holds for a variety of real-life non-smooth distributions like skew, zipfian, powlaw, beta e.t.c.. The latter is also verified by an accompanying experimental study. Moreover, NEFOS is a B-parametrized concrete structure, which works for both I/O and RAM model, without any kind of transformation or adaptation. Also, it is the first time an expected sublogarithmic bound for search operation was achieved for a broad family of non-smooth input distributions.},
  keywords =     {Data Structures, Data Management Algorithms},
}