Bibliography

[1]D. Knuth, The Art of Computer Programming. Boston, Addison Wesley-Longman, 1998, Vols. 1–3.

[2]A. C.-C. Yao, A study of concrete computational complexity, PhD thesis, University of Illinois, Champaign-Urbana, 1975.

[3]A. C.-C. Yao, Should tables be sorted? J. ACM, vol. 28, no. 3, 1981. pp. 615–628. DOI: 10.1145/322261.322274.

[4]A. C. Yao, Complexity in information theory, in Computational Information Theory, Springer, New York, 1988, pp. 1–15.

[5]C. A. R. Hoare, Notes on data structuring, in Structured Programming, Academic Press, London, 1972, pp. 83–174.

[6]D. E. Knuth, Optimum binary search trees, Acta Inf., vol. 1, no. 1, 1971, pp. 14–25. DOI: 10.1007/BF00264289.

[7]D. D. Sleator and R. E. Tarjan, Self-adjusting binary search trees, J. ACM, vol. 32, no. 3, 1985, pp. 652–686.

[8]D. D. Sleator and R. E. Tarjan, Amortized efficiency of list update and paging rules, Commun. ACM, vol. 28, no. 2, 1985, pp. 202–208. DOI: 10.1145/2786.2793.

[9]M. Thorup, Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operations, J. Algorithms, vol. 42, no. 2, 2002, pp. 205–230.

[10]M. L. Fredman and D. E. Willard, Blasting through the information theoretic barrier with fusion trees, in Proceedings of the Twentysecond Annual ACM Symposium on Theory of Computing, DOI: 10.1145/100216.100217.

[11]E. D. Demaine, D. Harmon, J. Iacono, and Pǎtraşcu, Dynamic optimality - almost, SIAM J. Comput., vol. 37, no. 1, 2007, pp. 240–251.

[12]T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Third Edition, MIT Press, 2009.

[13]R. Sedgewick, Algorithms. Addison-Wesley, 1983.

[14]C. Okasaki, The role of lazy evaluation in amortized data structures, in Proceedings of the 1996 ACM SIGPLAN International Conference on Functional Programming, Philadelphia, 1996, pp. 62–71, DOI: 10.1145/232627.232636.

[15]M. L. Fredman, J. Komlós, and E. Szemerédi, Storing a sparse table with 0(1) worst case access time, J. ACM, vol. 31, no. 3, 1984, pp. 538–544. DOI: 10.1145/828.1884.

[16]R. Pagh and F. F. Rodler, Cuckoo hashing, J. Algorithms, vol. 51, no. 2, 2004, pp. 122–144.

[17]M. Drmota and R. Kutzelnigg, A precise analysis of cuckoo hashing, ACM Trans. Algorithms, vol. 8, no. 2, 2012, 11:1–11:36, DOI:10.1145/2151171.2151174.

[18]R. Kutzelnigg, Bipartite Random Graphs and Cuckoo Hashing, in Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, P. Chassaing et al., Eds., Nancy, France, 2006, pp. 403–406.

[19]M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, in FOCS, IEEE Computer Society, 1984, pp. 338–346.

[20]C. Faloutsos, Indexing and mining streams, in Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, New York, 2004, p. 969.

[21]G. Cormode, M. N. Garofalakis, P. J. Haas, and C. Jermaine, Synopses for massive data: Samples, histograms, wavelets, sketches, Foundations and Trends in Databases, 2012, pp. 1–294.

[22]W. Johnson and J. Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, in Conference on Modern Analysis and Probability, American Mathematical Society, 1984, pp. 189–206.

[23]M. N. Garofalakis, J. Gehrke, and R. Rastogi, Querying and mining data streams: You only get one look a tutorial, in SIGMOD Conference, 2002, p. 635.

[24]J. Abello, P. M. Pardalos, and M. G. C. Resende, Eds., Handbook of Massive Data Sets, Kluwer, Norwalk, 2002.

[25]P. Ciaccia, M. Patella, and P. Zezula, M-tree: An efficient access method for similarity search in metric spaces, in Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB’97), Athens, Morgan Kauffman, 1997, pp. 426–435.

[26]P. Ciaccia, M. Patella, and P. Zezula, A cost model for similarity queries in metric spaces, in Proceedings of the 16th ACM SIGACTSIGMOD-SIGART Symposium on Principles of Database Systems (PODS’97), Seattle, ACM Press, 1998, pp. 59–68.

[27]P. Indyk and R. Motwani, Approximate nearest neighbors: Towards removing the curse of dimensionality, in Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, New York, ACM, 1998, pp. 604–613.

[28]P. Indyk, A sublinear time approximation scheme for clustering in metric spaces, in Symposium on Foundations of Computer Science, 2000, pp. 154–159.

[29]A. Gionis, P. Indyk, and R. Motwani, Similarity search in high dimensions via hashing, in Proceedings of the 25th International Conference on Very Large Data Bases, San Francisco, Morgan Kaufmann, 1999, pp. 518–529.

[30]W. Johnson and J. Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, in Conference on Modern Analysis and Probability, New Haven, American Mathematical Society, 1984, pp. 189–206.

[31]S. Kumar, M. Mohri, and A. Talwalkar, Sampling methods for the nystrom method, J. Mach. Learn. Res., vol. 13, no. 1, 2012, pp. 981–1006.

[32]P. Drineas and M. W. Mahoney, On the nystrom method for approximating a gram matrix for improved kernel-based learning, J. Mach. Learn. Res., vol. 6, 2005, pp. 2153–2175.

[33]D. Achlioptas and F. Mcsherry, Fast computation of low-rank matrix approximations, J. ACM, vol. 54, no. 2, 2007.

[34]J. K. Uhlmann, Satisfying general proximity/similarity queries with metric trees, Info. Proc. Lett., vol. 40, no. 4, 1991, pp. 175–179.

[35]J. K. Uhlmann, Metric trees, Applied Mathematics Letters, vol. 4, no. 5, 1991, pp. 61–62.

[36]E. V. Ruiz, An algorithm for finding nearest neighbours in (approximately) constant average time, Pattern Recogn. Lett., vol. 4, no. 3, 1986, pp. 145–157.

[37]T. Liu, A. W. Moore, E. Gray, and K. Yang, An investigation of practical approximate nearest neighbor algorithms, in NIPS2004, MIT Press, 2004, pp. 825–832.

[38]S. Dasgupta and Y. Freund, Random projection trees and low dimensional manifolds, in Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, New York, ACM, 2008, pp. 537–546.

[39]P. N. Yianilos, Data structures and algorithms for nearest neighbor search in general metric spaces, in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, SIAM, 1993, pp. 311–321.

[40]A. Gionis, P. Indyk, and R. Motwani, Similarity search in high dimensions via hashing, in Proceedings of the 25th International Conference on Very Large Data Bases, San Francisco, Morgan Kaufmann, 1999, pp. 518–529.

[41]P. Indyk and R. Motwani, Approximate nearest neighbors: Towards removing the curse of dimensionality, in Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, New York, ACM, 1998, pp. 604–613.

[42]R. Panigrahy, Entropy based nearest neighbor search in high dimensions, in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, Philadelphia, SIAM, 2006, pp. 1186–1195.

[43]M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, in Proceedings of the Twentieth Annual Symposium on Computational Geometry, New York, ACM, 2004, pp. 253–262.

[44]A. Joly and O. Buisson, A posteriori multi-probe locality sensitive hashing, in Multimedia, A. El-Saddik et al., Eds., ACM, 2008, pp. 209–218.

[45]L. Paulevé, H. Jégou, and L. Amsaleg, Locality sensitive hashing: A comparison of hash function types and querying mechanisms, Pattern Recogn. Lett., vol. 31, no. 11, 2010, pp. 1348–1358.

[46]R. Motwani, A. Naor, and R. Panigrahy, Lower bounds on locality sensitive hashing. SIAM J. Discrete Math., vol. 21, no. 4, 2007, pp. 930–935.

[47]A. Andoni and P. Indyk, Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, Commun. ACM, vol. 51, no. 1, 2008, pp. 117–122.

[48]M. S. Charikar, Similarity estimation techniques from rounding algorithms, in Proceedings of the Thirty-fourth Annual ACM Symposium on Theory of Computing, New York, ACM, 2002, pp. 380–388.

[49]L. Akoglu, R. Khandekar, V. Kumar, S. Parthasarathy, D. Rajan, and K.-L. Wu, Fast nearest neighbor search on large time-evolving graphs, in Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases, Nancy, France, Springer, 2014, pp. 17–33.

[50]J. L. Bentley, Multidimensional binary search trees used for associative searching, Commun. ACM, vol. 18, no. 9, 1975, pp. 509–517.

[51]J. H. Friedman, J. L. Bentley, and R. A. Finkel, An algorithm for finding best matches in logarithmic expected time, ACM Trans. Math. Softw., vol. 3, no. 3, 1977, pp. 209–226.

[52]D. P. Mehta and S. Sahni, Handbook Of Data Structures And Applications, Chapman & Hall, Boca Raton, 2004.

[53]P. Brass, Advanced Data Structures, Cambridge University Press, New York, 2008.

[54]R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge University Press, New York, 1995.

[55]In, G. F. Italiano and R. Raman, Algorithms and theory of computation handbook, in Topics in Data Structures, Chapman & Hall, Boca Raton, 2020, p. 5.

[56]D. Golovin, Uniquely represented data structures with applications to privacy, PhD thesis CMU-CS-08–135, Carnegie Mellon University, Pittsburgh, 2008.

[57]J. L. Carter and M. N. Wegman, Universal classes of hash functions, in Proceedings of the Ninth Annual ACM Symposium on Theory of Computing, Boulder, ACM, 1977, pp. 106–112.

[58]R. Sprugnoli, Perfect hashing functions: A single probe retrieving method for static sets, Commun. ACM, vol. 20, no. 11, 1977, pp. 841–850.

[59]M. Aumüller, M. Dietzfelbinger, and P. Woelfel, Explicit and efficient hash families suffice for cuckoo hashing with a stash, Algorithmica, vol. 70, no. 3, 2014, pp. 428–456.

[60]M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. E. Tarjan, Dynamic perfect hashing: Upper and lower bounds, SIAM J. Comput., vol. 23, no. 4, 1994, pp. 738–761.

[61]D. Belazzougui, F. C. Botelho, and M. Dietzfelbinger, Hash, displace, and compress, Lecture Notes in Computer Series, Springer, 2009, pp. 682–693.

[62]R. Pagh and F. F. Rodler, Cuckoo hashing, J. Algorithms, vol. 51, no. 2, 2004, pp. 122–144.

[63]R. Kutzelnigg, Bipartite Random Graphs and Cuckoo Hashing, in Proceedings of Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, Nancy, France, 2006, pp. 403–406.

[64]B. H. Bloom, Space/time trade-offs in hash coding with allowable errors, Commun. ACM, vol. 13, no. 7, 1970, pp. 422–426.

[65]A. Kirsch and M. Mitzenmacher, Less hashing, same performance: Building a better bloom filter, Random Struct. Algorithms, vol. 33, no. 2, 2008, pp. 187–218.

[66]C. Martiénez and S. Roura, Randomized binary search trees, J. ACM, vol. 45, no. 2, 1998, pp. 288–323. DOI: 10.1145/274787.274812.

[67]B. Reed, The height of a random binary search tree, J. ACM, vol. 50, no. 3, 2003, pp. 306–332. DOI: 10.1145/765568.765571.

[68]L. Devroye, A note on the height of binary search trees, J. ACM, vol. 33, no. 3, 1986, pp. 489–498. DOI: 10.1145/5925.5930.

[69]M. Drmota, An analytic approach to the height of binary search trees II, J. ACM, vol. 50, no. 3, 2003, pp. 333–374, DOI: 10.1145/765568.765572.

[70]D. D. Sleator and R. E. Tarjan, Self-adjusting binary search trees, J. ACM, vol. 32, no. 3, 1985, pp. 652–686. DOI: 10.1145/3828.3835.

[71]A. Elmasry, On the sequential access theorem and deque conjecture for splay trees, Theor. Comput. Sci., vol. 314, no. 3, 2004, pp. 459–466. DOI: 10.1016/j.tcs.2004.01.019.

[72]R. E. Tarjan, Sequential access in splay trees takes linear time, Combinatorica, vol. 5, no. 4, 1985, pp. 367–378. DOI: 10.1007/BF02579253.

[73]A. Blum, S. Chawla, and A. Kalai, Static optimality and dynamic search-optimality in lists and trees, in Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, SIAM, 2002, pp. 1–8.

[74]D. R. Morrison, Patricia and — Practical algorithms to retrieve information coded in alphanumeric, J. ACM, vol. 15, no. 4, 1968, pp. 514–534. DOI: 10.1145/321479.321481.

[75]E. Fredkin, Trie memory, Commun. ACM, vol. 3, no. 9, 1960, pp. 490–499. DOI: 10.1145/367390.367400.

[76]E. Ukkonen, Approximate string matching over suffix trees, in Proceedings of the Fourth Annual Symposium on Combinatorial Pattern Matching, Springer, 1993, pp. 228–242.

[77]G. Salton, E. A. Fox, and H. Wu, Extended Boolean information retrieval, Commun. ACM, vol. 26, no. 11, 1983, pp. 1022–1036. DOI: 10.1145/182.358466.

[78]J. H. Lee, Properties of extended Boolean models in information retrieval, in Proceedings of the 17th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Dublin, Springer, 1994, pp. 182–190.

[79]J. L. Bentley and J. H. Friedman, Data structures for range searching, ACM Comput. Surv., vol. 11, no. 4, 1979, pp. 397–409. DOI: 10.1145/356789.356797.

[80]J. L. Bentley, Multidimensional binary search trees used for associative searching, Commun. ACM, vol. 18, no. 9, 1975, pp. 509–517, DOI: 10.1145/361002.361007.

[81]E. Langetepe and G. Zachmann, Geometric Data Structures for Computer Graphics. A. K. Peters, Natick, 2006.

[82]O. Fries, K. Mehlhorn, and S. Näher, Dynamization of geometric data structures, in Proceedings of the First Annual Symposium on Computational Geometry, Baltimore, ACM, 1985, pp. 168–176. DOI: 10.1145/323233.323256.

[83]G. E. Blelloch, D. Golovin, and V. Vassilevska, Uniquely represented data structures for computational geometry, in Proceedings of the Eleventh Scandinavian Workshop on Algorithm Theory, Gothenburg, Springer, 2008, pp. 17–28.

[84]T. M. Chan, K. Larsen, and M. Pǎtraşcu, Orthogonal range searching on the RAM, revisited, in Proceedings of the Twenty-seventh ACM Symposium on Computational Geometry, arXiv:1011.5200, 2011, pp. 354–363.

[85]E. D. Demaine, D. Harmon, J. Iacono, D. Kane, and M. Pǎtraşcu, The geometry of binary search trees, in Proceedings of the 20th ACM/SIAM Symposium on Discrete Algorithys,Society for Industrial and Applied Mathematics, Philadelphia, 2009, pp. 496–505.

[86]J. R. Driscoll, N. Sarnak, D. D. Sleator, and R. E. Tarjan, Making data structures persistent, J. Comput. Syst. Sci., vol. 38, no. 1, 1989, pp. 86–124. DOI: http://dx.doi.org/10.1016/0022-0000(89)90034-2">10.1016/0022-0000(89)90034-2.

[87]N. I. Sarnak, Persistent data structures, AAI8706779, PhD thesis, New York, 1986.

[88]C. Okasaki. Purely Functional Data Structures, Cambridge University Press, New York, 1999.

[89]J. Iacono and M. Pǎtraşcu, Using hashing to solve the dictionary problem (in external memory), in Proceedings of the Twenty-third ACM/SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, 2012.

[90]M. Dietzfelbinger and F. Meyer auf der Heide, A new universal class of hash functions and dynamic hashing in real time, in Proceedings of the Seventeenth International Colloquium on Automata, Languages and Programming, Warwick, UK, Springer, 1990, pp. 6–19.

[91]G. H. Gonnet, Expected length of the longest probe sequence in hash code searching, J. ACM, vol. 28, no. 2, 1981, pp. 289–304. DOI: 10.1145/322248.322254.

[92]M. Mitzenmacher, The power of two choices in randomized load balancing, IEEE Trans. Parallel Distrib. Syst., vol. 12, no. 10, 2001, pp. 1094–1104. DOI: 10.1109/71.963420.

[93]A. Ostlin and R. Pagh, Uniform hashing in constant time and linear space, in Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, San Diego, San Diego, ACM, 2003, pp. 622–628. DOI: 10.1145/780542.780633.

[94]A. Siegel, On universal classes of extremely random constant-time hash functions, SIAM J. Comput., vol. 33, no. 3, 2004, pp. 505–543. DOI: 10.1137/S0097539701386216.

[95]M. Aumüller, T. Christiani, R. Pagh, and F. Silvestri, Distance-sensitive hashing, in PODS, the Symposium on Principles of Database Systems, ACM, 2018, pp. 89–104.

[96]R. Pagh, N. Pham, F. Silvestri, and M. Stöckel, I/O-efficient similarity join, Algorithmica, vol. 78, no. 4, 2017, pp. 1263–1283.

[97]J. Gudmundsson and R. Pagh, Range-efficient consistent sampling and locality-sensitive hashing for polygons, 2017, arXiv preprint arXiv:1701.05290.

[98]T. D. Ahle, M. Aumüller, and R. Pagh, Parameter-free locality sensitive hashing for spherical range reporting, in SIAM, 2017, pp. 239–256.

[99]M. Goswami, R. Pagh, F. Silvestri, and J. Sivertsen, Distance sensitive bloom filters without false negatives, in SIAM, 2017, pp. 257–269.

[100]R. E. Tarjan and A. C. Yao, Storing a sparse table, Commun. ACM, vol. 22, no. 11, 1979, pp. 606–611.

[101]R. J. Lipton, A. L. Rosenberg, and A. C. Yao, External hashing schemes for collections of data structures, J. ACM, vol. 27, no. 1, 1980, pp. 81–95.

[102]M. Bădoiu and E. D. Demaine, A simplified and dynamic unified structure, in Theoretical Informatics, Springer, Heidelbert, 2004, pp. 466–473.

[103]R. Sundar, On the deque conjecture for the splay algorithm, Combinatorica, vol. 12, no. 1, 1992, pp. 95–124. DOI: 10.1007/BF01191208.

[104]R. Grossi, J. Iacono, G. Navarro, R. Raman, and S. S. Rao, Asymptotically optimal encodings of range data structures for selection and top-k queries, ACM Trans. Algorithms, vol. 13, no. 2, 2017, 28:1–28:31.

[105]P. Bose, K. Douıíeb, J. Iacono, and S. Langerman, The power and limitations of static binary search trees with lazy finger, Algorithmica, vol. 76, no. 4, 2016, pp. 1264–1275.

[106]E. D. Demaine, J. Iacono, and S. Langerman, Worst-case optimal tree layout in external memory, Algorithmica, vol. 72, no. 2, 2015, pp. 369–378.

[107]P. Bose, K. Douıíeb, J. Iacono, and S. Langerman, The power and limitations of static binary search trees with lazy finger, in ISAAC: International Symposium on Algorithms and Computation, Springer, 2014, pp. 181–192.

[108]J. Iacono and Pǎtraşcu, Using hashing to solve the dictionary problem, in SIAM, 2012, pp. 570–582.

[109]S. Collette, J. Iacono, and S. Langerman, Confluent persistence revisited, in SIAM, 2012, pp. 593–601.

[110]G. S. Brodal, E. D. Demaine, J. T. Fineman, J. Iacono, S. Langerman, and J. I. Munro, Cache-oblivious dynamic dictionaries with update/query tradeoffs, in SIAM, 2010, pp. 1448–1456.

[111]K. Mehlhorn, Best possible bounds for the weighted path length of optimum binary search trees, in Automata Theory and Formal Languages, vol. 33, Springer, 1975, pp. 31–41.

[112]K. Mehlhorn, Nearly optimal binary search trees, Acta Inf., vol. 5, 1975, pp. 287–295.

[113]K. Mehlhorn, Dynamic binary search, in International Colloquium on Automata, Languages and Programming (ICALP), vol. 52, Springer, 1977, pp. 323–336.

[114]K. Mehlhorn, Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry. Monographs on Theoretical Computer Science. Springer, 1984, vol. 3.

[115]K. Mehlhorn, Data Structures and Algorithms 2: Graph Algorithms and NP-Completeness. Monographs on Theoretical Computer Science. Springer, 1984, vol. 2.

[116]K. Mehlhorn, Data Structures and Algorithms 1: Sorting and Searching. Monographs on Theoretical Computer Science. Springer, 1984, vol. 1.

[117]M. Dietzfelbinger, A. R. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. E. Tarjan, Dynamic perfect hashing: Upper and lower bounds, in Symposium on Foundations of Computer Science, 1988, pp. 524–531.

[118]K. Mehlhorn and A. K. Tsakalidis, Data structures, in Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), Elsevier, 1990, pp. 301–342.

[119]C. C. Wang, J. Derryberry, and D. D. Sleator, O(log log n)-competitive dynamic binary search trees, in Symposium on Discrete Algorithms (SODA), ACM, 2006, pp. 374–383.

[120]J. R. Driscoll, N. Sarnak, D. D. Sleator, and R. E. Tarjan, Making data structures persistent, J. Comput. Syst. Sci., vol. 38, no. 1, 1989, pp. 86–124.

[121]M. L. Fredman, R. Sedgewick, D. D. Sleator, and R. E. Tarjan, The pairing heap: A new form of self-adjusting heap, Algorithmica, vol. 1, no. 1, 1986, pp. 111–129.

[122]D. D. Sleator and R. E. Tarjan, Self-adjusting heaps, SIAM J. Comput., vol. 15, no. 1, 1986, pp. 52–69.

[123]D. D. Sleator, and R. E. Tarjan, Self-adjusting binary trees, in Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, ACM, 1983, pp. 235–245.

[124]L. Arge, G. S. Brodal, J. Truelsen, and C. Tsirogiannis, An optimal and practical cache-oblivious algorithm for computing multiresolution rasters, in European Symposium on Algorithms (ESA), vol. 8125, Springer, 2013, pp. 61–72.

[125]L. Arge and M. Thorup, Ram-efficient external memory sorting, in ISAAC: International Symposium on Algorithms and Computation, vol. 8283, Springer, 2013, pp. 491–501.

[126]L. Arge and K. G. Larsen, I/O-efficient spatial data structures for range queries, SIGSPATIAL Special, vol. 4, no. 2, 2012, pp. 2–7.

[127]P. K. Agarwal, L. Arge, and K. Yi, I/o-efficient batched union-find and its applications to terrain analysis, ACM Trans. Algorithms, vol. 7, no. 1, 2010, 11:1–11:21.

[128]L. Arge, M. de Berg, and H. J. Haverkort, Cache-oblivious R-trees, Algorithmica, vol. 53, no. 1, 2009, pp. 50–68.

[129]L. Arge, External geometric data structures, in International Conference on Computing and Combinatorics, vol. 3106, Springer, 2004, p. 1.

[130]L. Arge, M. de Berg, H. J. Haverkort, and K. Yi, The priority R-tree: A practically efficient and worst-case optimal R-tree. ACM Transactions on Algorithms (TALG), vol. 4, no. 1, 2008, p. 9.

[131]L. Arge, G. S. Brodal, and R. Fagerberg, Cache-oblivious data structures, in Handbook of Data Structures and Applications, Chapman & Hall, Boca Raton, 2004.

[132]L. Arge, The buffer tree: A technique for designing batched external data structures, Algorithmica, vol. 37, no. 1, 2003, pp. 1–24.

[133]J. S. Vitter, Algorithms and data structures for external memory, Found. Trends Theor. Comput. Sci., vol. 2, no. 4, 2008, pp. 305–474. DOI: 10.1561/0400000014.

[134]H. Zhang, Y. Wen, H. Xie, and N. Yu, Distributed Hash Table: Theory, Platforms and Applications, Springer, Heldelberg, 2013.

[135]C. Leng, J. Wu, J. Cheng, X. Zhang, and H. Lu, Hashing for distributed data, in Proceedings of the Thirty-second International Conference on Machine Learning, Lille, France, 2015, pp. 1642–1650.

[136]N. G. Bronson, J. Casper, H. Chafi, and K. Olukotun, A practical concurrent binary search tree, SIGPLAN Not., vol. 45, no. 5, 2010, pp. 257–268. DOI: 10.1145/1837853.1693488.

[137]B. K. Shrivastava, G. Khataniar, and D. Goswami, Binary search tree: An efficient overlay structure to support range query, in Proceedings of Twenty-seventh International Conference on Distributed Computing Systems Workshops, (ICDCSW’07), IEEE, 2007, p. 77. DOI: 10.1109/ICDCSW.2007.99.

[138]J. Aspnes and G. Shah, Skip graphs, ACM Trans. Algorithms, vol. 3, no. 4, 2007. DOI: 10.1145/1290672.1290674.

[139]A. Disterhoft, A. Funke, and K. Graffi, Packetskip: Skip graph for multidimensional search in structured peer-to-peer systems, in Proceedings of Eleventh IEEE International Conference on Self-Adaptive and Self-Organizing Systems, IEEE, September 2017, pp. 21–30. DOI: 10.1109/SASO.2017.11.

[140]C. C. Aggarwal, Data Streams: Models and Algorithms (Advances in Database Systems), Springer, Heidelberg, 2006.

[141]S. Muthukrishnan, Data streams: Algorithms and applications, Found. Trends Theor. Comput. Sci., vol. 1, no. 2, 2005, pp. 117–236. DOI: 10.1561/0400000002.

[142]W. Hu and B. Zhang, Study of sampling techniques and algorithms in data stream environments, in Proceedings of the Ninth International Conference on Fuzzy Systems and Knowledge Discovery, IEEE, 2012, pp. 1028–1034. DOI: 10.1109/FSKD.2012.6234278.

[143]G. Cormode, Data sketching, Commun. ACM, vol. 60, no. 9, 2017, pp. 48–55. DOI: 10.1145/3080008.

[144]G. Cormode, M. N. Garofalakis, P. J. Haas, and C. Jermaine, Synopses for massive data: Samples, histograms, wavelets, sketches, Foundations and Trends in Databases, vol. 4, no. 1–3, 2012, pp. 1–294. DOI: 10.1561/1900000004.

[145]N. Alon, Y. Matias, and M. Szegedy, The space complexity of approximating the frequency moments, in Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, Philadelphia, ACM, 1996, pp. 20–29. DOI: 10.1145/237814.237823.

[146]B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom, Models and issues in data stream systems, in Proceedings of the Twenty-first Symposium on Principles of Database Systems, Madison, Wisconsin: ACM, 2002, pp. 1–16. DOI: 10.1145/543613.543615.

[147]A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. J. Strauss, Surfing wavelets on streams: One-pass summaries for approximate aggregate queries, in Very Large Database Conference, 2001, pp. 79–88.

[148]P. Chaovalit, A. Gangopadhyay, G. Karabatis, and Z. Chen, Discrete wavelet transform-based time series analysis and mining, ACM Comput. Surv., vol. 43, no. 2, 2011, 6:1–6:37. DOI: 10.1145/1883612.1883613.

[149]S. Guha, N. Koudas, and K. Shim, Data-streams and histograms, in Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, Greece, ACM, 2001, pp. 471–475, DOI: 10.1145/380752.380841.

[150]D. Yang, B. Li, L. Rettig, and P. Cudré-Mauroux, Histosketch: Fast similarity-preserving sketching of streaming histograms with concept drift, in 2017 IEEE International Conference on Data Mining (ICDM), 2017, pp. 545–554. DOI: 10.1109/ICDM.2017.64.

[151]R. B. Rusu, J. Bandouch, F. Meier, I. Essa, and M. Beetz, Human Action Recognition using Global Point Feature Histograms and Action Shapes, Advanced Robotics journal, Robotics Society of Japan (RSJ), 2009.

[152]M. Rabin, Fingerprinting by Random Polynomials, ser. Center for Research in Computing Technology: Center for Research in Computing Technology. Center for Research in Computing Techn., Aiken Computation Laboratory, Univ., 1981.

[153]A. Z. Broder, Some applications of rabin’s fingerprinting method, in Sequences II: Methods in Communications, Security, and Computer Science, Springer-Verlag, 1993, pp. 143–152.

[154]R. Rivest, The md5 message-digest algorithm, United States, 1992.

[155]D. Rachmawati, J. T. Tarigan, and A. B. C. Ginting, A comparative study of message digest 5(md5) and sha256 algorithm, Journal of Physics: Conference Series, vol. 978, no. 1, 2018, p. 012 116.

[156]P. Rogaway and J. Steinberger, Constructing cryptographic hash functions from fixed-key blockciphers, in Advances in Cryptology - CRYPTO 2008, D. Wagner, Ed., Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 433–450.

[157]B. Preneel, Analysis and design of cryptographic hash functions, PhD thesis, 1993.

[158]F. Bauspiess and F. Damm, Requirements for cryptographic hash functions, Comput. Secur., vol. 11, no. 5, 1992, pp. 427–437, DOI: 10.1016/0167-4048(92)90007-E.

[159]S. Nakamoto, Bitcoin: A peer-to-peer electronic cash system, http://bitcoin.org/bitcoin.pdf, 2008.

[160]M. Swan, Blockchain: Blueprint for a New Economy, 1st. O’Reilly Media, Inc., 2015.

[161]D. Tapscott and A. Tapscott, Blockchain Revolution: How the Technology Behind Bitcoin Is Changing Money, Business, and the World. Brilliance Audio, 2016.

[162]A. Narayanan, Blockchains: Past, present, and future, in PODS, ACM, 2018, p. 193.

[163]A. Narayanan and J. Clark, Bitcoin’s academic pedigree, Commun. ACM, vol. 60, no. 12, 2017, pp. 36–45.

[164]R. C. Merkle, A certified digital signature, in Proceedings on Advances in Cryptology, ser. CRYPTO ’89, Santa Barbara, California, USA: Springer-Verlag New York, Inc., 1989, pp. 218–238.

[165]R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, vol. 21, no. 2, 1978, pp. 120–126, DOI: 10.1145/359340.359342.

[166]R. C. Merkle, A digital signature based on a conventional encryption function, in A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, ser. CRYPTO ’87, London, UK, UK: Springer-Verlag, 1988, pp. 369–378.

[167]C. C. Erway, A. Küpçü, C. Papamanthou, and R. Tamassia, Dynamic provable data possession, ACM Trans. Inf. Syst. Secur., vol. 17, no. 4, 2015, 15:1–15:29.

[168]M. Tahir and S. Ahmed, Tree-combined trie: A compressed data structure for fast ip address lookup, International Journal of Advanced Computer Science and Applications, vol. 6, no. 12, 2015. DOI: 10.14569/IJACSA.2015.061223.

[169]B. Pinkerton, Finding what people want: Experiences with the WebCrawler, in Proceedings of the 2nd International World Wide Web, Anonymous, Ed., ser. Online & CDROM review: the international journal of, vol. 18(6), Medford, NJ, USA: Learned Information, 1994.

[170]J. Cho, H. Garcia-Molina, and L. Page, Efficient crawling through URL ordering, Computer Networks, vol. 30, no. 1–7, 1998, pp. 161–172.

[171]H. Garcia-Molina, Challenges in crawling the web, in BNCOD, ser. Lecture Notes in Computer Science, vol. 2712, Springer, 2003, p. 3.

[172]A. Heydon and M. Najork, Mercator: A scalable, extensible web crawler, World Wide Web, vol. 2, no. 4, 1999, pp. 219–229, DOI: 10.1023/A:1019213109274.

[173]S. Melnik, S. Raghavan, B. Yang, and H. Garcia-Molina, Building a distributed full-text index for the web, in WWW, ACM, 2001, pp. 396–406.

[174]C. D. Manning, P. Raghavan, and H. Schütze, Introduction to Information Retrieval. New York, NY, USA: Cambridge University Press, 2008.

[175]C. S. Pabla, Completely fair scheduler, Linux J., vol. 2009, no. 184, 2009.

[176]J. C. Saez, A. Pousa, F. Castro, D. Chaver, and M. Prieto-Matias, Acfs: A completely fair scheduler for asymmetric single-isa multicore systems, in Proceedings of the 30th Annual ACM Symposium on Applied Computing, ser. SAC ’15, Salamanca, Spain: ACM, 2015, pp. 2027–2032, DOI: 10.1145/2695664.2695714.

[177]S. Iyer, R. R. Kompella, and N. McKeowa, Analysis of a memory architecture for fast packet buffers, in 2001 IEEE Workshop on High Performance Switching and Routing (IEEE Cat. No.01TH8552), 2001, pp. 368–373. DOI: 10.1109/HPSR.2001.923663.

[178]R. Motwani and D. Thomas, Caching queues in memory buffers, in Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ser. SODA ’04, New Orleans, Louisiana: Society for Industrial and Applied Mathematics, 2004, pp. 541–549.

[179]W.-c. Feng, K. G. Shin, D. D. Kandlur, and D. Saha, The blue active queue management algorithms, IEEE/ACM Trans. Netw., vol. 10, no. 4, 2002, pp. 513–528, DOI: 10.1109/TNET.2002.801399.

[180]L. Fan, P. Cao, J. Almeida, and A. Z. Broder, Summary cache: A scalable wide-area web cache sharing protocol, IEEE/ACM Trans. Netw., vol. 8, no. 3, 2000, pp. 281–293, DOI: 10.1109/90.851975.

[181]D. Giampaolo, Practical File System Design with the Be File System, 1st. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1998.

[182]A. Guttman, R-trees: A dynamic index structure for spatial searching, SIGMOD Rec., vol. 14, no. 2, 1984, pp. 47–57, DOI: 10.1145/971697.602266.

[183]T. Matsuyama, L. V. Hao, and M. Nagao, A file organization for geographic information systems based on spatial proximity, Computer Vision, Graphics, and Image Processing, vol. 26, no. 3, 1984, pp. 303–318. DOI: 10.1016/0734-189X(84)90215-9.

[184]S. D. Roth, Ray Casting for Modeling Solids, vol. 18, no. 2, 1982, pp. 109–144. DOI: 10.1016/0146664X(82)90169–1.

[185]M. Sugano, Indoor localization system using rssi measurement of wireless sensor network based on zigbee standard, in Wireless and Optical Communications, IASTED/ACTA Press, 2006, pp. 1–6.

[186]G. Cormode and M. Muthukrishnan, Approximating data with the count-min sketch, IEEE Softw., vol. 29, no. 1, 2012, pp. 64–69, DOI: 10.1109/MS.2011.127.

[187]A. C. Gilbert and P. Indyk, Sparse recovery using sparse matrices, Proceedings of the IEEE, vol. 98, no. 6, 2010, pp. 937–947.

[188]A. Z. Broder, On the resemblance and containment of documents, in In Compression and Complexity of Sequences (SEQUENCES’97, IEEE Computer Society, 1997, pp. 21–29.

[189]O. Chum, J. Philbin, and A. Zisserman, Near duplicate image detection: Min-hash and tf-idf weighting. In BMVC, M. Everingham, C. J. Needham, and R. Fraile, Eds., British Machine Vision Association, 2008, pp. 1–10.

[190]L. F. Mackert and G. M. Lohman, R* optimizer validation and performance evaluation for local queries, SIGMOD Rec., vol. 15, no. 2, 1986, pp. 84–95.

[191]L. Zhang and Y. Guan, Detecting click fraud in pay-per-click streams of online advertising networks, in Proceedings of the 2008 The 28th International Conference on Distributed Computing Systems, ser. ICDCS ’08, Washington, DC, USA: IEEE Computer Society, 2008, pp. 77–84.

[192]S. Nilsson and G. Karlsson, Ip-address lookup using lc-tries, IEEE J.Sel. A. Commun., vol. 17, no. 6, 2006, pp. 1083–1092.

[193]W. Pugh, Skip lists: A probabilistic alternative to balanced trees, Commun. ACM, vol. 33, no. 6, 1990, pp. 668–676.

[194]R. Bayer and E. McCreight, Organization and maintenance of large ordered indices, in Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control, ser. SIG-FIDET ’70, Houston, Texas: ACM, 1970, pp. 107–141.

[195]A. Haar, Zur Theorie der orthogonalen Funktionensysteme, Mathematische Annalen, vol. 69, no. 3, 1910, pp. 331–371, DOI:10.1007/BF01456326

[196]Aburrous et al. Predicting phishing websites using classification mining techniques with experimental case studies. In Proceedings of 7th International Conference on Information Technology: New Generations, IEEE, 2010.

[197]C. Liu, C. Yang, X. Zhang, and J. Chen, External integrity verification for outsourced big data in cloud and IoT: A big picture, Future generation computer systems, vol. 49, 2015, pp. 58–67.

[198]Belenky, Andrey, and Nirwan Ansari. IP traceback with deterministic packet marking. IEEE communications letters 7.4, 2003, 162–164.

[199]C. Albuquerque, B. J. Vickers, and T. Suda, Network border patrol, in Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No. 00CH37064), IEEE, vol. 1, 2000, pp. 322–331.

[200]I. Stoica, S. Shenker, and H. Zhang, Core-Stateless Fair Queuing: A Scalable Architecture to Approximate Fair Bandwidth Allocations in High Speed Networks, IEEE/ACM Transaction on Networking, vol. 11, no. 1, 2003, pp. 33–46.

[201]A. Vahdat, and B. David, Epidemic routing for partially connected ad hoc networks, 2000.

[202]N. Borisov, Computational puzzles as sybil defenses. Sixth IEEE International Conference on Peer-to-Peer Computing (P2P’06), IEEE, 2006.

[203]A. Singh, M. Castro, P. Druschel, and A. Rowstron, Defending against eclipse attacks on overlay networks. In Proceedings of the 11th Workshop on ACM SIGOPS European Workshop, ACM, September 2004, p. 21.

[204]L. Ganesh, and Y. Z. Ben, Identity theft protection in structured overlays. 1st IEEE ICNP Workshop on Secure Network Protocols, (NPSec), IEEE, 2005.

[205]M. W. Berry, T. D. Susan, and A. L. Todd, Computational methods for intelligent information access. Supercomputing’95: In Proceedings of the 1995 ACM/IEEE Conference on Supercomputing, IEEE, 1995.

[206]G. H. Golub, and C. F. Van Loan. Matrix Computations, JHU press, Maryland, Vol. 3, 2012.

[207]M. Agate, R. L. Grimsdale, P. F. Lister. The HERO Algorithm for Ray-Tracing Octrees. In: Grimsdale, R.L., Straßer, W. (eds), Advances in Computer Graphics Hardware IV. Eurographic Seminars (Tutorials and Perspectives in Computer Graphics), Springer, Berlin, Heidelberg, 1991.