An improved algorithm for dynamic nearest-neighbour models

References

• Albert, R., Jeong, H., and Barabási, A.L., 1999. Diameter of the World-Wide Web. Nature, 401 (6749), 130–131. doi:10.1038/43601
   Web of Science ®Google Scholar
• Aldous, D.J. and Ganesan, K., 2013. True scale-invariant random spatial networks. Proceedings of the National Academy of Sciences of the United States of America, 110 (22), 8782–8785. doi:10.1073/pnas.1304329110
   PubMed Web of Science ®Google Scholar
• Aldous, D.J. and Shun, J., 2010. Connected spatial networks over random points and a route-length statistic. Statistical Science, 25 (3), 275–288. doi:10.1214/10-STS335
   Web of Science ®Google Scholar
• Allen, J.F., 1983. Maintaining knowledge about temporal intervals. Communications of the ACM, 26 (11), 832–843. doi:10.1145/182.358434
   Web of Science ®Google Scholar
• Anselin, L., 1995. Local indicators of spatial association – LISA. Geographical Analysis, 27 (2), 93–115. doi:10.1111/j.1538-4632.1995.tb00338.x
   Web of Science ®Google Scholar
• Backstrom, L., et al., 2012. Four degrees of separation. Proceedings of the 4th Annual ACM Web Science Conference (WebSci), Evanston, IL, 33–42.
   Google Scholar
• Barabási, A.L., et al., 2002. Evolution of the social network of scientific collaborations. Physica A, 311 (3–4), 590–614. doi:10.1016/S0378-4371(02)00736-7
   Web of Science ®Google Scholar
• Barabási, A.L. and Albert, R., 1999. Emergence of scaling in random networks. Science, 286 (5439), 509–512. doi:10.1126/science.286.5439.509
   PubMed Web of Science ®Google Scholar
• Barabási, A.L., Albert, R., and Jeon, H., 2000. Scale-free characteristics of random networks: the topology of the World-Wide Web. Physica A, 281 (1–4), 69–77. doi:10.1016/S0378-4371(00)00018-2
   Web of Science ®Google Scholar
• Barabási, A.L. and Bonabeau, E., 2003. Scale-free networks. Scientific American, 288 (5), 50–59. doi:10.1038/scientificamerican0503-60
   Web of Science ®Google Scholar
• Barnes, T.J., 2004. A paper related to everything but more related to local things. Annals of the Association of American Geographers, 94 (2), 278–283. doi:10.1111/j.1467-8306.2004.09402004.x
   Web of Science ®Google Scholar
• Barthélemy, M., 2011. Spatial networks. Physics Reports, 499 (1–3), 1–101. doi:10.1016/j.physrep.2010.11.002
   Web of Science ®Google Scholar
• Baum, J.A.C., Shipilov, A.V., and Rowley, T.J., 2003. Where do small worlds come from? Industrial and Corporate Change, 12 (4), 697–725. doi:10.1093/icc/12.4.697
   Web of Science ®Google Scholar
• Beckmann, N., et al., 1990. The R*-tree: an efficient and robust access method for points and rectangles. Proceedings of the 16th ACM International Conference on Management of Data (SIGMOD), Atlantic City, NJ, 322–331.
   Google Scholar
• Bentley, J.L., 1975a. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18 (9), 509–517. doi:10.1145/361002.361007
   Web of Science ®Google Scholar
• Bentley, J.L., 1975b. A survey of techniques for fixed radius near neighbor searching. Stanford Linear Accelerator Center, Menlo Park, CA: Stanford University. SLAC-186, STAN-CS-75-513.
   Google Scholar
• Bentley, J.L., Stanat, D.F., and Williams, E.H., Jr., 1977. The complexity of finding fixed-radius near neighbors. Information Processing Letters, 6 (6), 209–212. doi:10.1016/0020-0190(77)90070-9
   Web of Science ®Google Scholar
• Bullmore, E. and Sporns, O., 2009. Complex brain networks: graph theoretical analysis of structural and functional systems. Nature Reviews Neuroscience, 10 (3), 186–198. doi:10.1038/nrn2575
   PubMed Web of Science ®Google Scholar
• Burke, J., et al., 2006. Participatory sensing. Proceedings of the 1st Workshop on World-Sensor-Web: Mobile Device Centric Sensory Networks and Applications (WSW). Boulder, CO.
   Google Scholar
• Cheung, K.L. and Fu, A.W.-c., 1998. Enhanced nearest neighbour search on the R-tree. ACM SIGMOD Record, 27 (3), 16–21. doi:10.1145/290593.290596
   Google Scholar
• DeLyser, D. and Sui, D.Z., 2012. Crossing the qualitative-quantitative divide II: inventive approaches to big data, mobile methods, and rhythmanalysis. Progress in Human Geography, 37 (2), 293–305. doi:10.1177/0309132512444063
   Web of Science ®Google Scholar
• Egenhofer, M.J., 1991. Reasoning about binary topological relations. Proceedings of the 2nd International Symposium on Advances in Spatial Databases (SSD), Zurich, Switzerland, 143–160.
   Google Scholar
• Figueroa, K. and Paredes, R., 2009. Approximate direct and reverse nearest neighbor queries, and the k-nearest neighbor graph. Proceedings of the 2nd International Workshop on Similarity Search and Applications (SISAP), Prague, Czech Republic, 91–98. doi:10.1016/j.antiviral.2009.07.022
   Google Scholar
• Finkel, R.A. and Bentley, J.L., 1974. Quad trees. A data structure for retrieval on composite keys. Acta Informatica, 4 (1), 1–9. doi:10.1007/BF00288933
   Google Scholar
• Fogliaroni, P., 2013. Qualitative spatial configuration queries. Towards next generation access methods for GIS. Amsterdam: IOS.
   Google Scholar
• Friedman, J.H., Bentley, J.L., and Finkel, R.A., 1977. An algorithm for finding best matches in logarith- mic expected time. ACM Transactions on Mathematical Software, 3 (3), 209–226. doi:10.1145/355744.355745
   Google Scholar
• Gao, J., et al., 2015. Selective hashing: closing the gap between radius search and k-NN search. Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, Australia, 349–358.
   Google Scholar
• Gilbert, E.N., 1959. Random graphs. Annals of Mathematical Statistics, 30 (4), 1141–1144. doi:10.1214/aoms/1177706098
   Google Scholar
• Glückler, J., 2007. Economic geography and the evolution of networks. Journal of Economic Geography, 7 (5), 619–634. doi:10.1093/jeg/lbm023
   Web of Science ®Google Scholar
• Goodchild, M.F., 2004. The validity and usefulness of laws in geographic information science and geography. Annals of the Association of American Geographers, 94 (2), 300–303. doi:10.1111/j.1467-8306.2004.09402008.x
   Web of Science ®Google Scholar
• Goodchild, M.F., 2007. Citizens as sensors: the world of volunteered geography. GeoJournal, 69 (4), 211–221. doi:10.1007/s10708-007-9111-y
   Google Scholar
• Guttman, A., 1984. R-trees: a dynamic index structure for spatial searching. Proceedings of the 10th ACM International Conference on Management of Data (SIGMOD), Boston, MA, 47–57.
   Google Scholar
• Haggett, P. and Chorley, R.J., 1969. Network analysis in geography. London: Edward Arnold.
   Google Scholar
• Harvey, F.J., 2013. A new age of discovery: the post-GIS era. Proceedings of the GI_Forum, Salzburg, Austria, 272–281.
   Google Scholar
• Hecht, B. and Moxley, E., 2009. Terabytes of Tobler: evaluating the first law in a massive, domain- neutral representation of world knowledge. Proceedings of the 9th International Conference on spatial information theory (COSIT), Aber Wrac'h, France, 88–105.
   Google Scholar
• Hjaltason, G.R. and Samet, H., 1995. Ranking in spatial databases. Proceedings of the 4th Symposium on Spatial Databases, Portland, ME, 83–95. doi:10.1177/014860719501900183
   Google Scholar
• Holland, P.W. and Leinhardt, S., 1981. An exponential family of probability distributions for directed graphs. Journal of the American Statistical Association, 76 (373), 33–50. doi:10.1080/01621459.1981.10477598
   Web of Science ®Google Scholar
• Holme, P. and Saramäki, J., 2012. Temporal networks. Physics Reports, 519 (3), 97–125. doi:10.1016/j.physrep.2012.03.001
   Web of Science ®Google Scholar
• Hunter, D.R., Goodreau, S.M., and Handcock, M.S., 2008. Goodness of fit of social network models. Journal of the American Statistical Association, 103 (481), 248–258. doi:10.1198/016214507000000446
   Web of Science ®Google Scholar
• Huttenhower, C., et al., 2007. Nearest neighbor networks: clustering expression data based on gene neighborhoods. BMC Bioinformatics, 8 (1), 250. doi:10.1186/1471-2105-8-250
   PubMedGoogle Scholar
• Kalapala, V., et al., 2006. Scale invariance in road networks. Physical Review E, 73 (2), 026130. doi:10.1103/PhysRevE.73.026130
   Web of Science ®Google Scholar
• Kamel, I. and Faloutsos, C., 1994. Hilbert R-tree: an improved R-tree using fractals. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), Santiago de Chile, Chile, 500–509.
   Google Scholar
• Knuth, D.E., 1973. The art of computer programming. Vol. 3. Reading, MA: Addison-Wesley.
   Google Scholar
• Kuratowski, C., 1930. Sur le problème des courbes gauches en topologie. Fundamenta Mathematicae, 15 (1), 271–283. doi:10.4064/fm-15-1-271-283
   Google Scholar
• Kurniawati, R., Jin, J.S., and Shepard, J.A., 1997. SS+ tree: an improved index structure for similarity searches in a high-dimensional feature space. Proceedings of the SPIE Electronic Imaging Conference, San José, CA, 110–120.
   Google Scholar
• Levin, L.A., 1986. Average case complete problems. SIAM Journal on Computing, 15 (1), 285–286. doi:10.1137/0215020
   Web of Science ®Google Scholar
• Levinthal, C., 1966. Molecular model-building by computer. Scientific American, 214 (6), 42–52. doi:10.1038/scientificamerican0666-42
   PubMed Web of Science ®Google Scholar
• Li, M., Westerholt, R., and Zipf, A., 2018. Do people communicate about their whereabouts? Investigating the relation between user-generated text messages and Foursquare check-in places. Geo-spatial Information Science, 21 (3), 159–172. doi:10.1080/10095020.2018.1498669
   Web of Science ®Google Scholar
• Louf, R., Roth, C., and Barthélemy, M., 2014. Scaling in transportation networks. PLoS ONE, 9 (7), e102007. doi:10.1371/journal.pone.0102007
   PubMed Web of Science ®Google Scholar
• MacLane, S., 1937. A combinatorial condition for planar graphs. Fundamenta Mathematicae, 28 (1), 22–31.
   Google Scholar
• Mattson, W. and Rice, B.M., 1999. Near-neighbor calculations using a modified cell-linked list method. Computer Physics Communications, 119 (2–3), 135–148. doi:10.1016/S0010-4655(98)00203-3
   Web of Science ®Google Scholar
• Micó, M.L., Oncina, J., and Carrasco, R.C., 1996. A fast branch & bound nearest neighbour classifier in metric spaces. Pattern Recognition Letters, 17 (7), 731–739. doi:10.1016/0167-8655(96)00032-3
   Web of Science ®Google Scholar
• Micó, M.L., Oncina, J., and Vidal, E., 1994. A new version of the nearest-neighbour approximating and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements. Pattern Recognition Letters, 15 (1), 9–17. doi:10.1016/0167-8655(94)90095-7
   Web of Science ®Google Scholar
• Miller, H.J., 2004. Tobler’s first law and spatial analysis. Annals of the Association of American Geographers, 94 (2), 284–289. doi:10.1111/j.1467-8306.2004.09402005.x
   Web of Science ®Google Scholar
• Mocnik, F.-B., 2015a. Modelling spatial information. Proceedings of the 1st Vienna Young Scientists Symposium (VSS), Vienna, Austria, 46–47.
   Google Scholar
• Mocnik, F.-B., 2015b. A scale-invariant spatial graph model. Thesis (PhD). Vienna University of Technology.
   Google Scholar
• Mocnik, F.-B., 2018a. Dimension as an invariant of street networks. Proceedings of the 7th International Conference on Complex Networks and Their Applications, Cambridge, UK, 455–457.
   Google Scholar
• Mocnik, F.-B., 2018b. The polynomial volume law of complex networks in the context of local and global optimization. Scientific Reports, 8, 11274. doi:10.1038/s41598-018-29131-0
   PubMed Web of Science ®Google Scholar
• Mocnik, F.-B., 2018c. Tradition as a spatiotemporal process – the case of Swedish folk music. Proceedings of the 21st AGILE Conference on Geographic Information Science. Lund, Sweden.
   Google Scholar
• Mocnik, F.-B. and Frank, A.U., 2015. Modelling spatial structures. Proceedings of the 12th Conference on Spatial Information Theory (COSIT), Santa Fe, NM, 44–64. http://doi.org/10.1007/978-3-319-23374-1_3
   Google Scholar
• Nelson, R.C. and Samet, H., 1987. A population analysis for hierarchical data structures. Proceedings of the 13th ACM International Conference on Management of Data (SIGMOD), San Francisco, CA, 270–277.
   Google Scholar
• Newman, M.E.J., 2001. The structure of scientific collaboration networks. Proceedings of the National Academy of Sciences of the United States of America, 98 (2), 404–409. doi:10.1073/pnas.98.2.404
   PubMed Web of Science ®Google Scholar
• Onnela, J.P., et al., 2007. Analysis of a large-scale weighted network of one-to-one human communication. New Journal of Physics, 9 (6), 179. doi:10.1088/1367-2630/9/6/179
   Web of Science ®Google Scholar
• Phillips, J.D., 2004. Doing justice to the law. Annals of the Association of American Geographers, 94 (2), 290–293. doi:10.1111/j.1467-8306.2004.09402006.x
   Web of Science ®Google Scholar
• Roussopoulos, N., Kelley, S., and Vincent, F., 1995. Nearest neigbor queries. Proceedings of the 21st ACM International Conference on Management of Data (SIGMOD), San José, CA, 71–79. doi:10.1016/0306-4522(94)00460-m
   Google Scholar
• Roussopoulos, N. and Leifker, D., 1985. Direct spatial search on pictorial databases using packed R-trees. Proceedings of the 11st ACM International Conference on Management of Data (SIGMOD), Austin, TX, 17–31.
   Google Scholar
• Sala, A., et al., 2010. Measurement-calibrated graph models for social network experiments. Proceedings of the 19th International World Wide Web Conference (WWW), Raleigh, NC, 861–870.
   Google Scholar
• Smith, J.M., 2004. Unlawful relations and verbal inflation. Annals of the Association of American Geographers, 94 (2), 294–299. doi:10.1111/j.1467-8306.2004.09402007.x
   Web of Science ®Google Scholar
• Sporns, O., Tonoi, G., and Kötter, R., 2005. The human connectome: a structural description of the human brain. PLoS Computational Biology, 1 (4), e42. doi:10.1371/journal.pcbi.0010042
   PubMed Web of Science ®Google Scholar
• Sproull, R.F., 1991. Refinements to nearest-neighbor searching in k-dimensional trees. Algorithmica, 6 (1–6), 579–589. doi:10.1007/BF01759061
   Google Scholar
• Staudt, C., Sazonovs, A., and Meyerhenke, H., 2016. NetworKit: a tool suite for large-scale complex network analysis. Network Science, 4 (4), 508–530. doi:10.1017/nws.2016.20
   Web of Science ®Google Scholar
• Stefanidis, A., Crooks, A., and Radzikowski, J., 2013. Harvesting ambient geospatial information from social media feeds. GeoJournal, 78 (2), 319–338. doi:10.1007/s10708-011-9438-2
   Google Scholar
• Sui, D.Z., 2004. Tobler’s first law of geography: a big idea for a small world? Annals of the Association of American Geographers, 94 (2), 269–277. doi:10.1111/j.1467-8306.2004.09402003.x
   Web of Science ®Google Scholar
• Tobler, W.R., 1970. A computer movie simulating urban growth in the Detroit region. Economic Geography, 46, 234–240. doi:10.2307/143141
   Web of Science ®Google Scholar
• Tobler, W.R., 1999. Linear pycnophylactic reallocation comment on a paper by D. Martin. International Journal of Geographical Information Science, 13 (1), 85–90. doi:10.1080/136588199241472
   Web of Science ®Google Scholar
• Tobler, W.R., 2004. On the first law of geography: a reply. Annals of the Association of American Geographers, 94 (2), 304–310. doi:10.1111/j.1467-8306.2004.09402009.x
   Web of Science ®Google Scholar
• Tokoro, K., Yamaguchi, K., and Masuda, S., 2006. Improvements of TLAESA nearest neighbour search algorithm and extension to approximation search. Proceedings of the 29th Australasian Computer Science Conference (ACSC), Hobart, Australia, 77–83.
   Google Scholar
• van den Heuvel, M.P., et al., 2012. High-cost, high-capacity backbone for global brain communication. Proceedings of the National Academy of Sciences of the United States of America, 109 (28), 11372–11377. doi:10.1073/pnas.1203593109
   PubMed Web of Science ®Google Scholar
• Vidal, E., 1994. New formulation and improvements of the nearest-neighbour approximating and elimi- nating search algorithm (AESA). Pattern Recognition Letters, 15 (1), 1–7. doi:10.1016/0167-8655(94)90094-9
   Web of Science ®Google Scholar
• Wagner, K., 1937. Über eine Eigenschaft der ebenen Komplexe. Mathematische Annalen, 114 (1), 570–590. doi:10.1007/BF01594196
   Google Scholar
• Watts, D.J. and Strogatz, S.H., 1998. Collective dynamics of small-world networks. Nature, 393 (6684), 440–442. doi:10.1038/30918
   PubMed Web of Science ®Google Scholar
• Waxman, B.M., 1988. Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 6 (9), 1617–1622. doi:10.1109/49.12889
   Web of Science ®Google Scholar
• Weiss, S.F., 1980. A probabilistic algorithm for nearest neighbour searching. Proceedings of the 3rd Annual ACM Conference on Research and Development in Information Retrieval, Cambridge, UK, 325–333.
   Google Scholar
• Westerholt, R., et al., 2016. Abundant topological outliers in social media data and their effect on spatial analysis. PLOS ONE, 11 (9), e0162360. doi:10.1371/journal.pone.0162360
   PubMed Web of Science ®Google Scholar
• Westlund, H., 2013. A brief history of time, space, and growth: Waldow Tobler’s first law of geography revisited. The Annals of Regional Science, 51 (3), 917–924. doi:10.1007/s00168-013-0571-3
   Web of Science ®Google Scholar
• White, D.A. and Jain, R., 1996. Similarity indexing with the SS-tree. Proceedings of the 12th International Conference on Data Engineering (ICDE), New Orleans, LA, 516–523.
   Google Scholar
• Whitney, H., 1931. Non-separable and planar graphs. Proceedings of the National Academy of Sciences of the United States of America, 17 (2), 125–127. doi:10.1073/pnas.17.2.125
   PubMedGoogle Scholar
• Xia, C., Hsu, W., and Lee, M.L., 2005. ERkNN: efficient reverse k-nearest neighbors retrieval with local kNN-distance estimation. Proceedings of the 14th ACM International Conference on Information and Knowledge Management (CIKM), Bremen, Germany, 533–540.
   Google Scholar
• Yook, S.H., Jeong, H., and Barabási, A.L., 2002. Modeling the internet’s large-scale topology. Proceedings of the National Academy of Sciences of the United States of America, 99 (21), 13382–13386. doi:10.1073/pnas.172501399
   PubMed Web of Science ®Google Scholar
• Zhong, X.F., et al., 2017. An improved k-NN classification with dynamic k. Proceedings of the 9th International Conference on Machine Learning and Computing (ICMLC). Singapore, 211–216.
   Google Scholar